考虑产品型号的作业车间调度

郝慧敏， 孙国华 ， 王改丽

(1.新疆工程学院 经济管理学院， 新疆 乌鲁木齐 830000；2.山东财经大学 管理科学与工程学院， 山东 济南 250014)

制造企业的数字化转型升级是一个渐进式的发展演变过程，重点是把有限的资源集中于产品前端的生产和后端的服务中，实现产品从“规模定制”向高度“个性化定制”转变。面对消费者需求小规模、多样性的特点，制造企业从提高生产效率和客户满意度、降低生产成本等角度优化车间调度方案，提升综合竞争力就显得尤为重要，这也一直是制造领域和控制科学研究的热点。

关于车间调度问题，Johnson[1]在1954年首先提出，自此车间调度方向的研究逐渐增多。在求解车间调度问题算法方面，小规模调度案例可以采用分支定界法、数学规划法和枚举法等精确算法，但实际生产过程中算例规模的扩大导致可行解以指数形式增大，因此，越来越多的智能算法应运而生，例如，Zhao等[2]设计出并行顺序移动和可变异概率的改进遗传算法；Gong等[3]提出一种混合进化算法用于研究车间调度问题中工人灵活性和能耗对生产成本的影响；李宝帅等[4]将深度强化学习算法用于求解作业车间调度问题；林剑等[5]提出一种基于离散Jaya算法优化线缆的生产调度，并通过仿真验证算法的有效性，从而提高传统电缆行业的生产与管理效率；为优化动态单机调度问题，Jun等[6]设计出一种基于决策树的数据挖掘方法；于蒙等[7]考虑将遗传算法与粒子群算法结合用于求解车间调度问题。

在求解车间调度问题时考虑的因素及目标函数构建方面，任丽[8]通过总结线缆生产车间调度问题的特点，构建了考虑设备选择和工件顺序2个关键因素的数学模型，并采用遗传算法求解；Senyigit等[9]考虑了等待时间、生产周期和生产成本3种因素；SANCHEZ-HERREAR等[10]考虑了生产延迟的因素，设计相应的局部迭代和贪婪随机自适应算法；针对车间生产效率低的问题，赵泽钰等[11]找出影响生产的因子和生产过程中的瓶颈，为生产线分配设备提供依据；SOTSKOV等[12]构建最小化最大完工时间的目标函数，求解2台并行设备的调度方案；陈魁等[13]采用粒子群算法求解运输时间最少的作业车间调度问题；刘玉婷[14]考虑了低碳环保的目标，对绿色柔性作业车间调度问题展开了研究。

从以上文献可以看出，研究车间调度问题时对产品的型号问题关注较少，通常将产品的计划生产数量看作工件的数量，如果当所有型号产品的计划生产量都较大时，工件总数的成倍增长使得遗传算法的染色体长度成倍增加，那么控制算法的运行时间将成为制定调度方案的难点。其次，忽略了同一类型不同规格型号产品所用的加工设备存在的相似性和产品的生产量差异，不考虑将性能相似的设备合并后根据生产量进行分配，致使调度方案的设计不能随着产品生产量的变化而灵活改变。如果当不同型号产品生产量相差较大时，生产量较小的设备在完成加工任务后就处于闲置状态，导致车间中性能相似的设备利用率存在较大差别，延长了产品的完工时间。更为重要的一点，制定的调度方案未考虑企业在实际生产过程中的排班问题；因此在缩短产品完工时间的同时也需要减少企业生产线操作人员排班的个数，最终才能有效降低企业的生产费用。

课题组结合企业的实际生产情况，针对以往调度方案的设计是基于产品的数量而忽略了产品的型号，以及不能根据产品的生产量合理分配加工设备，以减少排班次数的2个问题，构建以产品型号为基础的多目标数学规划模型，合并性能相似的设备，并通过遗传算法求解出既考虑产品型号又考虑生产量差异这2个因素的整体调度方案，达到均衡设备利用率，缩短产品交付周期和降低企业生产费用的效果。

1 问题描述

某一类型的产品有m种规格型号，加工这些产品的设备有(x+y+…+z)台，每种规格型号的产品有u道相同的工序和不同的生产数量Q，每道工序可在一台或多台设备上进行加工，不同规格型号产品的相同工序在不同的设备上花费的加工时间不同，调度方案原理如图1所示。

图1 调度方案设计原理

图中，1-1表示可用于加工第1道工序的第1台设备，2-1表示可用于加工第2道工序的第1台设备；每道工序的并行可加工设备确定好后，为每台设备分配需要加工的产品型号，第2行第1个数字2表示为加工第1道工序的第1台设备分配规格型号为2的产品进行加工，以此类推，为每道工序的每台设备分配相应的产品进行加工。

2 模型建立

作业车间调度方案的设计为符合企业的发展目标，构建的数学模型包括2个目标函数：①单件产品的最大加工时间最少；②按计划数量生产加工完成所有产品的总时间最短。模型假设如下：

1) 每种类型产品之间没有依赖关系，相互独立存在；

2) 产品在加工过程中不考虑设备故障等突发情况，且产品在加工完某道工序转运至下一道工序加工期间花费的转运时间忽略不计；

3) 产品加工阶段每道工序之间的暂存区容量较大，且产品在加工过程中，配置的设备只有在这件产品对应的工序加工完成后才可以加工下一件产品或停止加工。

构建模型用到的参数变量如表1。

表1 模型参数含义及说明

①目标函数

(1)

(2)

式(1)为第1个目标函数，表示单件产品的最大加工时间最少；式(2)为第2个目标函数式，表示所有产品按计划生产数量加工完成花费的总时间最短。

②约束条件

(3)

(4)

(5)

(6)

(7)

(8)

sjkh≥0,cjkh≥0;j=1,2,3，L,m;h=1,2,L,u。

(9)

其中，式(3)表示一共需要加工的j种规格型号产品的数量等于计划生产总量；式(4)表示每种规格型号产品中每个产品的每道工序至少有1台设备加工；式(5)和(6)表示每种规格型号产品其中每个产品每道工序的加工顺序约束；式(7)和(8)表示同一设备同一时刻只能加工1个产品的1道工序；式(9)表示加工时间为正数。

3 算法设计

遗传算法是一种常用的人工智能算法，该算法具有较强的稳定性和搜索能力，在应用过程中都能取得较好的计算效果，课题组也采用这种算法求解。

虽然不同规格型号产品的计划生产数量比较多，但只要是同一种规格型号的产品，在产品的规格型号数量不发生变化的情况下，得到的最优解中规格型号相同的产品单件加工时间不会发生变化，即规格型号相同的产品相同工序选择的加工设备不会发生变化。只有当产品的规格型号数量发生变化时，例如某种型号的产品加工的数量已经达到计划数量后，其余产品的加工时间才有可能发生变化，因此，课题组在设计遗传算法时，将同种规格型号的产品看作一个整体，从而简化算法的编码方式。此外，单件产品最大加工时间最少并不一定保证总加工时间最短，而采用2层遗传算法可以更好地满足2个目标函数。

3.1 染色体编码

课题组采用实数的编码方式，染色体编码以工序数为基础，将需要经过的加工工序数和可以加工每道工序的所有设备并行排列，每个基因表示对应工序性能相似的设备选择加工的产品，当产品的型号数量和对应工序的可选加工设备数相同时，一台设备对应一种型号的产品；当产品的型号数大于对应工序可选加工设备数时，增加虚拟设备，虚拟设备的加工情况和现有设备相同，增加虚拟设备的数量等于未分配加工设备的产品型号数；当产品的型号数量小于对应工序的可选加工设备数时，未分配产品的加工设备可重复选择产品型号，相当于增加虚拟产品，虚拟产品的规格型号和现有的某产品相同，染色体编码如图2所示。

图2 染色体编码

染色体的长度取决于产品的型号数量和每道工序可以选择的加工设备数量，这里将染色体按照工序数分为3段：M1-1表示可以加工第1道工序的第1台设备，M2-1表示可以加工第2道工序的第1台设备，VM2-3表示第2道工序的第3台设备为虚拟设备，基因上不同的数字表示不同型号的产品。因为可以加工第1道工序的设备数量和产品的型号数量相等，所以每台设备刚好对应一种型号的产品；加工第2道工序的设备有2台，而产品有3种型号，因此增加1台虚拟设备，理解为前2台设备中的其中1台设备在加工完一定数量的产品A或者产品B后再加工产品C，2台设备中最短的加工时间默认为产品C的加工时间；加工第3道工序的设备比产品的型号数量多，多出的设备可重复选择加工的产品。

3.2 适应度函数

第1个目标函数是每种规格型号产品的单件最大加工时间最少，对应的适应度函数为：

F=1/f1。

第2个目标函数是所有产品按计划数量加工需要的总完工时间最短，同时，为避免第2个目标函数对应的解中出现每种规格型号产品的单件加工时间大于第1个目标函数求解的结果，因此加入1个无限大的正数L和变量d，公式如下：

F=1/(f2+d×L)。

变量d的取值可以为0或者1，L为1个足够大的正数，如果染色体表示的解中出现了单件加工时间大于第1个目标函数即第1层遗传算法已经求解的结果，则通过变量d和L排除该解成为最终最优解的可能。

3.3 选择操作

选择操作采用轮盘赌策略，个体被选中的概率与适应度值相联系，若染色体i的适应度为Fi，染色体总数为N，则该染色体被选择的概率Pi为：

3.4 交叉操作

交叉操作的目的主要是生成新的染色体，考虑到车间调度问题设备选择加工产品的特性，染色体分段交叉的操作步骤如下：

1) 将每条染色体根据加工的工序数分成3段，每段的交叉概率设置为相同的参数，首先随机生成几个[0，1]的实数，这几个数可相同也可以不同，当每段的交叉概率大于对应生成的随机数时，从父代群体中选择2条染色体。

2) 随机生成与工序数相同的3对整数，每对整数的范围与每段需要选择加工的产品规格型号数相同，本例中第1对整数范围在[1，3]，第2对整数范围在[4，6]，以此类推，第3对整数范围在[7，10]，生成的整数分别对应2条染色体中的基因位置。

3) 对调父代中对应区间的基因，如果生成的解不符合要求，则保留新生成的子代中位于交叉区间内的基因，将区间外的基因进行调整，依次生成符合要求的子代染色体，如图3所示。

图3 染色体交叉

按照这样的交叉策略可以防止父代染色体经过1次交叉发生改变的基因数过多，在实际问题中，企业作业车间的设备以及产品的规格型号数量肯定相对较大，构成的染色体也较长，如果2条染色体按照2点交叉，很有可能导致优秀的父代染色体在遗传的过程中变化较大，减慢遗传算法的收敛速度，根据工序数分段2点交叉较好地弥补了这一缺点。

3.5 变异操作

变异操作是通过改变染色体中的个别基因，产生新个体。课题组采用互换方式完成变异操作，即随机选择染色体的其中1段，以变异概率交换1段中2个不同位置的基因，确保染色体的多样性。

4 算例分析

4.1 算例背景

为验证模型和算法的有效性，引用一家从事汽车仪表制造行业的某企业实际数据，该企业作业车间有15条生产线，其中9条生产线各生产加工一种规格型号的组合仪表，将这9种型号的组合仪表分别用产品A，产品B，…，产品I表示，产品某天计划生产的数量如表2所示，此时产品的单件最大加工时间为308 s。虽然仪表的规格型号不同，但加工过程中包含相同的8道工序，且相同工序在加工过程中使用的设备没有实质性的区别，所以每道工序的加工设备有9台。该企业的生产线每天安排2个班次，每个班次的工作时间为7 h，要求根据目标函数寻找每种型号产品每道工序配置的加工设备。

表2 产品计划生产量

4.2 算例求解

首先，通过第1层遗传算法寻找9种不同型号的产品每道工序配置的加工设备；其次，在满足第1层遗传算法求解结果的情况下，通过第2层遗传算法寻找9种型号的产品按计划完成加工任务，花费总时间最少的调度方案；最后，考虑减少排班个数以降低企业的生产费用，从而获得整体最优的调度方案。

2层遗传算法的设计原理和参数相同，种群规模设为100，交叉概率Pc为0.9，变异概率Pm为0.05，并加入精英染色体保留策略，保证算法的收敛速度，种群的保留概率设置为0.9。实验环境为Windows10 系统，Intel(R)Core(TM)i5-7300HQ CPU@2.5 GHz，采用MATLAB 2019a软件求解该企业的车间调度问题，第1层遗传算法的求解结果是产品D用时270 s，说明9种产品的单件最大加工时间最少为270 s，迭代次数如图4所示。

图4 遗传算法迭代图

当算法迭代至178次时，加工时间趋于稳定，求解单件最大加工时间最少的调度方案结果如表3所示。

表3 单件最大加工时间最少的结果

第1层遗传算法无法保证除了其中单件加工时间最大的产品D，其余产品的单件加工时间也为最优，因此加入第2层遗传算法，该层算法需要在第1层算法求解结果的基础上进行设计，将已经求解出的产品D经过8道工序加工配置的设备固定，每道工序剩余的设备可以选择其它型号的产品加工，第2层算法的其余操作与第1层相似，求解的调度方案如表4所示。

表4 基于2层遗传算法求解的调度方案

表中每一行可以解释为每种型号产品的8道工序配置的加工设备，以及在这些设备上单件产品花费的加工时间和按照生产量每种型号产品的完工时间。以第1行为例，A1-M1-1表示产品A的第1道工序在编号为M1-1的设备上加工，然后依次在相应的设备上完成8道工序的生产加工，且加工1件产品A的时间为167 s，加工246件产品A需要11.4 h。

4.3 最终调度方案

在解决实际调度问题时，只考虑单件产品最大加工时间最少和总完工时间最短这2个因素是不够充分的，还需要考虑企业安排工人的班次。某企业1个班次的工作时间为7 h，不论工作时间是否达到7 h，均按照1个班次的费用计算工人工资，所以接下来设计的最终调度方案主要是减少班次，或者在班次数量已经不能减少的情况下，尽量减少并行班次的工作时间。例如当某一种型号的产品生产加工数量达到计划生产量时，加工该产品的设备继续用来加工其它还未加工完的产品，此举既减少排班数，又缩短了产品完工时间，确保产品最终可以按时交付。产品加工最终调度方案如图5所示。

图5 产品加工调度方案

改进后的调度方案将产品的单件最大加工时间从308 s降至270 s，并且每种规格型号的产品按计划数量生产加工需要的总时间从13.75 h降至13.40 h，提高了班次内设备的利用率。另外，此方案将初始方案安排的加班次数由4个减少至3个，从而降低了企业的生产费用。

5 结语

课题组研究了加工产品总数较多，且加工产品型号相似的作业车间调度问题，通过建立单件最大加工时间最少以及所有产品按计划数量加工需要的总完工时间最短的多目标数学规划模型，采用2层遗传算法求解，并根据调度问题中设备选择加工的产品型号和产品经过的加工工序这2大特点，设计算法的编码、分段多点交叉和变异操作，缩短染色体的基因个数，尽可能多的保留优秀染色体的基因，加快算法收敛速度；同时，为更加符合企业的实际生产情况，提出减少企业排班数量的调度方案，并结合案例，验证算法的有效性，最终达到了均衡性能相似设备的利用率以及缩短总完工时间，降低企业生产费用的目的。在后续研究过程中，拟考虑产品在加工完某道工序转运至下一道工序加工期间花费的转运时间和设备故障等突发事件对调度方案的影响，进一步提高研究的全面性。