SCI论文（www.lunwensci.com）
摘要：为了提高制造业利润和用户满意度，提出了一种改进的人工蜂群算法，解决以加工成本和能耗成本之和为目标的单目标柔性作业车间调度问题。该算法采用一种有效的双层编码方式并结合随机方式和策略选择初始化雇佣蜂的蜜源用以生成质量更好的初始种群，提高了算法寻优能力。在寻优过程中，雇佣蜂阶段采用多父代交叉以及变异，保留优秀个体增加了雇佣蜂阶段种群的多样性；在跟随蜂阶段，采用了两种邻域搜索方式用以解决算法陷入局部最优。最后利用求解柔性作业车间的数据集进行对比实验研究，包括对传统人工蜂群算法的对比，以及对传统遗传算法的对比。对比表明：改进的人工蜂群算法不仅可以求解单目标柔性作业车间调度问题，而且收敛性好，迭代速度较快。
关键词：作业车间调度；单目标；人工蜂群算法；多父代交叉
Research on Flexible Job Shop Scheduling Based on Improved Artificial Bee
Colony Algorithm
Zhang Haonan，Tian Xinping，Sun Mengke
（School of Construction Machinery,Chang’an University,Xi’an 710054,China）
Abstract:In order to increase profits of manufacturing industries and user satisfaction,an enhanced artificial bee colony algorithm is proposedfor single-objective flexible job shop scheduling with the goal of minimizing the sum of processing costs and energy consumption costs.Thealgorithm employs a two-layer encoding method and combines random methods and strategy selection to initialize the food sources of employedbees to generate a better initial population and improve the optimization ability of the algorithm.During optimization,employed bees use multiparent crossover and mutation operations to retain excellent individuals and increase population diversity during the employed bee phase.Inthe onlooker bee phase,two neighborhood search methods are used to solve the problem of falling into local optima.Finally,comparativeexperimental research is carried out using data sets for solving flexible job shops,including comparisons with traditional artificial bee colonyalgorithms and traditional genetic algorithms.Comparison shows that the enhanced artificial bee colony algorithm not only has optimizationcapabilities but also has good convergence and fast iteration speed.
Key words:job shop scheduling;single objective;artificial bee colony algorithm;multi-parent crossover
0引言
作业车间调度问题（Jot shop Scheduling Problem，JSP）通常被定义为旨在优化一个或多个调度标准的决策问题，是最难的组合优化问题之一。柔性作业车间调度问题（Flexible JSP，FJSP）是传统调度问题的扩展。为了解决FJSP，必须考虑两个问题，一是机器分配；另一个是工序排序。机器分配为每项工序分配一台加工机器，而操作排序是将所有工序安排在相应机器上，以获得可行和高质量的解决方案。因此，FJSP比JSP问题更复杂，被列为NP-hard问题[1]。随着“工业4.0”的提出，制造业不能再将完工时间作为基准，有部分研究人员已经开始将能量消耗纳入作业车间的衡量范围内[2-5]。
Mansouri[6]提出一种考虑完工时间和能耗成本的双目标柔性作业车间调度模型，并设计了一种多目标的遗传算法；Luo[7]设计了一种蚁群优化算法将混合流水车间的生产成本和电力成本作为优化目标；Yin[8]针对柔性作业车间中的生产率、能源效率和噪声3个目标，设计了一种多目标遗传算法。关于新型智能算法用于车间调度的研究，Jiang[9]建立了一个以能耗成本、延期成本和最大完工时间为目标的数学模型，设计了一种离散猫群优化算法；Lei[10]提出了一种包含3层编码形式的混合蛙跳算法，平衡了工件加工时的机器负荷和能量消耗。
在众多的智能算法中，人工蜂群算法（Artificial BeeColony Algorithm,ABC）被广泛应用于柔性作业车间调度问题。研究表明，与其他群体智能算法相比较，ABC具有控制参数少，鲁棒性强等优点[11-12]。Li[13-14]提出了一种基于Pareto解集的多目标ABC算法，该算法提出了一种交叉运算，用于模拟蜂群之间的信息分享，此外，还设计了一个快速Pareto档案更新方法，以减少计算时间。传统ABC算法存在局部搜索能力弱，容易陷入局部最优等缺陷[15-16]。以上，为研究能源消耗和加工成本的柔性作业车间提供了重要的理论依据。本文提出的一种改进人工蜂群算法（Improved Artificial Bee Colony Algorithm,IABC）更好地求解柔性作业车间调度问题。
1问题描述和模型建立
其中，式（1）为优化目标：第一项表示加工成本，第二项表示机器在加工状态下的总能耗成本，第三项表示机器在待机状态下的总能耗成本；式（2）表示工序一旦开始加工，不能中断，直至完成；式（3）表示工件的所有工序遵循预先设定的前后顺序来依次完成加工；式（4）表示同一台机器一次加工的工件个数不能超过一件；式（5）表示所有工序只能在一台设备上连续完成加工；式（6）表示0-1变量；式（7）表示0-1变量。
2改进的人工蜂群算法
人工蜂群算法是一种新的群体智能算法，是Kara⁃bog[17-18]在总结了众多的研究成果之后提出的。其灵感来自于蜜蜂群的智能觅食行为，算法主要包括蜜蜂和蜜源两大要素，蜜蜂包括3种蜂群，有雇佣蜂、跟随蜂、侦察蜂，蜜源则是需要解决问题的可行解。算法首先将雇佣蜂与随机产生的蜜源联系起来，然后，每只雇佣蜂在其当前关联的蜜源附近移动到一个新的蜜源，最后在迭代的过程中对蜜源进行评估。在雇佣蜂完成这一过程后，它们与跟随蜂分享蜜源信息，跟随蜂选择满意的蜜源新进跟随。侦察蜂则是按一定规则搜索新的蜜源。上述过程反复进行，直到满足停止的标准。
2.1编码与解码
标准的人工蜂群算法是处理连续函数问题的优化方法，而在柔性作业车间的调度问题则是分配资源的离散性问题，因此需要对工件调度问题进行编码以代替原有形式。在柔性作业车间问题中应当考虑存在的两个问题，首先为工件工序的合理排序问题，其次是已排序好的工件的每一道工序都是有相应的机器集合的，因此需要对符合每一道工序选择符合最终优化目标的机器，以上在此选用双层编码形式。
第一层是工序排序层OS，它使用了一般JSP问题中基于工序的编码：每个基因直接由工件号编码，工序号出现的顺序代表对应工件的工序处理顺序，工件第j次出现代表工件i的第j道工序，假设工序串为[1 1 3 3 1 22]，数字1、2、3表示工件J1、J2、J3，这代表工序顺序为(O11,O12,O31,O32,O13,O21,O22)；第二层是机器分配层MA，每个编码片段上的元素表示为相应工序所选择的机器号，假设机器串编码为[1 3 4 2 4 2 1]，第一个1表示机器M1被选择用于处理工序O11。
解码过程：按工序系统的顺序解码，并尽可能早地在其可选的处理机器上处理每道工序，以这种方式依次解码，直到所有工序都安排在最早的位置上。
2.2种群初始化
初始种群的质量会影响到算法整体收敛的快慢，如果完全采用随机方法得到初始种群，那么初始解随机性过强；若完全采用策略选择则初始解不能达到很好的分散性，初始解质量难以得到保证，这必然会影响搜寻最优预测解的能力，导致需要通过增加迭代次数和种群大小为代价来获得最优解，进而提高了优化成本。因此，生成一个质量较好的初始种群是该算法的关键步骤，因此本文对工序串和机器串分别设计了相应的初始化规则，最终得到一个规模为Psize的种群。
对于Ma的初始化，采用随机选择Ma，全局最小处理时间Mb和最小完成时间Mc。对于最小处理时间规则，若某道工序拥有两个或两个以上的可选机器时，选择完成时间较早的机器来处理，该规则考虑了每个工序的完成时间来优化makespan。
对于Os的初始化，采用随机选择Oa，剩余工作量最大Ob和剩余工序数最多Oc。
在机器串的初始化中随机规则Ma的选择概率为50，全局最小处理时间Mb的选择概率为30，最小完成时间Mc的选择概率为20。
在工序串的初始化中随机规则Oa的选择概率为40，剩余工作量最大规则Ob的选择概率为30，剩余工序数最多规则Oc的选择概率为30。上述所有的初始化方法都是优先进行机器分配，然后再进行工序操作。
2.3雇佣蜂操作
结合本文所要优化的目标函数以及FJSP，提出了一种对传统人工蜂群中雇佣蜂阶段的改进IM操作，对工序排序串进行多父代交叉（Multi-parent Crossover，MX）操作，这种交叉方式不会产生非可行解，而且还能将父代的优良基因遗传到子代。
（1）交叉操作
首先通过初始解求得目标函数值，其次计算适应度值，然后选取适应度值最大的工序串为全局最优解。具体操作过程如下。
2.4跟随蜂操作
跟随蜂的主要任务是接受雇佣蜂的蜜源信息。传统人工蜂群算法中的跟随蜂采用随机的方式进行搜索，不保证搜索后一定会得到更好的蜜源。因此本文提出一种自适应变邻域搜索方法，是算法在搜索过程中自适应地选择搜索效率高的邻域进行搜索。这保证了算法向更好的蜜源方向发展，增强了算法的局部搜索能力，本文设计了两种不同的邻域结构。
（1）邻域结构N1
步骤1：随机选择两个工件J1和J2，使J1的操作数小于J2的操作数，并分别记录工件J1和J2的工序位置。
步骤2：从左到右，将工件J1的每道工序依次放入工件J2工序所在位置，并将J2的工序填入剩下的位置。
例如，工序的编码为3 2 1 2 3 1 1，随机生成两个工件J1和J2，1和3。由于工件3的操作数小于工件1的操作数，所以设置J1=3，J2=1。交换了J1和J2的操作后，新的编码顺序为1 2 3 2 1 3 1。
（2）邻域结构N2
步骤1：随机选择片段t，片段t的长度小于工序编码长度。
步骤2：将片段的顺序反转，重新插入到原位置。
例如，工序编码为3 2 1 2 3 1 1，随机选择工序片段2 1 2 3 1，经过操作，新的工序编码为3 1 3 2 1 2 1。
2.6算法流程
根据上述改进分析，用于解决单目标柔性作业车间问题的算法如下。
步骤1：初始化种群以及设置参数。
步骤2：计算适应度值，雇佣蜂实行交叉和变异操作。
步骤3：跟随蜂实行邻域操作N1和N2。
步骤4：判断蜜源是否达到最大搜索次数，若满足条件则雇佣蜂转为侦察蜂，搜索新蜜源，否则转到步骤5。
步骤5：判断算法是否达到最大迭代次数，如果是，则算法结束；如果未达到最大迭代次数，则跳转到步骤2。
3试验分析
为了验证IABC在求解FJSP问题时的有效性，选取Luan[19]的5个测试集RM01-RM05。
4结束语
本文提出了一种改进的人工蜂群算法来讨论单目标柔性作业车间调度问题，单目标柔性作业车间考虑了加工成本和能耗成本之和。在改进算法中，通过随机和规则选择的策略来初始化种群，这样即增加了种群的多样性，平衡了同时间内机器运行数目和能耗，同时也避免了过于依赖规则导致算法早熟。在雇佣蜂阶段采用一种多父代交叉的方法来加快整个算法的搜索速度，增强种群的多样性；在跟随蜂阶段，利用雇佣蜂提供的蜜源信息，采用自适应邻域搜索方法，有效地在最优解附近搜索全局最优解，从而防止最优解的丢失。最终通过5个算例进行了对比试验，对比算法包括改进的人工蜂群算法和传统人工蜂群算法，以及传统的遗传算法，对比实验证明IABC算法具有优秀的寻优能力和收敛性。
参考文献：
[1]Brucker P,Schlie R.Job-shop scheduling with multi-purposemachines[J].Computing,1990,45(4):369-375.
[2]Lei D M,Guo X P.An effective neighborhood search for schedul⁃ing in dual-resource constrained interval job shop with environ⁃mental objective[J].International Journal of Production Econom⁃ics,2015,159:296-303.
[3]May G,Stahl B,Taisch M,et al.Multi-objective genetic algo⁃rithm for energy-efficient job shop scheduling[J].InternationalJournal of Production Research,2015,53(23):7071-7089.
[4]Yildirim M B,Mouzon G.Single-Machine Sustainable Produc⁃tion Planning to Minimize Total Energy Consumption and TotalCompletion Time Using a Multiple Objective Genetic Algorithm[J].IEEE Transactions on Engineering Management,2012,59(4):585-597.
[5]Zhang R,Chiong R.Solving the energy-efficient job shop sched⁃uling problem:a multi-objective genetic algorithm with en⁃hanced local search for minimizing the total weighted tardinessand total energy consumption[J].Journal of Cleaner Production,2016,112:3361-3375.
[6]Mansouri S A,Aktas E,Besikci U.Green scheduling of a twomachine flowshop:Trade-off between makespan and energy con⁃sumption[J].European Journal of Operational Research,2016,248(3):772-788.
[7]Luo H,Du B,Huang G Q,et al.Hybrid flow shop scheduling con⁃sidering machine electricity consumption cost[J].InternationalJournal of Production Economics,2013,146(2):423-439.
[8]Yin L J,Li X Y,Gao L,et al.Energy-efficient job shop schedul⁃ing problem with variable spindle speed using a novel multi-ob⁃jective algorithm[J].Advances in Mechanical Engineering,2017,9(4):21.
[9]Jiang T H,Deng G L.Optimizing the Low-Carbon Flexible JobShop Scheduling Problem Considering Energy Consumption[J].IEEE Access,2018,6:46346-46355.
[10]Lei D M,Zheng Y L,Guo X P.A shuffled frog-leaping algo⁃rithm for flexible job shop scheduling with the consideration ofenergy consumption[J].International Journal of Production Re⁃search,2017,55(11):3126-3140.
[11]Peng K K,Pan Q K,Gao L,et al.An Improved Artificial BeeColony algorithm for real-world hybrid flowshop reschedulingin Steelmaking-refining-Continuous Casting process[J].Com⁃puters&Industrial Engineering,2018,122:235-250.
[12]Tasgetiren M F,Yuksel D,Gao L,et al.A Discrete ArtificialBee Colony Algorithm for the Energy-Efficient No-Wait Flow⁃shop Scheduling Problem[C]//25th International Conference onProduction Research Manufacturing Innovation(ICPR)-CyberPhysical Manufacturing,2019.
[13]Li J Q,Pan Q K,Gao K Z.Pareto-based discrete artificial beecolony algorithm for multi-objective flexible job shop schedul⁃ing problems[J].International Journal of Advanced Manufactur⁃ing Technology,2011,55(9-12):1159-1169.
[14]Li Y L,Li F,Pan Q K,et al.An Artificial Bee Colony Algorithmfor the Distributed Hybrid Flowshop Scheduling Problem[C]//25th International Conference on Production Research Manufac⁃turing Innovation(ICPR)-Cyber Physical Manufacturing,2019.
[15]Sharma N,Sharma H,Sharma A.Beer froth artificial bee colonyalgorithm for job-shop scheduling problem[J].Applied SoftComputing,2018,68:507-524.
[16]Xie J,Gao L,Pan Q K,et al.An Effective Multi-Objective Artifi⁃cial Bee Colony Algorithm for Energy Efficient Distributed JobShop Scheduling[C]//International Conference on ProductionResearch.2021.
[17]Karaboga D,Akay B.A comparative study of artificial bee colo⁃ny algorithm[J].Applied Mathematics and Computation,2009,214(1):108-132.
[18]Karaboga D,Basturk B.On the performance of artificial bee colo⁃ny(ABC)algorithm[J].Applied Soft Computing Journal,2008,8(1):687-697.
[19]栾飞,蔡宗琰,吴书强,等.求解低碳车间调度问题的改进鲸鱼算法[J].机械科学与技术,2020,39(5):721-728.
[20]胡中华,赵敏,撒鹏飞.基于人工蜂群算法的JSP的仿真与研究[J].机械科学与技术,2009,28(7):851-856.
关注SCI论文创作发表，寻求SCI论文修改润色、SCI论文代发表等服务支撑，请锁定SCI论文网！ 文章出自SCI论文网转载请注明出处：https://www.lunwensci.com/ligonglunwen/77356.html
