We propose a model for scheduling jobs in a parallel machine setting that takes into account the cost of migrations by assuming that the processing time of a job may depend on the specific set of machines among which the job is migrated. For the makespan minimization objective, the model generalizes classical scheduling problems such as unrelated parallel machine scheduling, as well as novel ones such as semi-partitioned and clustered scheduling. In the case of a hierarchical family of machines, we derive a compact integer linear programming (ILP) formulation for the job assignment subproblem, and show how to turn arbitrary ILP solutions into valid schedules. We also derive a polynomial-time 2-approximation algorithm for the problem. Extensions that incorporate memory capacity constraints are also discussed.

Bonifaci, V., D'Angelo, G., Marchetti-Spaccamela, A. (2021). Algorithms for hierarchical and semi-partitioned parallel scheduling. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 120, 116-136 [10.1016/j.jcss.2021.03.006].

Algorithms for hierarchical and semi-partitioned parallel scheduling

Bonifaci V.
;
2021-01-01

Abstract

We propose a model for scheduling jobs in a parallel machine setting that takes into account the cost of migrations by assuming that the processing time of a job may depend on the specific set of machines among which the job is migrated. For the makespan minimization objective, the model generalizes classical scheduling problems such as unrelated parallel machine scheduling, as well as novel ones such as semi-partitioned and clustered scheduling. In the case of a hierarchical family of machines, we derive a compact integer linear programming (ILP) formulation for the job assignment subproblem, and show how to turn arbitrary ILP solutions into valid schedules. We also derive a polynomial-time 2-approximation algorithm for the problem. Extensions that incorporate memory capacity constraints are also discussed.
Bonifaci, V., D'Angelo, G., Marchetti-Spaccamela, A. (2021). Algorithms for hierarchical and semi-partitioned parallel scheduling. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 120, 116-136 [10.1016/j.jcss.2021.03.006].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/387575
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact