The cold rolling mill scheduling problem: Some solution methods

摘要

This paper considers the problem of sequencing and scheduling jobs on a single cold rolling mill. It presents a new mathematical formulation of the problem, a branch- and-bound algorithm, as well as a new perturbation-based heuristic to solve the problem. The proposed branch-and-bound algoritm was tested and allowed to obtain, in a relatively short computational time, optimal solutions for one hundred 15-job instances while a commercial MIP solver failed to solve 65 of them even after several hours of computational time. Also, the proposed perturbation-based heuristic obtained the optimal solution for all instances with 10 and 15 jobs in few seconds of computational time.