Abstract: To solve parallel machine lot streaming problem with limited computing time,an improved Variable Neighborhood Decomposition Search(VNDS) algorithm based on order splitting strategies was proposed.By using the real-number coding,VNDS algorithm decomposed the codes into multiple small coding blocks with a fixed scale before each iteration,and there was a fixed size of codes were different between adjacent blocks.The neighborhood search of each coding block was carried out in turn by switch and insert neighborhoods in each iteration.The perturbed neighborhood of VNDS was designed by cyclic transfer theory.To adapt to the characteristic that orders and sub-lots could be split,two splitting strategies were used to improve the VNDS algorithm.The orders and sub-lots were split between two adjacent iterations or after the iteration process ended,so as to optimize tardiness and makespan.Experimental results proved that the improved VNDS algorithm could obtain better solutions in a limited time by comparing with variable neighborhood search algorithm,simulated annealing algorithm and artificial bee colony algorithm.Applying the proposed algorithm to actual production of a cigarette factor could effectively improve the efficiency of production planning.

Key words: unrelated parallel machine, lot streaming, order splitting, variable neighborhood decomposition search algorithm

摘要： 为解决有限运算时间下的并行机批量流问题,提出基于订单拆分策略改进的变邻域分解搜索(VNDS)算法。该算法采用实数编码,在每次迭代前,按照固定规模将编码分解为多个小的编码块,相邻编码块之间相差固定步长的编码;每次迭代中利用交换、插入邻域对各个编码块依次进行邻域搜索。利用循环转移理论设计算法的扰动邻域。为适应订单和子批可拆分的特点,利用两种拆分策略对VNDS算法进行改进,分别在算法两次相邻迭代之间和算法迭代过程终止后对订单或子批进行拆分,优化拖期和完工时间。实验结果表明,相比变邻域搜索算法、模拟退火算法和人工蜂群算法、改进后的VNDS算法在有限的时间内可以得到更好的解。将所提算法应用于卷烟厂的实际生产,可有效提高生产计划的制定效率。

关键词: 不相关并行机, 批量流, 订单拆分, 变邻域分解搜索算法