张维存，左天帅，张博涵

（河北工业大学 经济管理学院，天津 300401）

0 引言

在Job Shop环境下，搬运设备的调度和缓存区容量的设置是影响车间调度优化方案的两个重要因素，将搬运设备和有限缓存区在Job Shop调度问题中集成考虑可以减少生产总成本，缩短产品生产周期，提高资源利用率。因此，如何将两方面同时考虑，将成为本文研究的重点。

近年来，国内外很多学习者在两方面分别做了大量研究。在仅考虑搬运设备的情况下，Egbelu［1］等首次提出了在Job Shop环境下，搬运设备调度的一些启发式规则。Hurink［2］等将单搬运设备调度问题看作具有时间窗的旅行推销员问题，通过禁忌搜索算法解决了 Job Shop排产问题。之后，Hurink［3］等又针对单搬运设备，同时考虑了工件运输时间和空载时间，提出了基于邻域结构的局部搜索算法。何之洲［4］等同样仅针对带单搬运设备的Job Shop调度问题，提出了一种并行禁忌搜索算法，其优点在于调度任务中包括了加工工序的排序和搬运工序的指派。不同于前人，Deroussi［5］等提出了基于搬运设备而非加工设备的解决方案，虽有创新但针对对象仍局限于单搬运设备。

区别于单搬运设备，多个搬运设备的Job Shop问题则不仅需要为各加工工序指派加工设备，同时还需指派搬运设备。如：Driss［6］等首先应用基于邻域搜索的遗传算法进行搜索，其次使用禁忌搜索算法进行工序排序。Lacomme［7］等采用析取图求解多搬运设备的Job Shop问题。Zheng［8］等提出了针对同时调度加工设备和搬运设备的混合整数线性规划模型，该模型由加工设备调度和搬运设备调度子问题组成，采用禁忌搜索算法求解近似最优解。……