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

Permutation Flowshop Scheduling Problems With Maximal And Minimal Time Lags

J. Fondrevelle, A. Oulamara, M. Portmann
Published 2006 · Mathematics, Computer Science

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 study permutation flowshop problems with minimal and/or maximal time lags, where the time lags are defined between couples of successive operations of jobs. Such constraints may be used to model various industrial situations, for instance the production of perishable products. We present theoretical results concerning two-machine cases, we prove that the two-machine permutation flowshop with constant maximal time lags is strongly NP-hard. We develop an optimal branch and bound procedure to solve the m-machine permutation flowshop problem with minimal and maximal time lags. We test several lower bounds and heuristics providing upper bounds on different classes of benchmarks, and we carry out a performance analysis.
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)
A Heuristic Algorithm for the n Job, m Machine Sequencing Problem
H. G. Campbell (1970)
Machine Scheduling Problems: Classification, Complexity and Computations
A. H. G. Rinnooy Kan (1976)
Computers and Intractability: A Guide to the Theory of NP-Completeness
M. Garey (1978)
A Microcomputer Based Solution to a Practical Scheduling Problem
A. Hodson (1985)
Sequencing and scheduling
J. K. Lenstra (1985)
Handbooks in operations research and management science
G. Nemhauser (1989)
Sequencing and scheduling: algorithms and complexity
E. Lawler (1989)
A heuristic algorithm for flow shop sequencing problems
Rajasekhar Aalla (1992)
Chapter 9 Sequencing and scheduling: Algorithms and complexity
E. Lawler (1993)
A two-machine flowshop sequencing problem with limited waiting time constraints
D. Yang (1995)
The two-machine flow shop problem with delays and the one-machine total tardiness problem
W. Yu (1996)
Shop Problems With Two Machines and Time Lags
M. Dell'Amico (1996)
Single machine scheduling with chain: structured precedence constraints and separation time windows
Chengbin Chu (1996)
General Flowshop Models: Job Dependent Capacities, Job Overlapping and Deterioration
G. Finke (2002)
Complexity Results for Flow-Shop and Open-Shop Scheduling Problems with Transportation Delays
P. Brucker (2004)
Ordonnancement d'atelier avec contraintes temporelles entre opérations. (Scheduling problems with minimal and maximal time lag constraints)
Freddy Deppner (2004)
Minimizing Makespan in a Two-Machine Flow Shop with Delays and Unit-Time Operations is NP-Hard
W. Yu (2004)

This paper is referenced by
Exact method for the two-machine flow-shop problem with time delays
M. Mkadem (2021)
A hybrid evolutionary approach to job-shop scheduling with generic time lags
Madiha Harrabi (2021)
A comprehensive review of Branch-and-Bound algorithms: Guidelines and directions for further research on the flowshop scheduling problem
C. P. Tomazella (2020)
Two-machine flowshop scheduling problem with coupled-operations
N. Meziani (2019)
Minimizing the makespan in a flow shop environment under minimum and maximum time-lag constraints
Hamed Samarghandi (2019)
Three-machine flow shop scheduling with overlapping waiting time constraints
H. Kim (2019)
Influence of no-wait and time lag constraints in flowshop scheduling systems
A. Hipp (2019)
MILP models and valid inequalities for the two-machine permutation flowshop scheduling problem with minimal time lags
Imen Hamdi (2019)
Max-plus to solve the cyclic job shop problem with time lags
J. Barman (2018)
Permutation flowshop scheduling with time lag constraints and makespan criterion
Bailin Wang (2018)
Non-permutation flowshop scheduling problem with minimal and maximal time lags: theoretical study and heuristic
Emna Dhouib (2018)
Supply chain optimisation with both production and transportation integration: multiple vehicles for a single perishable product
P. Lacomme (2018)
A Branch and Bound Algorithm for Three-Machine Flow Shop with Overlapping Waiting Time Constraints
H. Kim (2017)
Competitive Agents Implementing Parallel Tabu Searches for Job Shop Scheduling Problem with Time Lags
Madiha Harrabi (2017)
Combining genetic algorithm and tabu search metaheuristic for job shop scheduling problem with generic time lags
Madiha Harrabi (2017)
Efficient heuristic for solving non-permutation flow-shop scheduling problems with maximal and minimal time lags
Song Ye (2017)
Effective Iterated Greedy Algorithm for Flow-Shop Scheduling Problems with Time lags
Ning Zhao (2017)
Minimizing the total completion time in a two-machine flowshop problem with time delays
Mohamed Kais Msakni (2016)
Complex Job-Shop Scheduling with Batching in Semiconductor Manufacturing
Sebastian Knopp (2016)
Research on medical scheduling problem with patient limited waiting and Variable Maintenance Duration
Yanhui Yu (2016)
Research on Coordination Scheduling Model and Application for Parallel Production Lines
Hongguang Bo (2016)
Gene Exchange Operators of Partheno-Genetic Algorithm for Permutation Flowshop Scheduling with Maximum and Minimum Time Lag Constraints
Bailin Wang (2015)
Upper and lower bounds for the permutation flowshop scheduling problem with minimal time lags
Imen Hamdi (2015)
Gene Shift Operators of Partheno-Genetic Algorithm for Permutation Flowshop Scheduling with Limited Waiting Times
Bailin Wang (2015)
A comparison of two-machine flowshop with availability constraints for limited waiting time
Yanhui Yu (2015)
Minimizing total tardiness in the permutation flowshop scheduling problem with minimal and maximal time lags
Imen Hamdi (2015)
Scatter search with path relinking for the job shop with time lags and setup times
M. González (2015)
Investigating the Efficiency of GRASP for the SDST HFS with Controllable Processing Times and Assignable Due Dates
M. Ashrafi (2014)
Lagrangian relaxation for the permutation flowshop scheduling problem with minimal and maximal time lags
Imen Hamdi (2014)
An efficient genetic algorithm for a hybrid flow shop scheduling problem with time lags and sequence-dependent setup time
Mohammad Farahmand-Mehr (2014)
Partheno-Genetic Algorithm for the Permutation Flowshop Scheduling Problem with Maximum Waiting Times
B. Wang (2014)
The two-machine no-wait general and proportionate open shop makespan problem
S. Panwalkar (2014)
See more
Semantic Scholar Logo Some data provided by SemanticScholar