于艳辉 侯东亮

［摘要］ 首先介绍了具有缓冲区约束的流水车间调度问题的一般框架、算法及其分类，主要针对启发式算法进行分析和总结，并进一步介绍了如何合理设置缓冲区以及存储时间有限的情况，最后，探讨了在此研究领域中的未来发展趋势。

［关键词］ 流水车间； 缓冲区限制； 启发式； 存储时间有限

doi : 10 . 3969 / j . issn . 1673 - 0194 . 2012 . 06. 029

［中图分类号］F273；F406.2［文献标识码］A［文章编号］1673 - 0194（2012）06- 0061- 03

常规的流水车间调度问题研究是在假设机器间缓冲区的存储能力是无限的前提下进行的，而在大量的实际生产加工环境中，由于存储设备（如存储罐、中间库存等）以及生产工艺在空间、时间等方面的限制，缓冲区的存储能力往往是有限的，例如化工、钢铁和制药等实际生产系统。因而，具有缓冲区限制的流水车间调度问题（Lｉｍｉｔｅｄ－Bｕｆｆｅｒ Ｆｌｏｗｓｈｏｐ Sｃｈｅｄｕｌｉｎｇ Pｒｏｂｌｅｍ， ＬＢＦＳＳＰ）更加符合实际应用背景，对该问题的研究具有重要的理论和实用价值。本文给出了ＬＢＦＳＳＰ问题的一般框架，依据大量的文献总结了该领域的研究理论和方法并进行了分类，进一步讨论了今后的研究方向。

１ＬＢＦＳＳＰ问题的一般框架

１．１问题描述

ＬＢＦＳＳＰ问题可以描述如下：设存在n个工件（1，2，…，n）及m台机器（1,2，…，m），该n个工件将依次在机器１至m上进行加工；在任一时刻，每个工件最多在一台机器上加工，且每台机器最多同时加工一个工件；在每两台相邻的机器j和j - 1之间，存在大小为Bj的缓冲区；工件在每台机器上的加工顺序相同，即所有工件在缓冲区中均服从先入先出规则（ Ｆｉｒｓｔ Ｉｎ Ｆｉｒｓｔ Ｏｕｔ ， ＦＩＦＯ），工序不允许中断。ＬＢＦＳＳＰ调度问题存在两种特殊情况：（１） 当缓冲区为零时，该问题转化成阻塞流水车间问题（ＢＦＳＳ）；……