Simple heuristics for the two machine openshop problem with blocking

Ming-Jong Yao, Hanijanto Soewandi, Salah E. Elmaghraby

Research output: Contribution to journalArticle

5 Scopus citations

Abstract

We consider a two-machine scheduling problem in an openshop with blocking. We are given the processing times of n jobs on both machines, and the objective is to minimize the makespan. Symbolically, we are dealing with the problem O2|block|Cmax. Four approaches are proposed: (1) A flowshop-based heuristic that is based on the Gilmore-Gomory algorithm for the F2|block|Cmax problem; (2) Two heuristics based on the idea of ‘matching’ to minimize ‘potential’ idle time on either machine, and (3) A random search algorithm that emulates some important characteristics of other ‘soflcomputing’ meta-heuristics. We derive some lower and upper bounds on the optimal objective value that should assist the decision maker in evaluating the result of a particular application. Numerical experiments with the procedures compare their performance under varying conditions and demonstrate the efficacy of the random search algorithm.

Original languageEnglish
Pages (from-to)537-547
Number of pages11
JournalJournal of the Chinese Institute of Industrial Engineers
Volume17
Issue number5
DOIs
StatePublished - 1 Jan 2000

Keywords

  • Heuristics
  • Openshop
  • Scheduling

Fingerprint Dive into the research topics of 'Simple heuristics for the two machine openshop problem with blocking'. Together they form a unique fingerprint.

Cite this