A Modelling and Tabu Search Heuristic for a Continuous Galvanizing Line Scheduling Problem

In this paper, we address a continuous galvanizing line scheduling problem in a steel plant. The continuous galvanizing line we research produces principally two kinds of coils, inner galvanized coils and outer galvanized coils. Due to the technical constraints, outer coils can not be produced continuously more than a specified number and some inner coils must be inserted between outer coils. The problem is to find a schedule of all coils that minimizes the sum of changeover costs, the number of inserted inner coils and the number of transition coils used. The difficulty of solving the problem lies in the interrelation of sequencing these two kinds of coils. We formulate the scheduling problem as an integer programming model by considering above practical requirements. A heuristic based on tabu search is developed to solve the problem. The matching algorithm is used during the procedure of generating an initial solution where the optimal assignment of candidate inner coils to be inserted and positions is found by Hungarian method and then the saving step is used to reduce the number of inner coils inserted. In implementing the tabu search heuristic, intensification search, diversification search and path relinking are used to improve the effectiveness of the algorithm. 28 instances of four sizes are randomly generated to simulate the actual production data. For all the instances with 20 and 30 coils and four out of five instances with 50 coils, the tabu search heuristic finds the optimal schedules as CPLEX does. For other instances, the heuristic always obtains the better schedules and consumes much less computation time than CPLEX. In real production environment, hundreds of coils are needed to be scheduled, and the heuristic is able to generate high quality schedules within reasonable computation time.