Simple heuristics for the two machine openshop problem with blocking

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

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


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
Issue number5
StatePublished - 1 Jan 2000


  • 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