Minimizing the number of machines for minimum length schedules

Gerd Finke (1) , Pierre Lemaire (2) , Jean-Marie Proth (3) , Maurice Queyranne (1)

1 G-SCOP_ROSP - Recherche Opérationnelle pour les Systèmes de Production
2 Leibniz - IMAG - Laboratoire Leibniz
3 SAGEP - Simulation, analyse et gestion des systèmes de production

In this paper, we present a new objective function for scheduling on parallel machines: minimizing the number of machines for schedules of minimum length. We study its complexity and we prove the NP-completeness of this problem, even if there is no precedences or for unitary execution times. We propose several polynomial algorithms for various particular cases.

Keywords: Parallel scheduling; Complexity; Minimum number of processors

Domains: Operations Research [math.OC]

Gerd Finke, Pierre Lemaire, Jean-Marie Proth, Maurice Queyranne. Minimizing the number of machines for minimum length schedules. European Journal of Operational Research, 2009, 199 (3), pp.702-705. ⟨10.1016/j.ejor.2006.11.050⟩. ⟨hal-00361039⟩