ABSTRACT

Since the problem of that collaborative plan, manufacturing plan and the scheduling solutions are hard to be paralleled and synchronized, the multi-objective model of integrated collaborative plan and scheduling for dual-resource is established, taking the collaborative planning into consideration under the environment of supply chain. There are three objectives in the model: the shortest completion time, the lowest cost and the minimum total tardiness. Take machines and workers as two kinds of constrained resources. Then, the improved SPEA2 algorithm is designed. In this algorithm, the chromosome pair encoding which is suitable for dual-resource and collaborative decision is designed. It includes the process coding, the machine coding, the worker coding and the collaborative decision variable. Finally, the correctness of the model and the efficiency of the algorithm are proved by the simulation experiment.

Keywords:Collaborative Planning, Multi-Objective, Integrated Model, Dual-Resource Scheduling

双资源多目标集成协作计划与调度模型及其求解算法

胡倩倩，马陈程，孙越，包振强，阚云

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

收稿日期：2017年5月31日；录用日期：2017年6月18日；发布日期：2017年6月21日

摘 要

针对现有生产系统中协作计划、生产计划以及调度方案不能同步制定的问题，考虑在供应链环境下有协作的计划与调度，建立了以完工时间最短、加工成本最低以及总拖期最短为目标的包含机器设备和操作工人两种约束资源的双资源多目标集成协作计划与调度模型。设计了SPEA2算法，在其中设计了既适合双资源要求又能满足协作决策要求的包含工序编码、机器编码、工人编码以及协作决策变量的染色体对编码方式，并对染色体的交叉变异等操作进行了改进。最后，用仿真实验来验证本文模型的正确性及算法的有效性。

关键词 :协作计划，多目标，集成模型，双资源调度

Copyright © 2017 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

生产调度是企业生产中面向任务组织生产、适应内外环境变化以及对外协作的核心模块。目前大部分相关研究只考虑到了机器设备这一个约束，然而据统计各领域中有60%~90%可归于人误行为/行动 [1] ，然而目前一般的调度问题在建模时往往并不考虑操作这些机器设备的工人因素 [2] [3] [4] 。自从Nelson给出双资源的定义 [5] 后，目前，国内外已有关于双资源生产调度问题的研究，但比较少：J. Xu等 [6] 对双资源约束系统的发展状况进行了研究；方叶祥等 [7] 同时考虑机器设备和操作工人两种资源，对并行生产线调度问题进行了研究；鞠全勇等人 [8] 对具有多道工艺路线约束的双资源作业车间调度问题进行了研究，考虑到大量存在于实际作业车间调度过程中的不确定因素，建立了模糊调度的数学模型；John等 [9] 基于学习遗忘作用来对考虑任务类型因素的双资源车间调度模型进行求解；刘晓霞等人 [10] 提出了一种双资源作业车间调度的生产费用计算方法；Kher等人 [11] 基于学习和遗忘规则来求解双资源模型；文献 [12] [13] 采用when/where/who等工人转移规则来求解双资源模型；Bernd等人 [14] 基于优先级规则来求解双资源问题；随着智能算法的出现，不少学者开始用遗传算法 [15] 等智能优化算法来求解该问题。文献 [16] 运用自适应蚁群算法对双资源车间调度进行优化求解；袁亮等人 [17] 对多目标的双资源柔性车间调度问题进行了研究，并用改进的遗传算法来进行求解；EIMarghy [18] 采用三维的染色体编码方法对遗传算法进行改进以求解双资源制约车间调度问题，并对单资源车间调度和双资源车间调度中6种分派规则性能进行了对比分析；孙志峻 [19] 为了研究双资源调度问题，在为工件分配机器设备和操作工人时介绍了一种调度算法，该算法将分派规则、遗传算法以及规约法结合，从而满足了其特定的性能评价指标。此外，由于不同的工人与机器设备的比率不同，生产调度中所涉及到的加工性能也不同，已有文献对此进行了研究，并在对研究进行分析的基础上给出了最终结果。综上，已有的研究对多资源调度问题研究尚浅，对双资源调度问题的研究还有待进一步深入。

此外，生产调度的实施需要计划的指导，计划是调度的目标，调度约束了计划。在传统的企业生产中，总是先有计划再有调度，但资料显示，20%~30%的生产计划将由于计划与执行阶段之间的时间延迟而被修改 [20] ，从而使计划得不到理想的优化；传统计划的制定往往以静态的生产状态为基础，而不考虑实际调度过程中出现的变化，也未曾考虑自身加工能力不足时的协作问题，这将导致计划与调度的严重脱节。集成协作计划与调度 [21] [22] [23] [24] 能有效的解决该问题。目前过于理想化的单目标优化算法已无法解决调度本身具有的多目标性问题 [25] 。自Chryssolouris和Chan [26] 提出计划与调度的概念之后，不少学者对此展开了研究。Bao Zhenqiang [27] 等研究了基于Pareto的多目标集成协作计划与调度模型；Arsenyan Jbid [28] 在产品开发过程中提出了一种集成的模糊方法来通过信息技术进行计划；Zhou Hong [29] 采用混合协同进化算法来求解集成产品计划问题；Bechendorff [30] 为了提升生产系统的柔性引入了可选生产计划；Phanden Rakesh Kumar [31] 认为工艺规划与调度是生产中最重要的两块，将二者有效的集成对提高计算机集成制造的效益至关重要，为此提出了一种将工艺规划与调度进行集成的有效方法。

但是考虑双资源的多目标集成协作计划与调度的研究很少，因此，本文建立了一种以完工时间最短、加工成本最低以及总拖期最短为目标的包含机器设备和操作工人两种约束资源的双资源多目标集成协作计划与调度模型，并选择了SPEA2 [32] 算法对其进行求解。

2. 建立模型

2.1. 问题描述

本文所研究的双资源多目标集成协作计划与调度模型中，有n个工件需要在由w个工人、m台设备组成的生产单元内加工完成。每个工件包含一道或多道工序，各工序间存在先后约束，每个工序可在一台或多台设备上加工，且设备的单位时间加工费用已知，但不同设备性能不同，因此工序的实际加工时间随设备性能的不同而不同。有w个工人，每个工人可操作一台或多台设备，且w < m。同一工人操作不同设备的效率不同，不同工人操作同一设备的效率也有所差异。因此工序的实际加工时间也因工人操作效率的不同而产生影响。由于企业自身加工能力不足，有一部分工件需要外包完成，假设工件一旦外包则整体外包，且协作伙伴能在规定时间内完成相应的协作任务。

调度的目标是确定所需协作的任务和各加工任务在设备上最佳的加工顺序以及合适的设备和操作设备的工人，使得资源配置最优，同时使完工时间、生产成本和总拖期这三个性能指标相对最佳。

2.2. 目标函数

本模型需要同时进行优化的目标函数如下：

生产成本函数

完工时间函数

，其中

总拖期函数

其中各字母表示的含义如下：

表示工件；

表示工件的总工序数；

表示工件的第道工序；

表示自行加工的工件的数量；

表示外包给协作伙伴的工件的数量；

表示决策变量，；

表示工件的协作成本；

表示工序的完工时刻；

表示设备的工时费；

表示工人操作设备的工时费；

表示工序在设备上的理论加工时间；

表示工序受工人操作效率的影响在设备上的实际加工时间；

表示工人所操作设备的时间；

表示工人操作设备的影响因子；

表示工件的拖期。

3. 算法设计

由于同时考虑了协作和双资源，本文基于SPEA2算法设计了适合本文模型的染色体编码、选择、交叉、变异操作，使算法能合理的制定协作计划，同时能进行生产作业排程和工人分派，从而更好的求解该双资源多目标集成协作计划与调度模型。

3.1. 编码方式

根据双资源多目标集成协作计划与调度模型的特点，设计了如图1所示的编码方式。其中，一个完整的染色体对由工序编码、机器编码、工人编码以及协作决策变量编码四部分组成。

工序编码采用如下方式：同一个工件用相同的实数表示，工序的顺序即为其所对应的实数对应出现的顺序。如图1所示，第一次出现的1表示第一个工件的第一道工序，第二次出现的1表示第一个工件的第二道工序，第三次出现的1表示第一个工件的第三道工序，以此类推。

机器编码采用基于实数的编码方式。结合本文算例，染色体1-3位分别表示加工第一个工件的第一、第二、第三道工序的机器，以此类推。

工人编码方式与机器编码类似。

图1. 带协作的染色体编码

协作决策编码采用0,1编码方式，用0表示协作，用1表示自行加工。协作决策变量染色体的长度等于工件数，首先随机生成一个0、1序列，结合本章中5个工件的算例，生成了如下的一条染色体，第一位的1代表工件1自行加工，第二位的1代表工件2自行加工，第三位的0代表工件3外包生产，以此类推。

3.2. 选择操作

尽可能使用国际标准单位(公制)，如厘米、千克、秒，在特殊情况下可以使用英制单位，如“3.5英寸磁盘”。避免把公制与英制混合使用。

本文所设计的算法在构造新群体时，首先进行环境选择(Environmental Selection)，其时间复杂度为

，然后进行繁殖选择(Mating Selection)。整体的平均时间复杂度为，具体选择过程

如下：

在进行环境选择时，将适应度值的个体存放到归档集中，即：

为进化种群，为归档集的规模。若，则再选择个适应度值小的支配个体放至；若，则通过修剪过程进行删减：

一直到。

其中表示个体和中第个个体之间的距离。

按顺序删除距离最近的个体。如图2所示，该图是一个规模为的拥有两个目标和的的修剪示意图。图中共8个个体，为此需要进行修剪。经计算，显然1和1l之间距离最近，然而它们与各自相邻的个体之间的距离各不相同，1与1r之间的距离小于1l与2r之间的距离，所以删除个体1。同理，再依次删除多余的两个个体——个体2和个体3。

环境选择完之后，用锦标赛法对选择配对。

3.3. 交叉操作

工序交叉：采用基于工序编码的IPOX 交叉操作。如图3所示，把所有的工件随机分成两个非空集合J1和J2，复制P1包含在J1的工件到C1，P2包含在J2的工件到C2，保留它们的位置，复制P2包含在J2的工件到C1，P1包含在J1的工件到C2，保留它们的顺序。

机器交叉：首先随机产生a个交叉点(a为不大于染色体长度的实数)，依次在M1和M2中选出这a个交叉点所对应的机器，并交换，M1和M2中其他的机器保留到子代产生两个子代C1和C2。如图4所示，随机交叉点为3个，分别是2,5,8位置。

工人交叉：与机器的交叉方法类似。

协作决策变量染色体交叉操作：随机选取h个交叉位(h < n，n为工件数或协作染色体的长度)，将父代染色体中对应位置上的基因进行交换即可。如图5所示，X1，X2分别为两条父代协作决策变量染色体，选取的交叉位有两个，分别是第一位、第三位，分别交换X1和X2中第一、第三位上的基因，便得到两个新的子代染色体C1和C2。

图2. SPEA2归档集修剪

图3. 工序交叉操作

图4. 机器交叉操作

图5. 标协作决策变量染色体交叉操作

3.4. 变异操作

工序变异：采用随机插入变异方式。先随机选择一个工序，然后再随机产生一个插入点，将该工序插入到产生的插入点位置，如图6所示。

机器变异：随机选择机器编码染色体中的一个基因，从可加工集里面任选一个替代，如图7所示。

工人变异：跟机器的变异方法类似。

协作决策变量染色体变异操作：随机选定一个变异位，由于采用的是0、1编码，变异时，变异位上的0变异为1，1变异为0即可。如图8所示，所选取的变异位为第三位，变异位上原本是1 (自行加工)，经过变异后变为0 (协作生产)。

4. 仿真与分析

本文采用拥有8台机器，6名工人和5种工件的某机械加工厂的应用案例来验证本文所构建的双资源多目标集成协作计划与调度模型。算法以Java编程语言实现，程序运行环境为P4 CPU，主频2.8 GHz，内存1.25 G。该多目标进化算法的执行参数为：种群大小50，进化代数200，变异概率0.001，交叉概率0.6。

详细加工信息如下：表1给出了工件原材料成本；表2给出了各工件的详细加工参数；表3给出了机器所对应的工人集以及效率；表4给出了工人单位时间加工费用。

程序运行完成后得到一组解，在生成调度方案的同时给出了生产协作计划，现列出其中一部分解，如表5。由表中数据可知，将部分工件外包给协作伙伴可以有效的解决拖期问题。可见，本文既考虑差异性操作效率又考虑集成协作的模型更贴近生产实际。

为了更为直观，我们根据上述试验结果给出了相应的对照调度甘特图。其中，图10为仅考虑工人差异性操作效率的调度方案中的一个解，图9为双资源多目标集成协作计划与调度模型方案中的一个解，后者考虑了协作，而前者没有。

很明显，图10中工件1和工件5均未能在其规定的交货期内完成任务，而图9中考虑了协作，将由于自身加工能力不足而无法及时完成的任务3和5外包给协作伙伴，在成本等其他目标不超预算的前提下，不仅大大缩短了完工时间，还有效地解决了拖期的问题。

图6. 工序变异操作

图7. 机器变异操作

图8. 协作决策变量染色体变异操作

表1. 工件原材料成本

表2. 生产调度问题的详细加工参数表

表3. 机器对应的工人集以及影响因子

表4. 工人单位时间加工费用

表5. 考虑协作情况下的部分双资源优化调度Pareto解集

图9. 考虑协作的计划与调度甘特图

图10. 不考虑协作的计划与调度甘特图

5. 结束语

本文在研究存在差异性工人操作效率的双资源调度问题的基础上，考虑实际生产过程中经常出现的因企业自身加工能力不足而需要将部分任务外包的情况，建立了双资源多目标集成协作计划与调度模型。针对该模型的特点，对SPEA2算法进行了改进，在其中设计了一种既适合双资源要求又能满足协作决策要求的包含工序编码、机器编码、工人编码以及协作决策变量的染色体对编码方式，并对染色体的交叉变异等操作进行了改进。最后，用仿真实验来验证相应的模型，结果证明所建模型是正确的，所改进的算法也是有效的。

基金项目

江苏省大学生创新创业训练计划项目(201611117026Z)。

文章引用

胡倩倩,马陈程,孙越,包振强,阚云. 双资源多目标集成协作计划与调度模型及其求解算法
A Multi-Objective Integrated Model and Its Algorithm of Collaborative Planning and Scheduling for Dual-Resource[J]. 管理科学与工程, 2017, 06(02): 71-82. http://dx.doi.org/10.12677/MSE.2017.62009

参考文献 (References)