A new enhanced-dynasearch & TS for the pickling-rolling scheduling problem

作者：Tang Li Xin^*; Zhao Ren

来源：Acta Automatica Sinica, 2010, 36(2): 304-313.

DOI：10.3724/SP.J.1004.2010.00304

• Algorithm design
• Block structures
• Capacity constraints
• Computational results
• Downstream units
• Dynasearch algorithm
• Feasible solution
• Flow requirements
• Insert neighborhood
• Integer programming models
• Local optima
• Neighborhood structure
• Penalty cost
• Polynomially searchable
• Practical production
• Production requirements
• Rolling scheduling
• Search process
• Steel industry
• Tabu list
• Technical constraints
• Transition costs

Motivated by pickling-rolling production in steel industry, the pickling-rolling scheduling problem is to create a schedule by selecting and sequencing many proper coils from the candidate pool with consideration of the changeovers cost between adjacent coils. Besides the capacity constraints and practical production technical constraints, the flow requirement constraint is also considered so that the total weight of the selected coils belonging to the same downstream unit satisfies the production requirement of the corresponding downstream unit, the objective being to minimize the total transition cost and the penalty cost on the left capacity. The problem is formulated as an integer programming model and a new tabu search (TS) with the enhanced dynasearch algorithm is developed for it. A two-phase heuristic based on nearest insert method is proposed to act as the initial feasible solution to the tabu search. The proposed algorithm designs a double tabu list to fit the different neighborhood structure. For the solution to escape from the local optima, the enhanced dynasearch neighborhood is embedded in each iteration. The dynasearch neighborhood is polynomially searchable by dynamic programming and it can perform a multiple-exchange composite move by combining swap and inner-insert neighborhoods. Based on the analysis of the characteristics of the problem, block structure is defined and several properties of the feasible solution are derived to accelerate the search process. Computational results show that the enhanced-dynsearch & TS algorithm is effective for solving the problem and outperforms the standard one by 3.62 % on average.

• 出版日期2010
• 单位东北大学