轩 华 王 晶 张慧贤 李 冰

(郑州大学管理工程学院 河南 郑州 450001)

0 引 言

带机器可利用约束和阻塞的混合流水车间调度问题(Hybrid Flowshop Scheduling Problem with Machine Available Constraint and Blocking，HFSP-MACB)同时考虑了机器故障和机器阻塞。由于机器故障或维护等使机器在一定时间内无法用于正常工作。在实际生产过程中，机器故障是常见的不确定因素，会对生产计划和结果产生偏差，甚至可能会引起配送等环节的混乱。因此在制定生产计划时考虑机器故障干扰，减少机器故障对调度性能的影响。此外，在相邻生产阶段的缓冲区能力有限或不存在，当工件完成前道工序的加工后，如不能进入缓冲区等待则需停留在加工它的机器上直至下游机器释放，从而导致了该机器的阻塞。这类问题在工业生产中有着较广泛的应用。例如，在船舶平面分段制造模式下，平面分段的重量和体积较大等导致难以储存，考虑到经济性，工序之间一般不设置缓冲区，当前道工序的任务完成后，需要下道工序的工位释放后才能继续进行加工，此时就形成了阻塞。同时，分段从前道工序运送到后道工序的运输时间不可忽略。因此，这就形成了考虑运输时间的HFSP-MACB。Hall等[1]已证明当机器数多于两台时不考虑运输时间的阻塞流水车间是强NP-hard，故所研究的带运输时间HFSP-MACB也是强NP-hard。

运输时间有两类，一类是与工件相关，即运输时间取决于工件自身；另一类是工件无关的，即运输时间由相邻生产阶段之间的距离决定。针对带运输考虑的两阶段HFSP，为最小化makespan，文献[2]假定运输时间取决于工件，每阶段有多台同构并行机，提出了一种两阶段启发式和一种分支定界精确方法；……