作业车间调度问题的杂草优化算法求解

黄　霞　叶春明　包晓晓

1(上海理工大学管理学院　上海 200093)2(江苏科技大学　江苏 张家港 215600)



作业车间调度问题的杂草优化算法求解

黄霞1,2叶春明1包晓晓1

1(上海理工大学管理学院上海 200093)2(江苏科技大学江苏 张家港 215600)

摘要针对作业车间调度问题JSP(Job-shop scheduling problem)，提出一种入侵式杂草优化算法。该算法中，子代以正态分布方式在父代个体周围扩散，兼顾全局搜索和局部搜索，并根据迭代次数不同对二者强度进行调节。通过典型算例进行仿真试验，并在反复实验中对算法参数进行修正。测试结果表明杂草算法求解作业车间调度问题的可行性和有效性，优于萤火虫算法和基本粒子群算法，是解决生产调度问题的一种有效方法。

关键词杂草优化算法作业车间调度问题最大完工时间

0引言

作业车间调度问题JSP是许多生产调度问题的简化模型，具有很多实际应用背景。作为一类满足任务配置和顺序约束要求的资源分配问题，JSP已被证明是最困难的约束组合优化问题和典型的NP-hard问题[1]。由于作业调度问题的复杂性，即使在规模较小时，当前要获得最优解仍是非常困难。它的求解难度远大于流水线调度问题，针对其算法的研究一直是学术界和工程界共同关注的重要课题。如何利用有限的资源，满足被加工任务的各种约束，并确定工件在相关设备上的加工顺序和时间，以保证所选择的性能指标最优，即研究如何有效地求解JSP，有着非常重要的理论意义和实用价值。

用于作业车间调度问题的技术与方法主要分为两类：一类是最优化方法；一类是近似方法。用最优化方法只能求解小规模的作业车间调度问题，而且速度很慢。对于大部分规模较大问题都不能用多项式算法求最优解，只能使用近似方法求近似解[2]。其中仿生智能群优化算法(如蚁群算法、粒子群算法、萤火虫算法、布谷鸟算法、杂草算法等以及各种混合智能算法)作为一种有效的近似求解方法，能在较短时间内可以获得较高质量的解，成为复杂优化问题的有效求解途径和国内外研究热点。

杂草算法IWO(invasiveweedoptimization)是由伊朗德黑兰大学的Mehrabian等为解决数值优化问题而首次提出[3]。杂草算法启发于自然界杂草丛生现象，它是模拟杂草殖民扩张过程而形成的一种仿生智能群优化算法。与经典的优化方法相比，IWO算法具有结构简单，鲁棒性强，易于理解和编程等特点。IWO算法作为一种数值优化算法，主要针对连续空间的浮点数问题而设计，适合求解具有连续变量的函数优化问题。目前，IWO算法已经成功应用于DNA编码顺序计算问题[4]、压电激励器的优化放置问题[5]、优化组合问题[6],天线阵列设计问题[7]等多个领域。

杂草算法在生产调度中的应用相对较少，在国内外有关此方面的文献目前只有少数几篇。文献[8]提出基于杂草搜索的方法解决中间buffers的流水车间调度问题，其目标函数是最小化最大完工时间。文献[9]将杂草算法应用于流水线车间调度，求解置换流水车调度问题和无等待流水车间调度问题。目前还未见到采用IWO算法求解作业调度方面的研究。因此，本文尝试运用IWO算法求解作业车间调度问题。首先从分析杂草算法的优化机理着手，设计一种基于升序排列(ROV)的操作编码，实现杂草连续位置到所有工序排列的转换。在此基础上应用杂草优化算法求解作业车间调度问题，经过反复实验和不断修正，设置出性能较好的参数值，并将求得的结果与其他两种算法相比较。算例测试结果证明IWO算法有较强的寻优性能和良好的鲁棒性。

1作业车间调度问题的数学描述

作业车间调度问题是具有特殊工艺特性和加工环境的最典型和最重要的调度问题。作业车间调度问题可描述为：n个工件在m台机器上加工，第i个工件在第j台机器上的操作时间Pij为已知，要求确定与工艺约束条件相容的各机器上所有工件的加工次序，使加工性能指标达到最优。除工艺约束外，通常还假定每一时刻每台机器只能加工一个工件，且每个工件只能被一台机器所加工，同时加工过程为不间断，机器间缓冲区容量为无限，不考虑工件加工的优先权。

关于JSP的求解往往要考虑生产调度实际期望达到的优化指标，问题的目标函数是这些优化指标的抽象表示。通常JSP所考虑的优化目标有三种：任务的最大完工时间最短、任务总的拖期最短和任务的提前/拖期惩罚代价最小。本文所考虑的优化目标是任务的最大完工时间最短，即完成所有任务所需的时间最短，对该指标的优化有利于提高单位时间内设备的利用率，从而提高生产的实际效率。常见的作业车间调度问题基本数学模型有三种：整数规划模型、线性规划模型和析取图模型。本文采用Baker[10]给出的JSP整数规划模型，下面是调度问题n/m/G/Cmax的一个整数规划模型描述：

(1)

Subjectto:

cik-pik+M(1-aihk)≥cih

(2)

cjk-pjk+M(1-xijk)≥cik

(3)

cik≥0

(4)

(5)

(6)

上述公式中所涉及的符号含义如下：i=1,2,…,n；h,k=1,2,…,m；cik和pik分别为第i个工件在机器k上的完成时间和加工时间；M是一个足够大的正数；aihk和xijk分别为指示系数和指示变量。式(1)表示目标函数，即最小化最大完成时间Makespan；式(2)表示工艺约束条件决定的每个工件的各个操作的加工先后顺序；式(3)表示加工各个工件的各机器的先后顺序，同是也保证在同一时刻一个工件不会分配给两台机器，以及两台机器不会同时加工一个工件；式(4)表示完工时间变量约束条件；式(5)和式(6)分别表示指示系数和指示变量可能的取值大小。

2杂草算法的优化机理

2.1杂草算法的基本原理

杂草专指那些生命力极其旺盛，具有入侵式的殖民化特点，可以生长于地球上的任何一块地方的植物。即使有除草剂的出现，杂草仍以其旺盛的生命力和顽强的意志力遍布地球的每一个角落。杂草入侵的一般过程是适应环境、乘机居留、占据地盘、结籽繁殖、扶养种群、随机应变、逐渐密集、适者生存、竞争消亡适应性好的个体获得更多的生存机会。杂草算法是一种基于模拟杂草入侵过程的数值优化计算方法。

2.2杂草算法的数学描述与分析

在基本IWO中，杂草表示所求问题的可行解，种群是所有杂草的集合。进化过程中，杂草通过繁殖产生种子，种子通过空间扩散，生长成杂草，如此反复。当种群中杂草数量达到预先设定的最大种群规模时，不是简单的从父代中筛选优秀个体进行繁殖，而是先让所有个体都自由繁殖和扩散后，再将父代和子代一起按适应度值排列并进行优选。通过以适应度为基准的繁殖机制，杂草算法使其产生的解在不可行和可行之间不断转化。这种机制给予那些适应度值差的个体繁殖机会，如果它们后代的适应度值好，这些后代仍有机会生存下来，这样能在最大限度上保留有用信息，也可以避免早熟和陷入局部最优。

杂草繁殖种子的数目与杂草的适应性成正比，通常适应度高的杂草产生种子较多，而适应度低的杂草产生种子较少。杂草产生种子的公式为：

(7)

其中，f为当前杂草的适应度值，fmax和fmin分别为当前种群中所生长的杂草的最大和最小适应度值；smax和smin分别表示一个杂草能产生种子的最大值和最小值。杂草产生的种子按平均值为0，标准差为σ的正态分布，扩散在父代杂草周围。种子生长位置与父代杂草的距离称为随机步长D∈[-σ，σ]，具体σ的计算公式如下：

(8)

式中iter为当前进化代数，itermax为最大进化代数，σ为当前标准差，σinit和σfinal分别为标准差的最初值和最终值，n为非线性调和因子。

杂草算法中，子代是以正态分布方式在父代个体周围扩散。在迭代初期σ较大，通过大的标准差值，使种子能以正态分布的方式扩散到距离父代杂草很远的地方，此时种群勘探能力较强(r选择)，对应于杂草算法的全局探索。随着迭代次数增加，当迭代进行到后期时，标准差σ逐渐变小，种子分布在距离父代杂草较近的地方，种子的扩散范围缩小，原先的优势群体较容易得到兴盛发展。此时开采能力较强(k选择)，对应于杂草算法的局部搜索。杂草算法兼顾全局搜索和局部搜索，并根据迭代次数不同对二者强度进行自适应性调节。

IWO的主要步骤如下:

1) 杂草种群初始化，随机初始化N颗杂草；

2) 杂草按式(7)产生相应个数的种子；

3) 杂草的种子按式(8)以随机步长进行空间扩散并生长为杂草，进入杂草种群；

4) 判断种群是否达到预设的最大种群规模，如满足则进行优先排序，并选择出适应度好的最大种群规模数个体，否则直接转到2)；

5) 判断是否达到最大迭代次数，若满足则输出最优解，并终止，否则转到2)。

3杂草算法求解作业车间调度问题

3.1编码方式

杂草优化算法主要适用于求解连续空间域的优化问题，而调度问题是离散空间的非数值优化问题。因此，应用杂草优化算法求解调度问题需在连续空间的染色体与离散空间的调度解之间建立一种对应关系。本算法采用一种基于工件升序排序ROV(rankedordervalue)的随机键编码方式[12]，用于实现从染色体连续位置矢量到工件排序的转换。对于n个工件m个机器的作业车间调度问题，基于工序的编码方法将每个染色体用n×m个代表工件基因组成，来表示一个工序排列，在这种工序排列中每个工件号均出现m次，可以隐式地保证工件的技术约束。

一条染色体位置矢量可以表示为Xi={xi,1,xi,2,…,xi,n×m}，则其对应工序初始排列为1,…1,…,j,…,j,…,n,…,n,其中j(0

3.2算法流程

上述编码规则中的染色体对应为算法中的杂草个体。根据上述ROV编码规则，杂草个体位置可以转换为一个工序排列，每个工序排列的Makespan作为杂草个体的适应度值。求解作业车间调度问题的杂草优化算法流程如下：

1) 初始化算法基本参数：设置初始杂草个数、最大杂草个数、问题的维数、扩张区间大小、最大最小种子数、初始标准差和最终标准差，以及最大迭代次数。

2) 随机产生初始化杂草种群，按照3.1节所述基于工序的编码规则，将种群中每一颗杂草位置转换为工序排列，计算对应工序排列的Makespan，作为适应度值。

3) 开始迭代，按式(7)对杂草种群的每一颗杂草，产生相应数目的种子；杂草的种子按式(8)以随机步长在一定范围内进行空间扩散并生长为新的杂草，对每一颗新杂草计算相应工序排列的Makespan，作为其适应度值，并将新杂草加入到杂草种群中。

4) 判断杂草种群是否达到预设的最大种群规模，如满足则按竞争性生存法则进行优先排序，选择出适应度值排在前面的最大种群规模数个体，并保存当前最优适应度值；否则直接转到3)。

5) 判断是否达到最大迭代次数，若满足则输出所有保存的适应度值中的最优解，并终止；否则转到3)。

4仿真实验

为了验证IWO算法求解作业车间调度问题的有效性及其性能，选择Taillard[13]提出的作业车间调度基准测试数据来进行验证。随机选取LA类的11个基准问题作为算例来进行仿真测试，并与基本粒子群算法BPSO[14](Basicparticleswarmoptimization)和萤火虫算法FA[15](FireflyAlgorithm)的实验结果进行比较验证算法的有效性。测试环境：操作系统Win8，处理器3.20GHz，CPUIntel(R)Core(TM)i5，内存4GB，采用MATLABR2010a实现算法编程。经过反复实验将杂草算法中参数设置如下性能较佳，初始杂草个数10，最大杂草个数45，初始标准差2，最终标准差0.001，最大种子个数20，最小种子个数1，非线性因子n=4。其他两种算法参数设置分别参照文献[14]和文献[15]，基本粒子群算法中，粒子数n=30，学习因子c1=0.8，c2=1.2，惯性权重w=0.5；萤火虫算法中，萤火虫数n=30，光强吸收系数γ=1.0，最大吸引度β0=1.0，步长因子α=0.2。每一种算法都是迭代100次，各自独立运行20次。测试结果如表1所示。

表1　三种算法优化结果对比分析

表1中，C*为问题已知最优值；Δmin为最小完工时间；Δmax为最大完工时间；Δavg为平均完工时间；Δstd为完工时间标准方差(其中Δavg、Δstd为四舍五入后所得结果)；加粗的数字代表最优值。为比较各算法性能，本文对测试问题的上面4项指标进行衡量。从测试数据可以看出，IWO算法的测试结果整体性能优于BPSO和FA算法。表中显示IWO算法有8个问题找到最优值，BPSO算法有7个问题找到最优值，FA算法仅有4个问题找到最优值。在独立运行20次中，IWO算法对LA01、LA05、LA06、LA10、LA11、LA12和LA14都能达到100%的寻优率，其他两种算法均未能达到100%寻优率。而对于未能找到最优值的LA03、LA08、LA17和LA20，IWO的4项指标均比BPSO和FA要小，反映出IWO算法具有良好的鲁棒性。

为了对比显示IWO算法求解作业车间调度问题的寻优效果，选取LA06问题对于这三种算法BPSO、FA和IWO各独立运行30次的最优结果进行演示。算法参数设置如前所述，最优结果显示如图1所示。每种算法均独立运行30次中，就寻优能力而言，IWO算法30次全部击中已知最优值，BPSO算法有20次击中最优值，FA算法只有2次击中最优值。从FA和BPSO运行结果的波动曲线来看，FA的波动曲线起伏最大，BPSO的起伏较平稳，但表现出一定的间断性。从图1对比寻优结果来看，无论从寻优次数还是寻优率来看，IWO算法均表现出较卓越的寻优性能。

为了进一步验证IWO算法的收敛性能，分别基于LA10和LA14问题，IWO算法独立运行10次，每次迭代100次的寻优曲线如图2和图3所示。从图2和图3的寻优曲线显示，对于LA10问题和LA14问题，IWO独立运行10次中，每次运行在迭代30次内均一致收敛到最优解，反映出IWO具有较强的收敛性能，在解空间能以较强的探索能力和较快的速度收敛到最优值。

图2　LA10问题运行10次寻优曲线图

图3　LA14问题运行10次寻优曲线图

5结语

本文采用一种新型的仿生智能群优化算法——杂草算法求解最小化最大完工时间的作业车间调度问题。仿真实验表明：杂草算法具有收敛速度快、鲁棒性强等优点。虽然对于较大规模的Job-shop生产调度问题，杂草算法没能搜索到已知最优值，但是相比其他智能算法，更接近最优值。鉴于杂草算法在解决生产调度问题中表现出的良好性能，本文意在抛砖引玉，期待杂草算法能在生产调度问题上有着更广泛的应用前景。下一步研究工作将着重于对IWO算法进行改进，并尝试将改进算法用于研究具有不同约束条件的车间调度问题。

参考文献

[1]GareyMR,JohnsonDS,SethiRavi.Thecomplexityofflowshopandjobshopscheduling[J].MathematicsofOperationsResearch,1976,1(2):117-129.

[2] 王永明,尹红丽,秦开大.作业车间调度理论及其优化方法研究[M].科学出版社,2013.

[3]MehrabianAR,LucasC.Anovelnumericaloptimizationalgorithminspiredfromweedcolonization[J].EcologicalInformatics,2006,1(4):355-366.

[4]ZhangX,WangY,CuiG,etal.ApplicationofanovelIWOtothedesignofencodingsequencesforDNAcomputiong[J].ComputersandMathematicswithApplications,2009,57(11/12):2001-2008.

[5]MehrabianAR,Yousefi-KomaA.Anoveltechniqueforoptimalplacementofpiezoelectricactuatorsonsmartstructures[J].JournaloftheFranklinInstitute,2011,348(1):12-23.

[6]SaravananB,VasudevanER,KothariDP.ASolutiontoUnitCommitmentProblemusingInvasiveWeedOptimizationAlgorithm[C]//InternationalConferenceonPower,EnergyandControl(ICPEC),2013:386-393.

[7]YanYingBai,ShaoqiuXiao,ChangrongLiu,etal.AHybridIWO/PSOAlgorithmforPatternSynthesisofConformalPhasedArrays[J].IEEETransactionsonAntennasandPropagation,2012,61(4):2328-2332.

[8]HongyanSang,QuankePan.Aneffectiveinvasiveweedoptimizationalgorithmfortheflowshopschedulingwithintermediatebuffers[C]//ChinesecontrolandDecisionconference,2013,25:861-864.

[9] 陈欢,周永权.入侵杂草优化算法的改进分析及应用研究[D].广西,广西民族大学,2013.

[10]BakerK.InroductiontoSequencingandScheduling[M].NewYork:JohnWiley&Sons,1974.

[11]KunduD,SureshK,GhoshS,etal.Multi-objectiveoptimizationwithartificialweedcolonies[J].InformationSciences,2010,181(12):2441-2454.

[12]BeanJC.Geneticalgorithmandrandomkeysforsequencingandoptimization[J].ORSAJournalofComputing,1994,6(2):154-159.

[13]TaillardE.Benchmarksforbasicschedulingproblems[J].EuropeanJournalofOperationalResearch,1993,64(2):278-285.

[14] 吴启迪,汪镭.智能微粒群算法研究及应用[M].南京:江苏教育出版社,2005.

[15] 刘长平,叶春明.一种新颖的仿生群智能优化算法:萤火虫算法[J].计算机应用研究,2011,28(9):3295-3297.

INVASIVE WEED OPTIMISATION ALGORITHM FOR JOB SHOP SCHEDULING

Huang Xia1,2Ye Chunming1Bao Xiaoxiao1

1(School of Business,University of Shanghai for Science and Technology,Shanghai 200093,China)2(Jiangsu University of Science and Technology,Zhangjiagang 215600,Jiangsu,China)

AbstractThis paper introduces an invasive weed optimisation algorithm aimed at solving job shop scheduling problem. In this algorithm, the offspring diffuses around the parent individuals in the way of normal distribution, combining the global search and local search and adjusting different strength of both according to the number of iterations. Simulation tests are carried out through typical examples, and in repeated experiments the parameters of the algorithm are corrected. Test results demonstrate the feasibility and effectiveness of IWO in solving job shop scheduling problem, it is superior to the firefly algorithm and basic particle swarm optimisation, and is an effective approach for solving production scheduling problem.

KeywordsInvasive weed optimisation (IWO) algorithmJob shop scheduling problemMakespan

收稿日期：2014-10-25。国家自然科学基金项目(71271138)；上海市一流学科建设项目(S1201YLXK)；沪江基金项目(A14006)；上海理工大学人文社科攀登计划项目(14XPB01)。黄霞，讲师，主研领域：智能算法，生产调度。叶春明，教授。包晓晓，硕士生。

中图分类号TH18TP301.6

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.06.056