基于自适应变邻域搜索算法的一类混合流水车间调度问题  

An Adaptive Variable Neighbourhood Search Algorithm for the Hybrid Flowshop Scheduling Problem

作　　者：李坤[1] 徐铮[2] 田慧欣[3] 

机构地区：[1]天津工业大学管理学院,天津300387 [2]东北师范大学商学院.吉林长春130024 [3]天津工业大学电气工程与自动化学院,天津300387

出　　处：《系统工程》2015年第11期121-129,共9页Systems Engineering

基　　金：国家自然科学基金资助项目(61403277);天津市教委项目(20132151)

摘　　要：混合流水车间调度是一类典型的生产调度问题,属于NP-难问题。传统的研究通常针对中间存储无限的情况,但是在实际生产中,相邻工序之间的存储一般是有限的。针对中间存储能力有限的混合流水车间调度问题,建立了该问题的混合整数规划模型,并提出了一个自适应变邻域搜索算法。在算法中,针对混合流水车间调度问题的特点,提出了基于工件顺序的编码及解码方法。针对传统邻域类型广域搜索能力不足的问题,提出了基于块删除与插入的大规模邻域搜索,并提出了邻域规模的自适应选择机制。基于随机测试问题的实验结果表明,所提出的自适应变邻域搜索算法具有较好的局域与广域搜索能力。As a NP-hard problem, the hybrid flowshop scheduling problem （HFSP） is a classical production scheduling problem. Traditional research generally do not consider the finite capacity of intermediate buffers, which is very common in practical production. In this paper, the HFSP with finite buffers is formulated as a mixed-integer programming nmdel and a adaptive variable neighbourhood search （AVNS） algorithm is proposed. In the AVNS algorithm, a new encoding and decoding method is presented based on the processing sequence of jobs. Due to the poor exploration ability of traditional neighborhood, a new large-scale neibourhood search method is de#igned based on the block operation of jobs, and an adaptive mechanism is developed to select appropriate neighborhood size. Computational results based on random problems illustrate the effectiveness and efficiency of the proposed AVNS algorithm.

关 键 词：混合流水车间调度 有限中间存储 自适应变邻域搜索 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]