← Back to Search

Get Citationsy

# 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

Download via 🐼 PaperPanda
Download via oaDOI
Download via OAB
Download via LibKey
Download via Google
Google Scholar

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.

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