Complexity analysis of job-shop scheduling with deteriorating jobs

This paper addresses job-shop scheduling problems with deteriorating jobs, i.e. jobs whose processing times are an increasing function of their starting time. A simple linear deterioration is assumed and our objective is makespan minimization. We provide a complete analysis of the complexity of flow-shops, open-shops and job-shop problems. We introduce a polynomial-time algorithm for the two-machine flow-shop, and prove NP-hardness when an arbitrary number of machines (three and above) is assumed. Similarly, we introduce a polynomial-time algorithm for the two-machine open-shop, and prove NP-hardness when an arbitrary number of machines (three and above) is assumed. Finally, we prove NP-hardness of the job-shop problem even for two machines, (C) 2002 Elsevier Science B.V. All rights reserved.