Split scheduling with uniform setup times

Abstract : 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.
Type de document :
Article dans une revue
Journal of Scheduling, Springer Verlag, 2015, 18 (2), pp.119-129 〈10.1007/s10951-014-0370-4〉
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

Contributeur : Marie-France Sagot <>
Soumis le : mercredi 31 mai 2017 - 10:02:10
Dernière modification le : mercredi 11 avril 2018 - 01:51:59
Document(s) archivé(s) le : mercredi 6 septembre 2017 - 15:01:34


Fichiers produits par l'(les) auteur(s)




Frans Schalekamp, René Sitters, Suzanne Van Der Ster, Leen Stougie, Víctor Verdugo, et al.. Split scheduling with uniform setup times. Journal of Scheduling, Springer Verlag, 2015, 18 (2), pp.119-129 〈10.1007/s10951-014-0370-4〉. 〈hal-01249095〉



Consultations de la notice


Téléchargements de fichiers