带有工件分组和容量约束限制,批处理机调度问题研究

０引言

批处理机调度问题的主要特征是把加热炉看成是批处理机，加热炉可以同时加工数个工件，工件以批方式进行加工，批中工件的进入、加工和离开都是按周期匀速进行，同一批中的工件都有自己的开始加工时间和完工时间。每个工件的加工时间均等于这批工件中加工时间的最大者，即基本加工时间。批处理机的调度问题包含如何分批及安排批的加工顺序。

由于工艺的原因，工件被分为若干个组，同一组的工件可以自由组批加工，不同组的工件不能一起加工。本文研究带有工件分组和容量约束限制批处理机调度问题。

虽然目前已有许多调度策略存在，大多数的研究采用的调度策略都是基于单一的算法研究得到的结果，忽视了对混合算法在这方面应用的研究，解的最优性能得不到保证。为了得到更好的解，利用不同类型算法的优点，设计出有效的混合算法是一种较好的选择。因此，本文采用基于路径重连的智能优化算法对带有工件分组和容量约束的批处理机调度问题进行研究。

１数学模型描述

设有n个工件要在一台半连续型批处理机上加工，这n个工件按照能否一起加工被分成k个组，把它们记为f(1),f(2)，…，f(k)；组f(i)(1

B■表示第i组中的第k个批。

批B■中全部工件加工完后才可以加工下一个批，组与组之间彼此独立；批B■的大小记为B■，基本加工时间记为P■即P■=maxP■▏J■∈B■；批的加工时间记为P■; 批处理机的容量为C。目标函数为最小拖期。

带有工件分组和容量约束限制的批处理机调度问题，用三参数表示法记作1|s-batch, ri incompatible|∑WjTj

２问题的分析以及基本性质

２．１完工时间在随机分布的情况之下，加工时间相似的工件组成一批可以减小总拖期

因为加工时间是由同批中加工时间最大的工件决定的，所以在加工时间相似的工件组成一批之后，可以提高批处理机的效率，也就是同一批加工时间内空闲的时间最小。在拖期是完全随机分布的情况下，加工时间相似的工件组成一批可以减小总拖期。

２．２加权平均交货时间和长的批后加工，可以减小总拖期

因为每一批中的不同工件交货时间不同，所以描述一个批的总交货期可以用加权平均交货时间来近似代替。这样的话，把交货时间越靠前的批越先加工，靠后的批稍迟加工，可以减小总拖期。

３TS&PR算法

３．１TS算法

禁忌搜索的基本过程是从一个初可行解S开始，确定满足特定条件的解S的邻域N(S)。然后从N（s）中选出最好的可行解S*，从S移动到S*。然后再从新的开始点重复搜索。为 了避免循环和陷入局部最优中，引入一个短期记忆装置，即长度为T的禁忌表，表中记录了最近进行的T个移动，在目前的迭代中，这些移动是被禁止的┌，T也叫作禁忌长度。

３．２PR算法

路径重连算法是沿着由起始解σA到向导解σB轨迹搜索，而由起始解σA开始到向导解σB结束的轨迹有很多，PR算法是通过与向导解有关邻域控制搜索轨迹的移动方向，其搜索性能对嵌入其中的局部搜索算法的邻域结构较敏感。一般来讲，局部搜索算法的邻域结构越好，PR算法的性能越好。局部搜索算法从起始解开始，在沿着起始解到向导解轨迹搜索移动过程中，向导解的属性逐步被引入到起始解中以形成一系列新解，直到搜索到与向导解相同的解以进行新的搜索。本文研究是用路径重连算法与禁忌搜索结合解决调度问题，问题的解与批之间加工的顺序相关，因此，局部搜索算法的邻域结构采用2种邻域：交换邻域N1(σA)和插入邻域N2(σA)。N1(σA)包括与向导解σB有关的经过交换的所有解，N2(A)包括与向导解有关的经过插入可获得的所有解。交换邻域首先从第一个要加工的位置i 开始，比较2个位置的批的序号是否相同，即σA(i)=σB(i)，如果相同，继续下一个加工位置位置，如果加工的批号不相同，在起始解内寻找与向导解对应的那一个批，即σA(j)=σB(i)，找到后，并确定该位置j，然后将σA(i)与σA(j)交换，其他加工位置的批号顺序不变。插入邻域初始过程与交换邻域一样，区别是插入邻域在起始解寻找与向导解对应位置相同的批号，找到确定该位置，如i

４TS&PR算法流程

１）分批

在同一组内，先把工件按照加工时间从大到小的次序排列，并在每C个工件处断开并分为一批。此时前面的批内都达到最大容量限制。同时清空禁忌表。

２）生成初始解与引导解

初始解的生成：

将个批按照加权平均交货时间从大到小排序，作为初始解。并计算此时的拖期f(A)。

引导解的生成：

将个批按照加权平均交货时间从小到大排序，作为引导解。并计算此时的拖期f(B)并与f(A)比较，把拖期小的解暂时作为最优解σ*。

３）按照邻域规则产生一个新的解σC。

4）如果σC（i）=σB(i) 则转到步骤8，否则转到步骤5。

5）在解σC中寻找与σB(i)中同一批所处的位置j，如果满足σC(j)=σB(i)，且ij均不在禁忌表内，则转到步骤6。否则，j=j+1，重复步骤3，直到σC(j)=σB(i)。

6）如果σC是按照交换邻域生成的，则交换对应的批：（σC(j)，σC(i)）否则，如是按照插入邻域生成的，在i

７）计算新的解σC的拖期，如果小于当前最优解，则此时的σC当做当前最优解。而且此时σ* =σC。并返回步骤2。

８）i=i+1 重复步骤3~步骤7，直到σC=σB。

９）迭代若干次，并输出此时的最优解。

５结束语

本文对带有工件分组和容量约束限制批处理机调度问题进行了研究，提出了一种新型的混合路径重连算法TS&PR。该算法将TS的构解机制与PR算法搜索机制相结合。采用这种新型路径重连算法可更有效地搜索解空间，从而克服基本禁忌搜索方式的不足。同时在算法设计中，对起始解和向导解选择规则、邻域结构设计及参考集更新准则等方面均做了一些创造性工作，为解决组合最优化问题提供了新的研究思路。

［责任编辑：张涛］

推荐访问： 工件 批处理 分组 调度 约束

---