Approximation of the parallel machine scheduling problem with additional unit resources - LAAS - Laboratoire d'Analyse et d'Architecture des Systèmes Access content directly
Journal Articles Discrete Applied Mathematics Year : 2016

Approximation of the parallel machine scheduling problem with additional unit resources

Abstract

We consider the problem of minimizing the makespan of a schedule on m parallel machines of n jobs, where each job requires exactly one of s additional unit resources. This problem collapses to P ||C max if every job requires a different resource. It is therefore NP-hard even if we fix the number of machines to 2 and strongly NP-hard in general. Although very basic, its approximability is not known, and more general cases, such as scheduling with conflicts, are often not approximable. We give a (2 − 2 /(m+1))-approximation algorithm for this problem, and show that when the deviation in jobs processing times is bounded by a ratio ρ, the same algorithm approximates the problem within a tight factor 1 + ρ (m−1)/n. This problem appears in the design of download plans for Earth observation satellites, when scheduling the transfer of the acquired data to ground stations. Within this context, it may be required to process jobs by batches standing for the set of files related to a single observation. We show that there exists a (2 − 1/m)-approximation algorithm respecting such batch sequences. Moreover, provided that the ratio ρ, between maximum and minimum processing time, is bounded by ⌊s−1/ m−1⌋, we show that the proposed algorithm approximates the optimal schedule within a factor 1 + (s−1)/n.
Fichier principal
Vignette du fichier
paper-Hebrard-et-al-2016.pdf (232 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01354589 , version 1 (18-08-2016)

Identifiers

Cite

Emmanuel Hébrard, Marie-José Huguet, Nicolas Jozefowiez, Adrien Maillard, Cédric Pralet, et al.. Approximation of the parallel machine scheduling problem with additional unit resources. Discrete Applied Mathematics, 2016, 215, pp.126-135. ⟨10.1016/j.dam.2016.07.003⟩. ⟨hal-01354589⟩
161 View
220 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More