Optimal Algorithms and a PTAS for Cost-Aware Scheduling

Abstract : We consider a natural generalization of classical scheduling problems in which using a time unit for processing a job causes some time-dependent cost which must be paid in addition to the standard scheduling cost. We study the scheduling objectives of minimizing the makespan and the sum of (weighted) completion times. It is not difficult to derive a polynomial-time algorithm for preemptive scheduling to minimize the makespan on unrelated machines. The problem of minimizing the total (weighted) completion time is considerably harder, even on a single machine. We present a polynomial-time algorithm that computes for any given sequence of jobs an optimal schedule, i.e., the optimal set of time-slots to be used for scheduling jobs according to the given sequence. This result is based on dynamic programming using a subtle analysis of the structure of optimal solutions and a potential function argument. With this algorithm, we solve the unweighted problem optimally in polynomial time. Furthermore, we argue that there is a (4+ε)-approximation algorithm for the strongly NP-hard problem with individual job weights. For this weighted version, we also give a PTAS based on a dual scheduling approach introduced for scheduling on a machine of varying speed.
Type de document :
Communication dans un congrès
Giuseppe F. Italiano; Giovanni Pighizzini; Donald T. Sannella. Mathematical Foundations of Computer Science (MFCS), Aug 2015, Milan, Italy. Springer, Lecture Notes in Computer Science, 9235, pp.211-222, 2015, 〈10.1007/978-3-662-48054-0_18〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01249098
Contributeur : Marie-France Sagot <>
Soumis le : vendredi 16 juin 2017 - 14:43:19
Dernière modification le : mercredi 11 avril 2018 - 01:54:41
Document(s) archivé(s) le : mercredi 13 décembre 2017 - 16:42:36

Fichier

ChenMRSV-MFCS15.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Lin Chen, Nicole Megow, Roman Rischke, Leen Stougie, José Verschae. Optimal Algorithms and a PTAS for Cost-Aware Scheduling. Giuseppe F. Italiano; Giovanni Pighizzini; Donald T. Sannella. Mathematical Foundations of Computer Science (MFCS), Aug 2015, Milan, Italy. Springer, Lecture Notes in Computer Science, 9235, pp.211-222, 2015, 〈10.1007/978-3-662-48054-0_18〉. 〈hal-01249098〉

Partager

Métriques

Consultations de la notice

146

Téléchargements de fichiers

36