A genetic algorithm for scheduling dual flow shops

Chie Wun Chiou*, Wen Min Chen, Chin Min Liu, Muh-Cherng Wu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


This study examines a dual-flow shop-scheduling problem that allows cross-shop processing. The scheduling objective is to minimize the coefficient of variation of slack time (lateness), where the slack time (ST) of a job denotes the difference between its due date and total completion time. This scheduling problem involves two decisions: job route assignment (assigning jobs to shops) and job sequencing. This study develops a genetic algorithm (GA) embedded with the earliest due date (EDD) dispatching rule for making these decisions. Numerical experiments with the GA algorithm indicate that the performance of adopting a cross-shop production policy may significantly outperform that of adopting a single-shop production policy. This is particularly true when the two flow shops are asymmetrically designed. This study develops a grouping heuristic algorithm to reduce setup time and due-date-based demand simultaneously. This study uses the proposed genetic algorithm (GA) to prove that the grouping heuristic algorithm performs well. Obtaining an approximate optimal solution makes it possible to decide the route assignment of jobs and the job sequencing of machines.

Original languageEnglish
Pages (from-to)1306-1314
Number of pages9
JournalExpert Systems with Applications
Issue number1
StatePublished - 1 Jan 2012


  • Dual flow shop
  • Due date
  • Genetic algorithm (GA)
  • Scheduling
  • Setup time

Fingerprint Dive into the research topics of 'A genetic algorithm for scheduling dual flow shops'. Together they form a unique fingerprint.

Cite this