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
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
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
10.1002/NAV.3800010110
Optimal two- and three-stage production schedules with setup times included
S. Johnson (1954)
10.1287/MNSC.5.3.293
Sequencing n Jobs on Two Machines with Arbitrary Time Lags
L. G. Mitten (1959)
10.1287/OPRE.12.5.655
Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
P. C. Gilmore (1964)
10.1287/OPRE.13.3.400
Application of the Branch and Bound Technique to Some Flow-Shop Scheduling Problems
E. Ignall (1965)
10.1016/S0167-5060(08)70743-X
Complexity of machine scheduling problems
P. Brucker (1975)
10.1016/0377-2217(80)90069-7
An adaptive branching rule for the permutation flow-shop problem
C. Potts (1978)
10.1109/TC.1980.1675569
Deterministic Scheduling with Pipelined Processors
J. Bruno (1980)
10.1016/0167-6377(82)90035-9
A decomposition algorithm for the single machine total tardiness problem
C. Potts (1982)
10.1051/RO/1983170201051
A concise survey of efficiently solvable special cases of the permutation flow-shop problem
C. Monma (1983)
10.1016/0305-0483(83)90088-9
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)
10.1057/JORS.1985.160
A Microcomputer Based Solution to a Practical Scheduling Problem
A. Hodson (1985)
10.1007/BF01919496
The flow shop problem with time lags and separated setup times
W. Szwarc (1986)
10.1287/opre.44.3.510
A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process
N. Hall (1996)
10.1287/opre.44.5.777
Shop Problems With Two Machines and Time Lags
M. Dell'Amico (1996)
10.1016/0377-2217(95)00119-0
Search heuristics for a flowshop scheduling problem in a printed circuit board assembly process
Y. Kim (1996)
10.1109/70.544767
Single machine scheduling with chain: structured precedence constraints and separation time windows
Chengbin Chu (1996)
10.1016/S0166-218X(96)00041-8
On the Complexity of Coupled-task Scheduling
A. J. Orman (1997)
10.1016/S0166-218X(99)00015-3
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)
10.1057/palgrave.jors.2601110
Minimizing total completion time in a no-wait flowshop with sequence-dependent additive changeover times
A. Allahverdi (2001)
10.1111/1475-3995.00363
General Flowshop Models: Job Dependent Capacities, Job Overlapping and Deterioration
G. Finke (2002)
10.1016/S0305-0548(03)00162-X
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)
10.1016/j.cor.2003.12.001
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)
10.1016/j.cor.2004.11.006
Permutation flowshop scheduling problems with maximal and minimal time lags
Julien Fondrevelle (2006)
10.1080/02522667.2006.10699688
Model formulations for the machine scheduling problem with limited waiting time constraints
Jen-Shiang Chen (2006)
10.1016/j.orl.2006.09.006
Approximation algorithms for UET scheduling problems with exact delays
A. Ageev (2007)



This paper is referenced by
10.1016/j.ejor.2019.08.045
Coupled task scheduling with exact delays: Literature review and models
M. Khatami (2020)
10.1016/j.eswa.2020.113556
A comprehensive review of Branch-and-Bound algorithms: Guidelines and directions for further research on the flowshop scheduling problem
C. P. Tomazella (2020)
10.4018/978-1-5225-9078-1.CH009
Smart Make-to-Order Production in a Flow Shop Environment for Industry 4.0
H. Rahman (2019)
10.1109/IESM45758.2019.8948177
Influence of no-wait and time lag constraints in flowshop scheduling systems
A. Hipp (2019)
10.2139/ssrn.3333563
Coupled Task Scheduling With Exact Delays: Literature Review and Models
M. Khatami (2018)
10.1016/j.cie.2018.04.021
Permutation flowshop scheduling with time lag constraints and makespan criterion
Bailin Wang (2018)
10.1080/09537287.2017.1314038
Describing the influence of set-up optimised sequencing on output lateness of workstations
Jonas Mayer (2017)
10.2991/MEITA-15.2015.109
Gene Exchange Operators of Partheno-Genetic Algorithm for Permutation Flowshop Scheduling with Maximum and Minimum Time Lag Constraints
Bailin Wang (2015)
10.1504/IJOR.2017.080596
Bounds for the permutation flowshop scheduling problem with exact time lags to minimize the total earliness and tardiness
Imen Hamdi (2014)
10.1016/j.eswa.2014.03.047
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)
10.1016/j.ejor.2014.04.030
The two-machine no-wait general and proportionate open shop makespan problem
S. Panwalkar (2014)
10.1002/9781118731598.CH4
A Comparison of Local Search Metaheuristics for a Hierarchical Flow Shop Optimization Problem with Time Lags
Emna Dhouib (2013)
10.1016/j.ejor.2013.05.031
The two-machine flowshop scheduling problem with sequence-independent setup times: New lower bounding strategies
Anis Gharbi (2013)
10.1016/J.IJPE.2012.08.006
Two-machine flow shop scheduling of polyurethane foam production
B. M. Lin (2013)
10.1111/j.1475-3995.2012.00876.x
Lexicographic optimization of a permutation flow shop scheduling problem with time lag constraints
Emna Dhouib (2013)
10.1109/CCCA.2011.6031387
Minimizing the makespan in the permutation flowshop problem with minimal and maximal time lags
Imen Hamdi (2011)
10.1016/j.ejor.2006.06.060
A survey of scheduling problems with setup times or costs
A. Allahverdi (2008)
Semantic Scholar Logo Some data provided by SemanticScholar