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

Permutation Flow Shops With Exact Time Lags To Minimise Maximum Lateness

J. Fondrevelle, A. Oulamara, M. Portmann, A. Allahverdi
Published 2009 · Engineering

Save to my Library
Download PDF
Analyze on Scholarcy Visualize in Litmaps
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
In this paper we investigate the m-machine permutation flow shop scheduling problem where exact time lags are defined between consecutive operations of every job. This generic model can be used for the study and analysis of various real situations that may arise, for instance, in the food-producing, pharmaceutical and steel industries. The objective is to minimise the maximum lateness. We study polynomial special cases and provide a dominance relation. We derive lower and upper bounds that are integrated in a branch-and-bound procedure to solve the problem. Three branching schemes are proposed and compared. We perform a computational analysis to evaluate the efficiency of the developed method.
This paper references
Optimal two- and three-stage production schedules with setup times included
S. Johnson (1954)
Sequencing n Jobs on Two Machines with Arbitrary Time Lags
L. G. Mitten (1959)
Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
P. C. Gilmore (1964)
Application of the Branch and Bound Technique to Some Flow-Shop Scheduling Problems
E. Ignall (1965)
Complexity of machine scheduling problems
P. Brucker (1975)
An adaptive branching rule for the permutation flow-shop problem
C. Potts (1978)
Deterministic Scheduling with Pipelined Processors
J. Bruno (1980)
A decomposition algorithm for the single machine total tardiness problem
C. Potts (1982)
A concise survey of efficiently solvable special cases of the permutation flow-shop problem
C. Monma (1983)
A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem
M. Nawaz (1983)
Some new results in flowshop scheduling
H. Roeck (1984)
A Microcomputer Based Solution to a Practical Scheduling Problem
A. Hodson (1985)
The flow shop problem with time lags and separated setup times
W. Szwarc (1986)
A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process
N. Hall (1996)
Shop Problems With Two Machines and Time Lags
M. Dell'Amico (1996)
Search heuristics for a flowshop scheduling problem in a printed circuit board assembly process
Y. Kim (1996)
Single machine scheduling with chain: structured precedence constraints and separation time windows
Chengbin Chu (1996)
On the Complexity of Coupled-task Scheduling
A. J. Orman (1997)
A Branch and Bound Algorithm for a Single-machine Scheduling Problem with Positive, Negative Time-lags
P. Brucker (1999)
Scheduling unit execution time tasks with symmetric time-lags
R. Janczewski (2001)
Minimizing total completion time in a no-wait flowshop with sequence-dependent additive changeover times
A. Allahverdi (2001)
General Flowshop Models: Job Dependent Capacities, Job Overlapping and Deterioration
G. Finke (2002)
A note on minimizing maximum lateness in a two-machine no-wait flowshop
P. Dileepan (2004)
Scheduling of coupled tasks
M. Tanas (2004)
Two-Machine No-Wait Flowshop Scheduling Problem to Minimize Maximum Lateness with Separate Setup and Removal Times
Julien Fondrevelle (2004)
A computational study of the permutation flow shop problem based on a tight lower bound
T. Ladhari (2005)
Résolution exacte de problèmes d'ordonnancement de type flowshop de permutation en présence de contraintes d'écarts temporels entre opérations. (Exact solution to permutation flowshop problems with time lag constraints between operations)
Julien Fondrevelle (2005)
Re´solution exacte de problemes d'ordonnancement de type flowshop de permutation en pre´sence de contraintes d'e´carts temporels entre ope´rations. Thesis (PhD)
J Fondrevelle (2005)
Permutation flowshop scheduling problems with maximal and minimal time lags
Julien Fondrevelle (2006)
Model formulations for the machine scheduling problem with limited waiting time constraints
Jen-Shiang Chen (2006)
Approximation algorithms for UET scheduling problems with exact delays
A. Ageev (2007)

This paper is referenced by
Coupled task scheduling with exact delays: Literature review and models
M. Khatami (2020)
A comprehensive review of Branch-and-Bound algorithms: Guidelines and directions for further research on the flowshop scheduling problem
C. P. Tomazella (2020)
Smart Make-to-Order Production in a Flow Shop Environment for Industry 4.0
H. Rahman (2019)
Influence of no-wait and time lag constraints in flowshop scheduling systems
A. Hipp (2019)
Coupled Task Scheduling With Exact Delays: Literature Review and Models
M. Khatami (2018)
Permutation flowshop scheduling with time lag constraints and makespan criterion
Bailin Wang (2018)
Describing the influence of set-up optimised sequencing on output lateness of workstations
Jonas Mayer (2017)
Gene Exchange Operators of Partheno-Genetic Algorithm for Permutation Flowshop Scheduling with Maximum and Minimum Time Lag Constraints
Bailin Wang (2015)
Bounds for the permutation flowshop scheduling problem with exact time lags to minimize the total earliness and tardiness
Imen Hamdi (2014)
Application of a modified GA, ACO and a random search procedure to solve the production scheduling of a case study bakery
F. Hecker (2014)
Application of evolutionary algorithms for bakery production scheduling
F. Hecker (2014)
The two-machine no-wait general and proportionate open shop makespan problem
S. Panwalkar (2014)
A Comparison of Local Search Metaheuristics for a Hierarchical Flow Shop Optimization Problem with Time Lags
Emna Dhouib (2013)
The two-machine flowshop scheduling problem with sequence-independent setup times: New lower bounding strategies
Anis Gharbi (2013)
Two-machine flow shop scheduling of polyurethane foam production
B. M. Lin (2013)
Lexicographic optimization of a permutation flow shop scheduling problem with time lag constraints
Emna Dhouib (2013)
Minimizing the makespan in the permutation flowshop problem with minimal and maximal time lags
Imen Hamdi (2011)
A survey of scheduling problems with setup times or costs
A. Allahverdi (2008)
Semantic Scholar Logo Some data provided by SemanticScholar