Article ID: | iaor20021180 |
Country: | United Kingdom |
Volume: | 52 |
Issue: | 6 |
Start Page Number: | 708 |
End Page Number: | 717 |
Publication Date: | Jun 2001 |
Journal: | Journal of the Operational Research Society |
Authors: | Gawiejnowicz S., Kononov A. |
Keywords: | production |
In this paper problems of time-dependent scheduling on dedicated machines are considered. The processing time of each job is described by a function which is dependent on the starting time of the job. The objective is to minimise the maximum completion time (makespan). We prove that under linear deterioration the two-machine flow shop problem is strongly NP-hard and the two-machine open shop problem is ordinarily NP-hard. We show that for the three-machine flow shop and simple linear deterioration there does not exist a polynomial-time approximation algorithm with the worst case ratio bounded by a constant, unless