TY - JOUR
T1 - Split Scheduling with Uniform Setup Times
AU - Schalekamp, F.
AU - Sitters, R.A.
AU - van der Ster, S.L.
AU - Stougie, L.
AU - Verdugo, V.
AU - van Zuylen, A.
N1 - April 2015, Volume 18, Issue 2, pp 119-129
PY - 2015
Y1 - 2015
N2 - We study a scheduling problem in which jobs may be split into parts, where the parts of a split job may be processed simultaneously on more than one machine. Each part of a job requires a setup time, however, on the machine where the job part is processed. During setup, a machine cannot process or set up any other job. We concentrate on the basic case in which setup times are job-, machine- and sequence-independent. Problems of this kind were encountered when modelling practical problems in planning disaster relief operations. Our main algorithmic result is a polynomial-time algorithm for minimising total completion time on two parallel identical machines. We argue, why the same problem with three machines is not an easy extension of the two-machine case, leaving the complexity of this case as a tantalising open problem. We give a constant-factor approximation algorithm for the general case with any number of machines and a polynomial-time approximation scheme for a fixed number of machines. For the version with the objective to minimise total weighted completion time, we prove NP-hardness. Finally, we conclude with an overview of the state of the art for other split scheduling problems with job-, machine- and sequence-independent setup times.
AB - We study a scheduling problem in which jobs may be split into parts, where the parts of a split job may be processed simultaneously on more than one machine. Each part of a job requires a setup time, however, on the machine where the job part is processed. During setup, a machine cannot process or set up any other job. We concentrate on the basic case in which setup times are job-, machine- and sequence-independent. Problems of this kind were encountered when modelling practical problems in planning disaster relief operations. Our main algorithmic result is a polynomial-time algorithm for minimising total completion time on two parallel identical machines. We argue, why the same problem with three machines is not an easy extension of the two-machine case, leaving the complexity of this case as a tantalising open problem. We give a constant-factor approximation algorithm for the general case with any number of machines and a polynomial-time approximation scheme for a fixed number of machines. For the version with the objective to minimise total weighted completion time, we prove NP-hardness. Finally, we conclude with an overview of the state of the art for other split scheduling problems with job-, machine- and sequence-independent setup times.
U2 - 10.1007/s10951-014-0370-4
DO - 10.1007/s10951-014-0370-4
M3 - Article
SN - 1094-6136
VL - 18
SP - 119
EP - 129
JO - Journal of Scheduling
JF - Journal of Scheduling
IS - 2
ER -