高级检索

  • ISSN 1006-3080
  • CN 31-1691/TQ
引用本文:
Citation:

柔性作业车间的成套订单调度问题

    作者简介: 徐震浩(1976-),女,河南洛阳人,副教授,博士,研究方向为生产计划与调度。E-mail:xuzhenhao@ecust.edu.cn;
  • 中图分类号: TP301

Whole-Set Orders Scheduling Problem in Flexible Job Shop

  • CLC number: TP301

  • 摘要: 随着加工制造业的发展,面向成套订单的加工生产方式得到广泛的应用,但由于柔性作业车间的特殊性以及成套订单问题的复杂性,目前对该问题进行的相关研究极少。本文以最大化加权订单成套率为目标,提出了一种柔性作业车间环境下的成套订单调度模型;根据问题特点在最大最小蚂蚁系统(MMAS)的基础上加入了一种新的邻域结构,通过削减和消除订单及工件的交货时间瓶颈提高了加权订单成套率。采用正交试验方法对算法参数进行整定,与其他元启发式算法的对比结果验证了本文算法的先进性和稳定性。
  • 图 1  具有邻域结构的最大最小蚂蚁系统流程图

    Figure 1.  Flowchart of MMAS-NS

    图 2  一种FJSP的编码方式

    Figure 2.  An encoding method of FJSP

    图 3  邻域搜索算法流程图

    Figure 3.  Flowchart of neighborhood search algorithm

    图 4  邻域搜索后调度甘特图

    Figure 4.  Gantt chart of scheduling after neighborhood search

    图 5  关键路径示意图

    Figure 5.  Schematic diagram of critical path

    图 6  不同因素水平下目标函数95%置信度LSD区间均值图

    Figure 6.  Prediction interval graphs of objective function at different factors and levels

    图 7  两个小规模测试实例下的算法收敛曲线图

    Figure 7.  Algorithmic convergence curves for two small-scale test instances

    图 8  中等规模和大规模测试实例下的算法收敛曲线图

    Figure 8.  Algorithmic convergence curves for medium and large scale test instances

    图 9  测试实例Case3的收敛曲线图

    Figure 9.  Convergence curves of case3 problem

    表 1  正交设计因素和水平表

    Table 1.  Factors and levels of orthogonal design

    FactorNpopραβ
    Level 1500.70.50.5
    Level 21200.911
    Level 32000.9522
    下载: 导出CSV

    表 2  4种算法在不同算例下的仿真结果对比

    Table 2.  Comparison of simulation results of four algorithms under different instances

    Problemn×m×oAlgorithmMaxMinAvgStd
    Case8×8×6IACO0.733 60.733 60.733 6
    MMAS0.733 60.651 70.717 20.036 6
    IICA0.733 60.733 60.733 6
    ICA0.733 60.651 70.700 80.044 9
    Mk0110×6×8IACO0.909 20.895 50.906 50.006 1
    MMAS0.909 20.754 10.806 20.019 5
    IICA0.909 20.812 70.889 90.043 2
    ICA0.812 70.724 80.793 00.028 7
    Mk0210×6×6IACO0.900 50.773 80.841 00.048 5
    MMAS0.900 50.773 60.807 10.052 4
    IICA0.900 50.763 10.836 90.047 6
    ICA0.900 50.763 10.814 00.050 4
    Setb4xx15×12×7IACO0.841 60.765 70.806 00.029 8
    MMAS0.755 60.652 60.695 30.069 0
    IICA0.767 30.650 50.701 90.056 1
    ICA0.742 40.652 60.688 10.069 5
    Setb4xxx15×13×10IACO0.865 60.727 80.789 50.049 2
    MMAS0.650 60.570 10.619 90.054 5
    IICA0.687 80.606 30.635 00.051 0
    ICA0.644 60.570 10.636 50.054 6
    seti5xyz15×18×9IACO0.799 70.675 30.737 70.061 4
    MMAS0.675 70.575 60.632 00.089 0
    IICA0.725 30.627 10.656 90.076 4
    ICA0.675 30.562 00.625 00.076 1
    Mk0820×10×11IACO0.854 30.707 50.733 30.104 1
    MMAS0.612 10.485 50.534 10.091 0
    IICA0.707 60.542 10.629 80.127 3
    ICA0.635 10.485 50.545 20.115 0
    Mk0920×10×15IACO0.727 80.658 80.696 50.065 2
    MMAS0.628 20.468 40.546 70.148 5
    IICA0.639 80.498 80.565 00.112 5
    ICA0.609 30.468 40.525 30.136 7
    Mk1020×15×12IACO0.654 10.387 80.540 40.113 3
    MMAS0.532 20.252 70.395 60.144 3
    IICA0.559 00.364 90.436 80.126 8
    ICA0.516 00.205 30.395 30.156 1
    下载: 导出CSV
  • [1] PAN Q K, TASGETIREN M F, SUGANTHAN P N, et al. A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem[J]. China Mechanical Engineering, 2011, 181(12): 2455-2468.
    [2] ZHANG R, WU C. A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardiness objective[J]. Computers & Operations Research, 2011, 38(5): 854-867.
    [3] 鲁建厦, 邓伟, 董巧英. 基于混合粒子群算法具有交货期瓶颈的作业车间调度问题[J]. 中国机械工程, 2014, 25(5): 624-629. doi: 10.3969/j.issn.1004-132X.2014.05.011
    [4] ZHOU S Y, CHEN R Q. A genetic algorithm: Weighted single machine scheduling problems to maximize the whole-set orders[J]. Systems Engineering, 2005(5): 22-24.
    [5] YU Z, YANG X. Full glowworm swarm optimization algorithm for whole-set orders scheduling in single machine[J]. Scientific World Journal, 2013, 2013: 1-6.
    [6] 周水银, 傅青. 最大化流水作业加权成套订单数的研究[J]. 控制工程, 2007, 14(2): 212-214. doi: 10.3969/j.issn.1671-7848.2007.02.029
    [7] 吴春辉, 周水银. 并行多机加权成套订单数极大化的混合遗传算法[J]. 系统工程理论与实践, 2006, 26(11): 125-129. doi: 10.3321/j.issn:1000-6788.2006.11.018
    [8] 傅青. 流水作业成套订单数及其多目标排序研究[D]. 武汉: 华中科技大学, 2007.
    [9] XING L N, CHEN Y W, WANG P, et al. A knowledge-based ant colony optimization for flexible job shop scheduling problems[J]. Applied Soft Computing Journal, 2010, 10(3): 888-896. doi: 10.1016/j.asoc.2009.10.006
    [10] DORIGO M, STÜTZLE T. Ant Colony Optimization: Overview and Recent Advances[M]. US : Springer, 2010: 227-263.
    [11] ESWARAMURTHY V P, TAMILARASI A. Hybridizing tabu search with ant colony optimization for solving job shop scheduling problems[J]. International Journal of Advanced Manufacturing Technology, 2009, 40(9/10): 1004-1015.
    [12] STÜTZLE T, HOOS H H. MAX-MIN, Ant system[M]. USA: Elsevier Science Publishers, 2000.
    [13] NOWICKI E, SMUTNICKI C. Some new tools to solve the job-shop problem[R]. Wroclaw: Technical University of Wroclaw, 2002.
    [14] 高亮, 张国辉, 王晓娟. 柔性作业车间调度智能算法及其应用[M]. 武汉: 华中科技大学出版社, 2012.
    [15] 张超勇, 邵新宇. 作业车间调度理论与算法[M]. 武汉: 华中科技大学出版社, 2014.
    [16] CHAMBERS J, BARNES J. Classical and flexible job shop scheduling by tabu search[D]. Austin: University of Texas at Austin, 1998.
    [17] BRANDIMARTE P. Routing and scheduling in a flexible job shop by tabu search[J]. Annals of Operations Research, 1993, 41(3): 157-183. doi: 10.1007/BF02023073
    [18] ATASHPAZ-GARGARI E, LUCAS C. Imperialist competitive algorithm: An algorithm for optimization inspired by imperialistic competition[C]//IEEE Congress on Evolutionary Computation. Singapore: IEEE, 2007: 4661-4667.
    [19] 徐震浩, 王程, 顾幸生. 基于DICA的存储受限流水车间调度[J]. 华东理工大学学报(自然科学版), 2018, 44(4): 563-572.
  • [1] 刘强钱军程志鹏寇文娟庄启昕 . 核壳结构Fe3O4@C改性PVDF柔性薄膜的介电性能研究. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20190218002
    [2] 金志超高大启朱昌明王喆 . 基于权重的多视角全局和局部结构风险最小化分类器. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180704001
    [3] 王学武夏泽龙顾幸生 . 基于事件触发的自适应邻域多目标进化算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20181120005
    [4] 薛敏杨健谭帅侍洪波 . 基于多数据结构的集成质量监控方法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180821002
    [5] 曹移林余炜 . 平行三阶段流水作业问题的近似算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180206001
    [6] 昌慧郝伟举刘洪来徐首红 . pH响应MSNs@polymer(FITC/FA)核-壳结构双重药物载体. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180421003
    [7] 王伟丁剑峰夏浙安李欣欣 . 扩链改性回收尼龙6/碳纤维复合材料的结构与性能. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20190512002
    [8] 林静远刘必林王立权 . 基于角质颚微结构的剑尖枪乌贼的日龄与生长. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.2018051200
    [9] 杨斌曾惠丹蒋烨佳陈春雨李文婧陈国荣 . B2O3对Yb3+掺杂磷酸盐玻璃结构和光学性能的影响. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180327002
    [10] 姚炜屹王际童乔文明凌立成 . 活性炭纤维孔结构和表面含氧官能团对甲醛吸附性能的影响. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180911002
    [11] 杨家宝何磊祝慧雯郭庆华龚岩于广锁 . N2和CO2稀释对CH4/O2扩散火焰反应区和结构特性的影响. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180928002
    [12] 高天阳虞慧群范贵生 . 基于模拟退火遗传算法的云资源调度方法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180416001
    [13] 赖兆林冯翔虞慧群 . 基于逆向学习行为粒子群算法的云计算大规模任务调度. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20190218001
    [14] 赵倩倩赵均徐祖华陈曦邵之江秦海中 . 空分装置群的设备启停及变负荷调度策略. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20181015005
    [15] 李岁王元华 . 油田水套加热炉高温空气燃烧瞬态模拟及最小换向时间. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180723008
    [16] 解冰朱宏擎 . 一种基于选择性卷积特征和最大后验高斯混合模型的细粒度图像分类算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180603001
    [17] 张星崔向伟李宗霖李志敏 . 基于能量循环再生系统酶法生产谷胱甘肽. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20190806001
    [18] 伏威袁伟娜 . 一种基于PTS方法降低FBMC系统PAPR的新方法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180409003
    [19] 金艳张永红宋兴福连伟何化于建国 . 耐盐菌MBR系统处理页岩气采出水性能及膜污染特性. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20190606001
    [20] 翁童袁伟娜 . 一种基于SPSO算法降低FBMC系统PAPR的新方法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20190731002
  • 加载中
图(9)表(2)
计量
  • 文章访问数:  7145
  • HTML全文浏览量:  1750
  • PDF下载量:  5
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-11-21
  • 网络出版日期:  2019-07-19

柔性作业车间的成套订单调度问题

    作者简介:徐震浩(1976-),女,河南洛阳人,副教授,博士,研究方向为生产计划与调度。E-mail:xuzhenhao@ecust.edu.cn
  • 华东理工大学化工过程先进控制和优化技术教育部重点实验室,上海 200237

摘要: 随着加工制造业的发展,面向成套订单的加工生产方式得到广泛的应用,但由于柔性作业车间的特殊性以及成套订单问题的复杂性,目前对该问题进行的相关研究极少。本文以最大化加权订单成套率为目标,提出了一种柔性作业车间环境下的成套订单调度模型;根据问题特点在最大最小蚂蚁系统(MMAS)的基础上加入了一种新的邻域结构,通过削减和消除订单及工件的交货时间瓶颈提高了加权订单成套率。采用正交试验方法对算法参数进行整定,与其他元启发式算法的对比结果验证了本文算法的先进性和稳定性。

English Abstract

  • 随着产品定制服务的出现,客户对产品的定制需求正朝着多品种、小批量、成套性方向发展。成套订单问题具有广泛的实际背景,有相当一部分企业采用定制生产方式,如大型工程、船舶制造等。对于某些大型机械,其工件定制通常具有配套性以满足产品模块化组装的要求,企业的竞争力不再局限于生产的高效率和快速性,并且延伸到了工件交付的准时性和成套性。虽然成套订单的生产调度问题是加工制造业面临和亟待解决的难点,但与一般的makespan最小化问题相比,具有加权订单成套率难以提高的特点。如何跳出局部最优,提高加权订单成套率是成套订单调度问题的难点和关键。目前,与成套订单调度问题相关的文献很少,且现有的相关研究仅围绕单机或两台机器的流水车间环境进行,鲜有对柔性作业车间环境下的成套订单调度问题的研究。与成套订单调度问题类似的问题是最小化提前/拖期惩罚、最小化总拖期等,与成套订单调度问题的相同点是都需要设置工件的交货时间。Pan等[1]利用离散蜂群算法解决了批量流水车间的最小化提前拖期问题;Zhang等[2]提出了一种基于块特性的邻域结构,融合模拟退火算法解决了最小化作业车间总拖期时间问题;鲁建厦等[3]提出了一种基于模拟退火的混合粒子群算法,解决了最小化作业车间下总加权拖期时间问题。成套订单调度问题是存在工件交货时间的前提下同时存在订单工件的配套问题,Zhou等[4]首先提出了成套订单问题并采用遗传算法解决了单机环境下加权成套订单的调度问题,Yu等[5]提出了采用随机键编码方式的萤火虫算法用来解决单机环境下成套订单的调度问题;周水银等[6]采用启发式规则研究解决了两台机器构成的流水车间环境下的成套订单调度问题;吴春辉等[7]提出了一种基于工件交货时间瓶颈的启发式规则,利用遗传算法解决了单一工序并行机环境下的成套订单调度问题;傅青[8]以最大化成套订单数和最小化总配送时间为多目标,采用遗传算法和启发式算法相结合的方法求解该多目标问题。

    蚁群算法具有相对较好的寻优特性,广泛应用于组合优化问题中[9]。本文在最大最小蚂蚁系统(Max-Min Ant System,MMAS)的基础上,根据成套订单问题工件之间配套性的特点设计了新的邻域结构,提出了一种具有邻域结构的最大最小蚂蚁系统(MAX-MIN Ant System with a Neighbor Structure,MMAS-NS)。通过邻域搜索反复迭代缩减瓶颈订单和瓶颈工件的交货时间瓶颈,达到消除订单工件交货时间瓶颈的效果,进而使瓶颈工件按时完工,最终达到提高加权订单成套率的目的。实验结果表明,MMAS-NS算法能够获得加权订单成套率较高的解,表现出比其他算法优越的性能。

    • 针对柔性作业车间环境下的成套订单调度问题模型,有以下描述:n个工件在m台机器上加工,这n个工件分别属于H个订单。

      订单层面看,每个订单来自不同的客户,对于订单h,其权重为${w_h}$,表示该订单的重要性,它包含${n_h}$个工件,可表示为$O = \{ O_{ij}^h,1 \leqslant h \leqslant H,$$ \leqslant {n_h}\} $

      工件层面看,$C_i^h$为工件$J_i^h$的完工时间,$d_i^h$为工件$J_i^h$的交货时间。每个工件$J_i^h$包含$n_i^h$道工序,可以表示为$O = \{ O_{ij}^h,1 \leqslant h \leqslant H,1 \leqslant i \leqslant {n_h},1 \leqslant j \leqslant n_i^h\} $。每道工序可以在若干台机器上加工,并按照预先规划好的工艺次序进行加工。每台机器可以加工工件的若干工序,并且在不同的机器上加工的工序集可以不同,$p_{ijk}^h$表示工序$O_{ij}^h$在机器k上的加工时间,$C_{ijk}^h$为工序$O_{ij}^h$在机器k上的完工时间。可加工工序$O_{ij}^h$机器集合为$M_{ij}^h$,且$M_{ij}^h \subseteq M,M = \{ {M_k},1 \leqslant k \leqslant m\} $。加工过程满足以下条件:

      (1)每台机床每次只能加工一个工件;

      (2)每个工序的加工过程不能中断;

      (3)工件之间具有相同的优先级;

      (4)不同工件的工序之间没有前后约束;

      (5)所有工件到达时间均为零。

      柔性作业车间环境下成套订单调度问题的数学模型表示如下:

      其中${x_h}$是决策变量,

      约束条件如下:

      其中${a_{hijkpl}}$${x_{hijopqk}}$是决策变量,

      $(1)$为问题的目标函数,即最大化加权成套订单数,它与每个订单的权值${w_h}$和该订单的成套系数${x_h}$有关;式$(2)$为加工工艺约束,即工件的某一工序只有在当前机器上加工完成后,才能进入下一台机器加工该工件的下一道工序;式$(3)$为工序非堵塞约束(资源约束),当前工序$O_{ij}^h$加工之前需要等待同机紧前工序${M_P}[O_{ij}^h]$加工完成才能开始加工,同机紧后工序${M_S}[O_{ij}^h]$需要在当前工序加工完成后才能开始加工。

    • 柔性作业车间的成套订单调度问题是以加权订单成套率作为目标函数,因此与其他目标函数的调度问题相比,具有以下特点:

      (1)加权订单成套率和工件交货期有密切关系。当交货期比较宽松时,甚至每个工件都能按时完工,进而每个订单都满足成套性要求,此时加权订单成套率为1;而当交货期设置得比较紧张时,未成套订单所包含的工件都具有较大的交货时间瓶颈,而且很难将其交货时间瓶颈削减至0。

      (2)难跳出局部最优状态。搜索过程停滞时,搜索结果的进一步改进需要加权订单成套率的进一步提高,即需要未成套的订单满足成套要求,而未成套订单可能包含多个工件,需要将每个工件的交货时间瓶颈削减到0才能满足成套要求。与以makespan作为目标函数的调度问题相比,显然成套订单调度问题的搜索过程更难跳出局部最优的状态。

    • 与其他种类蚁群算法(AS、ACO)相比,MMAS具有相对更好的搜索效果,但它仍然存在和其他元启发式算法相同的缺陷:全局寻优能力较强,局部搜索能力弱,迭代达到一定代数后,信息素集中在某条路径,种群同化现象严重,容易陷入局部最优。为了避免蚂蚁种群的过早同化,弥补群智能算法局部搜索能力的不足,本文针对成套订单调度问题的特点提出了一种新的邻域结构,结合MMAS得到带有邻域结构的最大最小蚂蚁系统(MMAS-NS)。MMAS-NS的流程如图1所示。

      图  1  具有邻域结构的最大最小蚂蚁系统流程图

      Figure 1.  Flowchart of MMAS-NS

    • 解的编码方式采用扩展的基于工序的编码方式。解个体由两部分组成:基于工序编码的工序加工顺序序列(OS)、基于机器编码的工序加工机器序列(MS)。OS段的数字代表工件,数字出现的次数代表该工件对应的工序;MS段依次代表工件工序的加工机器。一种FJSP的编码方式如图2所示。

      图  2  一种FJSP的编码方式

      Figure 2.  An encoding method of FJSP

    • 算法在150代内震荡幅度不超过5%时终止迭代过程。

    • 订单未成套的原因在于订单中存在工件完工时间超过规定交货期,要想该订单成套,需要削减和消除订单中瓶颈工件的交货时间瓶颈。对于订单h中的瓶颈工件i,其交货时间瓶颈定义如下:

      $B_i^h > 0$时,工件完工时间晚于规定交货时间,称工件具有交货时间瓶颈,该工件称为瓶颈工件,包含瓶颈工件的订单称为瓶颈订单。

      Nowicki等[10]针对作业车间下makespan最小化问题提出了有效邻域结构N5,利用关键块首和块尾工序交换缩短关键路径的长度;类似地,针对成套订单问题,重新选择针对瓶颈工件的关键路径,并利用类似N5的工序交换操作可以缩短瓶颈工件的关键路径长度,当瓶颈订单内所有瓶颈工件的交货时间瓶颈削减到0时,加权订单成套率得到提高。

      本文提出的新的邻域结构的主要思想:首先要选择迭代最优解Xiter-best或者全局最优解Xglobal-best作为邻域搜索的个体,然后选择该个体中未成套订单中权值较大的订单,接着选择该订单中交货时间瓶颈较大的瓶颈工件。由被选择工件的尾工序开始,从后向前选择一条关键路径,参考N5邻域结构进行关键工序位置交换产生新的解,再根据订单加权成套率对新产生的邻域解进行贪婪选择,重复以上过程直到不能继续对任何工件的交货时间瓶颈进行削减。

      邻域搜索算法结构如图3所示。图4为邻域搜索后的调度甘特图。在8工件5订单的情况下,假定绿色虚线是订单5中工件7的交货期,邻域搜索前工件7完工时间在交货期之后,在进行了工序O72向前插空在O83之前的操作后,工件7的尾工序O73的完工时间减小到13,因此订单5成套,其他工件的完工时间不变,加权订单成套率上升。

      图  3  邻域搜索算法流程图

      Figure 3.  Flowchart of neighborhood search algorithm

      图  4  邻域搜索后调度甘特图

      Figure 4.  Gantt chart of scheduling after neighborhood search

    • 待搜索解的选择:在邻域搜索过程中贪婪选择订单加权成套率高的解,当两个或多个解的订单加权成套率相同时,选择加权瓶颈小的订单(因为该解权值较高的未成套订单的交货时间瓶颈相对较小),订单加权瓶颈表示如下:

      瓶颈订单(Choosed_order)的选择:因为进行邻域搜索的解即为蚁群算法较优的解,可优化空间较小,所以直接选择未成套订单中权值最大的订单。若两个订单权值相同,选择订单总交货时间瓶颈较小的订单。

      瓶颈工件(Choosed_job)的选择:选择交货时间瓶颈大的工件。工件交货时间瓶颈越大越难以消除,若该工件瓶颈无法完全消除,可直接放弃对该订单的优化进行下一个订单的优化。

    • 本文的邻域结构不改变工序的加工机器,只改变工序间的相对位置。

      关键路径的选取:首先建立空的关键路径工序集Set_CriticalPath,将Choosed_job的最后一道工序放入关键路径。设关键工序集Set_CriticalPath中首道工序为${O_{\rm{first}}}$,若${O_{\rm{first}}}$存在同机紧前工序和同件紧前工序,则分别为${M_P}[{O_{\rm{first}}}]$${J_P}[{O_{\rm{first}}}]$。若${J_P}[{O_{\rm{first}}}]$的结束时间与${O_{\rm{first}}}$的开始时间相同,则选择${J_P}[{O_{\rm{first}}}]$加入关键工序集Set_CriticalPath,否则选择${M_P}[{O_{\rm{first}}}]$加入关键工序集Set_CriticalPath,直到${O_{\rm{first}}}$的开始时间为0。如图5所示甘特图中关键工序集为{O11,O12,O31,O23}。

      图  5  关键路径示意图

      Figure 5.  Schematic diagram of critical path

      可交换工序对和工序交换:工序交换使用N5邻域结构,N5邻域结构被证明是一种速度较快、效果较好的邻域结构。同机相连的关键工序形成关键块。对于首关键块,只交换块尾工序和块尾的同机紧前工序;对于中间关键块,可交换块首工序和块首的同机紧后工序,也可以交换块尾工序和块尾工序的同机紧前工序;对于尾关键块,只交换块首工序和块首工序的同机紧后工序。需要注意的是,若相邻工序属于同一个工件,则不能交换。

      邻域解生成:对于任意被选择的解个体,构造其邻域解时需要对关键路径中的可交换工序对分别进行工序位置交换,其他工序位置不变。由此所得到若干邻域解的适应度值需要重新计算。当存在邻域解的适应度值大于当前解时,则利用该邻域解替换当前解。

    • 成套订单调度问题优化难度较大,因此本文的测试实例是在已有FJSP实例基础上加入工件的交货时间、订单的工件分布情况、订单权值生成。其中工件交货时间在一定范围内随机生成,订单数量、订单情况(包含哪些工件)、订单权值随机生成。随机生成规则:每个订单包含的工件采用随机插入方法生成;订单数量、订单权值由式(8)生成。

    • 影响蚁群算法的参数主要有:蚂蚁数量Npop、信息素残留系数ρ、信息启发式因子α、期望启发式因子β等。本文通过正交试验方式对算法主要参数进行分析。正交试验使用的实例是20工件5机器11订单测试实例,工序时间表见文献[11]。正交试验因素和水平设置如表1所示。

      FactorNpopραβ
      Level 1500.70.50.5
      Level 21200.911
      Level 32000.9522

      表 1  正交设计因素和水平表

      Table 1.  Factors and levels of orthogonal design

      根据正交表给出的每一组因素水平组合情况,进行10次试验取平均值并做方差分析。

      图6示出了不同因素水平下目标函数95%置信度LSD区间均值。从图5可以看出,算法性能与Npopρα相关,与β无关。随着Npop的扩大,搜索次数增加,对解空间的搜索更加彻底,算法全局搜索能力增强,解的质量将有所提高,但搜索周期会相应变长;随着ρ的增长,信息素蒸发速度降低,算法可以持续进行更大范围的搜索,解的质量将有所提高,但收敛速度将减慢;α越低,搜索对信息素浓度的敏感性降低,当各条路径上信息素浓度差别较大时,较低的α可以使信息素浓度不同带来的影响减小,收敛速度减慢,搜索时间更长,得到更好的解,反之若α较大将会使这种浓度的差别指数级放大,加快收敛速度,往往会造成搜索收敛到局部最优解;β只在搜索开始阶段信息素浓度信息匮乏时引导搜索进行,随着迭代的进行,各路径间信息素浓度τ的差别逐渐增大,所以随着搜索的进行,β的作用越来越小。本文算法参数设置如下:Npop=200,ρ=0.95,α=0.5。

      图  6  不同因素水平下目标函数95%置信度LSD区间均值图

      Figure 6.  Prediction interval graphs of objective function at different factors and levels

    • 为了验证本文提出的邻域搜索算法的有效性,对小、中、大3种规模实例进行仿真实验。选取未加入邻域结构的MMAS作为对比算法,对每个实例分别利用MMAS-NS和MMAS进行10次仿真,MMAS算法参数设置和MMAS-NS相同,记录迭代过程平均值并作收敛曲线图,通过对比两种算法的收敛结果说明MMAS-NS算法的有效性。

    • 小规模算例包括文献[12]中的改编测试实例(8工件8机器6订单(实例1))和根据文献[13]提出的Mk01改编的实例(10工件6机器8订单(实例2))。两个算例的订单数量、订单所含工件、订单权值均采用随机方式生成。小规模算例的收敛曲线如图7所示。

      图  7  两个小规模测试实例下的算法收敛曲线图

      Figure 7.  Algorithmic convergence curves for two small-scale test instances

      图7可知,小规模实例下MMAS-NS和MMAS算法都能达到较好的寻优效果。因为实例规模较小,虽然未改进的MMAS也可以达到和MMAS-NS相近的寻优效果,但MMAS-NS每次搜索的结果更加稳定。以实例1为例,MMAS在10次优化仿真中有4次陷入了局部最优解,而MMAS-NS的搜索结果每次都能达到MMAS搜索结果的最优值,因此目标函数的平均收敛曲线收敛到了更好的值。由于搜索初始阶段信息素浓度信息缺乏,且没有采用精英保留策略,采用最早完工准则选择机器的方式本身可以构造较优的初始解,因此收敛曲线初始阶段可能出现下降情况。

    • 中等规模算和大规模实例由文献[14]提出的测试实例(实例3)和文献[13]提出的Mk10(实例4)改编而成。收敛曲线如图8所示。

      图  8  中等规模和大规模测试实例下的算法收敛曲线图

      Figure 8.  Algorithmic convergence curves for medium and large scale test instances

      图8表明,在中等规模的实例3中,MMAS-NS比MMAS寻优性能有很大提升,针对改造的Case3,加权订单成套率从0.6提升到了0.78,并且在200代以后寻优速度有了明显提升。与小规模实例不同,当问题规模提升后没有采用邻域搜索的MMAS搜索能力有限,而邻域搜索算法可以有效提升加权订单成套率,尤其是只含有单一工件的订单。以两种算法仿真结果中目标函数值的众数为例,10次MMAS仿真结果众数为0.5917,对应满足成套性的订单为1、4、6、7、10;10次MMAS-NS仿真结果众数为0.7847,对应满足成套性的订单为1、3、4、5、6、7、10,MMAS-NS在MMAS实现的成套订单基础上又实现了3、5的成套,而3、5都是单工件订单。由于是针对订单中的单一工件采用N5邻域结构优化(将该工件的尾工序作为关键路径的尾工序),该工件的加工时间可以有效减小,因此该订单将成套,加权订单成套率提升。大规模测试实例的收敛曲线显示,MMAS-NS针对大规模算例也有比MMAS更好的寻优性能,分析过程和中等规模算例类似,不再赘述。

    • 为了说明加入邻域搜索过程后MMAS-NS算法性能的优越性,本文针对不同规模下成套订单调度问题的测试实例进行仿真验证。选择最大最小蚂蚁系统(Max-Min Ant System,MMAS)、帝国竞争算法(Imperialist Competitive Algorithm,ICA)、带邻域结构的帝国竞争算法(Imperialist Competitive Algorithm with Neighborhood Structure,ICA-NS)作为对比算法。MMAS-NS和ICA-NS具有2.2节所述邻域结构。MMAS-NS和MMAS的算法参数根据3.1节分析结果进行设置,ICA和ICA-NS算法参数设置参考文献[18]进行,ICA-NS和ICA的区别是在ICA每完成一次迭代后对最强帝国代表的解个体进行邻域搜索。对每一个测试实例进行10次仿真,并对仿真结果进行以下指标的分析仿真结果如表2所示。n为总工件数,m为机器数,o表示订单数,最大加权订单成套率(Maximum Whole-Set Orders,Max)、最小加权订单成套率(Minimum Whole-Set Orders,Min)、平均加权订单成套率(Average Whole-Set Orders,Avg)、均方差(Standard Deviation,Std)。

      Problemn×m×oAlgorithmMaxMinAvgStd
      Case8×8×6IACO0.733 60.733 60.733 6
      MMAS0.733 60.651 70.717 20.036 6
      IICA0.733 60.733 60.733 6
      ICA0.733 60.651 70.700 80.044 9
      Mk0110×6×8IACO0.909 20.895 50.906 50.006 1
      MMAS0.909 20.754 10.806 20.019 5
      IICA0.909 20.812 70.889 90.043 2
      ICA0.812 70.724 80.793 00.028 7
      Mk0210×6×6IACO0.900 50.773 80.841 00.048 5
      MMAS0.900 50.773 60.807 10.052 4
      IICA0.900 50.763 10.836 90.047 6
      ICA0.900 50.763 10.814 00.050 4
      Setb4xx15×12×7IACO0.841 60.765 70.806 00.029 8
      MMAS0.755 60.652 60.695 30.069 0
      IICA0.767 30.650 50.701 90.056 1
      ICA0.742 40.652 60.688 10.069 5
      Setb4xxx15×13×10IACO0.865 60.727 80.789 50.049 2
      MMAS0.650 60.570 10.619 90.054 5
      IICA0.687 80.606 30.635 00.051 0
      ICA0.644 60.570 10.636 50.054 6
      seti5xyz15×18×9IACO0.799 70.675 30.737 70.061 4
      MMAS0.675 70.575 60.632 00.089 0
      IICA0.725 30.627 10.656 90.076 4
      ICA0.675 30.562 00.625 00.076 1
      Mk0820×10×11IACO0.854 30.707 50.733 30.104 1
      MMAS0.612 10.485 50.534 10.091 0
      IICA0.707 60.542 10.629 80.127 3
      ICA0.635 10.485 50.545 20.115 0
      Mk0920×10×15IACO0.727 80.658 80.696 50.065 2
      MMAS0.628 20.468 40.546 70.148 5
      IICA0.639 80.498 80.565 00.112 5
      ICA0.609 30.468 40.525 30.136 7
      Mk1020×15×12IACO0.654 10.387 80.540 40.113 3
      MMAS0.532 20.252 70.395 60.144 3
      IICA0.559 00.364 90.436 80.126 8
      ICA0.516 00.205 30.395 30.156 1

      表 2  4种算法在不同算例下的仿真结果对比

      Table 2.  Comparison of simulation results of four algorithms under different instances

      表2可知,当实例规模较小时,4种算法都能找到较好的解,而且加入邻域搜索的MMAS-NS和ICA-NS多次仿真的均方差均为0,说明在小规模测试实例下,加入了邻域结构的两种算法每次都能找到最优解。随着测试实例规模的扩大,不加入邻域搜索的MMAS和ICA仿真结果均值(Avg)大致相同,与MMAS-NS和ICA-NS相比结果较差,说明MMAS-NS和ICA-NS在中等规模和大规模实例下表现出更加良好的寻优性能,进而说明了邻域搜索结构的有效性。在中等规模和大规模测试实例下,MMAS-NS比ICA-NS的均值更好,这是因为MMAS-NS的机制是在每次迭代后,针对迭代最优解个体Xiter_best进行邻域搜索,而在MMAS的初始阶段几乎每次迭代的最优解都是不相同的,因而在MMAS的基础上加入邻域搜索可以对解空间进行更广阔的搜索;ICA算法具有收敛速度快的特点,而帝国和殖民地之间是进行有条件的更替,每次迭代最强帝国不一定改变,换句话说,ICA是自带精英保留策略的搜索算法,最强帝国一直是全局最优解(精英解),因而ICA-NS对解空间的搜索不如MMAS-NS充分,因此MMAS-NS有比ICA-NS更好的全局寻优效果。

      为了更加清楚地表现MMAS-NS和3种算法的搜索过程,绘制4种算法在中等规模实例的平均收敛曲线如图9所示。可以看出加入了邻域搜索后的两种改进算法相比原有的算法性能都得到了提升,而且MMAS-NS可以达到最好的寻优效果。ICA和ICA-NS收敛速度较快,但基于帝国竞争算法改进的ICA-NS存在邻域搜索不够充分的缺点,不过性能比ICA仍然有一定的提升。

      图  9  测试实例Case3的收敛曲线图

      Figure 9.  Convergence curves of case3 problem

    • 成套订单调度问题是一种在实际生产过程中广泛存在并亟待解决的调度问题,但由于该问题的复杂性,目前的相关研究主要集中于单机环境且研究成果较少。本文提出了一种新的基于柔性作业车间环境下的加权成套订单调度模型,分析了解决该问题的难点,并针对问题特点提出了一种新的邻域结构。针对瓶颈订单内包含的瓶颈工件,通过反复削减工件的交货时间瓶颈,最终达到提高加权订单成套率的目的。在不同规模实例下,通过MMAS-NS和MMAS的仿真结果对比,验证了该邻域结构的有效性。为了进一步表明算法的有效性,与帝国竞争算法ICA等其他元启发式算法的仿真结果进行了对比,说明了MMAS-NS在搜索性能方面的优越性及其他算法存在的不足。以上结论仅限于柔性作业车间环境下的研究,实际生产中的模型将会更加复杂。另外解个体中工序加工机器分配使用的是工序最早完工准则,如果考虑工序加工机器的安排,邻域搜索该如何改进,算法性能是否会有进一步的提升,是下一步需要考虑的问题。

(9)  表(2) 参考文献 (19) 相关文章 (20)

目录

    /

    返回文章