Ir al contenido

Documat

An ALNS to optimize makespan subject to total completion time for no‑wait fow shops with sequence‑dependent setup times

  • Fernando Siqueira de Almeida [1] ; Marcelo Seido Nagano [1]
    1. [1] Universidade de São Paulo

      Universidade de São Paulo

      Brasil

  • Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 32, Nº. 2, 2024, págs. 304-322
  • Idioma: inglés
  • DOI: 10.1007/s11750-024-00669-9
  • Enlaces
  • Resumen

    • In this article, we address the no-wait fow shop scheduling problem with sequence dependent setup times. The objective is to minimize makespan subject to an upper bound on total completion time. Although these performance measures and constraints have been extensively studied, they have never been considered together in this problem before. To solve the problem, we propose an adaptive large neighborhood search algorithm called ALNSA. Essentially, ALNSA improves an initial solution by dynamically selecting and executing a pair of destroy and repair methods based on their performance history. In addition to classic greedy and random methods used, we present two new mechanisms in which the greediness-randomness behavior is balanced. To evaluate performance, the proposed approach is compared with three heuristic methods—GL, HH1 and TOB—developed for the most similar problems found in the literature. Computational experiments show that the proposed method outperforms state-of-the-art approaches in the literature for the no-wait fow shop scheduling problem with sequence dependent setup times and is therefore recommended to solve the problem.

  • Referencias bibliográficas
    • Allahverdi A (2004) A new heuristic for m-machine fowshop scheduling problem with bicriteria of makespan and maximum tardiness. Comput Oper...
    • Allahverdi A, Aydilek H (2013) Algorithms for no-wait fowshops with total completion time subject to makespan. Int J Adv Manuf Technol 68(9–12):2237–2251...
    • Allahverdi A, Aydilek H (2014) Total completion time with makespan constraint in no-wait fowshops with setup times. Eur J Oper Res 238(3):724–734...
    • Allahverdi A, Aydilek H, Aydilek A (2018) No-wait fowshop scheduling problem with two criteria; total tardiness and makespan. Eur J Oper Res...
    • Allahverdi A, Aydilek H, Aydilek A (2020) No-wait fowshop scheduling problem with separate setup times to minimize total tardiness subject...
    • Araújo DC, Nagano MS (2011) A new efective heuristic method for the no-wait fowshop with sequencedependent setup times problem. Int J Ind...
    • Aydilek H, Allahverdi A (2012) Heuristics for no-wait fowshops with makespan subject to mean completion time. Appl Math Comput 219(1):351–359...
    • Azi N, Gendreau M, Potvin JY (2014) An adaptive large neighborhood search for a vehicle routing problem with multiple routes. Comput Oper...
    • Baker KR, Trietsch D (2019) Principles of sequencing and scheduling. Wiley
    • Beezão AC, Cordeau JF, Laporte G et al (2017) Scheduling identical parallel machines with tooling constraints. Eur J Oper Res 257(3):834–844...
    • Bianco L, Dell’Olmo P, Giordani S (1999) Flow shop no-wait scheduling with sequence dependent setup times and release dates. INFOR: Inform...
    • Demir E, Bektaş T, Laporte G (2012) An adaptive large neighborhood search heuristic for the pollutionrouting problem. Eur J Oper Res 223(2):346–359...
    • Emmons H, Vairaktarakis G (2013) Flow shop scheduling. Theoretical results, algorithms, and applications. Springer Science & Business...
    • Framinan JM, Leisten R (2006) A heuristic for scheduling a permutation fowshop with makespan objective subject to maximum tardiness. Int J...
    • Franca PM, Tin G Jr, Buriol L (2006) Genetic algorithms for the no-wait fowshop sequencing problem with time restrictions. Int J Prod Res...
    • Graham RL, Lawler EL, Lenstra JK et al (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discrete...
    • Hemmelmayr VC, Cordeau JF, Crainic TG (2012) An adaptive large neighborhood search heuristic for twoechelon vehicle routing problems arising...
    • Lee YH, Jung JW (2005) New heuristics for no-wait fowshop scheduling with precedence constraints and sequence dependent setup time. In: International...
    • Lin SW, Ying KC (2014) Minimizing shifts for personnel task scheduling problems: a three-phase algorithm. Eur J Oper Res 237(1):323–334
    • Lopez-Ibanez M, Dubois-Lacoste J, Caceres LP et al (2016) The irace package: iterated racing for automatic algorithm confguration. Oper Res...
    • Miyata HH, Nagano MS, Gupta JN (2019) Integrating preventive maintenance activities to the no-wait fow shop scheduling problem with dependent-sequence...
    • Nagano MS, Araújo DC (2014) New heuristics for the no-wait fowshop with sequence-dependent setup times problem. J Braz Soc Mech Sci Eng 36(1):139–151...
    • Nagano MS, Miyata HH, Araújo DC (2015) A constructive heuristic for total fowtime minimization in a nowait fowshop with sequence-dependent...
    • Nagano MS, Almeida FSd, Miyata HH (2020) An iterated greedy algorithm for the no-wait fowshop scheduling problem to minimize makespan subject...
    • Nawaz M, Enscore EE Jr, Ham I (1983) A heuristic algorithm for the m-machine, n-job fow-shop sequencing problem. Omega 11(1):91–95
    • Pinedo M (2016) Scheduling. Theory, algorithms, and systems, 5th edn. Springer Science & Business Media, Cham
    • Pisinger D, Ropke S (2019) Large neighborhood search. Handbook of metaheuristics. Springer, Cham, pp 99–127
    • Qian B, Zhou HB, Hu R, et al (2011) Hybrid diferential evolution optimization for no-wait fow-shop scheduling with sequence-dependent setup...
    • Qian B, Du P, Hu R, et al (2012) A diferential evolution algorithm with two speed-up methods for nfssp with sdsts and rds. In: Proceedings...
    • Qu Y, Bard JF (2012) A grasp with adaptive large neighborhood search for pickup and delivery problems with transshipment. Comput Oper Res...
    • Rifai AP, Nguyen HT, Dawal SZM (2016) Multi-objective adaptive large neighborhood search for distributed reentrant permutation fow shop scheduling....
    • Ropke S, Pisinger D (2006) An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transp Sci...
    • Ruiz R, Stützle T (2008) An iterated greedy heuristic for the sequence dependent setup times fowshop problem with makespan and weighted tardiness...
    • Samarghandi H (2015) A no-wait fow shop system with sequence dependent setup times and server constraints. IFAC-PapersOnLine 48(3):1604–1609...
    • Samarghandi H (2015) Studying the efect of server side-constraints on the makespan of the no-wait fowshop problem with sequence-dependent...
    • Samarghandi H, ElMekkawy TY (2014) Solving the no-wait fow-shop problem with sequence-dependent set-up times. Int J Comput Integr Manuf 27(3):213–228...
    • haw P (1998) Using constraint programming and local search methods to solve vehicle routing problems. In: International Conference on Principles...
    • Taillard E (1993) Benchmarks for basic scheduling problems. Eur J Oper Res 64(2):278–285. https://doi.org/ 10.1016/0377-2217(93)90182-M T’kindt...
    • Xu T, Zhu X, Li X (2012) Efcient iterated greedy algorithm to minimize makespan for the no-wait fowshop with sequence dependent setup times....
    • Ye H, Li W, Nault BR (2020) Trade-of balancing between maximum and total completion times for no-wait fow shop production. Int J Prod Res...
    • Zhuang WJ, Xu T, Sun MY (2014) A hybrid iterated greedy algorithm for no-wait fowshop with sequence dependent setup times to minimize makespan....
    • Zhu X, Li X, Gupta JN (2013a) Iterative algorithms for no-wait fowshop problems with sequence-dependent setup times. In: 2013 25th Chinese...
    • Zhu X, Li X, Wang Q (2013b) An adaptive intelligent method for manufacturing process optimization in steelworks. In: Proceedings of the 2013...
Fundación Dialnet

Mi Documat

Opciones de artículo

Opciones de compartir

Opciones de entorno