基于效率规则的混合作业车间调度算法应用研究

Research on M ixture Job Shop Scheduling Algorithm Based on Efficiency RulesWu Zhengjia Lin Pan Zhang Cheng Zhu Xiaoqin Luo Yuesheng(College of Mechanical＆ Material Engineering，China Three Gorges Univ.，Yichang 443002，China)Abstract In order to solve Mixture Job-Shop scheduling problem，this paper presents an algorithm of job-shop scheduling based on efficiency rule.Efficiency function of workpiece processing is introduced to processthe sorting and regulation of the order，which realizes the rapid，high-efficient and optimized output.Moreo-ver，this kind of algorithm is applied to develop workshop scheduling system ，which also uesed to factualMixture Job-Shop scheduling for verification.The results of calculation show good effect of scheduling opti-mization；and this algorithm can be well applied to mixed job-shop scheduling。

Keywords mixed job shop； efficiency rules； scheduling algorithm在混合作业车间调度问题中，其中-部分工序是没有严格 的先后顺序的；另-部分工序又具有严格 的顺序 ，也就是说会有-些工序具有-个或多个紧前或紧后工序l1].混合作业调度问题具有作业方式多样化、规模庞大、系统复杂等特点.应用传统的函数分析方法，又很难将所研究的问题抽象为相应的数学问题，且计算量极其庞大，步骤过程也较为繁琐，故难以顺利完成l2J。

本文设计了基于效率 函数初排排序再调节排序的方法 ，来解决混合作业 车间调度 ，并将该方法应用到具体的实例.结果表明这种基于效率规则的调度方法可以有效地优化混合作业车间最大完工时间 ，从而可以推广运用到混合车间调度问题的求解。

1 混合作业车间调度问题1.1 问题描述假设有 台机器 M ，M2， ，M 需要加工 个工件 ， 。，， .混合作业车间需要解决的两个关键问题 ：-是如何安排工序的顺序 ；二是如何确定工序在机器上的加工时问，并保持每个加工工件的工艺约束.和传统的车 间作业调度 问题相似 ，对此类混合作业车间调度问题也存在以下假设 ：1)-个工件 同-时间只能在-台机器上加工 ；2)正在加工的工序不允许中断；3)同-时间- 台机器只允许加工-个工件；4)每道工序只允许在-台机器上完成；5)工件在工序间可 以等待 ，工件未到达前机器可以闲置 ；6)工件与收稿 日期 ：2012-11-22通信作者 ：吴正佳(1964-)，男 ，教授 ，硕 士生导师 ，主要从事工业工程及先进制造技术研 究.E-mail：linpandjdj###163.com86 峡 大 学 学 报(自 然 科 学 版)机器的相关参数均-致 ，包括 ：工序在机器上的加工时间，工件的工艺路线 ；7)每个工件 的第-道工序开始加工时间大于等于零口 ]。

1.2 问题数学建模设有机器集 M-M ，M ，，M ，工件集 J-J ，J。，，J 和工序紧前集 SS ，S ，，S .其中工件 J 的加工工序为 J ，.，妇，加工工序J衄!的工序 紧前集 S 为 0 ，02，，OQ(Q ，i-l，2， ，n).其中 P 表示工件J 第 道工序 J 在机器 P ，上加工( -1，2，，Q ；i-1，2，， ；P ∈Ml，M2，， )，且加工时间为 丁 设 S ，和ET 分别为工序-， ，的开始时间和结束时间，且 ST ≥0(i-1，2，， ).则工件 -， 的前 e道工序的工时之和为：TS -Q∑T 工件 J 的所有工序的工时之和为 ：丁 -∑TJ- 1 J- l使用函数 r(i，J)度量工件加工效率或加工速度 ，其中0

设 为第 愚台机器 (忌-1，2，， )加工的工件数 ，E 为第 是台机器上最后-个加工工件完成 的时间，则 maxE )为所有的 台机器中的最长加工路径，即最大 make-span，本文 maxEh 将最小作为调度方案的评价指标 ，如式(2)所示厂：minmaxEh. (2)2 基于效率规则的混合作业调度算法设计2.1 建 立 队列对混合作业调度建立了 3个队列 ：工件队列.按其次序约束，出现多道紧前工序时，任意初始顺序 ，将每个 工件的加工工序 排列成队列L.， (i-1，2，，n)6].在此 队列 中，每个工序 的加工时间不能重叠，即工件 的前-道工序加工完成后才能进行后-道工序的加工。

机器队列.按实际加工顺 序，将每台机 器上加工的工件排 列成 队列 L (忌-1，2，，m).在此 队列中，每个工序的加 工时间互不重叠 ，即工件在同-台机器上 ，当-个加工任务完成之后才能开始另-个加工任务 。

工序多道紧前和紧后工序队列.建立工件每道工序的紧前 队列 L.厂挑(S-Ok，b-Q ，i-1，2， ，”)，b代表某个工件的第几道工序 ，5表示工序 b的 紧前工序的个数 .因此 ，计算各工序的实际开工时 间与完工时间时 ，必须保证 3个 队列的完整性.即调度 问题就变成如何根据队列 L.， 和 L 来确定工件队列的最终顺序 ，然后把 L.， 中的各工序如何插入到 LM中，并且保证目标函数值最优或近似最优。

2.2 初始化1)工件 队列：按照工件 的每-道工序 的次序约束，出现多道紧前工序时，初始顺序任意，建立各个工件的-个工件队列 LJ (i-1，2，，n)。

2)根据式(1)计算每道 工序的 r(i，J)，则对于各个工件 .， ( -1，2，，7"1)满 足 max(1-r(i， ))的工序必在队首，出现多道紧前工序时都按照先加工计算效率。

3)机器队列 ：初始时各机器都未被分配 ，即每个机器 队列 LM (忌-1，2，，m)均置空 Null，而且每个机器 加工的工件数 均置 0，Mk。也置 0。

4)建立多道紧前工序队列：依据各个工件的每道工序的紧前工序个数 ，建立各个工件的-个 紧前工序队列 L (5-Ok，6-Q ，i-1，2，， )E9-1o]。

2.3 初排算法的设计混合作业车间初排算法流程如下 ：Step1： -0(忌-1，2，， )，W -J l歹-1，2， ，Q ；愚1，2， ，i-1，2， ， ；Step2：存在多个紧前或紧后工序时，都按照此工PQ序先加工计算效率，丁S -∑T ，Ti-∑丁 ，r( ，J- 1 - 17"qe)- (e- 1，2， ，Q ；i- 1，2， ，”)； fStep3：在各 个 工序 中选 择 满 足加 工 效 率值 为max(1-r(i，J))( -1，2，，Q ；i-1，2，，n)的工序 J如果不唯- ，则取满足 maxTi-TS 的工序-， 然后循环到下-道工序 J针 ；Step4：如果 P ，则将工序 插入到机器列队LM 的队尾 ；Step5：分别依据式(3)、(4)和(5)计算工序 J 的开始时间 ST 、结束 时间 F叮和等待时间 wTST - maxFT 1，E (3)FT - ST T (4)T - STfJ- Eh。 (5)第 35卷 第 2期 吴正佳 ，等 基 于效率规则 的混合作业车间调度算法应用研究 87Step6：更新 - 1，并 E .-FTo；Step7：判断工件 队列 L (i-1，2， ，：r/)是否遍历完毕，是则跳转 Step8，否则，跳转 Step3；Step8：比较工件某个工序 的多个紧前或紧后工序 的开始时间 STo，ST 大的效率值发生改变 r(i， 1)- ；Step9：判断紧前工序队列数值是否全部为 1，是则算法结束 ，否则，跳转 Step2。

2.4 调节算法的设计设 W 为第 K 台机器完成第 L-1次加工 ， 后要进行第 Z次加 工 ，的等待 时间，即：W - T ，，(k1，2，， ；Z-1，2， )，贝4"kEh -∑(w T ，，)-∑w ∑T 。，(6)： 1 1 - 1E 为第 k台机器上的最后-道工序的时间。

设 - ，第 i台机器上 的第 L次加工 的工件 ， ，加工的工时为 丁出 ，则Step5：设计器 上第 J次加工 的工序为 御，J1次加工的工序为 ， ，，如果工序 ， ，的前-道工序 J p，qrl的结 间束时 FT幽.11%ST加，则交换 .， ，和在机器 M 上的加工顺序 ；Step6：重复计算 机器 队列 L (k-1，2，，m)中工序 -， ，。，及后面各工序 的开始时间、结束时间 、等待时间 ，并更新 E ，L-E ；Step7：j之E -maxE ；Step8：如果 E ≤L，则 L-E ，转 Step6，否则不再调节 ；Step9：算法结束。

3 实例计算与分析某车间有 4个工件在 4台机床上加工，每个工件有 4道工序，假定 每个工件在每 台机床上各加工 -次 ，并且每道工序的加工时间和每个工件的加工路线已知 ，详细数据见 以下 3个矩阵 ：nl”iE ∑(w T ，)-∑w ∑T ，(7)- tt因为 为确定的数 ，所以-1minE min∑ ∑Ti， l l l 1l”min∑ )∑T (8)、 1 Z- 1从 而 minE 与 min f∑w 等 价 ，minmax” )与minmax互w )等价，即nminE minf∑W (9)minmaxE 铮minmaxf∑w 7 (1o)、 1调节算法的目标为minmaxf∑w (11)具体调节算法流程为：Stepl：计算 w (愚-1，2，，m；Z-1，2，，7z )；Step2：求 LE -maxE ).这里 i存在 ，但不- 定唯- ，i∈ 1， 2，， Z)，k∈1，2， ，m；Step3：遍历机器队列 中 L (k-1，2， ，m)对任意-个 i，若 W -0(z-1，2，， )则排序结果最优，不需调节.此时 ，关键路径上的各个工序均无等待时间，排序结果最优，跳转 Step9；Step4：求 W -W ，但 W口≠O的工序 J如；1 11 11 11 11 23 33 72 12 11 21 12 12 32 12 21 5， J -l 34 21 21 24 23 13 44 3， s ， -运用上文中效率规则算法，对实例问题进行计算求解 ，并在开发的调度系统中以甘特图的形式进行调度结果输出，初排算法计算后输出结果和调节算法输出结果分别 如图 1～2所示.图中，纵轴表示机 器编号 ，横轴表示时间。

图 1 初排结果输 出界面 图 2 调节结果 输出界面通过以上调度甘特图可以看出，进行初排算法计算后最长时间为 17个工作时，再采用调节算法计算最终 的调度结果为 16个工作时.通过初排算法计算再调节计算后 ，整批工件的排产时间得到了很好 的优化.证明了这种基于效率规则 的调度算法可以很好地解决混合作业车间的调度问题，可以很好地应用 于混合作业车间调度。

88 i 峡 大 学 学 报 (自 然 科 学 版) 2013年 4月4 结 语基于效率规则的混合车间调度算法 ，基本思想是在工件效率 函数 的基础 上，设计初排排序再 调节排序 ，最终得出调度结果.这种算法在混合作业 车间调度问题中研究得比较少 ，可能还存在进-步的改进可能 ，但可 以作为混合作业车间调度问题的-个新 的研究方 向，开展相应有意义的研究工作。