haku: @indexterm COMBINATORIAL OPTIMIZATION / yhteensä: 13
viite: 6 / 13
Tekijä: | Mokotoff, E. Chretienne, P. |
Otsikko: | A cutting plane algorithm for the unrelated parallel machine scheduling problem |
Lehti: | European Journal of Operational Research
2002 : SEP, VOL. 141:3, p. 515-525 |
Asiasana: | OPTIMIZATION COMBINATORIAL OPTIMIZATION SCHEDULING ANALYTICAL REVIEW |
Kieli: | eng |
Tiivistelmä: | This paper deals with the polyhedral structure of the scheduling problem R / / Cmax. Strong valid inequalities are identified for fixed values of the maximum completion time and are used to build a cutting plane scheme from which an exact algorithm and an approximation algorithm are developed. The main algorithm includes a preprocessing phase to compute an upper bound with the list scheduling algorithm of Davis and Jaffe and a lower bound from the preemptive version of the problem. Computational results show that the proposed exact algorithm gives an optimal solution for almost all tested cases, within the fixed time and memory limits. |
SCIMA