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
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 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
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.1287/MNSC.16.10.B630
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)
10.1057/JORS.1985.160
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)
10.1016/S0927-0507(05)80189-6
Chapter 9 Sequencing and scheduling: Algorithms and complexity
E. Lawler (1993)
10.1016/0360-8352(94)00026-J
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)
10.1287/opre.44.5.777
Shop Problems With Two Machines and Time Lags
M. Dell'Amico (1996)
10.1109/70.544767
Single machine scheduling with chain: structured precedence constraints and separation time windows
Chengbin Chu (1996)
10.1111/1475-3995.00363
General Flowshop Models: Job Dependent Capacities, Job Overlapping and Deterioration
G. Finke (2002)
10.1023/B:ANOR.0000030683.64615.c8
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)
10.1023/B:JOSH.0000036858.59787.c2
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
10.1007/S10479-018-3082-X
Exact method for the two-machine flow-shop problem with time delays
M. Mkadem (2021)
10.1007/s10951-021-00683-w
A hybrid evolutionary approach to job-shop scheduling with generic time lags
Madiha Harrabi (2021)
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.1007/s10479-018-2967-z
Two-machine flowshop scheduling problem with coupled-operations
N. Meziani (2019)
10.1016/J.CIE.2019.07.048
Minimizing the makespan in a flow shop environment under minimum and maximum time-lag constraints
Hamed Samarghandi (2019)
10.1016/j.cor.2018.06.009
Three-machine flow shop scheduling with overlapping waiting time constraints
H. Kim (2019)
10.1109/IESM45758.2019.8948177
Influence of no-wait and time lag constraints in flowshop scheduling systems
A. Hipp (2019)
10.1007/s40092-019-00331-1
MILP models and valid inequalities for the two-machine permutation flowshop scheduling problem with minimal time lags
Imen Hamdi (2019)
10.1109/CoDIT.2018.8394918
Max-plus to solve the cyclic job shop problem with time lags
J. Barman (2018)
10.1016/j.cie.2018.04.021
Permutation flowshop scheduling with time lag constraints and makespan criterion
Bailin Wang (2018)
10.1007/s10479-018-2775-5
Non-permutation flowshop scheduling problem with minimal and maximal time lags: theoretical study and heuristic
Emna Dhouib (2018)
10.1080/00207543.2018.1431416
Supply chain optimisation with both production and transportation integration: multiple vehicles for a single perishable product
P. Lacomme (2018)
10.1016/J.IFACOL.2017.08.391
A Branch and Bound Algorithm for Three-Machine Flow Shop with Overlapping Waiting Time Constraints
H. Kim (2017)
10.2316/P.2017.848-052
Competitive Agents Implementing Parallel Tabu Searches for Job Shop Scheduling Problem with Time Lags
Madiha Harrabi (2017)
10.1109/ICEMIS.2017.8272985
Combining genetic algorithm and tabu search metaheuristic for job shop scheduling problem with generic time lags
Madiha Harrabi (2017)
10.1016/j.cie.2017.08.024
Efficient heuristic for solving non-permutation flow-shop scheduling problems with maximal and minimal time lags
Song Ye (2017)
10.1007/S10033-017-0108-2
Effective Iterated Greedy Algorithm for Flow-Shop Scheduling Problems with Time lags
Ning Zhao (2017)
10.1080/0305215X.2015.1099639
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)
10.1109/CCDC.2016.7531348
Research on medical scheduling problem with patient limited waiting and Variable Maintenance Duration
Yanhui Yu (2016)
10.2991/ICMMCT-16.2016.296
Research on Coordination Scheduling Model and Application for Parallel Production Lines
Hongguang Bo (2016)
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.1007/s11590-014-0761-7
Upper and lower bounds for the permutation flowshop scheduling problem with minimal time lags
Imen Hamdi (2015)
10.2991/ESAC-15.2015.52
Gene Shift Operators of Partheno-Genetic Algorithm for Permutation Flowshop Scheduling with Limited Waiting Times
Bailin Wang (2015)
10.1109/CCDC.2015.7161997
A comparison of two-machine flowshop with availability constraints for limited waiting time
Yanhui Yu (2015)
10.1007/s12351-014-0166-5
Minimizing total tardiness in the permutation flowshop scheduling problem with minimal and maximal time lags
Imen Hamdi (2015)
10.1016/j.cor.2015.02.005
Scatter search with path relinking for the job shop with time lags and setup times
M. González (2015)
10.4018/978-1-4666-4450-2.CH018
Investigating the Efficiency of GRASP for the SDST HFS with Controllable Processing Times and Assignable Due Dates
M. Ashrafi (2014)
10.1109/CoDIT.2014.6996865
Lagrangian relaxation for the permutation flowshop scheduling problem with minimal and maximal time lags
Imen Hamdi (2014)
10.1051/MFREVIEW/2014020
An efficient genetic algorithm for a hybrid flow shop scheduling problem with time lags and sequence-dependent setup time
Mohammad Farahmand-Mehr (2014)
10.4028/www.scientific.net/AMM.631-632.66
Partheno-Genetic Algorithm for the Permutation Flowshop Scheduling Problem with Maximum Waiting Times
B. Wang (2014)
10.1016/j.ejor.2014.04.030
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