An efficient optimal solution to the coil sequencing problem in electro-galvanizing line

This paper studies a coil sequencing problem that arises from electro-galvanizing line in steel industry. The problem is to find a processing sequence of steel coils such that the switching costs between consecutive coils are minimized while satisfying technical restrictions. The problem can be decomposed into several independent sub-problems, each corresponding to a turn which is a sequence of continuously processed coils with the same post-processing requirement. The coils in each turn can be further divided into several families each consisting of the coils with the same width. Based on analysis of the problem properties, a two-phase polynomial algorithm is developed to obtain an optimal turn. The sequence of coils in a family with given boundary coils (first and last coils) is determined in the first phase using a polynomial dynamic programming algorithm. In the second phase, the optimal turn is formed by another polynomial dynamic programming algorithm which takes the boundary coils for each family as state variables. The efficiency of the proposed algorithm is demonstrated through computational experiments. (C) 2010 Elsevier Ltd. All rights reserved.