Z企业配电箱作业车间调度问题优化研究

徐 璜

（安徽理工大学经济与管理学院，安徽 淮南 232000）

0 引言

1950年起，发达国家对生产效率提出了新需求，有学者开始研究作业车间调度问题（Job-Shop Scheduling Problem，JSP）。国际生产学会（CIRP）根据生产型国家对现代制造系统进行研究，总结了多达34种先进制造模式。这些模式为实现制造企业的现代化转型和发展带来了十分重要的理论价值和现实意义[1]。

20世纪末，我国制造业开始崛起，产业进入高速发展时期。制造业开始成为国民经济向好发展的重要力量[2]。随着制造业发展及物流运输系统的完善，国内制造业产业集聚程度不断提高[3]。随后，经济全球化，制造业竞争加大，给我国制造业带来冲击和挑战。这就要求企业降低生产制造成本、保证产品长期品质、适应市场和提供高附加服务，由此车间调度问题研究在国内进入新阶段。

该文基于JSP的优化策略帮助Z企业改进作业车间调度问题，提高产能，增强公司综合竞争力。

1 Z企业作业车间调度现状

Z企业是生产高低压成套配电设备的国企，近年来，随着公司产能扩张，作业车间沿用的传统管理模式难以满足需要。作业车间陆续出现产能积压、订单顺序紊乱以及加急货物难以优先生产等问题。其中，制定生产调度方案是影响优化加工时间、提高积压库存流转以及尽可能满足产品交货期的重要因素[4]。同时，Z企业管理层每过几年会有不同程度的人员流动，这种流动严重影响了生产管理工作效率，因此需要弱化岗位经验对岗位的影响。

为解决该问题，公司试行了ERP+MES计算机辅助软件，同时引入更多新的管理策略，虽然取得了一定成效，但是仍无法解决公司日益扩大规模对产能的要求、作业车间调度管理力度不足之间的矛盾和非长期从事该岗位的新管理人员带来的管理效率降低的问题。因此，研究基于人工智能算法的作业车间调度问题，为Z企业提供生产管理解决方案非常必要。

2 配电箱作业车间调度问题的数学模型

Z企业长期使用的作业车间调度数学模型可归于基于启发式算法的优先分派规则法（Priority Dispatch Rulers，PDR）。该模型在实际应用中常用的规则有RS、SPT、LPT、EDD和FCFS等。EDD是Z企业实际车间调度中拥有最高优先级的规则，即当出现加急订单时，作业车间管理者会安排无条件优先加工该加急订单；在无加急订单的情况下，作业车间管理者使用FCFS法则安排加工生产，即先到的订单先安排生产；同时，根据实际观察，在同等情况出现多个可选作业班组时一般会使用RS规则，即随机选择；作业班组/作业人员在面对多个订单时常常自发使用SPT法则，即最快能加工完成的优先加工，以在当前计件模式下谋求最高收益。

Z企业为解决作业车间调度问题引入ERP系统后，同时使用了ERP系统中的生产调度辅助工具，形成新的调度方法（以下简称ERP辅助法）。ERP辅助法融合了SPT法则、EDD法则、MOR法则和FCFS法则形成的新法则，可部分提高配电箱作业车间调度效率。

2.1 变量描述

n为工件总数，m为机器总数，Cj为每个工件的完工时间，Cmax为最大完工时间，Ojh为第j个工件的第h道工序，Mijh为第j个工件的第h道工序在机器“i”上加工，Pijh为第j个工件的第h道工序在机器“i”上加工的时间，Cjh为第j个工件的第h道工序完工时间。

2.2 配电箱作业车间调度问题的约束条件和数学描述

配电箱作业车间调度问题的约束条件和数学描述如公式（1）所示。

Cmax表述的是在作业车间内制造加工全部的工件所需要花费的最多时间，即所有工件工序数都为h，工件总数为j，所有配电箱的所有工序在机器上加工的时间都不为0，且每道工序都需要经过i台机器。

j台不同的配电箱在i台设备上加工，要满足工序的约束条件，即加工每个配电箱需要经过h道工序，因为工艺要求，所以配电箱有自己的工序先后顺序，每道工序可选用的加工机器不止1台，根据机器的不同工序所用时长也不同。工序的约束条件如下：1） 任一时刻，一道工序能且只能在唯一一台机器上加工，且工序加工作业不能中断。2） 任一时刻，1台机器上只能加工一道工序，不考虑工序间转运时间。3） 同一工件的工序先后顺序是固定的，而不同的工件间加工工序无先后顺序约束。4） 不考虑作业现场随机性因素。

配电箱作业车间调度问题调度目标是明确每台机器上工序加工顺序和工序对应的开工时间，使Cmax尽可能小。

3 基于遗传算法的作业车间调度优化

遗传算法属于启发式算法，最早是从生物遗传学和“物竞天择，适者生存”等生物学概念获得启发的，模型的解就是遗传算法中的“染色体”，通过遗传过程中自然选择、交叉以及基因变异等现象来提高个体存活率，经过一代代的传递，逐步发现最优的子代（解）的过程。1954年，学者Johnson针对2台机器有序加工的流水车间调度的问题进行了研究，随后各国的学者在对车间调度问题进行了后续的相关研究，也取得了比较显著的研究成果[5]。车间调度问题衍生出流水线车间调度问题、柔性作业车间调度问题等，但都是以经典作业车间调度问题（Job-Shop Scheduling Problem，JSP）为基础进行研究的。在经典作业车间调度问题中，每件工件的每道工序仅能在1台机器上加工，且仅能加工1次，同时加工时间t是一个固定值[6]。

当使用遗传算法求解时，从1组随机数中产生的初代种群开始进行演化。产生的每个个体（individual）都表示模型的1个解，称为染色体（chromosome）[7]。种群通过不断地演化和进化过程，每次都会产生新的一代（generation）。在模拟自然界对物种进行筛选的自然法则启发下，使用适应度函数（fitness function）或目标函数（objective function）对每个个体进行评价，适应度值高的个体生存下来的概率高，也就意味着问题的这个解被选中的概率高。演化产生出的下一代被称为子代（offspring）。上一代经过选择（selection）、交叉（crossover）以及变异（mutation）等操作产生子代。遗传算法共有5个基本要素，首先，是编码和解码。其次，是对种群初始化的方法。再次，是适应度函数的选择。从次，是选择、交叉和变异等遗传算子。最后，是种群的规模、交叉变异等算子的概率设置。

设定D为种群的规模，t为当前一代，D（t）和C（t）代表第t代的父代和子代，遗传算法的步骤如下。

步骤1：初始化产生初始种群D（t）t=0。

步骤2：评价种群D（t），计算每个个体的适应度值。

步骤3：判断是否满足终止条件，不满足就转步骤4，满足就直接输出结果。

步骤4 ：选择、交叉和变异3个遗传算子产生子代C（t）。

步骤5：D（t）=C（t）转步骤2t=t+1。

车间调度问题是通过优化在每个机器上工序加工顺序和对应工序开工时间，使Cmax尽可能取较小值。

3.1 约束条件

约束条件如公式（2）所示。

式中：i=1，2，3，…，m；j=1，2，3，…，n；h=1，2，3，…hj；Sjh为第j个工件的第h道工序加工开始的时间；Xijh为第j个工件的第h道工序在机器i上加工；Pijh为第j个工件的第h道工序在机器i上加工的时间；Cjh为第j个工件的第h道工序完工时间。

第j个工件的第h道工序完工时间Cjh如公式（3）所示。

Cjh≤S（h+1）（3）式中：S（h+1）为第j个工件的第h+1道工序开始时间（j=1，2，3，…，n；h=1，2，3，…，hj-1）。

第j个工件的第h道工序完工时间小于加工总时间，如公式（4）所示。

式中：j=1，2，3，…，n；Cmax为最大完工时间。

同一时间、同一道工序仅能在1台设备上加工，如公式（5）所示。

工件加工时间必须是正数，如公式（6）所示。

式中：h=1，2，3，…，hj；j=1，2，3，…，n。

3.2 染色体编码方式

染色体编码方法是遗传算法首先需要解决的问题。求解JSP问题的常见编码方式有MSOS编码、表格编码、A/B串编码、三元组编码和矩阵编码等。该文选用MSOS编码方式，如图1所示。

图1 基于MSOS的染色体编码

其中，Qab为工件a的第b道工序，a={1，4}，b={1，3}；Mx为工序可选设备中的第x台，x={1，6}；Jx为第x件工件，x={1，2}。

按机器选择的机器编码：每个工件的每道工序按顺序排列，例如第一个工件的第一道工序为O11，第j个工件的h道工序为Ojh。

按这个顺序排列：O11，O12，O21，O22，O23……。每个框代表每个工序所选择的机器，例如第一个框代表O11选择的机器。框里的数字则代表该道工序能够选择的机器里的第几个机器。例如O11能够加工的机器为M1、M2、M3、M4、M5和M6，4代表为这6台机器里的第四台机器，为M4。O21工序能够加工的机器为M2和M4，1则代表这2台机器里的第二台机器，为M2。以此生成MS这边的染色体。

按工序排列的机器编码：数字出现的顺序就是工件的顺序，数字几就是第几道工序。第一次出现数字“1”代表第一个工件的第一道工序，第二次出现数字“1”代表第一个工件的第二道工序，数字“2”第3次出现为第二个工件的第三道工序。

3.3 遗传算子

3.3.1 选择

选择算子的第一步是先确定1个数组，数组的位数就是机器的总数量，数组的顺序和机器顺序对应，数组上每个数字代表对应机器上的加工时长的数值。详细步骤如下。步骤1：确定1个整型数组，数组的长度就是机器总数m，依次为机器编号顺序，数组对应机器[M1，M2，…，Mm]上的总负荷。然后初始化数组，数组中每个元素的值初始化为0。再任选择一台工件的第一道工序，开始。

步骤2：在当前工序的可选加工机器集中，选择加工机器所需要的加工时间和数组中相应机器位置的时间数值相加，但是不更新数组。

步骤3：在相加后的时间中，选取对应数值最小的机器为当前工序的加工机器，将选中机器在可选机器集中的顺序号设置为按工序排列的机器染色体编码部分对应基因上的数。

步骤4：将当前被选择的加工机器的加工时间加到数组中相应位置机器的加工负荷中，同时更新数组作为下一次选择的依据。

步骤5：继续选择该工件的下一工序，不断重复步骤2~步骤4，直到该工件的所有工序的加工机器被选择完，然后停止循环。

步骤6：从工件集中除去已被选择的工件，从剩下的工件集中随机选择1个工件，同时选择当前工件的第一道工序，不断重复步骤2~步骤5，直到工件集中的所有工件都被选择。

3.3.2 交叉

交叉是遗传算法的核心操作，它可以决定遗传算法的全局搜索能力。在作业车间调度问题中设计交叉算子中需要留意是子代对父代优良特征的继承性。同时，使子代具有可行性。常用的交叉算子有JOX、SXX、SPX和PPX等，但是基于工序编码的交叉算子POX（precedence operation crossover）可以保证所有工件在父代和子代中出现的次数相同，并保持任意工件工序之间的顺序约束关系[8]，既具有优秀的继承父代优良特征的特性，同时其子代均为可行解，因此该文选用POX交叉算子，如图2所示。

假设父代m×n染色体父代1和父代2，POX产生子代1和子代2，POX交叉的具体流程如下：1） 把工件集{1，2，3，…，n}划分为2个非空子集J1{2，3}和J2{1，4}。2） 复制父代1包括在J1{2，3}的工件到子代1，父代1包括在J2{1，4}的工件到子代2，保留它们的位置。3） 复制父代2包括在J2{1，4}的工件到子代1，父代2包括在J1{2，3}的工件到子代2，保留它们的顺序。

其中，POX为基于工序编码的交叉算子；J1为工件1；J2为工件2，父代和子代染色体由工件集{1，2，3，4，5，6}组成。

图2展示4×6调度问题的2个父代交叉过程。2个父代1、父代2交叉生成子代1染色体基因为[3124231422]，子代2染色体基因为[4132621426]。经此得出优先操作算子，保留了工件J1和工件J2在机器上的位置，子代继承父代每台机器上工件次序。

图2 基于工序编码的交叉算子POX

3.3.3 变异

在遗传算法中，变异算子可以保持群体的多样性。这里的变异操作，是针对单个染色体的不同基因序号进行交换。变异可以使算法跳出局部最优解，不同变异方式对算法能否求得全局最优解有很大的影响。使用位置变异法作为变异算子，即从染色体中随机产生2个位置并交换这2个位置的值。

4 示例仿真

以4个工件、6台机器为例，各工件每道工序可选机器对应的生产时间见表1。该实例从J1到J4共有4个工件，其中J1、J2各有2道工序，J3、J4各有3道工序，h为具体工序，表中数值表示各工序在机器M1到M6上的加工时间。

表1 4×6实例表

甘特图是通过条状图来显示项目进度和其他时间相关信息的常用项目管理图表，以上案例仿真结果均使用甘特图来直观展现作业车间调度问题的优化结果，如图3所示。

图3 仿真甘特图

其中，J1为最早下单工件，J4为最晚下单工件，J2为加急订单，工件转运时间远小于各工序加工时间，忽略不计。

4.1 原有经验管理模式仿真

原有经验管理模式情况下如公式（7）所示。

根据EDD规则，优先生产J2；其余工件根据FCFS法则，按照J1、J3和J4的顺序加工。工件加工顺序为J2、J1、J3和J4，班组选择顺序为M5、M1、M3和M4。

有经验的管理者可以根据经验很快安排出加工时间5 4 15 17，制造跨度（makespan）=17；无相关经验的管理者依照PDR规则排出加工时间为5 4 16 19，makespan=19。

该案例为4工件、6机器调度案例，机器数小于工件数，即同一时刻可由多个空闲设备可供选择。而在实际生产中工件数往往远大于机器数，其调度负责程度更高，基于PDR规则的调度策略的精确度将会进一步下降，同时不同管理者使用PDR规则得出的不同makespan也暴露PDR策略调度方案中对人的依赖较大，在复杂调度方案中往往只能依靠有丰富经验的管理者才能得出较优方案。在实际生产中，使用该策略显然不利于公司产能扩大。

4.2 使用计算机辅助管理模式仿真

建立优先级。

将以上优先级信息预先置于Z企业ERP生产管理工具箱中。

ERP中生产辅助工具需要先输入各工件对应的设备优先级，在设备空闲情况下按照设备优先级从高到低顺序排列，遇到相同优先级时按照设备序号排列。由于辅助功能的局限性，因此一般安排同一工件仅由同一台设备完成。使用该方案仿真结果如图4所示，每台设备的所有工序均在同一台机器加工，makespan=16。

图4 使用计算机辅助管理模式的仿真甘特图

使用ERP中生产辅助工具进行生产调度在一定程度上规避了传统方案中对有经验管理者的过度依赖，在工件数不多的情况下可以更快捷地指定较为合适的调度方案。但是该方案的弊端依然明显，在遇到工件数多的情况下，调度方案就会出现异常，makespan甚至可能高于传统方案，此时依然需要有经验管理者的介入。

4.3 GA-JSP方案管理模式仿真

设置子代数量为200，在第0代时就可得到最优结果，makespan=15。

利用遗传算法后优化出的结果如图5所示，在图5（b）中可以看出最优解很快收敛得出最终makespan=15，优化结果略优于有丰富经验的管理者制定的传统方案和ERP辅助决策后的方案，远优于无经验管理者制定的传统调度方案。同时，该仿真仅用在4×6调度问题中，在调度方案更复杂的情况下，遗传算法解决这类问题的优势将更明显。

图5 GA-JSP的仿真甘特图

5 结语

针对Z企业配电箱作业调度采用的管理调度模式进行优化，通过引入遗传算法的JSP模型，解决了原有调度模式下，面对较大订单量时传统调度模式效率过低的问题，优化了拥有不同经验水平管理者对调度效率的影响，提高了调度策略在复杂环境下的适应性。在Z企业后续面临生产调度难题时提供了更高效的解决方案，同时针对这类管理者对作业车间调度产生较大影响的问题提供了新的解决思路。