1. Minimizing the number of machines for minimum length schedules
- Author
-
Finke, Gerd, Lemaire, Pierre, Proth, Jean-Marie, and Queyranne, Maurice
- Subjects
Machinery ,Magneto-electric machines ,Algorithms ,Algorithm ,Business ,Business, general ,Business, international - Abstract
To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2006.11.050 Byline: Gerd Finke (a), Pierre Lemaire (a), Jean-Marie Proth (b), Maurice Queyranne (a) Keywords: Parallel scheduling; Complexity; Minimum number of processors Abstract: 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. Author Affiliation: (a) Leibniz-IMAG, 46 Avenue Felix Viallet, 38 031 Grenoble cedex, France (b) INRIA-Lorraine, 615 Rue du Jardin Botanique, B.P. 101, F-54602 Villers-les-Nancy cedex, France Article History: Received 1 May 2005; Accepted 1 November 2006
- Published
- 2009