Skip to Main content Skip to Navigation
New interface
Journal articles

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 metadata

Cited literature [7 references]  Display  Hide  Download
Contributor : Marie-Jose Huguet Connect in order to contact the contributor
Submitted on : Thursday, August 18, 2016 - 9:59:55 PM
Last modification on : Tuesday, October 25, 2022 - 11:58:11 AM
Long-term archiving on: : Saturday, November 19, 2016 - 7:09:45 PM


Files produced by the author(s)



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⟩



Record views


Files downloads