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

Authors: C.T. Ng, Ali Allahverdi, Fawaz S. Al-Anzi, T.C. Edwin Cheng

Addresses: Department of Logistics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong, PR China. ' Department of Industrial and Management Systems Engineering, Kuwait University, P.O. Box 5969, Safat, Kuwait. ' Department of Computer Engineering, Kuwait University, P.O. Box 5969, Safat, Kuwait. ' Department of Logistics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong, PR China

Abstract: 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.

Keywords: flowshop scheduling; maximum lateness; dominance relation; heuristics; setup times; operational research.

DOI: 10.1504/IJOR.2007.012457

International Journal of Operational Research, 2007 Vol.2 No.2, pp.135 - 155

Published online: 14 Feb 2007 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article