具有缓冲区约束的流水车间调度问题综述

《具有缓冲区约束的流水车间调度问题综述》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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

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

3、流水车间问题（ＢＦＳＳ）；（２）当缓冲区为无穷时，该问题转化成一般流水车间调度问题（ＦＳＳ）。　　１．２ＬＢＦＳＳＰ调度问题的模型　　１．２．１一般数学模型　　该调度问题通常以加工完成时间最小化为目标，即ｍａｋｅｓｐａｎCmax，则数学模型可表示为如下形式：　　pij――工件Ji在机器Mj上的加工时间；Sij――工件Ji在机器Mj上的开工时间；Cij――工件Ji在机器Mj上的完工时间；Bi――工件Ji在两阶段间的缓冲区的大小；　　min｛Sn，m+pn，m｝　　≠k），j∈J　　２ＬＢＦＳＳＰ问题的研究方法　　对有缓冲区约束的流水车间调度问题的研究最早可以追

4、溯到２０世纪７０年代，分别由Ｐｒａｂｈａｋａｒ在１９７４年，Ｄｕｔｔａ和Ｃｕｎｉｎｇｈａｍ在１９７５年提出。Ｄｕｔｔａ和Ｃｕｎｎｉｎｇｈａｍ以及Ｒｅｄｄｉ详细地描述了有缓冲区约束的两台机器的流水车间调度问题的解法，但这一解法只能用于解决规模较小的问题。通过对大量文献的分析，现有的调度算法以启发式算法为主，与最优化方法相比较，启发式算法在调度效果和计算时间之间折中，能够在较短的时间获得近优解或最优解。近年来，禁忌搜索算法（ＴＳ）、遗传算法（ＧＡ）等都得到了广泛的应用。　　Ｐａｐａｄｉｍｉｔｒｉｏｕ和Ｋａｎｅｌｌａｋｉｓ在１９８０年证明了有缓冲区限制的两阶段流水

5、车间调度问题是ＮＰ完全问题，并给出了有缓冲区限制的两阶段流水车间调度与两阶段无等待流水车间调度ｍａｋｅｓｐａｎ之间的关系：=2b+1/b+1。通过进一步研究当buffer=1的情况，证明了与无缓冲区流水车间相比，完工时间可以减少１／３；同时证明了当m≥4且缓冲区为零时，该问题是ＮＰ完全的。Ｇｕｐｔａ在１９８８年针对多阶段的混合流水车间得到了相似的结论。在２０世纪９０年代，ＩｎｄｅｒＫｈｏｓｌａ研究了两阶段混合流水车间问题，其中第一阶段多机并行，第二阶段只有一台机器，两阶段间存在一个有限缓冲区。针对该问题建立了一个混合整数线性规划模型，以最小化加权完工时间为目

6、标函数，利用拉格朗日及拉格朗日松弛算法给出了问题的下界，并提出了基于优先准则的启发式算法。　　Ｌｅｉｓｔｅｎ研究了目标函数为最小化ｍａｋｅｓｐａｎ的流水车间，将ＮＥＨ等启发式算法分别应用在无缓冲区、无限缓冲区及有限缓冲区3种不同的情况，并进行了系统地分析。实验结果表明：对于有限缓冲区的置换流水车间，Ｎａｗａｚ，ｅｔａｌ．提出的ＮＥＨ算法是最好的启发式算法之一。Ａ．Ｂｅｎｌｏｇａｂ则基于对平均工作流和调度过程甘特图的分析，提出了一种新的启发式算法。Ｐａｃｃｉａｒｅｌｌｉ等在１９９７年研究了有缓冲区限制的两阶段批处理流水车间调度问题，证明了该问题是ＮＰ难的，并提

7、出当批生产数量大于缓冲区限制时，目标函数为最小化ｍａｋｅｓｐａｎ的该问题将转化为可用多项式时间解决的ＴＳＰ问题。　　２．１邻域搜索算法　　邻域搜索算法在ＬＢＦＳＳＰ问题中得到了广泛的应用，主要集中在禁忌搜索算法、遗传算法等。　　2.1.1禁忌搜索算法　　ＴＳ是Ｇｌｏｖｅｒ提出的模拟智能过程的一种具有记忆功能的全局逐步优化算法，对变动的排序在其可行解的所有空间中进行搜寻，通过设置禁忌表，避免陷入局部最优或重复过去的搜索，利用中、长期的存储机制进行强化和多样化搜索。　　ＣｚｅｓＩａｗ在文献［15］中针对两阶段的具有缓冲区限制的置换流水车间调度问题，提出了一种近似

8、算法，该算法在禁忌搜索算法的基础上减少了被搜索的邻域