A Comparative Study of Flow-Shop Algorithms

Kenneth R. Baker
Kenneth R. Baker
Duke University, Durham, North Carolina
Search for more papers by this author

Duke University, Durham, North Carolina

Published Online:1 Feb 1975https://doi.org/10.1287/opre.23.1.62

Abstract

This paper describes an experimental comparison of flow-shop algorithms, motivated by the need to consolidate recent research on this topic. Using a set of test problems, it investigated various branch-and-bound and elimination strategies in a comparative study and then combined them to produce a new and efficient solution algorithm.

Cited by
- Permutation flowshop scheduling to obtain the optimal solution/a lower bound with the makespan objective
  7 September 2020 | Sādhanā, Vol. 45, No. 1
- A computationally efficient Branch-and-Bound algorithm for the permutation flow-shop scheduling problem
  European Journal of Operational Research, Vol. 284, No. 3
- An Entropy Measure of Flow Dominance for Predicting Operations Performance
  1 October 2016 | Production and Operations Management, Vol. 25, No. 10
- Flow Shops and Flexible Flow Shops (Deterministic)
  11 February 2016
- A block based estimation of distribution algorithm using bivariate model for scheduling problems
  6 October 2013 | Soft Computing, Vol. 18, No. 6
- The m-Machine Flow Shop
  22 August 2012
- A Bottleneck-Assignment Based Branch-and-Bound Algorithm to Minimize the Makespan in an m-Machine Permutation Flowshop
  22 January 2013 | Technology Operation Management, Vol. 3, No. 1-2
- Trading off between makespan and customer responsiveness in flow shop sequencing
  15 September 2010 | International Journal of Production Research, Vol. 48, No. 22
- Using composite variable modeling to achieve realism and tractability in production planning: An example from automotive stamping
  3 March 2009 | IIE Transactions, Vol. 41, No. 5
- Multi-objective Simulated Annealing for Permutation Flow Shop Problems
- Scheduling Practice and Recent Developments in Flow Shop and Job Shop Scheduling
- Ant colony optimization for multi-objective flow shop scheduling problem
  Computers & Industrial Engineering, Vol. 54, No. 3
- A Lagrangean relaxation approach for the mixed-model flow line sequencing problem
  Computers & Operations Research, Vol. 35, No. 3
- Exact, Heuristic and Meta-heuristic Algorithms for Solving Shop Scheduling Problems
- Flow shop-sequencing problem with synchronous transfers and makespan minimization
  International Journal of Production Research, Vol. 45, No. 15
- A branch and bound procedure for the reentrant permutation flow-shop scheduling problem
  1 October 2005 | The International Journal of Advanced Manufacturing Technology, Vol. 29, No. 11-12
- Employee scheduling and makespan minimization in a flow shop with multi-processor work stations: a case study
  Omega, Vol. 32, No. 2
- A new lower bounding rule for permutation flow shop scheduling
  Journal of Information and Optimization Sciences, Vol. 22, No. 2
- Scheduling in Flow and Open Shops
- A permutation flow-shop scheduling problem with convex models of operation processing times
  Annals of Operations Research, Vol. 96, No. 1-4
- Makespan minimization in the two‐machine flowshop batch scheduling problem
  31 January 2000 | Naval Research Logistics (NRL), Vol. 47, No. 2
- Processes with nearly‐sequential routings: a comparative analysis
  10 May 1999 | Journal of Operations Management, Vol. 17, No. 4
- Genetic algorithm for the permutation flow-shopscheduling problem with linear models of operations
  Annals of Operations Research, Vol. 83, No. 0
- Minimization of the makespan in a two-machine problem under given resource constraints
  European Journal of Operational Research, Vol. 107, No. 2
- Distributed computing approaches toward manufacturing scheduling problems
  IIE Transactions, Vol. 30, No. 4
- Two-stage flowshop scheduling with a common second-stage machine
  Computers & Operations Research, Vol. 24, No. 12
- Scheduling permutation flow shops using the Lagrangian relaxation technique
  Annals of Operations Research, Vol. 70, No. 0
- A branch-and-bound algorithm with fuzzy inference for a permutation flowshop scheduling problem
  European Journal of Operational Research, Vol. 96, No. 3
- Flow-line scheduling problem with controllable processing times
  IIE Transactions, Vol. 29, No. 1
- The job shop scheduling problem: Conventional and new solution techniques
  European Journal of Operational Research, Vol. 93, No. 1
- A heuristic approach to n / m job shop scheduling: fuzzy dynamic scheduling algorithms
  27 April 2007 | Production Planning & Control, Vol. 7, No. 3
- Scheduling in Flexible Manufacturing Systems
- Scheduling in Flow and Open Shops
- Intelligence in Numerical Computing: Improving Batch Scheduling Algorithms through Explanation-Based Learning
- The interface of buffer design and cyclic scheduling decisions in deterministic flow lines
  Annals of Operations Research, Vol. 50, No. 1
- Influence of the structure of a static permutatino flowshop problem on the performance of single shot heuristics
  Computers & Industrial Engineering, Vol. 26, No. 3
- Scheduling in Flexible Manufacturing Systems
- The permutation flow shop problem with sum-of-completion times performance criterion
  Naval Research Logistics, Vol. 40, No. 6
- A tabu-search heuristic for the flexible-resource flow shop scheduling problem
  Annals of Operations Research, Vol. 41, No. 3
- Scheduling heuristic for the n-jobm-machine flow shop
  Omega, Vol. 21, No. 2
- Scheduling in Flexible Manufacturing Systems
- Addressing the gap in scheduling research: a review of optimization and heuristic methods in production scheduling
  27 April 2007 | International Journal of Production Research, Vol. 31, No. 1
- Neighbourhood search-based optimization algorithms for production scheduling: a survey
  Computer Integrated Manufacturing Systems, Vol. 5, No. 2
- A heuristic algorithm to schedule work in the repair industry
  International Journal of Production Research, Vol. 29, No. 12
- Algebraic, mathematical programming, and network models of the deterministic job-shop scheduling problem
  IEEE Transactions on Systems, Man, and Cybernetics, Vol. 21, No. 3
- Branch and bound algorithm for the flow shop with multiple processors
  European Journal of Operational Research, Vol. 51, No. 1
- Multiobjective flow-shop scheduling
  Naval Research Logistics, Vol. 37, No. 6
- Job-shop scheduling: limits of the binary disjunctive formulation
  30 March 2007 | International Journal of Production Research, Vol. 28, No. 12
- SCHEDULING OF BATCH PLANTS
- Flowshop Sequencing: A Graphical Approach
  SSRN Electronic Journal
- A new integer programming formulation for the permutation flowshop problem
  European Journal of Operational Research, Vol. 40, No. 1
- Elimination conditions and lower bounds for the permutation flow-shop sequencing problem
  Acta Mathematicae Applicatae Sinica, Vol. 2, No. 4
- Sequencing a generalized two-stage flowshop with finite intermediate storage
  Computers & Chemical Engineering, Vol. 9, No. 3
- Decomposition approaches in permutation scheduling problems with application to the M-machine flow shop scheduling problems
  European Journal of Operational Research, Vol. 19, No. 1
- Flowshop sequencing with probabilistic processing times
  Engineering Costs and Production Economics, Vol. 7, No. 2
- A heuristic proǵramminǵ procedure for sequencinǵ the static flowshop
  6 April 2007 | International Journal of Production Research, Vol. 20, No. 6
- An adaptive branching rule for the permutation flow-shop problem
  European Journal of Operational Research, Vol. 5, No. 1
- An improved lexicographic search algorithm for the flowshop scheduling problem
  Computers & Operations Research, Vol. 6, No. 2
- Four simple heuristics for scheduling a flow-shop
  International Journal of Production Research, Vol. 16, No. 3
- An improved branch and bound procedure for n × m flow shop problems
  21 November 2006 | Naval Research Logistics Quarterly, Vol. 22, No. 4
- References††The first comprehensive references list is due to Balinski and Spielberg (1969). A later list appears in the work of Garfinkel and Nemhauser (1972b).
- Scheduling in Flexible Manufacturing Systems
- Flow Shop Scheduling
- A branch and bound algorithm for the flow-shop scheduling problem
- A new scheduling algorithm based on approximate reasoning for manufacturing applications
- Multicriteria Flow-Shop Scheduling Problem

Volume 23, Issue 1

January-February 1975

Pages 2-187

Article Information

Metrics

Information

Published Online:February 01, 1975

Cite as

Kenneth R. Baker, (1975) A Comparative Study of Flow-Shop Algorithms. Operations Research 23(1):62-73.

https://doi.org/10.1287/opre.23.1.62

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

A Comparative Study of Flow-Shop Algorithms

Abstract

Volume 23, Issue 1

Article Information

Metrics

Information

Cite as

Sign Up for INFORMS Publications Updates and News