Article ID: | iaor2002694 |
Country: | United Kingdom |
Volume: | 28 |
Issue: | 11 |
Start Page Number: | 1111 |
End Page Number: | 1130 |
Publication Date: | Sep 2001 |
Journal: | Computers and Operations Research |
Authors: | Pan Jason Chao-Hsien, Chen Jen-Shiang, Cheng Hung-Liang |
Keywords: | heuristics |
The single-machine sequence-independent class setup scheduling problem is examined in this paper. It is assumed that jobs are classified into classes and a setup is required between jobs of different classes, but not of the same class. Furthermore, this setup time is fixed and depends only on the current job. Since the problem is NP-hard, a heuristic algorithm is proposed to find an approximate schedule that minimizes the maximum lateness on a set of jobs. The algorithm can easily be modified to solve the maximum tardiness problems as well. The accuracy of the heuristic algorithm in generating near optimal solutions is empirically evaluated.