基于紧急订单的并行流水线动态调度研究

朱华炳，涂学明，王 龙

（1.合肥工业大学 机械与汽车工程学院，合肥 230009；2.天纳克汽车工业（苏州）有限公司，苏州 215000）

0 引言

生产调度问题就是调动各种可用资源在规定的时间内完成生产任务，同时给出该加工任务中各种加工工序的加工次序以及时间参数[1]。多年来，研究者们对并行流水车间调度问题（Parallel Flow Shop Scheduling Problem，PFSP）的研究多以最大完工时间为目标[2～6]，较少考虑工件交货期的影响。当考虑交货期时，一般又都假设交货期为固定值[7～9]，而没有把交货期考虑为模糊变量，事实上，在生产调度实践中，由于一些调度信息的不确定性，工件的完工时间与交货期存在一些偏离是能够接受的。

在实际生产过程中，流水车间生产具有动态性、随机性等特点。它常常要面临随机动态事件的干扰，如原材料延迟到达、急件插入、交货期变更、机器故障、零件报废等[10]，这使得通常要根据事件的扰动及时调整调度方案。于是学者们提出了动态调度问题，它比静态调度问题更符合实际生产的需要，同时由于随机事件的影响，动态调度具有更大的计算复杂性，它是比静态调度更为复杂的NP-hard难题。

针对动态调度问题的复杂性，本文提出了一种基于改进遗传算法与仿真分析相结合的混合智能方法，考虑订单的模糊交货期，以完工时间和交货惩罚为优化目标，建立动态仿真模型，并进行优化，然后在分析紧急订单这一扰动因素基础上，实现并行流水线的动态调度。

1 多目标模糊并行流水线动态调度问题

1.1 多目标模糊并行流水线调度数学模型

假设αjk,βjk分别为工件i的提前完工和拖期的单位时间惩罚系数，交货期窗口为[ej,k,dj,k]；对于任意机器Mj，指派到该机器的工件集为Jj，则满足Jj⊆ J 。

i：工件代号；

k：位置代号；

j：流水线代号。

Kj：工件集Jj中包含的工件数目。

Jj,k：工件集Jj中的工件序列之一，即Jj,k∈Jj其

Pi,j：工件i在流水线j上的加工时间,i=1,2,··· ,n;j=1,2,···,m。

Bj,k：工件集Ji中，排在第k个位置上的工件在第j条流水线上的工件，即Jj,k的开始加工时刻。

Cj,k：工件Jj,k的完工时刻。

Ej,k：工件Jj,k提前时间值。

Tj,k：工件Jj,k拖期时间值。

Xi,k：0-1变量,i=1,2,···,n, k=1,2,···,n，当工件i被排在第k个位置时, Xi,k=1,否则Xi,k=0。

由以上变量可得：

基于以上的描述，多目标模糊并行流水线调度数学模型描述如下：给定一个调度方案σ∈П，则最优调度为：

约束(1)表示每个位置有且只有一个工件；

约束(2)表示每个工件必须被安排在某一流水线上进行生产；

约束(3)～(6)定义了工件在各流水线上的加工开始时刻，并且当前工件要满足：当前工件的前一个工件在当前流水线上生产完毕的条件；

约束(7)定义了每个工件在条流水线上的完工时间。其中加工顺序Xi,k和开始加工时刻Bj,k(i=1,2, ···, n；j=1, 2, ···, m；k = 1, 2, ···, n)为决策变量。

1.2 紧急订单下多目标模糊并行流水线动态调度

假设对于任意流水线Mj，指派到该流水线的工件集为Jj，

i：工件代号。

k：位置代号。

j：流水线代号。

t0：再调度时刻。

Ej：t0时刻前，Jj中包含的工件数目。

Dj：t0时刻后，Jj中包含的工件数目。

Kj：工件集Jj中包含的工件数目，Kj=Ej+Dj。

Jj,k：工件集Ji其中的工件序列之一，即Jj,k∈Jj

Pi,j：工件i在流水线j上的加工时间,i=1,2,···,n;j=1,2,···,m。

Bj,k：Jj,k的开始加工时刻。

Cj,k：Ji,k完工时间，q=1,2,···,k; k=1,2,···,Kj）。

1) t0时刻，流水线Mj处于加工状态。待加工的工件的开始加工时间B为的完工时间和再调j,k度时刻t0的最大值决定。即Bj,k的计算公式为：

2) t0时刻，流水线Mj处于待加工状态。对于待加工工件，如果工件的释放时间不等于再调度时刻t，则待加工的工件的开始加工时间B为

0j,k的完工时间和工件的释放时间ri最大值决定。即Bj,k的计算公式为：

2 遗传算法和计算机仿真

2.1 遗传算法

1) 染色体编码和解码

编码是遗传算法要解决的首要和关键问题，选择合理的编码方法对算法的质量和效率有很大影响。为此，本文设计了工序与加工流水线相融合的两层编码方法，如图1所示。第一层为工件顺序编码，第二层为工件对应的加工流水线编码。

图1 双染色体编码

2) 染色体交叉和变异

(1)染色体交叉

部分匹配交叉（partially mapping crossover，PMX）。首先随机选取两个交叉点，交换父代个体交叉点之间的片段，对于交叉点外的基因，若它不与交换过来的基因冲突则保留，若冲突则通过部分映射来确定，直到没有冲突的基因为止，从而获得后代个体。

(2) 染色体变异

染色体变异采用互换变异的方式，在染色上随机选择两个基因，然后互换其位置。

(3) 构造适应度函数

本文以完工时间和交货惩罚为优化目标，因此，适应度函数用多目标加权平均的方式表示，其中a,b可以根据实际求解需要来取值。

2.2 计算机仿真方法

计算机仿真技术是以多种学科和理论为基础，以计算机及其相应的软件为工具，通过虚拟试验的方法来分析和解决问题的一门综合性技术[11]。它被广泛应用于机械制造、航空、交通和通信等工程领域。eM-plant仿真软件，可以为建模、仿真模拟和显示提供了一种完全面向对象的、图形化的、集成的工作环境。对多目标模糊并行流水线调度问题进行仿真研究一般要经过三个步骤：仿真模型建立、仿真模型参数设定和仿真逻辑控制、仿真模型运行并对结果进行分析。

2.3 改进GA和仿真分析的混合智能方法

遗传算法在优化搜索效率方面具有的独特优势，而仿真软件在问题建模方面具有的简易、快速的特点。本文将改进遗传算法整合到eM-plant仿真软件中，设计了改进遗传算法与仿真分析相结合的混合智能方法，具体流程如图2所示。

3 实例分析

3.1 问题描述

合肥某机械厂冲压车间主要负责上料和冲压两道工序，车间共有六条冲压生产线。工件在各生产线上的加工时间及惩罚因子和交货期窗口分别如表1和表2所示。其中α，β分别为提前完工和拖期的单位时间惩罚系数，Ei_time交货期窗口下限，Li_time为交货期窗口上限。

3.2 仿真模型建立

根据问题描述，在eM-plant仿真软件中建立多目标并行流水线的仿真动态模型，如图3所示。

图2 混合智能方法

图3 动态仿真模型

表1 工件在不同生产线上的加工时间

表2 惩罚因子和交货期窗口

将有关数据输入仿真模型，并运行模型对多目标模糊并行流水线调度问题进行优化求解。各参数设定为：种群规模为30，迭代次数100，交叉概率0.8，变异概率0.1。求解获得满意调度方案，甘特图和最优解的迭代搜索过程分别如图4和图5所示。

图4 Gantt图

图5 迭代搜索曲线

3.3 问题求解

当有紧急订单时，生产调度人员必须根据原有的调度方案调整调度计划，以满足实际生产的需求，临时订单在各生产线上加工时间如表3所示，交货期窗口如表4所示。

表3 临时插入工件的加工时间

表4 临时紧插入工件交货期窗口

通过将改进遗传算法整合到eM-plant仿真软件中，结合两者各自的优点，建立并行流水线混合模型，求解获得最佳的调度方案，t0时刻和动态调度后的甘特图分别如图6和图7所示。最优解的搜索迭代过程如图8所示。

图6 t0=26min时的动态调度方案Gantt图

图7 动态调度最优解Gantt图

图8 动态调度迭代搜索曲线

4 结束语

本文针对多目标模糊并行流水线动态调度问题，以最小化最大完工时间、最小化交货惩罚为优化目标，建立了数学模型，提出了一种基于改进遗传算法和仿真分析的混合方法，并建立了动态仿真模型。通过实例分析，结果验证了该方法的有效性和可行性，为解决多目标模糊并行流水线动态调度问题提供了一种新思路，具有一定的理论研究意义和实践价值。

[1] 郑永前.生产系统工程[M].北京:机械工业出版社.2011:5-6.

[2] 赵建峰,朱晓春,汪木兰,等.基于自适应遗传算法混合Flow-shop的调度与仿真[J].组合机床与自动化加工技术,2010(3):99-102.

[3] 刘民,吴澄,杨英杰.并行多机调度问题的一种基于组合规则的遗传算法[J].电子学报,2000,28(5):1-3.

[4] Cheng R,Gen M.Parallel Machine Scheduling Problems Using Memetic Algorithms[J].Computers Industrial Engineering,1997,vol,33,PP.761-764.

[5] 刘志雄.置换流水车间调度粒子群优化与局部搜索方法研究[J].机械设计与制造,2010:167-169.

[6] 李峥峰,喻道远,杨曙年.基于工序约束并行机模型的冲压线调度[J]. 计算机集成制造系统,2009,15(12):2432-2438.

[7] 刘民,吴澄.解决并行多机提前/拖后调度问题的混合遗传算法方法[J].自动化学报,2000,26(2):258-262.

[8] Kramer F J, Lee C Y. Due windows scheduling for parallel machine[J].Math Compute Modeling,1994,20(2):22-36.

[9] 蔡兰,郭顺生,王彬.基于交货期的流水线车间调度算法设计与实现[J].机械设计与制造,2005,8:161-163.

[10] 钱晓龙,唐立新,刘文新.动态调度的研究方法综述[J].控制与决策,2001,16(2):141-145.

[11] 侯扬.基于仿真的制造系统对象建模及其应用[D].上海交通大学,2000.