haku: @author Toth, P. / yhteensä: 13
viite: 4 / 13
| Tekijä: | Fischetti, M. Martello, S. Toth, P. |
| Otsikko: | The fixed job schedule problem with working-time constraints. |
| Lehti: | Operations Research
1989 : MAY-JUN, VOL. 37:3, p. 395-403 |
| Asiasana: | PRODUCTION SCHEDULING |
| Kieli: | eng |
| Tiivistelmä: | The problem is a generalization of the fixed job schedule problem where no limit on the total working time is imposed. It is shown that the problem is polynomially solvable in the preemptive case. Several lower bounds for the problem are derived. One is determined through definition of a special class of graphs, for which the maximum clique problem is shown to be polynomial. These results, lower bounds and dominance criteria, are used to obtain a branch-and-bound algorithm for the optimal solution of the problem. The effectiveness of the algorithm is tested through computational experiments. The results show that the algorithm is, on average, more efficient for the data sets close to real-life situations. |
SCIMA