Minimizing the number of machines for minimum length schedules

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.

MoreLess

Year of publication:	2009
Authors:	Finke, Gerd ; Lemaire, Pierre ; Proth, Jean-Marie ; Queyranne, Maurice
Published in:	European Journal of Operational Research. - Elsevier, ISSN 0377-2217. - Vol. 199.2009, 3, p. 702-705
Publisher:	Elsevier
Keywords:	Parallel scheduling Complexity Minimum number of processors

More details

Type of publication:	Article
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10004973534