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

A Branch-and-bound Algorithm For A Two-machine Flowshop Scheduling Problem With Limited Waiting Time Constraints

B. Joo, Y.-D. Kim
Published 2009 · 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 consider a two-machine flowshop scheduling problem in which the waiting time of each job between the two machines cannot be greater than a certain time period. For the problem with the objective of minimizing makespan, we identify several dominance properties of the problem and develop a branch-and-bound (B&B) algorithm using the dominance properties. Computational tests are performed on randomly generated test problems for evaluation of performance of the B&B algorithm, and results show that the algorithm can solve problems with up to 150 jobs in a reasonable amount of CPU time.
This paper references
10.1002/NAV.3800010110
Optimal two- and three-stage production schedules with setup times included
S. Johnson (1954)
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)
Application of branch-and-bound technique to some flow shop problems
E Ignall (1965)
10.1080/00207546808929814
A GENERAL ALGORITHM FOR THE n × M FLOWSHOP SCHEDULING PROBLEM†
J. N. Gupta (1968)
10.1287/opre.19.7.1753
Technical Note - An Improved Combinatorial Algorithm for the Flowshop-Scheduling Problem
Jatinder N. D. Gupta (1971)
An improved combinatorial algorithm for the flowshop scheduling problem
JND Gupta (1971)
10.1080/05695557208974856
Optimal Scheduling in a Multistage Flowshop
J. Gupta (1972)
Optimal scheduling in a multi-stage flowshop
JND Gupta (1972)
10.1287/opre.21.6.1250
Optimal Elimination Methods in the m × n Flow-Shop Scheduling Problem
W. Szwarc (1973)
10.1002/NAV.3800210311
Two machine flow shop scheduling problems with sequence dependent setup times: A dynamic programming approach
Burton D. Corwin (1974)
10.1057/jors.1977.60
Introduction to sequencing and scheduling
A. J. Clewett (1974)
Two-machine flowshop scheduling problems with sequence dependent setup times: A dynamic programming approach
BB Corwin (1974)
10.1287/opre.26.1.53
A General Bounding Scheme for the Permutation Flow-Shop Problem
B. Lageweg (1978)
10.1016/0305-0483(83)90088-9
A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem
M. Nawaz (1983)
A heuristic m-machine flowshop scheduling method under the total tardiness criterion
Y. Choi (1992)
10.1016/0305-0548(93)90083-U
A new branch and bound algorithm for minimizing mean tardiness in two-machine flowshops
Y. Kim (1993)
10.1057/JORS.1993.3
Heuristics for Flowshop Scheduling Problems Minimizing Mean Tardiness
Y. Kim (1993)
10.1016/0360-8352(94)00026-J
A two-machine flowshop sequencing problem with limited waiting time constraints
D. Yang (1995)
10.1016/0377-2217(94)00029-C
Minimizing total tardiness in permutation flowshops
Y. Kim (1995)
A heuristic algorithm for mean flowtime minimization in permutation flowshop scheduling
H. Woo (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.1016/S0360-8352(02)00216-4
A hybrid two-stage flowshop with limited waiting time constraints
Ling-Huey Su (2003)
10.1057/palgrave.jors.2601784
A review and classification of heuristics for permutation flow-shop scheduling with makespan objective
J. Framiñan (2004)
10.1007/s10288-005-0069-7
Two-machine flow shop scheduling problems with minimal and maximal delays
Jean-Louis Bouquard (2006)
10.1016/j.dam.2005.04.011
Application of an optimization problem in Max-Plus algebra to scheduling problems
Jean-Louis Bouquard (2006)
10.1016/j.cor.2004.11.006
Permutation flowshop scheduling problems with maximal and minimal time lags
Julien Fondrevelle (2006)
10.1016/j.ejor.2005.02.001
Flowshop scheduling research after five decades
J. Gupta (2006)
10.1057/palgrave.jors.2602220
Minimizing makespan on a two-machine re-entrant flowshop
S. Choi (2007)
10.1016/j.cor.2006.09.028
Minimizing makespan on an m-machine re-entrant flowshop
S. Choi (2008)
10.1111/J.1937-5956.2000.TB00137.X
A REVIEW OF FLOWSHOP SCHEDULING RESEARCH WITH SETUP TIMES
T. E. Cheng (2009)



This paper is referenced by
10.1155/2020/8833645
A Genetic Algorithm for a Two-Machine Flowshop with a Limited Waiting Time Constraint and Sequence-Dependent Setup Times
Ju-Yong Lee (2020)
10.1007/s11518-020-5456-2
Makespan Minimization in Two-Machine Flow-Shop Scheduling under No-wait and Deterministic Unavailable Interval Constraints
Ke-Jia Chen (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.1080/0305215X.2019.1593974
A two-stage flow-shop scheduling problem with incompatible job families and limited waiting time
Y. Li (2020)
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.1016/J.COMPIND.2019.04.014
Sampling-based release control of multiple lots in time constraint tunnels
Alexandre Lima (2019)
10.1109/TEM.2017.2769059
Serial Production Lines With Waiting Time Limits: Bernoulli Reliability Model
Jun-Ho Lee (2018)
10.1109/TASE.2016.2642997
Scheduling Cluster Tools in Semiconductor Manufacturing: Recent Advances and Challenges
C. Pan (2018)
10.1016/j.cie.2018.04.021
Permutation flowshop scheduling with time lag constraints and makespan criterion
Bailin Wang (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)
Optimal Scheduling Algorithms to Minimize Total Flowtime on a Two-Machine Permutation Flowshop with Limited Waiting Times and Ready Times of Jobs
S. Choi (2017)
10.1016/j.cor.2016.01.017
Minimizing makespan in a two-machine flowshop with a limited waiting time constraint and sequence-dependent setup times
Young-Jin An (2016)
Heuristics for a two-machine permutation flowshop with limited queue time constraint and arrival times in a semiconductor manufacturing line
Seong-Woo Choi (2016)
10.1080/0951192X.2013.820348
Solving a new multi-objective hybrid flexible flowshop problem with limited waiting times and machine-sequence-dependent set-up time constraints
S. F. Attar (2014)
10.11591/TELKOMNIKA.V12I4.4783
Scheduling Two-machine Flowshop with Limited Waiting Times to Minimize Makespan
Bailin Wang (2014)
10.1109/WSC.2013.6721724
Two-stage lot scheduling with waiting time constraints and due dates
Tae-Sun Yu (2013)
10.1002/9781118731598.CH4
A Comparison of Local Search Metaheuristics for a Hierarchical Flow Shop Optimization Problem with Time Lags
Emna Dhouib (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/CSCWD.2012.6221901
An integrated and improved dispatching approach to reduce cycle time of wet etch and furnace operations in semiconductor fabrication
Chia-Yu Chang (2012)
10.5897/AJBM11.2232
Proposing a clonal selection algorithm for hybrid flow shop
M. Akhshabi (2012)
10.1016/j.cor.2011.10.006
Two-stage hybrid flow shop scheduling with dynamic job arrivals
Frank S. Yao (2012)
10.1016/j.cor.2011.02.017
A discrete time exact solution approach for a complex hybrid flow-shop scheduling problem with limited-wait constraints
C. Gicquel (2012)
A Scheduling Algorithm for Workstations with Limited Waiting Time Constraints in a Semiconductor Wafer Fabrication Facility
Byung-Jun Joo (2009)
10.1109/CCDC.2009.5194990
Batch delivery scheduling with limited waiting time constraint on a single machine
H. Gong (2009)
Semantic Scholar Logo Some data provided by SemanticScholar