基于改进遗传进化算法的复杂作业流程调度

张春燕

（无锡科技职业学院，江苏 无锡 214028）

基于改进遗传进化算法的复杂作业流程调度

张春燕

（无锡科技职业学院，江苏 无锡 214028）

为了提高车间或者工业生产速度和质量，需要对生产中复杂作业流程调度进行研究。当前算法利用调度静态求解法和动态优化法实现复杂作业流程的调度。该算法没有相关策略的制定，也没有高效的理论作为支撑，导致该算法存在调度效率低，资源的利用率和环境适应能力较差等问题。为此，提出基于改进遗传进化算法的复杂作业流程调度。该算法先对复杂作业流程调度问题进行描述，针对调度问题描述，利用改进遗传进化算法对车间作业调度问题进行解决，将问题描述中的数学规划模型建立在规定的定义上。然后构建合适的编码实现改进遗传进化算法正常运行，过程中按一定要求对JSSP染色体进行编码，选择初始种群，并对适应度函数进行计算，引入交叉算子和变异算子扩大寻优范围。最后利用无延迟作业计划解决死锁状况，并通过调度过程流程图和作业调度整体结构流程图实现调度。实验结果表明，本文所提算法充分利用了现有资源实现了复杂作业流程的高效调度，同时也具有比较好的适应能力和灵活性。

遗传进化算法；复杂作业流程；调度

0 引言

车间复杂作业流程的调度，是完成车间资源优化配置比较有效的手段[1]。制造业作为国家实体经济重要的组成部分，当前面临着市场的残酷竞争，制造型企业发展中出现了严峻考验，比如资源濒临枯竭、劳动力成本的不断增加、客户对产品质量的要求陆续提升等[2]。如何考虑产品质量、服务、时间以及成本等因素，提高品牌声誉，得到客户的青睐，成为了制造型企业着重考虑的方面[3]。近些年来，中国的制造业平均水平有了很大的提高，不过在生产的效率以及生产现代化的水平上，与发达国家相比还有一定差距。由于复杂作业的调度是提升产品加工效率和实现制造型企业现代化发展的前提与基础，怎样实现实用又高效的复杂作业调度，成为了先进生产模式的首要问题之一[4]。车间作业的流程调度是目前调度领域中最繁琐和最困难的问题之一，所以采用当前的复杂作业流程调度算法，无法实现物料、机器和时间等相关资源的正确调度[5]。为了解决上述问题，本文提出了一种基于改进遗传进化算法的复杂作业流程调度，可完善当前复杂作业流程的正确调度，提高了调度的速度，提升了产品生产效率[6]。生产车间的复杂作业流程调度在一定程度上决定了制造型企业的生存，这样的重要性引起了人们的讨论，和有关专家学者的广泛关注与研究，以下介绍了几种比较优秀的调度算法[7]。

文献[8]算法中提出了工作流程调度的效率，是评价工作整体表现重要指标之一。工作流程调度问题是 NP-hard问题，异构式计算环境将该问题变得更为棘手，分层基因算法把启发式算法和GA算法结合，根据GA算法优化通过正向分层后的作业调度队列，很显著地减少了作业流程运行时间，该算法利用作业分层的优先级生成作业队列，将队列内的同层作业在整体上当作一位基因进行处理，可有效规划作业流程，但是耗时较长。文献[9]算法提出调度规则是实际生产中车间作业调度有关问题重要解决方式，不过它通常只在指定调度条件下性能较好，条件发生变化时，需要实时进行选择和评价。实现调度规则实时选择与评价方法的综述，用来研究实际生产中车间实时调度问题。概述了调度规则发展、特点以及分类，对调度规则选择与评价方法做出总结，全面介绍调度规则选择方法，其中包含使用比较多的人工智能方法，给出了实验方法，实验证明该法对调度的选择和评估进行了深度研究，但是存在实际应用效果较差的问题。文献[10]算法中，在传统的优先级调度算法基础上，提出利用动态优先级驱动调度算法。该算法把复杂作业流程区分为四个等级，依次分配至已经设置好的等待队列中，等待队列内设置了不同优先级阈值，对优先级进行动态调整，达到阈值之后提升至就绪队列中，并通过实验证明该算法缩短了高优先级的作业流程响应时间，但是调度正确性较差。

针对上述产生的问题，提出一种基于改进遗传进化算法的复杂作业流程调度，并利用实验证明，该算法可对复杂作业流程进行高速稳定地调度。

1 复杂作业流程调度问题描述

假设大规模复杂作业车间内有n个工件，要在m台设备上进行加工，工件i内包含道工序，i = 1… n 。各个工序间有工艺先后顺序的约束，每台设备j最多进行一次加工，j=1…m，代表工件i于 j上的加工工序，,ijp 代表工序,ijO 加工时间，,ikt 代表工序,ijO 开工时间，其中调度任务为：在m台设备上对n个工件进行加工，对各个设备上的各工序加工顺序和相关开工时间进行确定，用来对各个工件拖期时间进行最小化操作，并满足以下约束条件：

全部工件工艺路线以及工序加工的时间保持不变，其中工序一旦开始，加工就不允许中断，在同一时间各设备最多可加工一个工件，在同一时间各工件最多可在一台设备进行加工。根据上述参数和描述，得到复杂作业调度问题所对应的数学规划模型，也就是目标函数：

式（1）是复杂作业流程调度问题目标，也就是最小化的拖期时间之和。式（2）代表相同工件在不同工序间加工顺序的约束，各工件在任意时间仅可在一台设备上加工。式（3）与式（4）为相同设备上的不同工件间加工的顺序约束，进而保障各设备在任意时刻最多加工一个工件。式（5）保障各个工件须到车间之后才能开工。复杂作业流程调度问题大概为上述内容，下面利用改进遗传进化算法解决复杂作业流程调度问题。

2 基于改进遗传进化算法的复杂作业流程调度

2.1 关于作业调度的定义

针对调度问题描述，利用改进遗传进化算法对车间作业调度问题（JSSP）进行解决。车间作业调度的基本约束条件为进行调度理论分析主要约束条件，可否解决JSSP基本的约束条件，满足作业调度问题是作业调度问题研究的关键。为了更好地解决调度问题，将上述的数学规划模型建立在以下定义上。

定义一：假设P表示n个工件集合，那么P能够表达为式（6）：

定义二：假设M表示m台设备的集合，那么M可表达为式（7）：

定义三：假设iP的工序数量为ik，iJP表示iP工件工序集合，那么iJP可表达为式（8）：

定义四：假设 Pi中的工序到 Ji中的元素，在设备M中的加工次序是记为i（1）,i（2）,… i（ k），其中，那么设备加工的次序Q可表达为下式：

定义五：假设iM上加工工序的排列为iJM，其中0im＜＜，那么iJM可表达为式（10）：

式中，il代表在设备iM上的加工工序总数，代表设备M第i个加工零件工序的代号。

式中，iJM 表示第i台设备上加工工序的排列阵。

定义七：有了设备加工的次序阵Q以及设备加工的工序排列阵JM，则可描述一个加工，不过缺少一个描述加工的时间矩阵，由此将加工时间矩阵定义为：

上述矩阵中每个元素均和矩阵JM内的元素对应。根据上述七个定义，和1中的数学规划模型以及基本约束条件，对车间作业调度遗传编码进行研究。

2.2 改进遗传进化算法编码

依据作业调度的定义，对改进遗传进化算法编码进行分析，构建合适的编码是实现改进遗传进化算法正常运行的重要前提，根据JSSP数学规划模型可知，JSSP的解可表示为所有设备的工序排列矩阵JM，因此JSSP染色体的编码可否表达JSSP的一个有效解，其关键就在于可否直接或者间接表示为设备工序的排列矩阵JSSP。综上，JSSP染色体的编码需做到以下几点：

1. JSSP的染色体编码应是有序编码串。只有有序，才能将JSSP染色体的编码，唯一地映象成一个设备工序排列矩阵JM；

2. JSSP染色体的编码串应包括零件加工时的所有特征，也就是哪一个工件第几个工序，在哪一台设备上加工。只有这样JSSP染色体的编码串才可以唯一地映象成一个设备工序的排列矩阵JM；

3. JSSP染色体的编码应尽可能地精简，只有精简才有利于改进遗传进化算法操作的效率。

根据上述 JSSP染色体的编码需做到的 3点要求，给出了JSSP染色体编码的方式。就是单一编码方式，将所有工件工序进行统一的编号，则文中的调度问题利用如下方式进行表示：

在研究JSSP染色体之后，接下来开始选取初始的种群，随机生成A个位数，成为nk的染色体串初始的种群，每个染色体串利用以上方式表示，尽量保持各个基因间相互独立。

为了使改进遗传进化算法对适应度比较高的个体，有更多生存机会，利用对目标函数标度，获得适应度函数其中α和β为常数。

由于遗传进化一般为双亲繁殖，所以利用这一特点，引入交叉算子，各代的各个体按照一定交叉概率，交换部分基因，生产新基因组合，用来使各解可以有机会对其优秀基因进行交流，能够得到比父代更佳的解结构，也就是最优解。

为了使改进遗传进化算法，并很好地应用于作业流程调度中，在交叉算子的基础上引入了变异算子。变异算子对各个体每一位按照一定概率生成新的变化，生成新的基因型，可以进一步扩大寻优范围，进而利于保障算法全局的最优性。

2.3 复杂作业流程调度的实现

以2.1和2.2中内容为基础，在实现调度之前，先对死锁的概念进行介绍。死锁是在安排某工序加工时，这个工序前一道工序还没有被安排进行加工，进而造成调度没办法继续进行的情况。死锁的问题得以解决，则复杂作业流程的调度问题可以获得最大优化。

图1 调度过程流程图Fig.1 Flow chart of scheduling process

图2 作业调度整体结构流程图Fig.2 The whole structure flow chart of job scheduling

由此采用无延迟作业计划解决死锁情况，使每代的个体代表的解均是近优解，进而加快迭代的过程收敛速度。这里只简单介绍死锁的解决方法，并不作详细的探讨。得到死锁的解决办法后，利用调度过程流程图和作业调度整体结构流程图完成对调度的研究。

以上就是基于改进遗传进化算法的复杂作业流程调度全解[11][12]，根据流程图实现调度的准确高效操作。

3 实验结果与分析

为了证明基于改进遗传进化算法的复杂作业流程调度的有效性，需要进行一次相关的实验与分析。在MATLAB R2015b环境下搭建复杂作业流程调度实验平台，实验数据取自于JSP。

随机生成10个大规模JSP算例，其中工件数集合是[100 150 200]，设备数量集合是[20 30 50]，各个工件操作过程中有5个工序，各个工序加工的时间服从[1 100]均匀分布。随机在设备集合中选取设备进行加工，各工序在加工设备上只加工一次。

选取100个工件，和20台设备，利用不同的调度算法，测试不同算法的调度性能。表1为不同算法下100*20算例调度结果。

分析表1可知，本文算法的拖期时间和运行时间均少于文献所提算法。文献[8]算法的拖期时间最长，该算法利用作业分层的优先级生成作业队列，将队列内的同层作业在整体上当作一位基因进行处理，在流程规划的同时没有指定最小拖期指标，导致拖期时间长。文献[9]算法调度运行的时间最长，该算法概述了调度规则发展、特点以及分类，对调度规则选择与评价方法做出总结，全面介绍调度规则选择方法，没有明确的约束条件，因此调度的运行时间相比其它调度算法较长。本文算法对调度的基本约束条件和最小拖期函数进行了研究和分析，建立了数学规划模型，减少了调度运行时间，同时也减少了拖期时间。上述实验证明了本文所提算法具有一定的可行性。图3为不同算法加工时间（s）对比。

表1 不同算法调度性能对比（100*20）Table 1 Comparison of scheduling performance of different algorithms (100*20)

图3 不同算法加工时间对比Fig.3 Comparison of processing time of different algorithms

由图3可知，本文调度算法加工时间，明显少于文献算法加工时间。因为在利用本文算法实现调度过程中，构建了合适的编码，并对JSSP染色体的编码提出了要求，利用双亲繁殖的特点引入交叉算子，在交叉算子基础上，加入变异算子，优化了本文算法调度精度，由于调度精度的增加，提高了设备加工的速度，减少了加工时间。下面是调度规模分别为100*50，150*30，150*20时，不同算法调度的负载均衡度[13]（%）对比。

通过对不同算法在不同规模下的负载均衡度对比结果可知[14]，负载均衡度越高代表调度的稳定性越好，而表中本文算法的负载均衡度相比文献算法的负载均衡度较高。进一步说明了本文算法具有高度可实践性和可扩展性。

表2 不同算法调度的负载均衡度对比（100*50）Table 2 Comparison of load balancing of different algorithms scheduling (100*50)

表3 不同算法调度的负载均衡度对比（150*30）Table 3 Comparison of load balancing of different algorithms scheduling (150*30)

表4 不同算法调度的负载均衡度对比（150*20）Table 4 Comparison of load balancing of different algorithms scheduling (150*20)

4 结束语

文中的交叉算子和变异算子使调度程序可视化程度受到了影响，因此需要与生产企业的调度部门所制定的生产流程调度计划进行连接，从而可以直接应用到生产中。

采用当前算法对复杂作业流程进行调度时，无法对作业流程进行稳定，高效地调度。而基于改进遗传进化算法的复杂作业流程调度可以实现作业流程的可靠调度，并利用实验证明，本文所提算法具有实际意义。

[1] 郭晴, 杨海霞, 刘永泰. 云计算环境下的复杂数据库并行调度模型仿真[J]. 计算机仿真, 2015, 32(6): 360-363.

[2] 翟颖妮, 王军强, 褚崴, 等. 基于TOC理论的大规模作业车间调度问题研究[J]. 机械科学与技术, 2015, 34(8):1222-1228.

[3] 闫俊刚, 邢立宁, 张忠山, 等. 具有双重时间窗约束的作业车间调度算法[J]. 科学技术与工程, 2016, 16(26): 85-92.

[4] 刘迷, LiuMi. 云计算下虚拟信息资源大数据特征集成调度[J]. 科技通报, 2015, 31(10): 199-201.

[5] 孙琼琼, 蔡琪. 文化框架下多群智能优化算法的云作业调度[J]. 计算机测量与控制, 2015, 23(1): 273-276.

[6] 刘海客, 李集林, 张华健. 一种改进的M-LWDF动态业务调度方法[J]. 电子设计工程, 2016, 24(22): 26-29.

[7] 李斌. 面向计算思维的集装箱码头装卸作业调度[J]. 交通运输系统工程与信息, 2016, 16(3): 161-167.

[8] 谢涛, 董滔. 基于混合GA算法的工作流作业调度队列优化[J]. 计算机工程与应用, 2016, 52(24): 85-90.

[9] 范华丽, 熊禾根, 蒋国璋,等. 动态车间作业调度问题中调度规则算法研究综述[J]. 计算机应用研究, 2016, 33(3):648-653.

[10] 李薛剑, 李凯. 一种基于动态优先级的RQ作业调度算法[J]. 小型微型计算机系统, 2017, 38(1): 124-128.

[11] 吴琼, 纪志成, 吴定会. 协同混合粒子群算法求解车间作业调度问题[J]. 计算机工程与应用, 2016, 52(5): 266-270.

[12] 马莉, 唐善成, 王静, 赵安新. 云计算环境下的动态反馈作业调度算法[J]. 西安交通大学学报, 2014, 48(7): 77-82.

[13] 王鹏, 黄焱, 李坤, 郭又铭. 云计算集群相空间负载均衡度优先调度算法研究[J]. 计算机研究与发展, 2014, 51(5):1095-1107.

[14] 翟颖妮, 王军强, 褚崴, 刘昌军. 基于TOC理论的大规模作业车间调度问题研究[J]. 机械科学与技术, 2015, 34(8):1222-1228.

Complex Job Scheduling Based on Improved Genetic Evolution Algorithm

ZHANG Chun-yan
(Wuxi Professional College of Science and Technology, Wuxi 214028)

In order to improve the production speed and quality of the workshop or industry, it is necessary to study the complicated operation process in production. The current algorithm USES the scheduling static solution method and the dynamic optimization method to implement the scheduling of complex job processes. The algorithm is not related to strategy formulation and no effective theory as the support, leading to low efficiency of the algorithm exists scheduling, resource utilization and environmental adaptation ability is poor. In this paper, the complex operation process scheduling based on improving genetic evolutionary algorithm is proposed. The algorithm for complex process scheduling problem is described first, in view of the scheduling problem description, using the improved genetic algorithm for solving job shop scheduling problem, described the problem of mathematical programming model based on the definition of the rules. And then build a suitable encoding to achieve improved genetic evolutionary algorithm run normally, process according to certain requirements for JSSP chromosome coding,choose the initial population, and the fitness function calculation, the introduction of crossover operator and mutation operator for expanding the scope of the optimization. Finally, the problem of deadlock condition was solved by using the non-delayed operation plan, and the scheduling of the whole structure flowchart was implemented by scheduling process flowchart and operation scheduling. The experimental results show that the proposed algorithm made full use of existing resources to achieve the efficient scheduling of complex process, at the same time also has a good adaptability and flexibility.

Genetic evolutionary algorithm; Complex operation process; Scheduling

国家自然科学基金(61300149)，江苏高校品牌专业建设工程资助项目(Top-notch Academic Programs Project of Jiangsu Higher Education Institutions，TAPP)，江苏省教育厅高校哲学社会科学研究指导项目(2016SJD880064)

张春燕(1982-)，女，江苏南通人，讲师，硕士，主要研究方向为人工智能算法与模式识别，计算机控制系统等方面。

TP18

A

10.3969/j.issn.1003-6970.2017.12.019

本文著录格式：张春燕. 基于改进遗传进化算法的复杂作业流程调度[J]. 软件，2017，38（12）：98-103