Single-machine scheduling problems with precedence constraints and simple linear deterioration

摘要

This paper deals with single machine scheduling problems with simple linear deterioration in which the processing time of a job is a simple linear function of its execution starting time. The objective is to determine the optimal schedule to minimize the weighted sum of the θth (θ is a positive integer number) power of waiting times. It is proved that the general problem can be solved in polynomial time. In addition, for the jobs with weak (strong) parallel chains and a series-parallel digraph precedence constraints, it is also proved that these problems can be solved in polynomial time, respectively.