haku: @journal_id 112 / yhteensä: 1577
viite: 263 / 1577
| Tekijä: | Fischetti, M. Martello, S. Toth, P. |
| Otsikko: | Approximation algorithms for fixed job schedule problems |
| Lehti: | Operations Research
1992 : JAN-FEB, VOL.40:SUP.1, p.S96-S108 |
| Asiasana: | JOB-SHOP SCHEDULING ALGORITHMS ROAD TRANSPORT JOB PERFORMANCE |
| Kieli: | eng |
| Tiivistelmä: | Two generalizations of the fixed job schedule problem, obtained by imposing a bound on the spread-time or on the working time of each processor are investigated. These NP-hard problems can arise in bus driver scheduling. The bus driver problem can be described as follows. Given the daily bus schedule of a transit company, find the minimum number of drivers needed to perform all increments of work by satisfying the constraints laid down by the union contract and company regulations. Several polynomial-time approximation algorithms are introduced, efficient implementations for them are given, and their complexity and worst case performance are analyzed. |
SCIMA