Minimizing L_max for large-scale, job-shop scheduling problems

Abstract

The academic literature in 2000 presented a procedure for solving the job-shop-scheduling problem of minimizing L _max. The iterative-adaptive simulation-based procedure is shown here to perform well on large-scale problems. However, there is potential for improvement in closing the gap between best-known solutions and the lower bound. In the present paper, a simulated annealing post-processing procedure is presented and evaluated on large-scale problems. A new neighbourhood structure for local searches in the job-shop scheduling problem is developed. The procedure is also evaluated using benchmark problems and new upper bounds are established.

Acknowledgements

Research was supported, in part, by the Furniture Manufacturing and Management Center, North Carolina State University, and by the Office of Naval Research, Contract No. N00014-90-J-1009.

Notes

*To whom correspondence should be addressed. E-mail: [email protected]@eos.ncsu.edu

Additional information

Notes on contributors

K. A. Thoney

*To whom correspondence should be addressed. E-mail: [email protected]@eos.ncsu.edu