Online citations, reference lists, and bibliographies.
← Back to Search

Some Heuristic Algorithms For Total Tardiness Minimization In A Flowshop With Blocking

D. P. Ronconi, Luís R.S. Henriques
Published 2009 · Computer Science

Save to my Library
Download PDF
Analyze on Scholarcy Visualize in Litmaps
Share
Reduce the time it takes to create your bibliography by a factor of 10 by using the world’s favourite reference manager
Time to take this seriously.
Get Citationsy
The flowshop scheduling problem with blocking in-process is addressed in this paper. In this environment, there are no buffers between successive machines; therefore intermediate queues of jobs waiting in the system for their next operations are not allowed. Heuristic approaches are proposed to minimize the total tardiness criterion. A constructive heuristic that explores specific characteristics of the problem is presented. Moreover, a GRASP-based heuristic is proposed and coupled with a path relinking strategy to search for better outcomes. Computational tests are presented and the comparisons made with an adaptation of the NEH algorithm and with a branch-and-bound algorithm indicate that the new approaches are promising.
This paper references
10.1016/S0167-5060(08)70743-X
Complexity of machine scheduling problems
P. Brucker (1975)
10.1016/0167-6377(82)90035-9
A decomposition algorithm for the single machine total tardiness problem
C. Potts (1982)
10.1016/0305-0483(83)90088-9
A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem
M. Nawaz (1983)
10.1016/0305-0483(84)90011-2
A state-of-art survey of static scheduling research involving due dates
Tapan Sen (1984)
Die Einbeziehung beschränkter Zwischenlager in die Auftragsreihenfolgeplanung bei Reihenfertigung
R. Leisten (1985)
10.1287/opre.37.6.925
Sequencing in an Assembly Line with Blocking to Minimize Cycle Time
S. McCormick (1989)
10.1016/0167-6377(89)90002-3
A probabilistic heuristic for a computationally difficult set covering problem
T. Feo (1989)
10.1287/moor.15.3.483
Minimizing Total Tardiness on One Machine is NP-Hard
J. Du (1990)
10.1080/00207549008942855
Flowshop sequencing problems with limited buffer storage
R. Leisten (1990)
10.1007/BF01324886
Sequencing of parts and robot moves in a robotic cell
S. Sethi (1992)
10.1016/0377-2217(93)90182-M
Benchmarks for basic scheduling problems
É. Taillard (1993)
10.1080/15458830.1996.11770714
Scheduling: Theory, Algorithms, and Systems
Michael Pinedo (1994)
10.1287/opre.44.3.510
A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process
N. Hall (1996)
10.1007/978-1-4615-4102-8
Interfaces in Computer Science and Operations Research
R. Barr (1997)
10.1007/978-1-4615-4102-8_1
Tabu Search and Adaptive Memory Programming — Advances, Applications and Challenges
F. Glover (1997)
10.1016/S0377-2217(97)00213-0
Heuristics for the flow line problem with setup costs
R. Z. Ríos-Mercado (1998)
10.1016/S0305-0548(98)00060-4
Tabu search for total tardiness minimization in flowshop scheduling problems
V. Armentano (1999)
10.1287/ijoc.11.1.44
GRASP and Path Relinking for 2-Layer Straight Line Crossing Minimization
M. Laguna (1999)
10.1287/opre.48.1.177.12451
Minimizing Cycle Time in a Blocking Flowshop
I. Abadi (2000)
10.1590/S0104-530X2000000300011
Minimização do tempo total de atraso no problema de flowshop com buffer zero através de busca tabu
V. Armentano (2000)
10.1016/S0377-2217(99)00224-6
Sequencing of jobs in some production system
J. Grabowski (2000)
10.1016/S0925-5273(99)00014-6
Tabu search for minimizing total tardiness in a job shop
V. Armentano (2000)
10.1016/S0377-2217(00)00319-2
A new dominance rule to minimize total weighted tardiness with unequal release dates
M. S. Akturk (2001)
10.1057/palgrave.jors.2601220
Lower bounding schemes for flowshops with blocking in-process
D. Ronconi (2001)
10.1002/net.1023
Local search with perturbations for the prize-collecting Steiner tree problem in graphs
S. Canuto (2001)
10.1016/S0925-5273(99)00104-8
Minimizing makespan in a blocking flowshop using genetic algorithms
Vince Caraffa (2001)
10.1287/ijoc.14.3.228.116
A Hybrid GRASP with Perturbations for the Steiner Problem in Graphs
Celso C. Ribeiro (2002)
Handbook of applied optimization
P. Pardalos (2002)
10.1007/978-3-319-91086-4
Handbook of metaheuristics
F. Glover (2003)
10.1007/0-306-48056-5_8
Greedy Randomized Adaptive Search Procedures
M. Resende (2003)
10.1016/S0167-8191(03)00014-0
Parallel GRASP with path-relinking for job shop scheduling
Renata M. Aiex (2003)
10.1016/S0925-5273(03)00065-3
A note on constructive heuristics for the flowshop problem with blocking
D. Ronconi (2004)
10.1007/0-387-25383-1_2
GRASP with Path-Relinking: Recent Advances and Applications
Mauricio G.C. Resendel (2005)
10.1007/B107306
Metaheuristics : progress as real problem solvers
T. Ibaraki (2005)
10.1007/11427186_32
GRASP with Path-Relinking for the Weighted Maximum Satisfiability Problem
P. Festa (2005)
10.1007/s10479-005-2444-3
A Branch-and-Bound Algorithm to Minimize the Makespan in a Flowshop with Blocking
D. Ronconi (2005)
10.1016/J.OMEGA.2004.07.023
Total tardiness minimization on unrelated parallel machine scheduling with auxiliary equipment constraints
Jeng-Fung Chen (2006)
10.1016/j.ejor.2004.08.019
Scatter search for project scheduling with resource availability cost
D. Yamashita (2006)
10.1016/J.OMEGA.2005.03.003
On the NEH heuristic for minimizing the makespan in permutation flow shops
P. Kalczynski (2007)
10.1016/J.OMEGA.2005.07.004
The permutation flow shop problem with blocking. A tabu search approach
J. Grabowski (2007)
10.1016/J.OMEGA.2006.11.003
Efficient composite heuristics for total flowtime minimization in permutation flow shops
Xiaoping Li (2009)



This paper is referenced by
10.1016/j.eswa.2020.113837
Multi-temperature simulated annealing for optimizing mixed-blocking permutation flowshop scheduling problems
Shih-Wei Lin (2021)
10.1145/3396474.3396475
Scheduling Tardiness Constrained Flow Shop with Simultaneously Loaded Stations Using Genetic Algorithm
D. Davendra (2020)
Scheduling of a Real World Filter Production with Lot-Size 1
F. Herrmann (2020)
10.4018/978-1-7998-0268-6.ch004
A Variable Neighborhood Search Algorithm to Solve the Flow Shop-Scheduling Problem Through Blocking
D. Bouzidi (2020)
10.1016/j.eswa.2019.113166
A hybrid discrete water wave optimization algorithm for the no-idle flowshop scheduling problem with total tardiness criterion
F. Zhao (2020)
10.1109/ACCESS.2020.3014106
Minimizing Total Completion Time in Mixed-Blocking Permutation Flowshops
Chen-Yang Cheng (2020)
10.1016/j.cor.2019.104824
A filtered beam search method for the m-machine permutation flowshop scheduling problem minimizing the earliness and tardiness penalties and the waiting time of the jobs
E. Birgin (2020)
10.1016/J.ESWA.2019.06.069
The blocking flow shop scheduling problem: A comprehensive and conceptual review
Hugo Hissashi Miyata (2019)
10.1007/s10489-019-01457-w
A discrete gravitational search algorithm for the blocking flow shop problem with total flow time minimization
F. Zhao (2019)
10.1007/S10696-018-9310-5
Material flow optimisation of production planning and scheduling problem in flexible manufacturing system by real coded genetic algorithm (RCGA)
K. Bhosale (2019)
10.1007/s10845-017-1358-7
An evolutionary clustering search for the total tardiness blocking flow shop problem
M. S. Nagano (2019)
10.1016/j.knosys.2018.11.021
A novel multi-objective discrete water wave optimization for solving multi-objective blocking flow-shop scheduling problem
Zhongshi Shao (2019)
10.1016/j.eswa.2018.12.039
An iterated greedy algorithm for solving the total tardiness parallel blocking flow shop scheduling problem
I. Ribas (2019)
10.1007/978-3-319-95930-6_63
Hybrid Estimation of Distribution Algorithm for Blocking Flow-Shop Scheduling Problem with Sequence-Dependent Setup Times
Zi-Qi Zhang (2018)
10.1016/j.eswa.2018.06.020
A multi-objective discrete invasive weed optimization for multi-objective blocking flow-shop scheduling problem
Zhongshi Shao (2018)
Résolution de problèmes d’ordonnancement de type Flow-Shop de permutation en présence de contraintes de ressources non-renouvelables
I. Laribi (2018)
10.1016/j.swevo.2017.12.005
A novel discrete water wave optimization algorithm for blocking flow-shop scheduling problem with sequence-dependent setup times
Zhongshi Shao (2018)
Due dates for the Taillard’s Benchmark adapted to the parallel flow shop scheduling problem and best solutions
Immaculada Ribas Vila (2018)
10.37610/DYO.V0I66.533
Secuenciación con Almacenes Limitados. Una Revisión de la Literatura
C. Andrés (2018)
10.1007/s10479-017-2465-8
Evolutionary multiobjective optimization for the multi-machine flow shop scheduling problem under blocking
Nouri Nouha (2018)
10.1016/j.engappai.2018.09.005
Discrete differential evolution algorithm for distributed blocking flowshop scheduling with makespan criterion
Guanghui Zhang (2018)
10.1080/0305215X.2017.1353090
Estimation of distribution algorithm with path relinking for the blocking flow-shop scheduling problem
Zhongshi Shao (2017)
10.1016/j.cor.2016.07.002
Iterated greedy algorithms for the blocking flowshop scheduling problem with makespan criterion
M. F. Tasgetiren (2017)
10.1016/j.cie.2017.07.037
Self-adaptive discrete invasive weed optimization for the blocking flow-shop scheduling problem to minimize total tardiness
Zhongshi Shao (2017)
10.17562/PB-53-10
An Efficient Iterated Greedy Algorithm for the Makespan Blocking Flow Shop Scheduling Problem
Nouri Nouha (2016)
10.1007/978-3-319-33625-1_9
Total Tardiness Minimization in a Flow Shop with Blocking Using an Iterated Greedy Algorithm
Nouri Nouha (2016)
10.1016/j.cie.2016.08.026
Stochastic flexible flow shop scheduling problem under quantitative and qualitative decision criteria
E. M. González-Neira (2016)
10.17562/PB-53-1
On the Sufficiency of Using Degree Sequence of the Vertices to Generate Random Networks Corresponding to Real-World Networks
N. Meghanathan (2016)
10.3390/systems4010015
Using Optimization Models for Scheduling in Enterprise Resource Planning Systems
F. Herrmann (2016)
10.1007/978-1-4939-6530-4_9
GRASP with path-relinking
M. C. Resende (2016)
10.3390/a9040071
A Variable Block Insertion Heuristic for the Blocking Flowshop Scheduling Problem with Total Flowtime Criterion
M. F. Tasgetiren (2016)
10.1145/2739480.2754638
Minimizing Regular Objectives for Blocking Permutation Flow Shop Scheduling: Heuristic Approaches
Nouri Nouha (2015)
See more
Semantic Scholar Logo Some data provided by SemanticScholar