作业车间批量调度策略研究

*于 华，王 雷

作业车间批量调度策略研究

*于 华，王 雷

（安徽工程大学机械与汽车工程学院，安徽，芜湖 241000）

作业车间调度问题是最困难的组合优化问题之一，在实际生产中具有广泛应用。调度的目的是使完工时间最小化。本文针对实际的具有批量调度问题，分析并比较了几种调度策略。采用遗传算法进行求解，针对作业车间调度问题使用了一种单亲移位算子进行交叉和变异以避免不可行解的产生。最后给出了这些调度策略的仿真实例，结果表明，使用不同的调度策略将得到不同的优化结果，为实际的生产提供一定的指导作用。

作业车间调度；遗传算法；单亲移位交叉算子；批量调度

作业车间调度问题(Job shop scheduling problem, JSP)是许多实际问题的简化模型，是最典型、最困难的组合优化问题。遗传算法(Genetic algorithm, GA)作为全局搜索算法，广泛应用于各种优化问题中，并已成为求解复杂JSP问题的主要方法[1-5]。

但是到目前为止，绝大多数的经典车间作业调度问题只假设每种加工工件是单件的情况，而忽视了在实际生产过程中每种工件的加工数量却是大于或等于1的任意自然数。因此，研究在此情况下的批量或者分批调度才显得尤为重要。白俊杰等人[6]提出了一种基于粒子群算法的多目标柔性分批调度算法，将工件分割为具有柔性批量的多个子批量，并使子批量的工艺路线选取和加工排序同时得到优化。孙志峻等人[5]提出了一种等量分批调度遗传算法，使子批数量的确定和子批加工顺序的安排同时得到优化。文献[2]考虑机床资源的分配和生产调度的同时，更注重批量调度，并分析了几种调度方案。鞠全勇等人[7]将粒子群算法与遗传算法相结合，提出了一种混合优化算法求解多目标批量调度问题。曾强等人[8]对基于准时交货的批量生产FJSP多目标优化调度问题进行了研究。以上这些基本上都是从多目标的角度或者改进智能优化算法的角度对批量调度进行了较为深入的研究。而本文研究了基于GA的不同调度方式对调度结果性能的影响，算法的性能不是本文研究的重点问题，主要目的是分析几种调度策略多调度结果的影响，为研究实际生产调度问题提供一种可行的指导思想。最后通过实例进行了比较分析，仿真结果表明：使用不同的调度策略将得到不同的优化结果，在实际的生产中具有重要的指导意义。

1 作业车间调度问题描述

一般Job-Shop调度问题可描述为：有若干个工件，每个工件包含若干个工序，这些工序需要在若干台设备上进行加工，每道工序有确定的加工时间。调度的问题是要求给出任务在加工设备上的合理排序，以使得目标函数值达到最优。同时做出以下假设：

(1) 所有工件在零时刻同时到达；

(2) 每一工件在同一时间只能在一台设备上加工；

(3) 工序加工的不可抢占，即若一道工序在一台设备上加工，必须加工完成后，才能加工另一道工序；

(4) 一台设备在同一时间只能加工一个工件；

(5) 工序的加工时间，是一个事先确定的固定值；

(6) 每一工件的加工路线是固定的，并且每一道工序只能被指定的唯一设备加工；

(7) 工件的加工允许等待；

(8) 整个加工过程中，设备连续可用，无故障；

本文以总完工时间最短为目标的数学规划模型可表示为：

min()=(C) (1)

式中各符号的含义如下：

c：工件在设备上的完工时间；

t：工件在设备上的加工时间；

a：如果工件在设备上先于在设备上加工，a=1，否则a=0；

x：如果工件先于工件到达设备，x=1，否则x=0；

：一个很大的正数；

式(1)为以完工时间makespan为优化目标的函数；式(2)和式(3)分别表示工艺约束和设备约束。

2 求解车间调度GA算法

2.1 编码设计

求解Job-Shop调度问题的遗传算法编码主要有基于工序的编码、基于工件的编码、基于优先表编码、基于优先规则编码和基于机器的编码等多种。由于基于工序的编码具有编码和解码方案简单、柔性高、容易实现等特点，本文选取基于工序的编码与解码。以下以一个简单的实例来具体阐述基于该编码与解码方法的调度问题。该问题的加工时间和工艺约束如表1所示。

表1 加工时间和工艺约束

Table 1 Processing time and process constraints

设它的一个染色体为[211312332]，其中1、2和3分别表示工件J1、J2和J3。染色体中从左向右出现数字的次数分别表示工件的加工工序，如第一个数字2表示工件J2的第一道工序，第二个数字2表示工件J2的第二道工序，其它意义相同。对上述染色体进行解码后得到最优调度Gantt图如图1所示，总最小完工时间Makespan = 13。

图1 解码获得的调度结果

2.2 适应度函数确定

适应度函数通常取目标函数直接作为适应度函数，在这里取最大的流程时间() = max(C)的倒数作为适应度函数，由此来计算每个染色体的适应度值

() = 1/() (7)

2.3 遗传操作设计

（1）复制

（2）交叉

在一般的遗传算法中，交叉是一个重要的遗传算子，是对发生交叉的双亲随机选择交叉位置后，使交叉点后的部分交换，产生新的个体。但对JSP问题，如果交叉算子使用不当会产生不满足约束条件的解，即非法解。因此，本文采用一个单亲移位交叉算子，即通过一个染色体进行交叉，这样不但简化了遗传操作，而且可以避免非法解的产生。

算法描述如下：

step1.随机产生一个正整数；

step2.取出染色体中位置后的-个基因；

step3.将取出的基因移动至染色体最前端。

例如1=(123)，=3，则

2=(123)。

在交叉过程中，交叉概率p用于控制交叉操作的频率。概率太大时，种群中串的更新很快，进而会使高适配值的个体很快被破坏掉；概率太小时，交叉操作很少进行，从而会使停滞不前。因此，交叉概率介于0.5~0.8之间能很好地平衡这两者的关系。

（3）变异

在二进制编码的遗传算法中，变异是将染色体中某一位由1变为0，或反之。但在自然数编码的情况下，对某一位单独进行变异容易产生非法解。因此，本文采用基因逆序的方法进行变异。描述如下：

step1.随机产生两个正整数1，2，且1不等于2；

step2.将两个位置之间的基因值逆序放置。

例如，1=(34643)，1=3，2=6，则2=(34643)。

为了加大种群多样性，要对变异概率p选择适当的数值。概率太小则不会产生新个体，概率太大则使GA成为随机搜索。因此，选取变异概率为0.05~0.15之间较为合适。

3 调度实例

现有4个Job类型的工件需要在4台设备加工，各个Job类型的各个操作的加工时间和可用机床等信息，如表2所示。本问题的评价指标是寻求最短生产周期（makespan），在此采用GA对于批量调度的方案进行研究。

表2 加工时间和工艺约束

本文采取基于工序的编码方式，其它遗传算法参数选择：种群规模= 40，进化代数= 50，交叉概率p= 0.7，变异概率p= 0.1。

♦ 方案1 单件重复调度最小完工时间

对于单件调度，用遗传算法寻求到的最小完工时间是24。由于每类加工工件的数量是3，那么最终加工完所有工件的时间是72(24×3)。图2所示的是其调度Gantt图。从图中我们可以很容易发现这种方案存在的不足：以后各批次的开始加工时间都要满足24的整数倍，方可开始加工，这样将使得有些加工设备没有得到充分利用，降低了资源的利用率。

图2 方案1的调度Gantt图

♦ 方案2 整体调度法

整体调度法的思想是把要加工每一种工件一次性加工完成，其调度Gantt图如图3所示。从图中可以看出最终工件全部加工完毕的生产周期是63，比第一种方案节省9个时间单位。这种方法的优点是不需要频繁的调整安装，提高了加工效率。

图3 方案2的调度Gantt图

♦ 方案3 把每一个加工工件当作一个不同类的加工工件看待去调度加工

此方案完全与前两种方案的思路与众不同。此方案并不考虑同种工件之间的数量。将全部的12个工件当作12个互不相同的工件来调度进行加工。图4所示时其调度Gantt图（其中编号1、2和3代表任务1；4、5和6代表任务2；7、8和9代表任务3；10、11和12代表任务4）。从图中可以看出加工完所有工件的最小完工时间为60，比第一种方案减少了12个时间单位，比第二种方案减少了3个时间单位，说明使用此种调度方案可以得到较优的结果。值得注意的是，如果当任务数量比较大时，使用该方法将得到比其他方案更加好的结果。

图4 方案3的调度Gantt图

4 结论

从上述对不同调度策略方案的调度结果分析很容易得到的结论是：由单批次（单件）所获得的调度方案对后续批次的加工顺序起不到指导性的作用，单件最优加工顺序不适用于批量调度。因此，在实际的生产过程中可考虑使用“不考虑工件之间的批次性”这种方案加工工件将得到更加优化的结果。

[1] 王万良,吴启迪,宋毅.求解作业车间调度问题的改进型自适应遗传算法[J].系统工程理论与实践,2004(2): 58-62.

[2] 孙志峻,安进,黄卫清.作业车间多工艺路线批量作业计划优化[J].机械科学与技术,2002,21(3) :348-350,354.

[3] 张超勇,饶运清,李培根.基于POX交叉的遗传算法求解Job shop调度问题[J].中国机械工程,2004,15(23): 2149-2153.

[4] Byung Joo Park, Hyung Rim Choi, Hyun Soo Kim. A hybrid genetic algorithm for the job shop scheduling problems [J], Computers & Industrial Engineering, 2003, 45(4):597-613.

[5] 孙志峻,安进,黄卫清.作业车间多工艺路线批量作业计划优化[J].中国机械工程,2008,19( 2) :183-187.

[6] 白俊杰,龚毅光,王宁生,等.多目标柔性作业车间分批优化调度[J].计算机集成制造系统,2010,16( 2) :396-403.

[7] 鞠全勇,朱剑英.多目标批量生产柔性作业车间优化调度[J].机械工程学报, 2007, 43 ( 8 ):148-154.

[8] 曾强,杨育,沈玲,等.基于准时交货的批量生产FJSP多目标优化[J].计算机集成制造系统,2011,17(8):1780- 1789.

RESEARCH ON STRATEGY OF JOB-SHOP BATCH SCHEDULING

*YU Hua, WANG Lei

(School of Mechanical and Automotive Engineering, Anhui Polytechnic University, Wuhu, Anhui 241000, China)

Job-shop scheduling problem (JSP) is one of the most difficult combinatorial optimization problems which are widely applied to the practical production. The purpose of job-shop scheduling is to minimize the completion time. Aiming at batch process scheduling problem, several schemes are analyzed and compared. A partheno-genetic operation (PGO) for crossover operation in JSP is proposed in order to avoid unfeasible solutions. Finally, an example is given and the results of these schemes show that the different optimal scheduling results will be obtained by different schemes. Therefore, these schemes can provide certain instructional significance for practical production.

job-shop scheduling; genetic algorithm; partheno-genetic operation; batch process schedule

TP311

A

10.3969/j.issn.1674-8085.2013.01.017

1674-8085(2013)01-0079-04

2012-05-12；

2012-07-20

国家自然科学基金项目（51175262），安徽省自然科学基金项目(1208085QE94)，安徽高校省级自然科学研究项目(KJ2012B008)，安徽工程大学博士科研启动基金项目（2011YQQ006）

*于 华(1966-)，女，山东烟台人，讲师，硕士，主要从事机械制造及其自动化方面的研究(E-mail: yh@ahpu.edu.cn);

王 雷(1982-)，男，安徽亳州人，讲师，博士，主要从事制造系统调度与控制方面的研究(.E-mail:wangdalei2000@126.com)