文章快速检索 高级检索

Hybrid multiagent genetic algorithm for job shop scheduling problem
LI Xiaotao, PENG Chong
School of Mechanical Engineering and Automation, Beijing University of Aeronautics and Astronautics, Beijing 100083, China
Received: 2016-01-26; Accepted: 2016-02-29; Published online: 2016-03-07
Foundation item: National Science and Technology Major Project (2015ZX04005005)
Corresponding author. E-mail:pch@buaa.edu.cn
Abstract: For the NP-hard characteristic of job shop scheduling problem (JSP) and big valley property of its solution space, this paper proposes a hybrid algorithm based multiagent genetic algorithm (MAGA) and adaptive simulated annealing algorithm (ASA) to obtain the minimal makespan schedule. First, each chromosome is regarded as independent agent which is randomly initialized under condition of operation-based encoding method. Combined with multiagent cooperation and competition theory, a neighborhood interaction operator is designed to realize the interaction between agents, and then a certain number of agents are utilized to do global searching to find several individuals with high fitness. Second, in order to prevent the algorithm from falling into local optimum, ASA is adopted to carry out local optimization for each agent. Finally, the effectiveness of the proposed hybrid algorithm is verified by the computational results of typical problems from benchmark library.
Key words: job shop scheduling     multiagent (JSP)     genetic algorithm     neighborhood interaction operator     adaptive simulated annealing algorithm (ASA)

1 JSP的析取图模型

JSP定义：N个工件在M台机器上加工，分别记作集合{Ji|i=1, 2, …, N}、{Mi|i=1, 2, …, M}，其中Ji为工件代号，Mi为机器代号。每个工件有特定的工艺，并给定每个工件使用机器的顺序及它在对应机器上的工序所需的加工时间，调度的具体内容就是确定每台机器上工件的加工顺序和每个工序的开工时间，使得最大完工时间(记作Cmax) 最短，并假定：

1) 不同工件的工序之间没有顺序约束。

2) 某一工序一旦开始加工就不能中断，每台机器同一时刻只能加工一个工件，且机器不发生故障。

3) 所有零件均在零时刻到达，且在加工过程中经过每台机器且只经过一次。

 工件 机器序列 加工时间 J1 M3-M2-M1 2-3-6 J2 M1-M3-M2 4-5-2 J3 M2-M1-M3 3-5-4

 图 1 析取图模型 Fig. 1 Disjunctive graph model

2 基于MAGA与ASA混合算法的JSP寻优

2.1 定义染色体agent邻居环境

 (1)
 (2)

 图 2 多智能体网格系统[14] Fig. 2 Multiagent lattice system[14]
2.2 设计邻居交互算子

1) 当个体与其4个邻居进行比较后，其适应度比邻居都要高，则它为一个赢家，相应的内容保持不变。

2) 当个体的适应度比4个邻居中最高适应度的个体要低，那么它便是一个输家，于是它将被适应度最高的邻居占领。

 图 3 轮流交叉算子 Fig. 3 Alternating position crossover operator

 图 4 基本倒位变异算子 Fig. 4 Simple inversion mutation operator

 图 5 移位变异算子 Fig. 5 Displacement mutation operator

2.3 混合算法流程

 图 6 混合多智能体遗传算法流程图 Fig. 6 Flowchart of hybrid MAGA

JSP寻优的具体步骤流程如下：

1) 构造多智能体网格环境

2) 初始化每个agent的编码序列

3) 执行agent交互操作

4) 判断agent交互操作次数Cint是否达到它的最大迭代次数G，若不满足则Cint增加1并回到第3) 步，否则执行第5) 步。

5) 对每个染色体agent进行局部搜索

6) 判断是否满足混合算法的停机准则

3 实例验证 3.1 算法实现

1) 全局搜索参数

2) 基于ASA局部搜索的参数

 (3)

3.2 计算结果分析

 实例代号 实例规模 已知最优解 最好结果 新算法 文献[6] 文献[8] 文献[17] Ft06 6×6 55 55 55 55 55 Ft10 10×10 930 930 930 930 930 Ft20 20×5 1 165 1 165 1 165 1 165 1165 La01 10×5 666 666 666 666 666 La02 10×5 655 655 655 655 655 La03 10×5 597 597 597 597 597 La04 10×5 590 590 590 590 590 La05 10×5 593 593 593 593 593 La06 15×5 926 926 926 926 926 La07 15×5 890 890 890 890 890 La08 15×5 863 863 863 863 863 La09 15×5 951 951 951 951 951 La10 15×5 958 958 958 958 958 La11 20×5 1 222 1 222 1 222 1 222 1 222 La12 20×5 1 039 1 039 1 039 1 039 1 039 La13 20×5 1 150 1 150 1 150 1 150 1 150 La14 20×5 1 292 1 292 1 292 1 292 1 292 La15 20×5 1 207 1 207 1 207 1 207 1 207 La16 10×10 945 945 945 945 945 La17 10×10 784 784 784 784 784 La18 10×10 848 848 848 848 848 La19 10×10 842 842 842 842 842 La20 10×10 902 902 907 902 902 La21 15×10 1 046 1 046 1 052 1 046 1 046 La22 15×10 927 927 930 927 927 La23 15×10 1 032 1 032 1 032 1 032 1 032 La24 15×10 935 938 941 941 940 La25 15×10 977 977 977 977 984 La26 20×10 1 218 1 218 1 218 1 218 1 218 La27 20×10 1 235 1 235 1 246 1 239 1 261 La28 20×10 1 216 1 216 1 216 1 216 1 216 La29 20×10 1 152 1 175 1 165 1 173 1 190 La30 20×10 1 355 1 355 1 355 1 355 1 355 La31 30×10 1 784 1 784 1 784 1 784 1 784 La32 30×10 1 850 1 850 1 850 1 850 1 850 La33 30×10 1 719 1 719 1 719 1 719 1 719 La34 30×10 1 271 1 271 1 271 1 271 1 271 La35 30×10 1 888 1 888 1 888 1 888 1 888 La36 15×15 1 268 1 285 1 279 1 278 1 281 La37 15×15 1 397 1 397 1 407 1 397 1 431 La38 15×15 1 196 1 196 1 213 1 208 1 196 La39 15×15 1 233 1 240 1 244 1 233 1 241 La40 15×15 1 222 1 224 1 233 1 225 1 233

 (4)

 (5)

1) 与文献[6]相比，对于Ft06、Ft10、Ft20与La01~La19、La23、La25、La26、La28、La30~La35共32个实例，新算法与之均能找到最优解。对于剩下11个实例，新算法能找到9个更好的解，并且La20、La21、La22、La27、La37、La38为最优解。

2) 与文献[8]相比，对于Ft06、Ft10、Ft20与La01~La23、La25、La26、La28、La30~La35、La37共36个实例，新算法与之均能找到最优解。对于剩下7个实例，新算法能找到4个更好的解，并且La27、La38为最优解。

3) 与文献[17]相比，对于Ft06、Ft10、Ft20与La01~La23、La26、La28、La30~La35、La38共35个实例新算法与之均能找到最优解。对于剩下8个实例，新算法能找到7个更好的解，并且La25、La27、La37为最优解。

 图 7 La27的调度甘特图 Fig. 7 Gantt chart of La27
4 结论

1) 新算法融入多智能体协同理论将每一个染色体视作独立的智能体，在邻居交互算子的设计中，采用赢家机制保留优良的个体，在占领机制中引入协作准则使得适应度较低的个体也能够提供有用的信息，提高了算法的收敛速率，能够快速地找到多个适应度较高的可行解，具有更好的全局搜索效率。

2) 采用插入式解码方式对智能体解码获得主动调度，保证了最优调度的存在，并进一步考虑到工序编码方式下的遗传操作的局限性，将其映射到一个非循环有向图作为局部优化的初始解，结合自适应模拟退火算法对每个智能体进一步优化，避免了算法陷入局部最优。

3) 通过选取基准测试库中的43个实例进行算法对比，计算结果验证了新算法的有效性和优越性。

 [1] GAREY M R, JOHNSON D S, SETHI R. The complexity of flowshop and job shop scheduling[J]. Mathematics of Operations Research, 1976, 1 (2): 117–129. DOI:10.1287/moor.1.2.117 [2] GIFFLER B, THOMPSON G L. Algorithms for solving productionscheduling problems[J]. Operations Research, 1960, 8 (4): 487–503. DOI:10.1287/opre.8.4.487 [3] ADAMS J, BALAS E, ZAWACK D. The shifting bottleneck procedure for job shop scheduling[J]. Management Science, 1988, 34 (3): 391–401. DOI:10.1287/mnsc.34.3.391 [4] BEASLEY J E. OR-library:Distributing test problems by electronic mails[J]. Journal of Operation Research Society, 1990, 41 (11): 1069–1072. DOI:10.1057/jors.1990.166 [5] APPLEGATE D, COOK W. A computational study of the job shop scheduling problem[J]. ORSA Journal on Computing, 1991, 3 (2): 149–156. DOI:10.1287/ijoc.3.2.149 [6] 赵诗奎, 方水良, 顾新建. 作业车间调度的空闲时间邻域搜索遗传算法[J]. 计算机集成制造系统, 2014, 20 (8): 1930–1940. ZHAO S K, FANG S L, GU X J. Idle time neighborhood search genetic algorithm for job shop scheduling[J]. Computer Integrated Manufacturing Systems, 2014, 20 (8): 1930–1940. (in Chinese) [7] VAN LAARHOVEN P J M, AARTS E H L, LENSTRA J K. Job shop scheduling by simulated annealing[J]. Operations Research, 1992, 40 (1): 113–125. DOI:10.1287/opre.40.1.113 [8] LIN T L, HORNG S J, KAO T W, et al. An efficient job-shop scheduling algorithm based on particle swarm optimization[J]. Expert Systems with Applications, 2010, 37 (3): 2629–2636. DOI:10.1016/j.eswa.2009.08.015 [9] WANG X, DUAN H B. A hybrid biogeography-based optimization algorithm for job shop scheduling problem[J]. Computers & Industrial Engineering, 2014, 73 : 96–114. [10] CHENG R, GEN M, TSUJIMURA Y. A tutorial survey of job shop scheduling problems using genetic algorithms-I.Representation[J]. Computers & Industrial Engineering, 1996, 30 (4): 983–997. [11] GORDINI N. A genetic algorithm approach for SMEs bankruptcy prediction:Empirical evidence from Italy[J]. Expert Systems with Applications, 2014, 41 (14): 6433–6445. DOI:10.1016/j.eswa.2014.04.026 [12] KUMAR K S, PAULRAJ G. Genetic algorithm based deformation control and clamping force optimisation of workpiece fixture system[J]. International Journal of Production Research, 2011, 49 (7): 1903–1935. DOI:10.1080/00207540903499438 [13] 陶杨, 韩维. 基于改进多目标遗传算法的舰尾紊流模拟方法[J]. 北京航空航天大学学报, 2015, 41 (3): 443–448. TAO Y, HAN W. Carrier airwake simulation methods based on improved multi-objective genetic algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics, 2015, 41 (3): 443–448. (in Chinese) [14] ZHONG W C, LIU J, XUE M Z, et al. A multiagent genetic algorithm for global numerical optimization[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B:Cybernetics, 2004, 34 (2): 1128–1141. DOI:10.1109/TSMCB.2003.821456 [15] SIVASUBRAMANI S, SWARUP K S. Multiagent based differential evolution approach to optimal power flow[J]. Applied Soft Computing, 2012, 12 (2): 735–740. DOI:10.1016/j.asoc.2011.09.016 [16] BLUM C, ROLI A. Metaheuristics in combinatorial optimization:Overview and conceptual comparison[J]. ACM Computing Surveys (CSUR), 2003, 35 (3): 268–308. DOI:10.1145/937503 [17] GAO L, ZHANG G H, ZHANG L P, et al. An efficient memetic algorithm for solving the job shop scheduling problem[J]. Computers & Industrial Engineering, 2011, 60 (4): 699–705. [18] XIA W, WU Z. An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems[J]. Computers & Industrial Engineering, 2005, 48 (2): 409–425. [19] HUANG M D, ROMEO F, SANGIOVANNI V A K.Efficient general cooling schedule for simulated annealing[C]//Proceeding of IEEE International Conference on Computer Aided Design.Piscataway, NJ:IEEE Press, 1986:381-384. [20] POTTS C N. Analysis of a heuristic for one machine sequencing with release dates and delivery times[J]. Operations Research, 1980, 28 (6): 1436–1441. DOI:10.1287/opre.28.6.1436 [21] BALAS E, VAZACOPOULOS A. Guided local search with shifting bottleneck for job shop scheduling[J]. Management Science, 1998, 44 (2): 262–275. DOI:10.1287/mnsc.44.2.262 [22] BAKER K R. Introduction to sequencing and scheduling[M]. New York: John Wiley & Sons, 1974. [23] BALAS E. Machine scheduling via disjunctive graphs:An implicit enumeration algorithm[J]. Operation Research, 1969, 17 (6): 941–957. DOI:10.1287/opre.17.6.941

#### 文章信息

LI Xiaotao, PENG Chong

Hybrid multiagent genetic algorithm for job shop scheduling problem

Journal of Beijing University of Aeronautics and Astronsutics, 2017, 43(2): 410-416
http://dx.doi.org/10.13700/j.bh.1001-5965.2016.0103