Article ID: | iaor20072858 |
Country: | United Kingdom |
Volume: | 13 |
Issue: | 2 |
Start Page Number: | 91 |
End Page Number: | 98 |
Publication Date: | Mar 2006 |
Journal: | International Transactions in Operational Research |
Authors: | Lin B.M.T., Cheng T.C. Edwin |
Keywords: | flowshop, deteriorating items |
This paper considers a flowshop-scheduling problem with a waiting time constraint imposed to restrict the processing of the two operations of each job. If the second operation of a job cannot start within a specified waiting time after the completion of its first operation, then an extra processing time will be incurred for its second operation as a penalty. We first show that even a greatly restricted version of the problem is strongly NP-hard. We then develop an O(n2) algorithm to determine the makespan of a processing sequence of the jobs.