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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [7 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-01354589
Contributor : Marie-Jose Huguet <>
Submitted on : Thursday, August 18, 2016 - 9:59:55 PM
Last modification on : Friday, January 10, 2020 - 9:10:16 PM
Long-term archiving on: Saturday, November 19, 2016 - 7:09:45 PM

File

paper-Hebrard-et-al-2016.pdf
Files produced by the author(s)

Identifiers

Citation

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, Elsevier, 2016, 215, pp.126-135. ⟨10.1016/j.dam.2016.07.003⟩. ⟨hal-01354589⟩

Share

Metrics

Record views

399

Files downloads

383