A polynomial time algorithm for makespan minimization on one machine with forbidden start and completion times |
| |
Authors: | Christophe Rapine Nadia Brauner |
| |
Institution: | 1. Université de Lorraine, LGIPM, île du Saulcy, 57045 Metz, France;2. Laboratory G-SCOP, 46 avenue Félix Viallet, 38031 Grenoble Cedex, France |
| |
Abstract: | We consider the problem of scheduling independent jobs on a single resource under a special unavailability constraint: a set of forbidden instants is given, where no job is allowed to start or complete. We show that a schedule without idle time always exists if the number of forbidden instants is less than the number of distinct processing times appearing in the instance. We derive quite a fast algorithm to find such a schedule, based on an hybridization between a list algorithm and local exchange. As a corollary minimizing the makespan for a fixed number of forbidden instants is polynomial. |
| |
Keywords: | Scheduling Makespan criterion Availability constraints |
本文献已被 ScienceDirect 等数据库收录! |
|