Minimizing the number of machines for minimum length schedules |
| |
| Authors: | Gerd Finke Pierre Lemaire Jean-Marie Proth Maurice Queyranne |
| |
| Institution: | aLeibniz-IMAG, 46 Avenue Félix Viallet, 38 031 Grenoble cedex, France;bINRIA-Lorraine, 615 Rue du Jardin Botanique, B.P. 101, F-54602 Villers-lès-Nancy cedex, France |
| |
| 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. |
| |
| Keywords: | Parallel scheduling Complexity Minimum number of processors |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
