Single-machine scheduling with a time-dependent deterioration
Source: The International Journal of Advanced Manufacturing Technology, Volume 43, Numbers 7-8, August 2009 , pp. 805-809(5)
Abstract:The paper deals with the single-machine scheduling problems with a time-dependent deterioration. By time-dependent deterioration, we mean that the processing time of a job is defined by an increasing function of total normal processing time of jobs in front of it in the sequence. We show that, even with the introduction of time-dependent deterioration to job processing times, the single-machine makespan minimization problem remains polynomially solvable. We also show that an optimal schedule of the total completion time minimization problem is V-shaped with respect to normal job processing times.
Document Type: Research Article
Affiliations: 1: School of Science, Shenyang Institute of Aeronautical Engineering, Shenyang, 110136, People’s Republic of China, Email: firstname.lastname@example.org 2: School of Science, Shenyang Institute of Aeronautical Engineering, Shenyang, 110136, People’s Republic of China
Publication date: August 1, 2009