肖鹏飞，张超勇+，孟磊磊,2，洪 辉，戴 稳

(1.华中科技大学数字制造装备与技术国家重点实验室，湖北 武汉 430074；2 聊城大学 计算机学院，山东 聊城 252059)

0 引言

流水车间是一类制造行业常见的生产布局配置形式[1-2]。流水车间调度问题可以描述为：工件集N={J1,J2,…,Jn}由机器集M={M1,M2,…,Mm}进行加工，每个工件经由相同的工艺路线，即经由机器M1，M2，…直到最后一台机器Mm加工。调度决策就是安排工件通过每台机器的加工顺序。若规定所有m台机器上n个工件的加工顺序均相同，则称其为置换流水车间调度(Permutation Flow-shop Scheduling，PFS)问题；若允许不同机器上工件的加工顺序可以改变，这类松弛置换约束条件的调度问题称为非置换流水车间调度(Non-Permutation Flow-shop Scheduling，NPFS)问题。NPFS问题需要满足以下约束条件：①每台机器每个时刻只能加工一道工序且不允许中断；②每个工件Jj都有对应于机器i(i=1,2,…,m)上的工序加工时间pij，准备时间包含在加工时间内或可以忽略不计；③每台机器前的等待队列容量足够大，以满足重新排列工件加工顺序的需要。相较于PFS问题n!的解规模，NPFS问题有最多高达(n!)max{m-2,1}种不同候选解，研究表明当机器数m≥3时，NPFS为非确定性多项式(NP)难题。调度方案的生产周期(makespan)是所有工件最后一道工序完工时间的最大值。最小化Makespan的NPFS问题较为常见，简记为Fm||Cmax[3]。

目前，在求解流水车间调度问题的传统方法中，精确算法受限于问题的规模和性质，而启发式和元启发式算法能在较短的时间获得问题的近优解。针对Fm||Cmax问题，Ying[4]提出一种迭代贪婪(Iterated Greedy，IG)算法，并分三阶段运用IG算法改进……