关键词: 下料问题, 母板设计, 板坯设计, 禁忌搜索, 列生成

Abstract: Aiming at the organization mode of designing mother plates and slabs before the production implementation in the demand-oriented production of medium and heavy plate,the integrated optimal design problem of mother plate and slab was investigated,in which flexibility in cross section and length of mother plate and slab and transformation relationship between mother plate and slab were taken into consideration together.It was modelled and solved as a cutting stock problem by considering making decisions on cross section and length of mother plate and slab simultaneously.The flexibility was transformed into constraints and a non linear mixed integer programming model with an objective minimizing the total quantity of surplus material and material loss in manufacturing process was built.A hybrid optimal algorithm combined tabu search and column generation was employed: tabu search was mainly used to deal with optimal choice of slab cross section.A one-to-many encoding scheme was adopted to reduce the dimensions of search space;a code string was decoded to make decisions on the length of mother plates and slabs and cutting patterns.A sub-problem was a mother plate design problem considering length flexibility and material processing loss and could be solved with a modified algorithm based on column generation.Applicable essential factors of tabu search such as neighborhood structure and tabu object were designed according to problem characteristics.The case experiments with the data instance from a steel plant showed that the modeling and solving method was feasible and effective.

Key words: cutting stock problem, mother plate design, slab design, tabu search, column generation