NP-hard cases in scheduling deteriorating jobs on dedicated machines

NP-hard cases in scheduling deteriorating jobs on dedicated machines

0.00 Avg rating0 Votes
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: ,
Keywords: production
Abstract:

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 P = NP. We also prove that the three-machine open shop problem with simple linear deterioration is ordinarily NP-hard, even if the jobs have equal deterioration rates on the third machine.

Reviews

Required fields are marked *. Your email address will not be published.