Computer Science ›› 2020, Vol. 47 ›› Issue (7): 186-191.doi: 10.11896/jsjkx.190600089

• Artificial Intelligence • Previous Articles     Next Articles

Novel Artificial Bee Colony Algorithm for Solving Many-objective Scheduling

ZHENG You-lian1, LEI De-ming2, ZHENG Qiao-xian1   

  1. 1 School of Computer Science and Information Engineering,Hubei University,Wuhan 430062,China
    2 School of Automation,Wuhan University of Technology,Wuhan 430070,China
  • Received:2019-06-18 Online:2020-07-15 Published:2020-07-16
  • About author:ZHENG You-lian,born in 1972,Ph.D,associate professor.Her main research interests include intelligent optimization and scheduling.
    ZHENG Qiao-xian,born in 1978,Ph.D,associate professor.Her main research interests include intelligent algorithm and assembly line scheduling.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China (61803149)

Abstract: Many-objective continuous optimization problem has been considered extensively while there are few studies on many-objective combination optimization problem.Artificial bee colony(ABC) algorithm has been successfully applied to solve various production scheduling problem,but ABC is seldom used to solve many-objective scheduling problem and many-objective scheduling problem itself is also seldom handled.Aiming at multi-objective flexible job shop scheduling problem,a new ABC algorithm is proposed to optimize simultaneously maximum completion time,total tardiness,total energy consumption and total workload.Unlike the general flexible job shop scheduling problem,the above problem is green scheduling one because of the inclusion of total energy consumption.The new ABC has new characteristics which are obviously different from the existing ABC algorithm.Its number of onlooker bees is less that of employed bees,employed bee focuses on global search while onlooker bee only carries out local search,which avoids the algorithm from falling into local optimization through the different search methods of two kinds of bees.At the same time,onlooker bee just selects some best employed bees or members of external file,and some employed bees cannot become follower objects to avoid wasting computing resources on search for poor solutions.A new strategy is adopted to handle scout.The simulation results show that the ratio of the number of non-dominated solutions to population scale for many-objective scheduling problem is notably less than the same ratio for many-objective continuous optimization problem.Compared with multi-objective genetic algorithm and variable neighborhood search,the computational results show that ABC has better results than two comparative algorithms on solving the considered many-objective scheduling.

Key words: Artificial bee colony, Multi-objective optimization, Scheduling problem, External archive, Local optima

CLC Number: 

  • TP301.6
[1] KARABOGA D,AKAY B.A comparative study of artificial bee colony algorithms[J].Applied Mathematics and Computation,2009,214(1):108-132.
[2] ZHAO X Q,DUAN S Y,MA X M.A multi-objective artificial bee colony based on limit search strategy[J].Control and Decision,2020,35(8):1793-1802.
[3] XIANG Y,ZHOU Y R,LIU H L.An elitism based multi-objective artificial bee colony algorithm[J].European Journal of Ope-rational Research,2015,245(1):168-193.
[4] SAAD A,KHAN S A,MAHMOOD A.A multi-objective evolutionary artificial bee colony algorithm for optimizing network topology design[J].Swarm and Evolutionary Computation,2018,38:187-201.
[5] LIANG R H,WU C Y,CHEN Y T,et al.Multi-objective dynamic optimal power flow using improved artificial bee colony algorithm based on Pareto optimization[J].International Tran-sactions on Electrical Energy Systems,2016,26(4):692-712.
[6] LI J Q,PAN Q K,GAO K Z.Pareto-based discrete artificial bee colony algorithm for multi-objective flexible job shop scheduling problem[J].International Journal of Advanced Manufacturing Technology,2011,55(9-12):1159-1169.
[7] PAN Q K,FAITH T M,SUGANTHAN P N,et al.A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem[J].Information Science,2011,181:2455-2468.
[8] ZHANG R,SONG S J,WU C.A hybrid artificial bee colony algorithm for the job shop scheduling problem[J].International Journal of Production Economics,2013,141(1):167-178.
[9] LEI D M,GUO X P.Scheduling job shop with lot streaming and transportation through a modified artificial bee colony[J].International Journal of Production Research,2013,51(16):4930-4941.
[10] HAN Y Y,GONG D W,SUN X Y.A discrete artificial bee colony algorithm incorporating differential evolution for the flow-shop scheduling problem with blocking[J].Engineering Optimization,2015,47(7):927-946.
[11] ASADZADEH L.A parallel artificial bee colony algorithm forthe job shop scheduling problem with a dynamic migration stra-tegy[J].Computers and Industrial Engineering,2016,102,359-367.
[12] SUNDAR S,SUGANTHAN P N,JIN C T,et al.A hybrid artificial bee colony algorithm for the job-shop scheduling problem with no-wait constraint[J].Soft Computing,2017,21(5):1193-1202.
[13] GONG D W,HAN Y Y,SUN J Y.A novel hybrid multi-objective artificial bee colony algorithm for blocking lot-straming flow shop scheduling problems[J].Knowledge-based Systems,2018,148:115-130.
[14] WU R,GUO S S,LI Y B,et al.An improved artificial bee colony algorithm for distributed and flexible job-shop scheduling problem [J].Control and Decision,2019.
[15] LI X Y,XIAO S Q,WANG C Y,et al.Mathematical modelling and a discrete artificial bee colony algorithm for the welding shop scheduling problem[J].Memeting Computing,2019,11:371-389.
[16] GAO K Z,SUGANTHAN P N,PAN Q K,et al.An improved artificial bee colony algorithm for flexible job-shop scheduling problem with fuzzy processing time[J].Expert Systems with Applications,2016,65:52-67.
[17] BEHNAMIAN J.Decomposition based hybrid VNS-TS algo-rithm for distributed parallel factories scheduling with virtual corporation[J].Computers and Operations Research,2014,52:181-191.
[18] CHANG H C,LIU T K.Optimisation of distributed manufacturing flexible job shop scheduling by using hybrid genetic algorithms[J].Journal of Intelligent Manufacturing,2017,28:1973-1986.
[19] DE G L,PEZZELLA F.An improved genetic algorithm for the distributed and flexible job shop scheduling problem[J].European Journal of Operational Research,2010,200(2):395-408.
[20] LEI D M,YUAN Y,CAI J C,et al.An imperialist competitive algorithm with memory for distributed unrelated parallel machines scheduling[J].International Journal of Production Research,2020,58(2):597-614.
[21] LIN J,WANG Z J,LI X D.A backtracking search hyper-heuristic for the distributed assembly flow shop scheduling problem[J].Swarm and Evolutionary Computation,2017,36,124-135.
[22] PIROOZFARD H,WONG K Y,WONG W P.Minimizing total carbon footprint and total late work criterion in flexible job shop scheduling by using an improved multi-objective genetic algorithm[J].Resources Conservation and Recycling,2018,128:267-283.
[23] BAGHERI A,ZANDIEH M.Bi-criteria flexible job-shop sche-duling with sequence-dependent setup times-variable neighbor-hood search approach[J].Journal Manufacturing Systems,2011,30(1):8-15.
[24] LEI D M,ZHENG Y L,GUO X P.A shuffled frog leaping algorithm for flexible job shop scheduling with the consideration of energy consumption [J].International Journal of Production Research,2017,55(11):3126-3140.
[25] LI M,LEI D M.Novel imperialist competitive algorithm formany-objective flexible job shop scheduling [J].Control theory and Applications,2018,35(1):1-9.
[26] KONG W J,DING J L,CHAI T Y.Survey on large-dimensional multi-objective evolutionary algorithms[J].Control and Decision,2010,25(3):321-326.
[27] DEB K,PRATAP A,AGARWAL S,et al.A fast and elitistmultiobjective genetic algorithm:NSGA-II [J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.
[28] BRANDIMARTE P.Routing and scheduling in a flexible jobshop by tabu search [J].Annals of Operations Research,1993,41(1):157-183.
[29] KNOWLES J D,CORNE D W.On metrics for comparing non- dominated sets[C]//Proc. of 2002 Congress on Evolutionary Computation.Honolulu,2002:711-716.
[30] LEI D M.Pareto archive particle swarm optimization multi-objective fuzzy job shop scheduling problems[J].International Journal of Advanced Manufacturing Technology,2008,37(1/2):157-165.
[1] ZHANG Qing-qi, LIU Man-dan. Multi-objective Five-elements Cycle Optimization Algorithm for Complex Network Community Discovery [J]. Computer Science, 2020, 47(8): 284-290.
[2] CHEN Meng-hui, CAO Qian-feng and LAN Yan-qi. Heuristic Algorithm Based on Block Mining and Recombination for Permutation Flow-shop Scheduling Problem [J]. Computer Science, 2020, 47(6A): 108-113.
[3] ZHAO Song-hui, REN Zhi-lei, JIANG He. Multi-objective Optimization Methods for Software Upgradeability Problem [J]. Computer Science, 2020, 47(6): 16-23.
[4] XIA Chun-yan, WANG Xing-ya, ZHANG Yan. Test Case Prioritization Based on Multi-objective Optimization [J]. Computer Science, 2020, 47(6): 38-43.
[5] SUN Min, CHEN Zhong-xiong, YE Qiao-nan. Workflow Scheduling Strategy Based on HEDSM Under Cloud Environment [J]. Computer Science, 2020, 47(6): 252-259.
[6] DONG Hail, XU Xiao- peng, XIE Xie. Solving Multi-flexible Job-shop Scheduling by Multi-objective Algorithm [J]. Computer Science, 2020, 47(12): 239-244.
[7] WANG Xu-liang, NIE Tie-zheng, TANG Xin-ran, HUANG Ju, LI Di, YAN Ming-sen, LIU Chang. Study on Dynamic Adaptive Caching Strategy for Streaming Data Processing [J]. Computer Science, 2020, 47(11): 122-127.
[8] DONG Ming-gang,LIU Bao,JING Chao. Multi-objective Differential Evolution Algorithm with Fuzzy Adaptive Ranking-based Mutation [J]. Computer Science, 2019, 46(7): 224-232.
[9] MU Xiao-fang, DENG Hong-xia, LI Xiao-bin, ZHAO Peng. Two-phase Image Steganalysis Algorithm Based on Artificial Bee Colony Algorithm [J]. Computer Science, 2019, 46(6): 174-179.
[10] WANG Chen-xin, YANG Jia-hai, ZHUANG Yi, LUO Nian-long. Node Resource Scheduling for Future Network Experimentation Facility [J]. Computer Science, 2019, 46(12): 95-100.
[11] ZHAO Yun-tao, CHEN Jing-cheng, LI Wei-gang. Multi-objective Grey Wolf Optimization Hybrid Adaptive Differential Evolution Mechanism [J]. Computer Science, 2019, 46(11A): 83-88.
[12] XU Kai-yong, XIAO Jing-xu, GUO Song, DAI Le-yu, DUAN Jia-liang. Android Malicious Application Detection Based on Improved Artificial Bee Colony Algorithms [J]. Computer Science, 2019, 46(11A): 421-427.
[13] MA Yuan-feng,LI Ang-ru,YU Hui-min,PAN Xiao-ying. Dynamic Crowding Distance-based Hybrid Immune Algorithm for Multi-objective Optimization Problem [J]. Computer Science, 2018, 45(6A): 63-68.
[14] FU Xiao. Task Scheduling Scheme Based on Sharing Mechanism and Swarm Intelligence
Optimization Algorithm in Cloud Computing
[J]. Computer Science, 2018, 45(6A): 290-294.
[15] CHEN Xiang, WANG Qiu-ping. Multi-objective Supervised Defect Prediction Modeling Method Based on Code Changes [J]. Computer Science, 2018, 45(6): 161-165.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[2] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[3] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[4] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[5] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[6] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[7] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[8] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[9] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .
[10] WANG Zhen-chao, HOU Huan-huan and LIAN Rui. Path Optimization Scheme for Restraining Degree of Disorder in CMT[J]. Computer Science, 2018, 45(4): 122 -125 .