Modeling and solution for the coil sequencing problem in steel color-coating production

This paper studies the problem of selecting coils and sequencing them to form a production plan by considering production practical requirements, which arises on the color coating line in the steel industry. The problem can be modeled as a generalization of the prize collecting vehicle routing problem which should make both sequencing and selecting decisions. We propose tabu search-based algorithm (TS) to solve the problem. After each move in the searching procedure, the sequencing decision is adjusted to optimal by a dynamic programming algorithm which can solve up to the industrial sized problem quickly. Thus, TS procedure essentially makes the selecting decision. To further improve the TS algorithm, composite neighborhoods involving block moves are proposed. In addition, compound moves are implemented by choosing improvement strategy from variable neighborhoods alternately at each iteration. To evaluate the performance of the TS algorithm, by reformulating the problem as a set covering model with double-side inequality capacity constraints, the lower bound is constructed using a column generation algorithm where the pricing problem is solved by dynamic programming method based on derived dominance rules. From the computation results based on randomly generated instances, the average deviation between the feasible solution and lower bound is 4.2334%, thus the performance of the proposed TS algorithm and column generation is demonstrated. Alternately, another TS algorithm without DP is proposed for the possible larger scale instances.