haku: @author Toth, P. / yhteensä: 13
viite: 7 / 13
| Tekijä: | Fischetti, M. Martello, S. Toth, P. |
| Otsikko: | The fixed job schedule problem with spread-time constraints. |
| Lehti: | Operations Research
1987 : NOV-DEC, VOL. 35:6, p. 849-858 |
| Asiasana: | SCHEDULING BRANCH AND BOUND METHODS |
| Kieli: | eng |
| Tiivistelmä: | A generalization of the fixed job schedule problem is considered in which each processor is available only for prefixed time units from the release time of the earliest task assigned to it. The problem has practical as well as theoretical interest, since it arises as subproblem in heuristic algorithms used in solving the overall bus driver scheduling problem. An algorithm is given for the problem's preemptive version and special cases are described that can be solved in polynomial time. Dominance criteria are introduced and a reduction procedure and a branch-and-bound algorithm are given, and the algorithm's average performance is analyzed. |
SCIMA