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 N P-hard. We then develop an O(n2) algorithm to determine the makespan of a processing sequence of the jobs.
|Number of pages||8|
|Journal||International Transactions in Operational Research|
|State||Published - 1 Jan 2006|
- Flowshop scheduling
- N P-hardness
- Waiting time