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, External archive, Local optima, Multi-objective optimization, Scheduling problem

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] SUN Gang, WU Jiang-jiang, CHEN Hao, LI Jun, XU Shi-yuan. Hidden Preference-based Multi-objective Evolutionary Algorithm Based on Chebyshev Distance [J]. Computer Science, 2022, 49(6): 297-304.
[2] LI Hao-dong, HU Jie, FAN Qin-qin. Multimodal Multi-objective Optimization Based on Parallel Zoning Search and Its Application [J]. Computer Science, 2022, 49(5): 212-220.
[3] PENG Dong-yang, WANG Rui, HU Gu-yu, ZU Jia-chen, WANG Tian-feng. Fair Joint Optimization of QoE and Energy Efficiency in Caching Strategy for Videos [J]. Computer Science, 2022, 49(4): 312-320.
[4] GUAN Zheng, DENG Yang-lin, NIE Ren-can. Non-negative Matrix Factorization Based on Spectral Reconstruction Constraint for Hyperspectral and Panchromatic Image Fusion [J]. Computer Science, 2021, 48(9): 153-159.
[5] SHI Ke-xiang, BAO Li-yong, DING Hong-wei, GUAN Zheng, ZHAO Lei. Chaos Artificial Bee Colony Algorithm Based on Homogenizing Optimization of Generated Time Series [J]. Computer Science, 2021, 48(7): 270-280.
[6] ZHANG Ju, LI Xue-yun. Research on Intelligent Production Line Scheduling Problem Based on LGSO Algorithm [J]. Computer Science, 2021, 48(6A): 668-672.
[7] WANG Ke, QU Hua, ZHAO Ji-hong. Multi-objective Optimization Method Based on Reinforcement Learning in Multi-domain SFC Deployment [J]. Computer Science, 2021, 48(12): 324-330.
[8] CUI Guo-nan, WANG Li-song, KANG Jie-xiang, GAO Zhong-jie, WANG Hui, YIN Wei. Fuzzy Clustering Validity Index Combined with Multi-objective Optimization Algorithm and Its Application [J]. Computer Science, 2021, 48(10): 197-203.
[9] ZHU Han-qing, MA Wu-bin, ZHOU Hao-hao, WU Ya-hui, HUANG Hong-bin. Microservices User Requests Allocation Strategy Based on Improved Multi-objective Evolutionary Algorithms [J]. Computer Science, 2021, 48(10): 343-350.
[10] 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.
[11] 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.
[12] ZHAO Song-hui, REN Zhi-lei, JIANG He. Multi-objective Optimization Methods for Software Upgradeability Problem [J]. Computer Science, 2020, 47(6): 16-23.
[13] XIA Chun-yan, WANG Xing-ya, ZHANG Yan. Test Case Prioritization Based on Multi-objective Optimization [J]. Computer Science, 2020, 47(6): 38-43.
[14] 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.
[15] 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.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!