Scheduling two-stage hybrid flow shops with parallel batch, release time, and machine eligibility constraints

I. Lin Wang, Taho Yang, Yu Bang Chang

Research output: Contribution to journalArticlepeer-review

23 Citations (Scopus)


This paper investigates a difficult scheduling problem on a specialized two-stage hybrid flow shop with multiple processors that appears in semiconductor manufacturing industry, where the first and second stages process serial jobs and parallel batches, respectively. The objective is to seek job-machine, job-batch, and batch-machine assignments such that makespan is minimized, while considering parallel batch, release time, and machine eligibility constraints. We first propose amixed integer programming (MIP) formulation for this problem, then gives a heuristic approach for solving larger problems. In order to handle real world large-scale scheduling problems, we propose an efficient dispatching rule called BFIFO that assigns jobs or batches to machines based on first-in-first-out principle, and then give several reoptimization techniques usingMIP and local search heuristics involving interchange, translocation and transposition among assigned jobs. Computational experiments indicate our proposed re-optimization techniques are efficient. In particular, our approaches can produce good solutions for scheduling up to 160 jobs on 40 machines at both stages within 10 min.

Original languageEnglish
Pages (from-to)2271-2280
Number of pages10
JournalJournal of Intelligent Manufacturing
Issue number6
Publication statusPublished - 2012 Dec

All Science Journal Classification (ASJC) codes

  • Software
  • Industrial and Manufacturing Engineering
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Scheduling two-stage hybrid flow shops with parallel batch, release time, and machine eligibility constraints'. Together they form a unique fingerprint.

Cite this