Single-machine scheduling problems with past-sequence-dependent delivery times

We consider single-machine scheduling problems with past-sequence-dependent (p-s-d) job delivery times. The p-s-d delivery time is needed to remove any waiting time-induced adverse effects on the job's condition (prior to delivering the job to the customer) and it is therefore proportional to the job's waiting time. We show that single-machine scheduling problems with p-s-d delivery times and with either completion time-related criteria (such as the makespan or the total job completion time) or due date related criteria (such as the maximum lateness or the number of tardy jobs) can be solved by simple polynomial-time algorithms. (C) 2010 Elsevier B.V. All rights reserved.