人工蜂群算法求解混合约束流水车间调度问题

孙厚权，张其亮

(江苏科技大学 电气与信息工程学院，江苏 张家港 215600)

0 引 言

流水车间调度问题是一类经典的组合优化问题，当机器数m>2时，该类问题被证明为NP-难问题[1]。传统的FSS问题是在假设相邻工序之间存在无限大的缓冲区这一前提下进行的，然而在实际生产过程中，工序之间的缓冲区往往是有限的甚至是不存在的。例如，在钢铁轧制过程中，为了防止金属成分遭到破坏，在钢板冷却之前，板坯的一系列加热过程必须连续进行，工件在工序之间的加工不能有停顿，此类流水车间调度问题被称为无等待流水车间调度(no wait flow shop scheduling，NWFSS)问题；另外，在一些食品加工生产线，食品在一个工序加工完成后，若紧邻下一道工序的加工机器非空闲，则加工食品将被阻塞在当前工序的加工机器上，直到紧邻下一道工序的加工机器可用，该类问题被称为阻塞流水车间调度(blocking flow shop scheduling，BFSS)问题。

相对于传统的流水车间调度问题，NWFSS问题和BFSS问题更具有实际意义。查阅文献知，国内外已有不少专家学者对NWFSS问题、BFSS问题进行了研究，并取得了较好的成果。但是目前的研究大都假定所有工序间的约束是单一约束，对工序间可能具有不同缓冲约束的调度问题研究相对较少，目前类似的研究文献主要有：文献[2]将传统BFSS问题定义为RSb(release when starting blocking)，在此基础上提出了一种新的阻塞调度问题，称之为RCb(release when completing blocking)，并对工序具有两种混合阻塞约束的调度问题进行了分析和求解；文献[3]针对工序间RSB约束和RCB约束及RCB*(release when completing blocking*)约束混合存在的流水车间调度问题设计了遗传算法进行求解，算法虽然能得到较优解，但是在样本空间较大时，算法收敛速度较慢，效率不高；文……