Single-machine scheduling with a time-dependent deterioration

Authors: Wang, Ji-Bo¹; Wang, Li-Yan²; Wang, Dan²; Wang, Xiao-Yuan²

Source: The International Journal of Advanced Manufacturing Technology, Volume 43, Numbers 7-8, August 2009 , pp. 805-809(5)

Publisher: Springer

Buy & download fulltext article:

Price: $47.00 plus tax (Refund Policy)

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.

Keywords: Scheduling; Single machine; Time-dependent; Deteriorating jobs

Document Type: Research article

DOI: http://dx.doi.org/10.1007/s00170-008-1760-6

Affiliations: 1: School of Science, Shenyang Institute of Aeronautical Engineering, Shenyang, 110136, People's Republic of China, Email: wangjibo75@yahoo.com.cn 2: School of Science, Shenyang Institute of Aeronautical Engineering, Shenyang, 110136, People's Republic of China

Publication date: 2009-08-01