Article ID: | iaor20072856 |
Country: | United Kingdom |
Volume: | 2 |
Issue: | 2 |
Start Page Number: | 135 |
End Page Number: | 155 |
Publication Date: | Feb 2007 |
Journal: | International Journal of Operational Research |
Authors: | Allahverdi Ali, Cheng T.C. Edwin, Ng C.T., Al-Anzi Fawaz S. |
Keywords: | heuristics: genetic algorithms |
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 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 is large. The analysis also shows that PGA significantly outperforms EDD and EEDD.