A variable arc exchange heuristic for float glass manufacturing problems

摘要

Float glass manufacturing problems concern a finding of cost minimizing production sequence such that total scraps are minimized. We show that these problems could be transformed into Asymmetric Traveling Salesman Problems with Time Window (ATSPTW), where a customer is defined as a production order and an arc connecting two orders indicates changeover scraps and setup time. A variable arc exchange heuristic, comprising of 2-opt and 3-opt, is proposed for solving those large problem instances. The results from the proposed heuristic, when compared with those of the optimization model, indicate that both could successfully find the optimal solution to the problems of smaller size. When the problems get bigger, the solution quality of our proposed heuristic deteriorates; but, with tractable computational time compared with that of the optimization model, whose solution could not be found due to a run-out-of-memory error.