基于折衷策略的Blocking流水车间调度构造启发式算法.pdf

系统1=程理论与实践 第lO期 14-05 文章编号：1000-6788(2008)10-01 基于折衷策略的Blocking流水车间调度构造启发式算法 洪宗友1，庞哈利2 (1．沈阳化工学院数理系，沈阳110142；2．东北大学系统．1程研究所，沈阳110004) 摘要：针对目标函数为Makespan的Blocking流水车间调度问题，经过对目标函数结构的分析，提出了一 种基于折衷策略对工件进行初始排序的启发式算法．通过对大量典型算例的计算，实验结果证明了设计 的算法在解的质量上超越了NEH算法． 关键词：流水车间调度；启发式；Blocking 中图分类号：Iir29 文献标志码：A on Onaconstructiveheuristic based Study algorithm compromise for policyBlockingflow-shopscheduling HONG Ha-li2 Zong-youl，PANG of InstituteofChemical 110142，China；2．Institute (1．Depa血舱IltScience，Shenyang Technology，Shenyang of两咖EIlgineering， Northeastern 110004，China) University，Shebang Abstrs畦Thisaddressesthe of with of schedulingobjective paper problemBlockingflow-shop makespan．A ofthe isbasedonthe ofthestructureofthe compromiseInitial-Sequencingpolicy pIoI)osedalgorithm analysis objective results withthefamousNEH basedonbenchmarksdemonstrated function．Computationaland㈣pE—目lm algorithm the ofthe aLgoritIlIn． superiorperformanceproposed Key words：flow-shopscheduling；heuristic；Blocking O引言 常规的流水车间调度问题假设机器间缓冲区的存储能力是无限的．然而，在很多实际的生产加工环境 中，因为工艺要求、空间因素或存储设备本身容量(如存储罐、中间库存等)的限制，机器(工序)问的缓冲 区往往是有限的，甚至不存在中间缓冲区．这种有限缓冲区生产环境下的调度问题称为具有存储约束的流 水车间调度问题．在有限的缓冲区容量约束下，若一个工件已完成在某台机器上的加工操作，但该机器下 游的缓冲区已满，则称该工件被阻塞(blocked)，工件将滞留在这台机器上直至下游缓冲区可用为止．比如 后，如果下游机器忙且(或)中间缓冲区满，则该工件(作业)将滞留在机器上，直至中间缓冲区被释放．在 Blocking流水车间调度问题中，仅考虑机器间不存在存储缓冲区情况，工件在某机器上完成加工后，如果下 游机器忙，该工件将滞留在这台机器上，直至下游机