基于两阶段蚁群算法的带非等效并行机的作业车间调度

本资料包含pdf文件1个，下载需要1积分

Two-·stage Ant Colony Algorithm Based Job Shop Scheduling withUnrelated Parallel M achinesZHANG Jie ZHANG Peng LIU Guobao(School of Mechanical Engineering，Shanghai Jiao Tong University，Shanghai 200240)Abstract：The job shop scheduling problem with unrelated parallel machines is investigated.Multiple objectives such as productioncost and on time delivery rate for manufacturing system are taken into account in the proposed scheduling mode1.Considering thesuperiority of ant colony algorithm in solving the complex optimization problem，the mapping relationship between schedulingproblem an d ant colony parallel search is structured.The schedule process consists of tw o stages：tasks assignment and tasksequencing.For each stage，the ant colony optimization is designed respectively SO that a two-stage ant colony system(TSACS)withinheritance relationship is proposed.It can compress the solution space an d improve the solving speed. Key parameters of TSACSare identified through the uniform experiment and statistical an alysis.Computational experiments of 8 examples with diferent sizesare conducted.Th e results indicate that the proposed TSACA sign ificantly outperform s the improved genetic algorithm in bothoptimization results an d computational eficiency.Th e implementation of TSACS in real-life case also demonstrates that the waitingtime betw een operations can be reduced and the product delivery cycle Can be shoened。

Key words：Job shop scheduling problem Unrelated paralel machines Ant colony algorithm Multi-objective optimization0 前言电子/电器、汽车等行业某些制造系统具有如下特征[1-2]：① 多条并行生产线，或多道工序且每道国家自然科学基金资助项H(60934008)。20121205收到初稿，20130220收到修改稿工序具有多台并行设备生产，该类制造系统调度问题 是 作 业 车 间调 度 问题 (Job shop schedulingproblem，JSP)和并行机调度问题的混合；② 并行生产线或设备功能相同，但存在加工能力不同、生产时间不等、生产成本不-致等非等效特征。该类制造系统的生产调度问题是带非等效并行机的作业车间调度问题。如何对这类生产调度问题进行有效建2013年3月 张 洁等：基于两阶段蚁群算法的带非等效并行机的作业车间调度 137模与调度，是快速响应和满足客户需求的必要条件，研究这类生产调度模型与方法，具有重要的理论意义和工程应用价值。

国内外相关领域学者对等效并行多机调度模型和算法进行了大量的研究，等效并行多机调度问题已被证明为 NP完全问题3。但等效并行机调度忽略了实际制造系统中并行设备存在非等效差异这- 重要特点，因此，考虑实际生产需求，对非等效并行机调度问题的研究越来越多。CHRISTOFOROS等4J以最携完工时间为目标研究非等效并行多机调度问题，设计了启发式算法和数学规划相结合的精确解方法进行求解。AZIZOGLUE5考虑每台设备对相同工序的加工成本不-致，且加工成本与加工时间呈非线性关系，建立最携生产成本的生产调度模型。CORREA等[61在研究非等效并行机调度过程中，考虑订单优先级约束，以最携订单完成时间为目标建立调度模型。

综上所述，以上文献对并行机的等效与否的界定多数仅考虑设备能力的问题，而实际的制造系统中，各种功能相同的并行设备还存在生产同类产品所需工时不等、生产成本不-致等非等效特征；以上文献对单-工序的单级并行机调度研究较多，而实际生产中，-般是具有多道生产工序，且每道工序中具有多台并行设备的复杂生产系统；调度过程中各优化目标之间存在相互约束甚至相互冲突，多目标优化成为复杂非等效并行机调度问题研究的趋势。

因此，本文针对带非等效并行机的JSP多目标调度问题，分析了这类生产调度问题中的约束条件，同时考虑制造系统对生产成本、准时交货率等目标要求，构建生产调度多目标Pareto优化模型〖虑蚁群算法的分布式计算特性，建立调度问题与蚁群并行搜索算法的映射关系～调度过程分成任务分派和任务排序两个阶段，每个阶段分别采用蚁群优化。为了压缩求解空间，加快算法的求解速度，将两阶段寻优蚂蚁有机结合，构建-种具有继承关系的两阶段蚁群并行搜索生产调度算法。

1 调度问题优化模型I.I 问题描述带非等效并行机的作业车间假设：加工车间按设备功能分为多个加工区(粗车区、精车区、磨削区等1，每个加工区内有若干非等效并行机；车间可同时加工不同类型的零件且零件具有各自不同的加工工序，工序是预先确定的；构成同-产品的零件间具有基本对象模型(Basic object models，BOM)约束关系，处于低位码的零件比高位码的零件优先加工；调度的最小单位是任务，每个任务包含若干相同类型的零件，每个任务具有独立交货期；加工过程中，每个任务不重复访问同-设备组。

作业车间生产调度问题常见的是基于单目标优化，如使任务在系统中的流通时间(Makespan)最短，任务的流通时间反映任务在系统中的驻留时间，能较全面地反映系统的生产时间。随着产品生命周期的日益缩短和客户需求水平的不断提高，企业对于准时交货的要求越来越高，产品的提前/拖期惩罚最少也成为衡量调度系统性能的-个主要目标。因此，本文建立了双目标模型：① 使所有任务在系统中的流通时间最短，即Makespan最小；② 保证任务的准时交货水平，即提前/拖期惩罚成本最校1.2 数学模型目标函数与约束条件，min∑ (1)i1，min∑( )≤min Vf，J，m，≤‰ 碥， ，k， < ∈1，略 嚎 x mkXjImk≤1， ，∑∑(嚆 - D)≤(2)(3)(4)(5)(6)(7)式中，1，为零件类型索引 v1，2，，V；f为任务索引，f1，2，，I；m为设备组索引，m1，2，，M ；k为设备索引，k1，2，， ； 为工序索引， 1，2，， ； 为任务f中零件1，的数量；为任务f的释放时间； 为任务f的交货期；为任务f的 BOM 层次； / 为任务f的提前/拖期惩罚系数。 为零件 1，的工序 在设备组 m 内设备 七的加工时间； 为零件 1，的工序 在设备组m内设备 七的加工准备时间；Lm 为设备组 m内设备 七在调度周期内最大负荷； 为任务f的工序在设备组 m内设备 k的开始加工时间； 为任务f的工序 ，在设备组 m内设备七的结束加工时间；为 O/1变量，1表示任务f在设备组 中的设备k上先于任务.，加工； 为任务f完工时间， M Km jtmax∑∑∑( )；巨为任务提前惩罚， ma)ml kl j10，di- ； 为任务拖期惩罚，Dlmax0， -dj。

138 机 械 工 程 学 报 第 49卷第 6期式(1)、(2)分别表示最携最大完工时间和最小化提前/拖期惩罚目标函数。约束条件中，式(3)表示任务 f的开始加工时间不小于任务释放时间；式(4)表示包含低位码零件的任务 fl先于包含高位码零件的任务 f2进行加工，该过程考虑准备加工时间；式(5)确定了任务 f的第.，道工序的加工结束时间等于其开始加工时间与加工时间之和；式(6)表示-台设备-次只能处理-个任务；式(7)为设备负荷约束，安排在设备上的任务占用负荷不得超过该设备最大负荷。

1-3 多目标 Pareto优化生产过程中，提前和落后于交货期完工都将受到惩罚，完工时间须尽量靠近交货期；减小最大完工时间可使车间生产过程成本降低，本文建立调度目标之间是相互关联、相互制约，是-个多目标优化的过程，它是 Pareto优化问题。按照 Pareto优化方法7，多目标优化的结果是-组无法相互比较的非受支配解，包含着按照各种指标评价的所得到的妥协的解的集合( ， ，，尺：l， ∈N。图1为两目标情形的Pareto最优解集分布曲线。在实际决策过程中，通常需要从非受支配解集中选择-个最优妥协解作为给定问题的最终解 。本文采用偏离度函数评价 Pareto最优解的优劣。第 个 Pareto最优解总的偏离度如式(8)所示∑o(k)eokl(8)式中， 为第n个 Pareto最优解在第k个评价指标上的偏离度。

闼避皿 图1 两个目标时的Pareto最优解分布2 两阶蚁群并行搜索算法2.1 模型与算法的映射关系蚁群优化算法在求解组合优化问题的过程中，首先需要对问题建立映射模型，这种建模主要是基于两维析取图的可视化建模。所谓两维析取图建模，就是通过定义集合G(O， ，R)，将这些组合优化问题建立其相应的平面模型，其中D为节点集、为有向或无向实线集、 为无向虚线集。如在最基本 TSP问题中，可以定义节点集D为所有城市的节点，连接两城市之间的线段为无向实线集 ， 中的每个元素表征了两城市之间的距离， 为所有可能的路径集。通过人工蚂蚁对所有节点的遍历及相应信息素释放，以求得相对较短的旅行路径。在建立了两维析取图模型后，才能将蚁群算法中路径的选择、信息素的释放等概念运用于模型中进行问题的求解及优化。

建立析取图模型是运用蚁群算法的基础，也是利用蚁群算法解决各种实际工程问题的先决条件。

但由于两维析取图模型所定义的元素较少导致模型可携带的信息量较少，难以应对多约束、多资源或者柔性加工等更为复杂的调度问题建模，因此-般的两维析取图模型只能解决基本的作业车间调度问题或流水车间作业调度问题，很难对类似多约束条件下的作业车间调度这类较复杂的问题建立适合蚁群算法求解的模型。本文针对带非等效并行机的JSP调度问题，基于图论理论，建立调度算法与调度模型的映射关系，构建基于图模型的解空间网络。

根据调度问题描述，对解空间网络的要求如下：① 将调度问题中每台设备的加工工艺特性映射到模型中，每台机器对应的加工工艺都应有模型中的节点元素进行映射，模型中的每个节点元素也应唯-对应相应的机器加工特性；② 能在模型中完整地反映每个任务的工艺顺序；③ 在人工蚂蚁对模型进行-个遍历后，通过散列等处理方式就能得到-个对应的可行解；④ 模型的网络特点便于蚂蚁信息素的释放，即模型中应体现出 路径”的特点，便于蚂蚁在路径上进行信息素的释放。

根据以上分析，本文采用基于四维析取图模型的建模 映射方 法。 四维析 取 图模 型可用集 合G(O，O ， ， ， ， )来表示。其中D为所有实节点的集合，实结点 表示任务f的第 ，道工序可由设备组k内设备m进行加工，其中f、，、k分别为、Y、z轴上的坐标，分别代表了工序维、设备组维、任务维，m是新引入的-个维度，代表-个设备组内的设备；D 为所有虚节点的集合，虚节点表示任务f 的第.， 道工序不可由设备组k 内设备m 进行加工；U为有向实线的集合，有向实线表示同-任务的不同工序之间工艺顺序； 为无向虚线的集合，无向虚线v连接理论上可进行先后加工的两道工序； 为单点划线结合，单点划线W连接-次遍历中不能同时选择的两道工序，由单点划线连接的节点称为互斥节点，蚂蚁在-次寻迹中对互斥节点只能选择-个； 为车间所有设备组内设备集合。针对带非等效并行机的JSP问题，构建机 械 工 程 学 报 第 49卷第 6期2.2.2 任务排序采用基于设备的编码方式，将第-阶段获得的任务分派结果按设备分成不同的矢量组。矢量的每个分量包含信息：任务号、工序号、设备号、优先权值、加工时间和可开始加工时间等。优化每台设备上任务的加工顺序使任务的最大完工时间最校蚂蚁遍历设备上的任务后得到任务加工顺序，单台设备任务排序阶段构建解序列的过程中，蚂蚁采用伪随机比例的状态转移规则来选择设备 下-步要加工的任务 ，，规则由式(11)给出， 由式(12)决定f lI (- ) I 其他p/JI，k-。

式中， L 表示蚂蚁游历到顺序i时选择任务.，的概率， ( )为当前尚未参加排序的任务集； 表示 设 备 上任 务顺 序 之 间 的信 息 素 水 平 ； l/ 为当前时刻任务 在安排在设备k的顺序 i处启发式信息。按照 大小，从 (f)中随机选全个任务添加到已排序的部分任务集之后，直至 (f)为空。

2.2-3 信息素更新策略局部信息素更新。在解序列的构建过程中，蚂蚁每经过-条边，都将立刻按式(13)更新该边上的信息素。局部信息素蒸发率 满足 0< <1，ro是信息素初始值。局部更新的作用在于蚂蚁每-次经过边，该边的信息素 将会减少，从而使其他蚂蚁选中该边的概率相对减少，增加探索新路径的机会，使算法不会陷入停滞状态。

÷-(1- ) (13)全局信息素更新。在每次迭代中，当所有蚂蚁都构建出完整的解序列且对当代最优蚂蚁执行局部搜索后，为加强较优路径的信息，且不造成过快收敛，算法对所有局部最优路径更新信息素，，为整体影响因子，P为蚂蚁信息素挥发系数， 为当前任务占用的设备负荷，c 为当前任务排序结果的完工时间。在任务分派阶段按式(14)更新信息素，在任务排序阶段按式(1 5)更新信息素-(1- )TImk (14)I1 ，- -(1- ) c， (15)2.2.4 局部搜索策略考虑同-设备组内均为并行机，功能相同，效率不等，因此在任务分派阶段局部搜索策略如下：当前最优任务分派路径 vi上同-设备组内的任意两台设备上两个任务节点互换位置 ，，得变异解 。若 < ，意味着变异提高了解的质量，则让蚂蚁在vi 上释放信息素，并保留该蚂蚁并用于第二阶段，即任务排序阶段的路径搜索；若 ，表示该局部搜索在任务分派阶段没能对搜索路径进行有效的改进，则进行任务排序阶段的局部搜索。

考虑同-设备上任务的互换对其他设备上任务排序的影响较大，因此任务排序阶段的局部搜索采取的方式是：任取当前最优路径 上在单台设备的任务排序，将当前最优方案的各节点插入到与之都不相邻的两元素之问，得到变异顺序v 1， ，并检查由此形成的新方案 vi：与原局部最优解的优劣，若 ：< ，意味着变异提高了解的质量，则让蚂蚁在 上释放信息素，否则继续执行插入邻域搜索直至检查完当前最优方案上所有的节点。两阶段蚁群优化过程中，具有继承关系的局部搜索使信息素有方向地集中到相对较优的路径上。

综上所述，求解带非等效并行机的Job Shop调度 问题 的两 阶段蚁群算法(Two.stage ant cdonysystem，TSACS)基本流程如图5所示。

( 塑 )... .. .. .. ... .. ... ..- 蚁群参数初始化二]二 蚂蚁搜索依设备选择概率选定任各工序的加工设备厂 量亭匦 l I否Ll局部更新与优秀蚂蚁保留I 最优的设备分配否 - - 任务选择概率确定1在设备上加工顺序r< 竺f I否 车匝L l t最优的任务安排顺序是图5 两阶蚁群算法流程图3 计算结果与比较3.1 确定算法关键组合参数在蚁群算法参数中，信息素启发式因子 越大表明信息素越重要，蚂蚁越有可能选择已走过的路径；期望启发式因子 越大，表明启发函数在下-步搜索中将发挥比较重要的作用，蚂蚁越有可能搜2013年3月 张 洁等：基于两阶段蚁群算法的带非等效并行机的作业车间调度 141索新路径；全局信息素蒸发速度 越小，信息素挥发速度就越慢，有助于发现更好的解；整体影响因子Y越大，当前最优解对整体寻优过程影响越明显；针对蚁群系统框架，引入伪随机概率 ，对算法性能起着关键作用的参数为 、 qo。在验证算法性能之前，首先通过仿真试验分析不同的参数组合配置对算法性能的影响，以便确定较好的参数组合配置。

根据两阶段蚁群算法特点，任务分派的结果作为任务排序的输入，算法两个阶段有机结合但搜索过程相互独立，为简化参数组合试验的规模，两阶段蚁群基本参数设置相同。P和，参数组合应该满足-定的条件，如果P》 ，将很难起到强化作用1UJ，经过大量试验，取值范围为6≤ / ≤10是比较满意的。

本文考虑的关键参数组合为 qo、P，如果对于每个参数在其取值范围内取g个水平，则共有g种水平组合，为了确定最优的参数组合需要进行g次试验，如果水平数 较大，试验组数将会很大以至于难以实现。本文采用均匀试验设计方案，以兼顾效率与性能L9。

依据 DORGO 等NACS 的试验分析 ，设定、 q0、P的试验取值分别为0.5，l，2，4，2，3，4，5，0.6，0.7，0.8，0.9，0.1，0.2，0.3，0.4，即有 4个因素，每个因素取值范围为 4个水平，4个因素的- 次项及二次项各有 4项，4项因素间的两两交互作用设有 6项，共 14项，即试验数不能小于 l4，因此均匀设计表选用 (4 )，均匀表设计见表 1，表 1中的数字代表参数的取值水平。

表 1 均匀试验方案均匀表设计参数l 2 3 4 5 6 7 8 9 1O l1 l2 l3 l4 l5 l6口8g0p设备组M4，且各设备组内非等效设备均为 3，任务数 10，初设蚁群数 Nuts50，迭代次数Iter1O0，信息素初始值 10。采用与文献[10相同的方法随机生成算例。每种参数组合的算例独立运行 20次，解的优劣以偏差量 ( - ； )/(‰ - )评价，X代表当前值，Xmi 代表已知最优解，Xmax代表已知最差解， 越接近 0表示解越好。图6将 值按从大Nd，的顺序排列，并给出参数组合的 95%置信区间的直观图，当参数组合取1l，即 l， 3，qo0.8，PO.1时，求解的结果较为集中，离散化程度低。

厘凶迎皇咖诺参数组合图 6 参数组合的 95%置信区间DORIGO等8的试验分析已经表明P0.1时算法具有较好性能，ACS算法对于蚂蚁数目的取值具有较强的鲁棒性，结合本文算例，算法均采用蚂蚁数 Nuts50。由于蚁群算法的收敛性证明存在理论困难，因此本文通过大量的数值试验对收敛性加以定性分析，图7所示为试验中随机抽取-个算例的三次重复试验的算法收敛曲线图，在算法初期 目标函数值下降很快，随着迭代的深入，算法收敛性趋于平稳，当迭代次数超过50次时，算法具有稳定的收敛性。

宝g星翟H根堪迭代次数图7 TSACS收敛散点分布图综上所述 ，TSACS算法基本参数：蚂蚁数Nuts50，迭代次数 lter50，信息素启发式因子 1，期望启发式因子 3，整体信息素蒸发速度P0.1，局部信息素蒸发度 0.1，整体影响因子Y0.02，伪随机概率 0.8。

3.2 算法性能的对比分析为验证算法有效性，采用精确解方法对模型求解。分别采用 ILOG公司的CPLEX工具和基于松弛量最小 SLA(Least amount of slack)规则的调度方法。SLA规则选择松弛量最小的工件首先接受服务，工件松弛量交付期-当前时刻-剩余加工时4 4 1 2 l 3 3 2 1 1 4 2 4 2 2 2 4 3 2 l 2 2 3 1 2 3 4 3 3 3 l 4 l 2 4 4 3 2 l 3 2 1 3 3 l 4 3 4 3 4 2 3 3 1 2 4 2 4 4 14 ； 2013年3月 张 洁等：基于两阶段蚁群算法的带非等效并行机的作业车间调度 143芒星茁蜮图 11 TSACS与 IGA计算时间对比从图 lO可以看出，TSACS在最优值和平均值两个指标上均好于文献的 IGA，问题规南小时，IGA求解结果较集中，但随着问题规模增大，最优值到平均值的偏离程度越来越大，稳定性变差；TSACS虽然在任务数量小于 15时计算结果的稳定性不如IGA，但随着问题规模增大，TSACS的表现越来越好，这也充分说明了两阶段蚁群优化过程使设备利用率提高。由图1 1可知，在算法的时间性能方面，在问题规南小时，TSACS的表现同样不如IGA，少量的任务排序很容易就能完成，而此时TSACS的两阶段优化过程是浪费时间的；但随着任务数量增加，问题复杂度呈指数增长，TSACS的两阶段搜索过程的优势得到体现，前-阶的搜索为第二阶的蚁群提供了筛淹过滤的作用，为第二阶的蚂蚁寻优节省了大量时间。这也充分说明了蚁群优化算法更适合求解大规模调度问题。

3.3 多目标优化结果同样选择上述文献[1o1中的 IGA 算法作为对比，为了比较的公平性，TSACS算法和 IGA算法采用相同的群体规模 100，而且在每组测试函数中均迭代相同的次数，算法基本参数设备不变。为计算方便，选取任务数量为6的情况进行试验。其中，提前/拖期惩罚系数 / 的选取采用文献[11中的方法，即服从[1，201间的均匀分布。在算例试验后，以图形化的方式给出这两种方法生成的 Pareto前沿，并对所得解的数量、分布性能以及散布范围等作比较。这两种算法迭代 50次后得到的结果如图12所示。由图 12可知，两种方法都能很好地逼近Pareto前沿，搜索效率很高。在解区间[225，245]上，TSACS算法求解结果分布较为紧凑，算法搜索到的解多集中在该区段，从侧面反映了蚁群算法具有很强的搜索较优解的能力。

3.4 企业生产数据验证本文提出的 TSACO算法作为离散制造车间生产过程调度系统的组成部分之-，在上海某军工企籁陌船分布函数 /图 12 TSACS与 IGA算法 Pareto优化目标求解结果比较业生产车间进行了实施。该企业产品部件较多，-个型号-般有-千种以上的零件，而且产品的批量较小，是属于多任务的生产加工车间，主要加工结构件。车间以班组为单位，主要分为车工组、铣工组、钳工组、机修工组等班组，属于多设备组、不同类型设备具有不同的数量、同-类型设备组内设备非等效性。从 目前车间反镭的情况来看，调度系统 的实施使生产过程 中工序 间等待时间减少18%，产品交付周期缩短 12%。在工业现场的实际应用进-步证明了TSACO算法的有效性。

4 结论(1)根据实际制造车间中带非等效并行机的JSP调度问题，考虑制造系统对生产成本、准时交货率等目标要求，构建了生产调度多目标模型。

(2)基于析取图可视化模型，建立了调度问题与蚁群并行搜索的映射关系，将调度过程分成任务分派和任务排序两个阶段。

(3)为了提高获得较优解的概率，压缩求解空间，并快速获得较优解，将两阶段寻优蚂蚁有机结合，构建-种具有继承关系的两阶段蚁群并行搜索算法。

(4)为了获认好的算法参数，通过均匀试验和统计分析确定了算法的关键参数组合。

最后，运用所提出的算法对多个算例进行了求解，试验结果证实了不论在求解时间，还是求解质量，TSACS算法均体现出了很强的优势。