On A Scheduling Problem of Time Deteriorating Jobs

AbstractWe consider a scheduling problem with a single machine and a set of jobs which have to be processed sequentially. While waiting for processing, jobs may deteriorate, causing the processing requirement of each job to grow after a fixed waiting timet0. We prove that the problem of minimizing the makespan—completion time for all jobs—is NP-hard. Next we consider the problem for a natural special case where the job requirement grows linearly at a job-specific rate aftert0. We develop a fully polynomial time approximation scheme for the problem in this case. We also give further NP-hardness results, and a polynomial time algorithm for the case where the job-specific rate is proportional to the initial processing requirement of each job