Single-machine scheduling with past-sequence-dependent delivery times and release times

This paper studies the problem of single-machine scheduling with past-sequence-dependent delivery times, which was introduced in Koulamas and Kyparisis (2010) [5]. We focus on the scenario with release times such that any job is available for processing on or after its specific release time. Both preemptive and non-preemptive models are considered, aiming at minimizing the total completion time. An optimal algorithm is presented for the preemptive model where any job may be preempted during processing on the machine and then resumed from where it was interrupted later on. For the non-preemptive model, we show that it is NP-hard and mainly develop an approximation algorithm.