An effective artificial bee colony algorithm for the flexible job-shop scheduling problem
Tóm tắt
An effective artificial bee colony (ABC) algorithm is proposed in this paper for solving the flexible job-shop scheduling problem with the criterion to minimize the maximum completion time (makespan). The ABC algorithm stresses the balance between global exploration and local exploitation. First, multiple strategies are utilized in a combination to generate the initial solutions with certain quality and diversity as the food sources. Second, crossover and mutation operators are well designed for machine assignment and operation sequence to generate the new neighbor food sources for the employed bees. Third, a local search strategy based on critical path is proposed and embedded in the searching framework to enhance the local intensification capability for the onlooker bees. Meanwhile, an updating mechanism of population by generating the scout bees with the initialing strategy is proposed to enrich the searching behavior and avoid the premature convergence of the algorithm. In addition, a well-designed left-shift decoding scheme is employed to transform a solution to an active schedule. Numerical simulation results based on well-known benchmarks and comparisons with some existing algorithms demonstrate the effectiveness of the proposed ABC algorithm.
Tài liệu tham khảo
Bruker P, Schlie R (1990) Job-shop scheduling with multi-purpose machines. Computing 45(4):369–375
Brandimarte P (1993) Routing and scheduling in a flexible job shop by tabu search. Ann Oper Res 41(3):157–183
Paulli J (1995) A hierarchical approach for the FMS scheduling problem. Eur J Operat Res 86(1):32–42
Kacem I, Hammadi S, Borne P (2002) Pareto-optimality approach for flexible job-shop scheduling problems: hybridization of evolutionary algorithms and fuzzy logic. Math Comput Simul 60(3–5):245–276
Kacem I, Hammadi S, Borne P (2002) Approach by localization and multi-objective evolutionary optimization for flexible job-shop scheduling problems. IEEE Trans Sys Man Cybern Part C 32(1):1–13
Xia WJ, Wu ZM (2005) An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Comput Ind Eng 48(2):409–425
Ho NB, Tay JC, Lai EMK (2007) An effective architecture for learning and evolving flexible job-shop schedules. Eur J Operat Res 179(2):316–333
Saidi-mehrabad M, Fattahi P (2007) Flexible job shop scheduling with tabu search algorithms. Int J Adv Manuf Tech 32(5–6):563–570
Fattahi P, Saidi M, Jolai F (2007) Mathematical modeling and heuristic approaches to flexible job shop scheduling problems. J of Int Manuf 18(3):331–342
Gao J, Sun LY, Gen M (2008) A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Com Oper Res 35(9):2892–2907
Chen JC, Chen KH, Wu JJ, Chen CW (2008) A study of the flexible job shop scheduling problem with parallel machines and reentrant process. Int J Adv Manuf Tech 39(3–4):344–354
Zhang GH, Gao L, Li XY, Li PG (2008) Variable neighborhood genetic algorithm for the flexible job shop scheduling problems. Lect Notes Com Sci 5315:503–512
Gen M, Gao J, Lin L (2009) Multistage-based genetic algorithm for flexible job-shop scheduling problem. Studies Com Int 187:183–196
Xing LN, Chen YW, Wang P, Zhao QS, Xiong J (2010) A knowledge-based ant colony optimization for flexible job shop scheduling problems. Applied Soft Com 10(3):888–896
Yazdani M, Amiri M, Zandieh M (2010) Flexible job-shop scheduling with parallel variable neighborhood search algorithm. Expert Sys Appl 37(1):678–687
Moradi E, Fatemi Ghomi SMT, Zandieh M (2010) An efficient architecture for scheduling flexible job-shop with machine availability constraints. Int J Adv Manuf Tech 51(1–4):325–339
Defersha FM, Chen M (2010) A parallel genetic algorithm for a flexible job-shop scheduling problem with sequence dependent setups. Int J Adv Manuf Tech 49(1–4):263–279
Zhang GH, Gao L, Shi Y (2011) An effective genetic algorithm for the flexible job-shop scheduling problem. Experts Sys Appl 38(4):3563–3573
Li JQ, Pan QK, Suganthan PN, Chua TJ (2011) A hybrid tabu search algorithm with an efficient neighborhood structure for the flexible job shop scheduling problem. Int J Adv Manuf Tech 52(5–8):683–697
Dauzere-Peres S, Paulli J (1997) An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search. Ann Oper Res 70:281–306
Mastrolilli M, Gambardella LM (2000) Effective neighborhood functions for the flexible job shop problem. J Sched 3(1):3–20
Baykasoglu A (2002) Linguistic-based meta-heuristic optimization model for flexible job shop scheduling. Int J Product Res 44(17):4523–4543
Chan FTS, Wong TC, Chan LY (2006) Flexible job-shop scheduling problem under resource constraints. Int J Product Res 44(11):2071–2089
Pezzella F, Morganti G, Ciaschetti G (2008) A genetic algorithm for the flexible job-shop scheduling problem. Comput Oper Res 35(10):3202–3212
Tay JC, Ho NB (2008) Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems. Comput Ind Eng 54(3):453–473
Moslehi G, Mahnam M (2011) A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search. Int J Product Econ 129(1):14–22
Karaboga D (2005) An idea based on honey bee swarm for numerical optimization, Technical Report TR06. Computer Engineering Department, Erciyes University, Turkey
Karaboga N (2009) A new design method based on artificial bee colony algorithm for digital IIR filters. J Frankl Inst 346(4):328–348
Karaboga D, Akay B (2009) A comparative study of artificial bee colony algorithm. Appl Math Comput 24(1):108–132
Karaboga D, Basturk B (2008) On the performance of artificial bee colony (ABC) algorithm. Applied Soft Comput 8(1):687–697
Karaboga D, Basturk B (2007) A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. J Global Optim 39(3):459–471
Baykasoglu A, Ozbakir L, Tapkan P (2007) Artificial bee colony algorithm and its application to generalized assignment problem. In: Swarm intelligence focus on ant and particle swarm optimization. I-Tech Education and Publishing, Vienna, pp 113–144
Wong LP, Low MYH, Chong CS (2008) Bee colony optimization with local search for traveling salesman problem. In: Proc. of 6th IEEE International Conference on Industrial Informatics, pp 1019–1025
Pan QK, Tasgetiren MF, Suganthan PN, Chua TJ (2011) A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem. Inf Sci 181(12):2455–2468
Wang XJ, Gao L, Zhang CY, Shao XY (2010) A multi-objective genetic algorithm based on immune and entropy principle for flexible job-shop scheduling problem. Int J Adv Manuf Tech 51(5–8):757–767
Watanabe M, Ida K, Gen M (2005) A genetic algorithm with modified crossover operator and search area adaptation for the job-shop scheduling problem. Comput Ind Eng 48(4):743–752
Zhang GH, Shao XY, Li PG, Gao L (2009) An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem. Comput Ind Eng 56(4):1309–1318
Tay JC, Wibowo D (2004) GENACE: an efficient cultural algorithm for solving the flexible job-shop problem. In: Proc. of the IEEE Congress on Evolutionary Computation, pp 1759–1766