Mathematica Eterna
Open Access

Abstract

Single-machine scheduling with past-sequence-dependent delivery times and deteriorating jobs

Guochen Sun

This paper addresses some single-machine scheduling problems with past-sequence-dependent (p-s-d) delivery times and deteriorating jobs. By the past-sequence-dependent (p-s-d) delivery times, we mean that the delivery time of any job is proportional to the job’s waiting time. It is assumed that the deterioration process reflects a increase in the process time as a function of the job’s starting time. This paper shows that the single-machine scheduling problems to minimize the makespan and the total completion time are polynomially solvable under the proposed model. It further shows that the problems to minimize the total weighted completion time, discounted total weighted completion time and total tardiness are polynomially solvable under certain conditions.