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.

► This paper studies one single-machine scheduling problem with past-sequence-dependent delivery times and release times. ► The objective of the problem is to minimize the total completion time. ► For the preemptive model, we present an optimal algorithm which is a modified Shortest Remaining Processing Time rule. ► For the non-preemptive model, we show that it is NP-hard and propose an approximation algorithm.