基于SPEAⅡ的双资源多目标车间调度模型

任晓青，殷日超，杨雨露，包振强，王维中

(扬州大学信息工程学院，江苏扬州 225127)

基于SPEAⅡ的双资源多目标车间调度模型

任晓青，殷日超，杨雨露，包振强*，王维中

(扬州大学信息工程学院，江苏扬州 225127)

针对复杂制造业环境下实际作业车间受多种资源约束的问题，考虑工人综合素质及实际参与操作设备的人员数等因素所存在的差异性对工作效率的影响，建立了一种包含机器设备和操作工人2种约束资源的多目标车间调度模型，然后以完工时间最短、加工成本最低以及总拖期最小为目标，采用改进的强度帕累托进化算法(strength Pareto evolutionary algorithmⅡ，SPEAⅡ)求解该模型.仿真结果验证了该模型的正确性以及该文算法的可行性和有效性.

差异性操作效率;双资源;强度帕累托进化算法;多目标;调度模型

作业车间调度问题是制造业企业生产管理的核心，大多数相关研究仅考虑到机器设备的约束，然而据统计各领域中有60% ～90%的失效系统可归因于人误行为［1］，因此关于双资源车间调度问题的研究相继见诸报道.刘晓霞［2］，Ertay［3］，Ren［4］等同时考虑了机器设备和操作工人的约束，但将两者仅视为相互独立的资源.实际生产中，尤其是在单件小批量的生产方式下存在着大量不同工人操作同一机器以及同一工人操作不同机器时操作效率差异显著的现象，即存在差异性工人操作效率，这直接影响了生产成本及完工时间等目标.目前，求解双资源调度模型的方法主要有基于学习和遗忘规则［5］、工人转移规则［6-7］及优先级规则［8］等的启发式算法，以及遗传算法［9］、混合禁忌搜索［10］等智能算法.其中，改进的强度帕累托进化算法［11］(strength Pareto evolutionary algorithmⅡ，SPEAⅡ)在求解多目标问题时表现出良好的收敛性和解集分布性，且运行效率高.本文将在考虑差异性工人操作效率影响的基础上，建立以完工时间最短、加工成本最低以及总拖期最小为目标的双资源多目标车间调度模型，并应用改进的SPEAⅡ算法求解该模型.

1 建立模型

现有 n 个工件 Ji(i∈{1，2，3，…，n})，需要在由 w 个工人 Pp(p∈{1，2，3，…，w})和 m 台机器Mk(k∈{1，2，3，…，m})组成的车间内加工完成.每个工件包含一道或多道工序 Oij(j∈{1，2，3，…，Ni})，Ni为Ji的总工序数，各工序间存在先后约束的关系，每个工序可在一台或多台机器上加工，且机器在单位时间内的加工费用已知，但因各机器的性能不同，故工序的实际加工时间存在差异.每个工人可操作一台或多台机器，即w＜m.同一工人操作不同机器的效率及不同工人操作同一机器的效率均有所差异，因此工序的实际加工时间将受工人操作效率的影响.

调度的目标是确定各项加工任务在机器中的最佳加工顺序和选择合适的机器及其对应的操作工人，使得资源配置最优化，同时使完工时间、生产总成本和总拖期3项性能指标相对最佳.本文需要同时优化的目标函数有:

1）生产成本函数

式中为Oij受工人操作效率的影响在M k中的实际完工时间，，tijk为Oij在M k中的理论完工时间，ek为工人操作M k的影响因子，Ck为M k的单位时间加工费用，W k为工人操作M k的单位时间加工费用，t p为工人P p的操作时间.

2）完工时间函数

3）总拖期函数

2 本文算法

2.1 算法流程

本文算法实现步骤如下：

1）随机初始化产生一个规模为x的种群R0，令规模为y的归档集Q0为空，用T表示预定的进化代数，同时初始化且令进化代数t＝0；

2）计算Rt和Q t中各个体的适应度；

3）选择Rt和Q t中的非支配个体保存至Qt＋1.若｜Qt＋1｜＞y，则通过修剪过程进行删减；若｜Qt＋1｜＜y，则再选择y－｜Qt＋1｜个适应度值小的支配个体保存至Qt＋1；

4）若t＞T，则结束进化，此时Qt＋1中所有非支配解即最终所求的最优解；否则，继续进行下一步；

5）采用锦标赛法对Qt＋1选择配对；

6）对配对染色体进行交叉、变异，从中选择优秀的个体进入下一代，令t＝t＋1，转至步骤2）.

2.2 编码

根据本文双资源多目标车间调度模型的特点，同时结合本文算例，设计了如图1所示的三维编码方式.每个完整的染色体均由如下三部分组成：

1）工序编码.同一个工件用相同的实数表示，工序的加工顺序即其对应的实数出现的顺序.如图1所示的工序编码中，第1次出现的“2”表示第2个工件的第1道工序，第2次出现的“2”表示第2个工件的第2道工序，第3次出现的“2”表示第2个工件的第3道工序，以此类推.

2）机器编码.采用实数编码方式.如图1中机器编码染色体的前三位数字分别表示O11由M7加工，O12由M6加工，O13由M7加工，以此类推.

3）工人编码.类似于机器编码方式.

图1 三维染色体编码Fig.1 Chromosome coding scheme

2.3 选择

在构造新的群体时，首先通过计算Rt和Q t中各个体的适应度进行环境选择，然后采用锦标赛法对Qt＋1配对进行繁殖选择.

2.4 交叉

1）工序交叉.将全部工件随机分成2个非空集合X1，X2，X1＝｛1，3，5｝，X2＝｛2，4｝，复制父代染色体U1中包含在X1的工件到子代染色体V1，复制父代染色体U2中包含在X2的工件到子代染色体V2，保留它们的位置；复制U2中包含在X2的工件到V1，复制U1中包含在X1的工件到V2，保留它们的顺序，如图2（a）所示.

2）机器交叉.首先随机产生a个交叉点（a为不大于染色体长度的实数），然后依次在父代染色体A1，A2中寻找并交换这些交叉点所对应的机器，其余机器则保留到子代产生两个子代染色体V1，V2，如图2（b）所示.由图2（b）可见，随机交叉点为3个，分别是位置2，5，8.

3）工人交叉.其方法类似于机器交叉操作.

图2 交叉操作Fig.2 Crossover operation

2.5 变异

1）工序变异.随机选择一个工序，再随机产生一个插入点，将该工序插入到产生的插入点位置，如图3（a）所示，即可由父代染色体P1变异为子代染色体C1.

2）机器变异.随机选择机器编码染色体中的一个基因，从可加工集｛1，3，5，6，7｝中任选一个替代之，如图3（b）所示.

3）工人变异.与机器变异操作方法类似.

图3 变异操作Fig.3 Mutation operation

3 仿真与分析

本文算法运用Java编程语言实现，程序运行环境为P4 CPU，主频为2.8 GHz，内存为1.25 GB.

某机械加工车间计划由8台机器（M1～M8）和6名工人来生产5种各自具有多道工序的工件（J1～J5）.各工件原材料成本分别为160，210，440，340，570元，每台机器的单位时间加工费用分别为8，5，10，9，7，6，9，4元·h－1，每个工人单位时间加工费用分别为20，15，15，20，15，20元·h－1.其余加工数据如表1～2所示.

表1 各机器对应的工人操作效率Tab.1 Worker efficiency of each machine

表2 柔性作业车间调度的加工时间Tab.2 Associated time of each job

程序运行结束后得到一组解，笔者根据个人偏好，在优先考虑交货期的前提下选取部分Pareto优化结果，并采用本文算法对考虑平均工人操作效率的双资源车间调度模型进行仿真，结果如表3所示.由表3可见，考虑差异性工人操作效率影响普遍比考虑平均工人操作效率下的结果更优.

限于篇幅，同样仅根据个人偏好选择表3中第4组结果给出对应的甘特图，如图4所示.图4（a）中“5－2－6－8”表示工件5的第2道工序由工人6在机器8中加工完成.由图4可知，考虑差异性工人操作效率的影响明显比考虑平均工人操作效率下的完工时间短，机器利用率更高，综合效益更大.

图4 甘特图Fig.4 Gantt

4 结语

本文在研究双资源车间调度问题的基础上，考虑差异性操作工人操作效率的影响，建立了一种新的双资源多目标车间调度模型.针对该模型的特点，提出一种改进的SPEAⅡ算法，设计了一种适合双资源要求的三维编码方式，并对染色体的交叉、变异等操作进行了改进，对过程中可能产生的非法染色体进行了相应的修复处理.仿真结果表明，合理的工人分配不仅能缩短生产周期，降低生产成本，还能提高企业的综合效益.

［1］何旭红，黄祥瑞.工业系统中人的可靠性分析：原理、方法与应用 ［M］.北京：清华大学出版社，2007：137.

［2］刘晓霞，谢里阳，崔敬巍.双资源生产车间调度问题的研究 ［J］.计算机工程与应用，2007，43（6）：10－13.

［3］ERTAY T，SATOGLU S I.System parameter selection with information axiom for the new product introduction to the hybrid manufacturing systems under dual－resource constraint［J］.Int J Prod Res，2012，50（7）：1825－1839.

［4］REN Huiyuan，JIANG Lili，XI Xiaoying，et al.Heuristic optimization for dual－resource constrained job shop scheduling［C］／／2009 International Asia Conference on Informatics in Control，Automation and Robotics.Bangkok，Thailand：Institute of Electrical and Electronics Engineers Computer Society，2009：485－488.

［5］KHER H V.Examination of flexibility acquisition policies in dual resource constrained job shops with simultaneous worker learning and forgetting effects［J］.J Oper Res Soc，2000，51（5）：592－601.

［6］SALUM L，ARAZ O U.Using the when／where rules in dual resource constrained systems for a hybrid pushpull control［J］.Int J Prod Res，2009，47（6）：1661－1677.

［7］BOKHORST J A C，SLOMP J，GAALMAN G J C.On the who－rule in dual resource constrained（DRC）manufacturing systems［J］.Int J Prod Res，2004，42（23）：5049－5074.

［8］BERND S R，JENS H，TORSTEN H.Analysis of priority rule－based scheduling in dual－resource－constrained shop－floor scenarios［C］／／International Conference on Advances in Machine Learning and Systems Engineering.Berkeley，United States：Springer Verlag，2010，68：269－281.

［9］ELMARAGHY H，PATEL V，ABDALLAH I B.Scheduling of manufacturing systems under dual－resource constraints using genetic algorithms［J］.J Manuf Syst，2000，19（3）：186－198.

［10］LIANG Di，LIU Si，TAO Ze.Based on Petri nets and hybrid genetic－Tabu search approach to scheduling optimization for dual－resource constrained job shop［C］／／Proceedings of the 2nd International Conference on Electronic and Mechanical Engineering and Information Technology.Shenyang，Liaoning，China：Atlantis Press，2012：1355－1359.

［11］AMIN－TAHMASBI H，TAVAKKOLI－MOGHADDAM R.Solving a bi－objective flowshop scheduling problem by a multi－objective immune system and comparing with SPEA2＋and SPGA ［J］.Adv Eng Softw，2011，42（10）：772－779.

Multi－objective dual－resource shop scheduling model based on SPEAⅡ

REN Xiaoqing，YIN Richao，YANG Yulu，BAO Zhenqiang＊，WANG Weizhong

（Sch of Inf Engin，Yangzhou Univ，Yangzhou 225127，China）

Multiple resource constraints exist in the actual job shop under the complex manufacturing environment，so a multi－objective dual resource shop scheduling model considering differences between operational efficiency is established.There are three objectives in the model：the shortest completion time，the lowest cost and the minimum total tardiness.In view of the limitation of traditional algorithms for single resource，an improved SPEAⅡis proposed for model in this paper.Finally，the feasibility and efficiency of the model are proved by the simulation experiment.

differences between operational efficiency；dual－resource；strength Pareto evolutionary algorithm；multi－objective；scheduling model

TP 18

A

1007-824X(2015)03-0051-05

2014-10-16.* 联系人，E-mail:yzbzq@163.com.

国家自然科学基金资助项目(61170201);江苏省研究生科研创新项目(CXZZ13-0919);江苏省大学生创新项目(201411117041Z).

任晓青，殷日超，杨雨露，等.基于SPEAⅡ的双资源多目标车间调度模型［J］.扬州大学学报(自然科学版)，2015，18(3):51-55.

（责任编辑 林 子）