论文部分内容阅读
混合流水车间调度是一类典型的生产调度问题,属于NP-难问题。传统的研究通常针对中间存储无限的情况,但是在实际生产中,相邻工序之间的存储一般是有限的。针对中间存储能力有限的混合流水车间调度问题,建立了该问题的混合整数规划模型,并提出了一个自适应变邻域搜索算法。在算法中,针对混合流水车间调度问题的特点,提出了基于工件顺序的编码及解码方法。针对传统邻域类型广域搜索能力不足的问题,提出了基于块删除与插入的大规模邻域搜索,并提出了邻域规模的自适应选择机制。基于随机测试问题的实验结果表明,所提出的自适应变邻域搜索算法具有较好的局域与广域搜索能力。
Hybrid flow shop scheduling is a typical class of production scheduling problem, which belongs to the NP-hard problem. Traditional research usually focuses on the infinite storage in the middle, but in actual production, the storage between adjacent processes is usually limited. Aiming at the problem of mixed flow shop scheduling with limited storage capacity, a mixed integer programming model of the problem is established and an adaptive variable neighborhood search algorithm is proposed. In the algorithm, according to the characteristics of the hybrid flow shop scheduling problem, a coding and decoding method based on the workpiece order is proposed. Aiming at the problem of insufficient searching power of traditional neighborhood type, a large-scale neighborhood search based on block deletion and insertion is proposed and an adaptive selection mechanism of neighborhood size is proposed. Experimental results based on stochastic test problems show that the proposed adaptive variable neighborhood search algorithm has better local and wide area search capabilities.