Scheduling for fabrication and assembly in a two-machine flowshop with a fixed job sequence

F. J. Hwang, M. Y. Kovalyov, Miao-Tsong Lin

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


This paper studies a problem of scheduling fabrication and assembly operations in a two-machine flowshop, subject to the same predetermined job sequence on each machine. In the manufacturing setting, there are n products, each of which consists of two components: a common component and a unique component which are fabricated on machine 1 and then assembled on machine 2. Common components of all products are processed in batches preceded by a constant setup time. The manufacturing process related to each single product is called a job. We address four regular performance measures: the total job completion time, the maximum job lateness, the total job tardiness, and the number of tardy jobs. Several optimality properties are presented. Based upon the concept of critical path and block schedule, a generic dynamic programming algorithm is developed to find an optimal schedule in O(n7) time.

Original languageEnglish
Pages (from-to)263-279
Number of pages17
JournalAnnals of Operations Research
Issue number1
StatePublished - Jun 2014


  • Batch scheduling
  • Dynamic programming
  • Fixed sequence
  • Two-machine flowshop

Fingerprint Dive into the research topics of 'Scheduling for fabrication and assembly in a two-machine flowshop with a fixed job sequence'. Together they form a unique fingerprint.

Cite this