批量生产作业车间的双资源多目标调度问题研究

2011-10-18初红艳费仁元李风光邓颖辉

制造技术与机床 2011年9期

初红艳费仁元李风光邓颖辉

(北京工业大学机电学院，北京100124)

车间批量调度在先进制造系统的生产实际中具有非常高的普遍性，研究车间批量调度的优化方法，不仅可以促进调度理论的发展，而且对于企业提高生产效率和生产能力，降低生产成本有着重要的影响［1］;双资源调度是指在调度过程中不仅考虑加工设备受到制约的情况，而且要考虑有着熟练加工能力或特殊加工能力的工人，工人和设备的合理利用明显有利于提高产品的综合效益;多目标调度则是指在作业车间内将各工件的工序合理安排在设备上，并确定各工序的开工时间，同时优化给定的多个性能指标。

通过对实际生产状况的分析，针对作业车间批量生产的问题提出了分批调度策略。建立双资源多目标优化调度模型，对分批后的工件采用遗传算法和禁忌搜索算法相结合的混合优化算法进行调度。调度算例验证了研究的可行性和有效性，对生产实践具有一定的指导作用。

1 分批调度策略

分批的核心思想是:当车间只加工一类工件时，必定存在一个最优的分批方案。

先确定一定数量某种工件单独加工时应该划分的子批数，然后计算每个子批包含的工件数，计算每个子批的每道工序需要的新的加工时间，并将每个子批看做一个新工件。在此基础上采用调度算法进行调度。

某工件单独加工时，需要划分的批次判定公式为

式中:m为工序数;n为批数;ti为该工件第i工序的加工时间;tL为最长工序的加工时间;K为子批中包含的工件数(此时判定公式并不是求得最终结果的公式，K根据计算结果能取非整数)，T为考虑分批的时间参数。

进行分批时，依次取n=1，2，…，N(N为工件的数目)，根据式(1)计算此时的时间参数T，比较找出最小的T，输出与其对应的分批数n。

分批算法中引入了参数K，可以取为非整数，这样就丰富了分批的情况，而不仅仅局限于完全等分批。比如，10个工件，可以分成4个子批，每个子批包含工件数为2，2，3，3。这样会比完全等分批更有可能得到最优解。另外，该算法是确定了合理的分批数目之后再进行子批相关数据的计算，相比于计算每次分批之后的子批数据，大大减小了计算任务。

2 双资源多目标调度算法

遗传算法经常被用于解决车间调度问题，经典的遗传算法虽然具有较好的全局优化求解能力，但当出现适应度很大的超常个体时，容易引起早熟收敛;而禁忌搜索算法通过引入禁忌表，避免迂回搜索，局部搜索能力强，弥补了遗传算法的不足。

本文利用遗传算法良好的全局搜索能力和禁忌搜索算法具有记忆能力的局部优化特性，将两种算法进行混合［2］，用于解决双资源多目标车间调度问题。先用遗传算法进行全局搜索，通过遗传操作，改善种群质量，再以该种群作为禁忌搜索算法的初始解，用禁忌搜索算法进行局部搜索，以在算法的全局收敛性能和避免早熟收敛方面有较大改善。

2．1 算法描述

算法流程如下:

Step 1:给定初始参数(包括最大迭代次数Y，群体规模s，交叉概率Pc和变异概率Pm);

Step 2:按照给定编码方式编码，产生初始群体，其中有s个染色体;

Step 3:按照给定的解码方式解码，得到每个个体的各优化指标，包括生产周期T1，T2，…，Ts，工件总延误时间d1，d2，…，ds，设备闲置时间e1，e2，…，es和工人闲置时间w1，w2，…，ws;

Step 4:按照多目标决策理论计算群体中每个个体的适应度值f(x1)，f(x2)，…，f(xs);

Step 5:调用TS搜索过程，对群体中的每一个个体进行局部搜索，从群体中选择r个较优解添加到禁忌表中作为禁忌对象。记各禁忌对象未被选择的次数为Li(i=1，2，…，r)，如果Li大于禁忌长度L，将所对应个体释放，转Step 6;否则直接转Step 6;

Step 6:根据交叉概率和变异概率对种群进行交叉、变异遗传操作，得到新种群;

Step 7:如果循环次数y＜Y，令y=y+1，转Step 3;否则转Step 8;

Step 8:停止运算，从禁忌表中选择确定数量的非劣解;

Step 9:使用层次分析法从非劣解集合中选择较优解作为最终的调度方案。

2.2 遗传编码

采用基于工序的编码方式。给同一工件的所有工序指定相同的符号，再根据它们在染色体中出现的顺序进行解释。例如，对于n个工件，每个工件有m道工序的问题，每个染色体由n×m个代表工序的基因组成，每个工件出现在染色体中m次。

以1个3工件，每个工件3道工序的问题为例，染色体的表达形式为211122333，其中第一个2表示工件2的第1道工序，第二个1表示工件1的第2道工序。

2．3 解码

解码即对编码进行翻译，产生具体可操作的工序安排方案。具体解码过程是:

(1)假设所有工序的理想可被加工起始时刻:设备k可以使用的时刻Mk=0(k=1，2，…，m)，工人w可以使用的时刻Pw=0(w=1，2，…，p)，工件i的第一道工序可被加工时刻Ti1=0(i=1，2，…，n);

(2)从工序集合S中取出此刻排在第一位未被调度的工序Oij(工件i的第j道工序)，从能加工工序Oij的设备集合中挑选最先空闲的设备k，其可以使用的时刻为Mk，从能操作设备k的工人集合中挑选最先空闲的工人w，其可以工作的最早时间为Pw;

(3)工序Oij开始加工时刻Tb=max(Mk，Pw，Tij)，得到工序Oij的完工时刻fij=Tb+tij，其中Tij为工件i的第j道工序可被加工的时刻，tij为加工工序Oij所需的时间;

(4)如果j=Ji，则工件i的完工时间Fi=fij，否则Ti(j+1)=fij，且Mk=fij，Pw=fij，其中j=1，2，…，Ji，Ji为工件i的工序总数;

(5)检查工序集合S中是否还有未被调度的工序，如有，转(2)，否则，生产周期T=max(Fi)。

2．4 遗传操作

(1)选择本研究通过禁忌搜索算法保留相对优秀的个体，因此选择操作将各个解的适应度值按顺序排列即可。

(2)交叉采用循环交叉操作。循环交叉操作是将另一个父代个体作为参照，以对当前父代个体中的基因位置进行重组［3］。

例如，给定2个染色体p1，p2，如图1所示。随机选择一个操作位置，如第2个位置，其对应的基因为6和5，则交叉过程为:首先选择循环链6-5，5-7，7-1，1-3，3-8，8-6，如图 1 所示。对应位置的基因交换后，生成新个体q1，q2，如图2所示。

(3)变异采用逆转变异法，即在染色体中随机选择两点，然后将两点间的基因以逆向排序插入到原位置中。如给定一个染色体p1，假设选中2号、5号位置，则变异后的染色体为q1，如图3所示。

2．5 禁忌搜索算法参数确定

(1)禁忌对象和候选解的确定以遗传操作后得到的种群作为禁忌搜索算法的候选解。禁忌对象是指那些被置入禁忌表中的变化元素，禁忌的目的是为了尽量避免迂回搜索。本算法将候选解中最优的40%作为禁忌对象，置入禁忌表中。

(2)禁忌长度的确定禁忌长度是禁忌对象在不考虑藐视准则的情况下允许未被选取的最大次数。禁忌长度根据不同的初始种群大小依据经验选取不同值。本文中禁忌长度随着种群规模的增大而增大。当某禁忌对象未被选取的次数达到禁忌长度值时，将该禁忌对象相对应的染色体释放，参与遗传操作，以避免产生局部最优。

3 多目标决策理论在算法中的应用

多目标决策理论的基本问题是研究如何在有多个相互冲突的决策准则(因素、目标、目的)下进行科学和有效地决策。层次分析法是20世纪70年代由美国学者萨蒂提出的一种多目标评价决策方法。其基本思路是决策者将复杂问题分解为若干层次和若干要素，在各要素间进行简单的比较、判断和计算，以获得不同要素和不同待选方案的权重，从而为选择最优方案提供决策依据。

在多目标车间调度问题中利用多目标决策理论，首先要确定各个目标的权重系数，然后对各个优化目标做无量纲化处理，确定目标函数。最后再根据层次分析法由非劣解集合求出较优解。

3．1 计算各目标权重系数

根据生产车间的具体情况，确定目标之间的相对重要性。目标比较的尺度分为5个等级:同样重要、稍微重要、明显重要、强烈重要与极端重要。对应的隶属函数分别为s1、s2、s3、s4、s5，如图 4 所示。

本研究的车间调度问题中，优化目标为生产周期、工件总延误时间、设备闲置时间和工人闲置时间。对这些目标两两比较，重要性较小的数为1。

假设根据生产需要，确定各个目标重要程度如表1所示。以重要度级别的隶属度函数作为随机数的概率密度函数，按照概率分布产生随机数分别代替重要度级别，得到目标比较矩阵表2。

把目标比较矩阵表2的每一元素除以其相应列所有元素的总和，得到标准两两比较矩阵，根据对比平均法［4-5］，再把标准两两比较矩阵各行元素相加并取平均值得到各目标的权重:生产周期权重ω1=0.374 3，工件总延误时间权重ω2=0.284 1，设备闲置时间权重ω3=0.189 7，工人闲置时间权重ω4=0.151 9。

表1 目标比较矩阵

表2 用随机数代替重要度级别得到的目标比较矩阵

3．2 计算目标函数值

在车间调度问题中，计算各指标值后，为把多个指标值集合成作为调度结果衡量标准的函数，需要对调度方案的各指标值按下列公式进行无量纲标准化处理:

标准化处理后，一个调度结果所对应的生产周期，工件总延迟时间，设备闲置时间和工人闲置时间分别表示为f1(x)、f2(x)、f3(x)、f4(x)，f(x)为衡量调度结果综合指标的目标函数，因为各单项指标均是求极小值，则按照线性加权和方法得到目标函数为:

此目标函数即为遗传算法的适应度函数。

3．3 获得非劣解集合和较优解

在优化算法的计算过程中，可以获得和保留非劣解。本文采用禁忌搜索算法实现。

获得非劣解集合后，根据层次分析法由非劣解集合中获得较优解。

根据目标比较矩阵表1，按照1-5标度法生成层次分析法的层次比较矩阵表3，然后把层次比较矩阵表3的每一元素除以其相应列所有元素的总和，得到标准两两比较矩阵，再把标准两两比较矩阵各行元素相加并取平均值就得到各目标的权重:生产周期权重ω1=0.449 5，工件延误时间权重ω2=0.259 6，设备闲置时间权重 ω3=0.170 7，工人闲置时间权重 ω4=0.120 2。则各个目标权重系数矩阵为U=［0.449 5 0.259 6 0.170 7 0.120 2］T。