The cold rolling mill scheduling problem: Some solution methods. (October 2019) - Boctor, Fayez F.
Highlights: This paper presents the first MIP formulation for the considered problem. A branch-and-bound algorithm is proposed to solve it. A perturbation-based heuristic approach is developed. Three 100-instance sets with respectively 10, 15 and 25 jobs are used to evaluate the proposed heuristic. The proposed heuristic produced the optimal solution for all 10-job and 15-job instances. Abstract: 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.