A Modelling and a New Hybrid MILP/CP Decomposition Method for Parallel Continuous Galvanizing Line Scheduling Problem

摘要

In this paper we develop a new hybrid Mixed Integer Linear Programming/Constraint Programming (MILP/CP) decomposition method to solve a parallel Continuous Galvanizing Line (CGL) scheduling problem. The objective of the problem is to minimize the total production cost. Unlike common parallel scheduling problems, in this problem sequencing on each CGL is difficult because of the complex production rules of CGLs. Furthermore, all coils are required to be delivered on time, which means an assignment between coils and CGLs may not result into feasible scheduling. The problem is formulated as an integer programming model, but its structure is not suitable for optimization software package to solve. That is the reason why a new hybrid MILP/CP decomposition method is developed. To accelerate the method and reduce the computational time, a heuristic which tries to find the nature of infeasible assignments and obtain more effective cuts is embedded into the framework of the hybrid method. Some properties and a heuristic are employed to tell why the assignment is unfeasible and to derive more effective cuts. 60 instances are randomly generated to simulate actual production data. The new hybrid method is compared with the basic hybrid method without any features proposed in this paper. Numerical results show that the new hybrid method solves all instances in much less computation time than the basic one, especially for large scale instances.