The three-machine flowshop scheduling problem to minimise maximum lateness with separate setup times

Chi To Ng, Ali Allahverdi, Fawaz S. Al-Anzi, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

13 Citations (Scopus)


We address the three-machine flowshop scheduling problem to minimise maximum lateness, where setup times are considered separate from processing times. We establish a dominance relation for the problem where it specifies which of the two adjacent jobs should precede in an optimal solution. Moreover, we propose three heuristics: Earliest Due Date (EDD), an Enhanced Earliest Due Date (EEDD) and a Polynomial Genetic-based Algorithm (PGA). We conduct computational analysis on randomly generated problems to evaluate the performance of the proposed heuristics. The analysis shows that the performance of EEDD is acceptable if the computational time is of the main concern and the number of jobs are large. The analysis also shows that PGA significantly outperforms EDD and EEDD.
Original languageEnglish
Pages (from-to)135-155
Number of pages21
JournalInternational Journal of Operational Research
Issue number2
Publication statusPublished - 12 Apr 2007


  • Dominance relation
  • Flowshop
  • Heuristics
  • Maximum lateness
  • Scheduling

ASJC Scopus subject areas

  • Management Science and Operations Research

Cite this