Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

An efficient iterated greedy algorithm for a multi-objective no-wait flow shop problem with sequence dependent setup times

An efficient iterated greedy algorithm for a multi-objective no-wait flow shop problem with... In this article, we address the m-machine no-wait flow shop scheduling problem with sequence dependent setup times. The objective is to minimize total tardiness subject to an upper bound on makespan. Although these constraints and performance measures have all been extensively studied independently, they have never been considered together in this problem before. So, this multi-criteria approach provides more realistic solutions for complex scenarios. To solve the problem, we developed a new heuristic called IGA\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$IG_{A}$$\end{document}. The proposed method repeatedly performs a process of destruction and construction of an existing solution in order to improve it. The novelty of this method includes a mechanism capable of adapting the destruction intensity according to the instance size and the number of iterations, calibrating the algorithm during the search. Computational experiments indicate that IGA\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$IG_{A}$$\end{document} outperforms the best literature method for similar applications in overall solution quality by about 35%. Therefore, IGA\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$IG_{A}$$\end{document} is recommended to solve the problem. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png 4OR Springer Journals

An efficient iterated greedy algorithm for a multi-objective no-wait flow shop problem with sequence dependent setup times

de Almeida, Fernando Siqueira; Nagano, Marcelo Seido
4OR , Volume OnlineFirst – Mar 10, 2023
Download PDF
15 pages

Loading next page...
 
/lp/springer-journals/an-efficient-iterated-greedy-algorithm-for-a-multi-objective-no-wait-ub2h00qTC9
Publisher
Springer Journals
Copyright
Copyright © The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature 2023. Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
ISSN
1619-4500
eISSN
1614-2411
DOI
10.1007/s10288-023-00535-7
Publisher site
See Article on Publisher Site

Abstract

In this article, we address the m-machine no-wait flow shop scheduling problem with sequence dependent setup times. The objective is to minimize total tardiness subject to an upper bound on makespan. Although these constraints and performance measures have all been extensively studied independently, they have never been considered together in this problem before. So, this multi-criteria approach provides more realistic solutions for complex scenarios. To solve the problem, we developed a new heuristic called IGA\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$IG_{A}$$\end{document}. The proposed method repeatedly performs a process of destruction and construction of an existing solution in order to improve it. The novelty of this method includes a mechanism capable of adapting the destruction intensity according to the instance size and the number of iterations, calibrating the algorithm during the search. Computational experiments indicate that IGA\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$IG_{A}$$\end{document} outperforms the best literature method for similar applications in overall solution quality by about 35%. Therefore, IGA\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$IG_{A}$$\end{document} is recommended to solve the problem.

Journal

4OR – Springer Journals

Published: Mar 10, 2023

Keywords: Iterated greedy; Flow shop; No-wait; Sequence-dependent setup; Total tardiness; Makespan; 68T20; 90C59

References

  • Minimizing total tardiness in no-wait flowshops
    Aldowaisan, T; Allahverdi, A
  • Total tardiness performance in m-machine no-wait flowshops with separate setup times
    Aldowaisan, T; Allahverdi, A
  • A new heuristic for m-machine flowshop scheduling problem with bicriteria of makespan and maximum tardiness
    Allahverdi, A
  • Algorithms for no-wait flowshops with total completion time subject to makespan
    Allahverdi, A; Aydilek, H
  • Total completion time with makespan constraint in no-wait flowshops with setup times
    Allahverdi, A; Aydilek, H
  • No-wait flowshop scheduling problem with two criteria; total tardiness and makespan
    Allahverdi, A; Aydilek, H; Aydilek, A
  • No-wait flowshop scheduling problem with separate setup times to minimize total tardiness subject to makespan
    Allahverdi, A; Aydilek, H; Aydilek, A
  • A new effective heuristic method for the no-wait flowshop with sequence-dependent setup times problem
    Ara, DC; Nagano, MS
  • Heuristics for no-wait flowshops with makespan subject to mean completion time
    Aydilek, H; Allahverdi, A
  • Flow shop no-wait scheduling with sequence dependent setup times and release dates
    Bianco, L; Dell’Olmo, P; Giordani, S
  • Multi-objective sequence dependent setup times permutation flowshop: a new algorithm and a comprehensive study
    Ciavotta, M; Minella, G; Ruiz, R
  • A hybrid tp plus pls algorithm for bi-objective flow-shop scheduling problems
    Dubois-Lacoste, J; Lopez-Ibanez, M; Stutzle, T
  • Neh-based heuristics for the permutation flowshop scheduling problem to minimise total tardiness
    Fernandez-Viagas, V; Framinan, JM
  • A heuristic for scheduling a permutation flowshop with makespan objective subject to maximum tardiness
    Framinan, JM; Leisten, R
  • Order scheduling with tardiness objective: improved approximate solutions
    Framinan, JM; Perez-Gonzalez, P
  • Genetic algorithms for the no-wait flowshop sequencing problem with time restrictions
    Franca, PM; Tin, G; Buriol, L
  • An iterated greedy heuristic for no-wait flow shops with sequence dependent setup times, learning and forgetting effects
    Li, X; Yang, Z; Ruiz, R
  • The irace package: iterated racing for automatic algorithm configuration
    Lopez-Ibanez, M; Dubois-Lacoste, J; Caceres, LP
  • A review and evaluation of multiobjective algorithms for the flowshop scheduling problem
    Minella, G; Ruiz, R; Ciavotta, M
  • Restarted iterated Pareto greedy algorithm for multi-objective flowshop scheduling problems
    Minella, G; Ruiz, R; Ciavotta, M
  • Integrating preventive maintenance activities to the no-wait flow shop scheduling problem with dependent-sequence setup times and makespan minimization
    Miyata, HH; Nagano, MS; Gupta, JN
  • New heuristics for the no-wait flowshop with sequence-dependent setup times problem
    Nagano, MS; Araújo, DC
  • An iterated greedy algorithm for the no-wait flowshop scheduling problem to minimize makespan subject to total completion time
    Nagano, MS; Almeida, FS; Miyata, HH
  • A heuristic algorithm for the m-machine, n-job flowshop sequencing problem
    Nawaz, M; Enscore, EE; Ham, I
  • An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem
    Pan, QK; Ruiz, R
  • A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem
    Ruiz, R; Stützle, T
  • An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives
    Ruiz, R; Stützle, T
  • Solving the no-wait flow-shop problem with sequence-dependent set-up times
    Samarghandi, H; ElMekkawy, TY
  • Benchmarks for basic scheduling problems
    Taillard, E
  • Iterated greedy algorithms for the blocking flowshop scheduling problem with makespan criterion
    Tasgetiren, MF; Kizilay, D; Pan, QK
  • Minimization of total tardiness in no-wait flowshop production systems with preventive maintenance
    Yamada, T; Nagano, M; Miyata, H