Flowshop and Jobshop Schedules: Complexity and Approximation

Teofilo Gonzalez
Teofilo Gonzalez
University of Minnesota, Minneapolis, Minnesota
Search for more papers by this author
,
Sartaj Sahni
Sartaj Sahni
University of Minnesota, Minneapolis, Minnesota
Search for more papers by this author

Teofilo Gonzalez

University of Minnesota, Minneapolis, Minnesota

Search for more papers by this author

Sartaj Sahni

University of Minnesota, Minneapolis, Minnesota

Search for more papers by this author

Published Online:1 Feb 1978https://doi.org/10.1287/opre.26.1.36

Abstract

We show that finding minimum finish time preemptive and non-preemptive schedules for flow shops and job shops is NP-complete. Bounds on the performance of various heuristics to generate reasonably good schedules are also obtained.

Cited by
- A contextual snapshot learning-based deep reinforcement learning for reliability-aware flexible job shop scheduling in semiconductor manufacturing
  15 March 2026 | The International Journal of Advanced Manufacturing Technology, Vol. 143, No. 9-10
- A two-stage iterated greedy algorithm for distributed blocking flowshop scheduling problem
  Expert Systems with Applications, Vol. 300
- Sustainable scheduling for job shops with joint maintenance, machine speed scaling, and uncertain processing times
  Robotics and Computer-Integrated Manufacturing, Vol. 97
- Scheduling for two stages with a single machine and a job shop
  Computers & Operations Research, Vol. 183
- Flexible Job Shop Scheduling Problem using graph neural networks and reinforcement learning
  Computers & Operations Research, Vol. 182
- Extended Invalid Action Mask: Training-Time Size-Agnostic Safe Reinforcement Learning for Flexible Job Shop Scheduling Problems
- Research Progress and Prospects of Job Shop Scheduling Algorithms
- HILP: Accounting for Workload-Level Parallelism in System-on-Chip Design Space Exploration
- Matrix Assembly System Scheduling Optimization in Automotive Manufacturing: A Deep Q-Network Approach
- Smart scheduling of dynamic job shop based on discrete event simulation and deep reinforcement learning
  24 June 2023 | Journal of Intelligent Manufacturing, Vol. 35, No. 6
- Bicriteria two-machine flowshop scheduling: approximation algorithms and their limits
  31 May 2023 | Journal of Scheduling, Vol. 27, No. 1
- An actor-critic algorithm with policy gradients to solve the job shop scheduling problem using deep double recurrent agents
  European Journal of Operational Research, Vol. 312, No. 3
- A Hyper-Heuristic Algorithm with Q-Learning for Distributed Flow Shop-Vehicle Transport-U-Assembly Integrated Scheduling Problem
  21 August 2024
- DAG-based workflows scheduling using Actor–Critic Deep Reinforcement Learning
  Future Generation Computer Systems, Vol. 150
- A general efficient neighborhood structure framework for the job-shop and flexible job-shop scheduling problems
  European Journal of Operational Research, Vol. 311, No. 2
- Modeling and optimization of bakery production scheduling to minimize makespan and oven idle time
  5 January 2023 | Scientific Reports, Vol. 13, No. 1
- A reinforcement learning method for scheduling service function chains with multi-resource constraints
  Computer Networks, Vol. 235
- A knowledge-driven cooperative scatter search algorithm with reinforcement learning for the distributed blocking flow shop scheduling problem
  Expert Systems with Applications, Vol. 230
- A state-of-the-art survey on multi-scenario scheduling
  European Journal of Operational Research, Vol. 310, No. 1
- A cooperative population-based iterated greedy algorithm for distributed permutation flowshop group scheduling problem
  Engineering Applications of Artificial Intelligence, Vol. 125
- An effective hyper heuristic-based memetic algorithm for the distributed assembly permutation flow-shop scheduling problem
  Applied Soft Computing, Vol. 135
- A Hyper-Heuristic Algorithm with Q-Learning for Distributed Permutation Flowshop Scheduling Problem
  30 July 2023
- Multi-Resource Scheduling for Multiple Service Function Chains with Deep Reinforcement Learning
- Complexity and approximation of open shop scheduling to minimize the makespan: A review of models and approaches
  Computers & Operations Research, Vol. 144
- Application of Non-Dominated Sorting Genetic Algorithm (NSGA-II) to Increase the Efficiency of Bakery Production: A Case Study
  16 August 2022 | Processes, Vol. 10, No. 8
- Optimal Management of Production and Maintenance Actions According to an Integrated Scheduling Strategy with Operational Considerations
- An approach for joint scheduling of production and predictive maintenance activities
  Journal of Manufacturing Systems, Vol. 64
- An Integrated Intelligent Computation for Complex Problems in Engineering Management
- Distributed assembly permutation flow-shop scheduling problem with sequence-dependent set-up times using a novel biogeography-based optimization algorithm
  25 February 2021 | Engineering Optimization, Vol. 54, No. 4
- Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph
  16 August 2021 | Journal of Combinatorial Optimization, Vol. 43, No. 3
- Scheduling Coflows With Dependency Graph
  IEEE/ACM Transactions on Networking, Vol. 30, No. 1
- Heuristic Scheduling of Job Orders in a Build-to-Order Manufacturing System
  Computer Systems Science and Engineering, Vol. 40, No. 3
- Flow shop scheduling with general position weighted learning effects to minimise total weighted completion time
  1 September 2020 | Journal of the Operational Research Society, Vol. 72, No. 12
- Minimizing total job completion time in MapReduce scheduling
  Computers & Industrial Engineering, Vol. 158
- A matrix-cube-based estimation of distribution algorithm for the distributed assembly permutation flow-shop scheduling problem
  Swarm and Evolutionary Computation, Vol. 60
- A Mixed-Integer Linear Model for Solving the Open Shop Scheduling Problem
  29 July 2021
- An integrated cuckoo search optimizer for single and multi-objective optimization problems
  11 March 2021 | PeerJ Computer Science, Vol. 7
- CONVJSSP: Convolutional Learning for Job-Shop Scheduling Problems
- Algorithms for a two‐machine flowshop problem with jobs of two classes
  23 March 2018 | International Transactions in Operational Research, Vol. 27, No. 6
- Co-scheduling aperiodic real-time tasks with end-to-end firm and soft deadlines in two-stage systems
  21 July 2020 | Real-Time Systems, Vol. 56, No. 4
- An energy-efficient permutation flowshop scheduling problem
  Expert Systems with Applications, Vol. 150
- A Robust Two-Machine Flow-Shop Scheduling Model with Scenario-Dependent Processing Times
  Discrete Dynamics in Nature and Society, Vol. 2020
- Efficient algorithms for flexible job shop scheduling with parallel machines
  11 April 2020 | Naval Research Logistics (NRL), Vol. 67, No. 4
- A new weighted distance-based approximation methodology for flow shop scheduling group decisions under the interval-valued fuzzy processing time
  Applied Soft Computing, Vol. 91
- Min–max regret criterion-based robust model for the permutation flow-shop scheduling problem
  24 May 2019 | Engineering Optimization, Vol. 52, No. 4
- New efficient constructive heuristics for the two-stage multi-machine assembly scheduling problem
  Computers & Industrial Engineering, Vol. 140
- Introduction for Integrated Process Planning and Scheduling
  4 June 2020
- A New Approach to Solve Job Sequencing Problem Using Dynamic Programming with Reduced Time Complexity
  19 July 2020
- Improved heuristics algorithms for re-scheduling flexible job shops in the era of Zero Defect manufacturing
  Procedia Manufacturing, Vol. 51
- Job Shop Scheduling Problem with Job Sizes and Inventories
- Approximation algorithms for process systems engineering
  Computers & Chemical Engineering, Vol. 132
- Integrated optimisation on flow-shop production with cutting stock
  18 December 2018 | International Journal of Production Research, Vol. 57, No. 19
- Study on flow shop scheduling with sum-of-logarithm-processing-times-based learning effects
  30 March 2019 | Journal of Applied Mathematics and Computing, Vol. 61, No. 1-2
- Permutation flowshop scheduling with simple linear deterioration
  15 October 2018 | Engineering Optimization, Vol. 51, No. 8
- A new solution approach for flow shop scheduling with an exponential time-dependent learning effect
- Scheduling Mutual Exclusion Accesses in Equal-Length Jobs
  8 August 2019 | ACM Transactions on Parallel Computing, Vol. 6, No. 2
- Effective heuristics and metaheuristics to minimize total flowtime for the distributed permutation flowshop problem
  Expert Systems with Applications, Vol. 124
- Research on m ‐machine flow shop scheduling with truncated learning effects
  7 July 2016 | International Transactions in Operational Research, Vol. 26, No. 3
- A fully polynomial time approximation scheme for scheduling on parallel identical two-stage openshops
  5 June 2018 | Journal of Combinatorial Optimization, Vol. 37, No. 2
- Online scheduling of ordered flow shops
  European Journal of Operational Research, Vol. 272, No. 1
- New Approach to Solve Dynamic Job Shop Scheduling Problem Using Genetic Algorithm
- A modified Genetic Algorithm approach to minimize total weighted tardiness with stochastic rework and reprocessing times
  Computers & Industrial Engineering, Vol. 123
- A two-stage three-machine assembly flow shop scheduling with learning consideration to minimize the flowtime by six hybrids of particle swarm optimization
  Swarm and Evolutionary Computation, Vol. 41
- An approximation scheme for minimizing the makespan of the parallel identical multi-stage flow-shops
  Theoretical Computer Science, Vol. 734
- Control-Theoretic Models and Algorithms for Supply Chain Scheduling with Capacity Disruption and Recovery Considerations
  8 November 2017
- Approximation Algorithms for Two-Machine Flow-Shop Scheduling with a Conflict Graph
  29 June 2018
- A New Robust Scheduling Model for Permutation Flow Shop Problem
  5 September 2018
- Polymodel description and qualitative analysis of problems for measurement-computer operations planning in cyberphysical systems
  Journal of Applied Engineering Science, Vol. 16, No. 4
- A heuristically directed immune algorithm to minimize makespan and total flow time in permutation flow shops
  27 July 2017 | The International Journal of Advanced Manufacturing Technology, Vol. 93, No. 9-12
- A backtracking search hyper-heuristic for the distributed assembly flow-shop scheduling problem
  Swarm and Evolutionary Computation, Vol. 36
- Approximation results for the two-machine job shop under limited machine availability
  28 January 2017 | OPSEARCH, Vol. 54, No. 3
- Hybrid monkey search algorithm for flow shop scheduling problem under makespan and total flow time
  Applied Soft Computing, Vol. 55
- Iterated local search for distributed multiple assembly no-wait flowshop scheduling
- Fuzzy greedy search heuristic for combinatorial optimization with specific application to machine scheduling
  17 May 2016 | International Journal of Management Science and Engineering Management, Vol. 12, No. 2
- An effective constructive heuristic for permutation flow shop scheduling problem with total flow time criterion
  26 August 2016 | The International Journal of Advanced Manufacturing Technology, Vol. 90, No. 1-4
- An Incorporation of the Fuzzy Greedy Search Heuristic With Evolutionary Approaches for Combinatorial Optimization in Operations Management
  International Journal of Applied Evolutionary Computation, Vol. 8, No. 2
- Solving Scheduling Problems with Genetic Algorithms Using a Priority Encoding Scheme
  18 May 2017
- Fast Multi-objective Hybrid Evolutionary Algorithm for Flow Shop Scheduling Problem
  24 August 2016
- An FPTAS for the parallel two-stage flowshop problem
  Theoretical Computer Science, Vol. 657
- Production scheduling with a piecewise-linear energy cost function
- Correlation of job-shop scheduling problem features with scheduling efficiency
  Expert Systems with Applications, Vol. 62
- Scheduling Methods for Efficient Stamping Operations at an Automotive Company
  1 November 2016 | Production and Operations Management, Vol. 25, No. 11
- A hybrid discrete biogeography-based optimization for the permutation flow shop scheduling problem
  1 October 2015 | International Journal of Production Research, Vol. 54, No. 16
- Flow shop scheduling decisions through Techniques for Order Preference by Similarity to an Ideal Solution (TOPSIS)
  13 July 2016 | International Journal of Production Management and Engineering, Vol. 4, No. 2
- Minimization of maximum lateness in an m-machine permutation flow shop with a general exponential learning effect
  Computers & Industrial Engineering, Vol. 97
- An effective hybrid biogeography-based optimization algorithm for the distributed assembly permutation flow-shop scheduling problem
  Computers & Industrial Engineering, Vol. 97
- Solving permutation flowshop scheduling problems with a discrete differential evolution algorithm
  AI Communications, Vol. 29, No. 2
- Two simple and effective heuristics for minimizing the makespan in non-permutation flow shops
  Computers & Operations Research, Vol. 66
- Permutation flowshop group scheduling with position-based learning effect
  Computers & Industrial Engineering, Vol. 92
- A dynamic model and an algorithm for short-term supply chain scheduling in the smart factory industry 4.0
  19 January 2015 | International Journal of Production Research, Vol. 54, No. 2
- Flow Shops and Flexible Flow Shops (Deterministic)
  11 February 2016
- A PTAS for the Multiple Parallel Identical Multi-stage Flow-Shops to Minimize the Makespan
  27 May 2016
- Bounding the Running Time of Algorithms for Scheduling and Packing Problems
  SIAM Journal on Discrete Mathematics, Vol. 30, No. 1
- Dynamic job sequencing in two parallel two-machine flow shop
- Heuristic algorithms to minimize total weighted tardiness with stochastic rework and reprocessing times
  Journal of Manufacturing Systems, Vol. 37
- Two-agent two-machine flowshop scheduling with learning effects to minimize the total completion time
  Computers & Industrial Engineering, Vol. 87
- Using heuristic algorithms to solve the scheduling problems with job-dependent and machine-dependent learning effects
  22 August 2013 | Journal of Intelligent Manufacturing, Vol. 26, No. 4
- Minimizing total completion time in a two-stage hybrid flow shop with dedicated machines at the first stage
  Computers & Operations Research, Vol. 58
- Permutation flowshop problems with bi-criterion makespan and total completion time objective and position-weighted learning effects
  Computers & Operations Research, Vol. 58
- Proportionate flow shop: New complexity results and models with due date assignment
  29 January 2015 | Naval Research Logistics (NRL), Vol. 62, No. 2
- Scheduling MapReduce Jobs and Data Shuffle on Unrelated Processors
  20 June 2015
- A combination of flow shop scheduling and the shortest path problem
  29 October 2013 | Journal of Combinatorial Optimization, Vol. 29, No. 1
- A Local Search Algorithm for the Flow Shop Scheduling Problem with Release Dates
  Discrete Dynamics in Nature and Society, Vol. 2015
- On the Fairness-Efficiency Tradeoff for Packet Processing with Multiple Resources
  2 December 2014
- An approximation algorithm for the three-machine scheduling problem with the routes given by the same partial order
  Computers & Industrial Engineering, Vol. 76
- An application framework for scheduling optimization problems
- Flow shop scheduling with heterogeneous workers
  European Journal of Operational Research, Vol. 237, No. 2
- A Heuristic Algorithm for Flow Shop Scheduling Problem
  1 September 2014 | Applied Mechanics and Materials, Vol. 643
- Multi-stage supply chain scheduling with non-preemptive continuous operations and execution control
  10 June 2013 | International Journal of Production Research, Vol. 52, No. 13
- The optimal number of used machines in a two-stage flexible flowshop scheduling problem
  8 August 2013 | Journal of Scheduling, Vol. 17, No. 2
- A branch and bound algorithm for the two-machine flowshop problem with unit-time operations and time delays
  7 March 2014 | RAIRO - Operations Research, Vol. 48, No. 2
- A Truncated Sum of Processing‐Times–Based Learning Model for a Two‐Machine Flowshop Scheduling Problem
  20 October 2011 | Human Factors and Ergonomics in Manufacturing & Service Industries, Vol. 24, No. 2
- Flowshop scheduling with a general exponential learning effect
  Computers & Operations Research, Vol. 43
- Some results of the worst-case analysis for flow shop scheduling with a learning effect
  19 April 2013 | Annals of Operations Research, Vol. 211, No. 1
- Several flow shop scheduling problems with truncated position-based learning effect
  Computers & Operations Research, Vol. 40, No. 12
- A scheduling model for the refurbishing process in recycling management
  17 October 2013 | International Journal of Production Research, Vol. 51, No. 23-24
- A new three-machine shop scheduling: complexity and approximation algorithm
  12 April 2012 | Journal of Combinatorial Optimization, Vol. 26, No. 4
- The computational complexity analysis of the two-processor flowshop problems with position dependent job processing times
  Applied Mathematics and Computation, Vol. 221
- New approximation algorithms for flow shop total completion time problem
  Engineering Optimization, Vol. 45, No. 9
- Effective heuristics for the no-wait flow shop scheduling problem with total flow time minimization
  17 August 2012 | The International Journal of Advanced Manufacturing Technology, Vol. 66, No. 9-12
- On-line and semi-online scheduling for flow shop problems on two machines
  Optimization, Vol. 62, No. 4
- An enhanced migrating birds optimization algorithm for no-wait flow shop scheduling problem
- Worst case analysis of flow shop scheduling problems with a time-dependent learning effect
  International Journal of Production Economics, Vol. 142, No. 1
- The m-Machine Flow Shop
  22 August 2012
- The Hybrid Flow Shop
  22 August 2012
- Improved Flow Shop Schedules with Total Completion Time Criterion
- Bounding the Running Time of Algorithms for Scheduling and Packing Problems
- A Hybrid Algorithm for the Permutation Flow Shop Scheduling Problem
- A comprehensive review and evaluation of permutation flowshop heuristics to minimize flowtime
  Computers & Operations Research, Vol. 40, No. 1
- Flowshop Scheduling Problems with a Position-Dependent Exponential Learning Effect
  Mathematical Problems in Engineering, Vol. 2013
- A two-machine flowshop scheduling problem with a truncated sum of processing-times-based learning function
  Applied Mathematical Modelling, Vol. 36, No. 10
- Local search methods for the flowshop scheduling problem with flowtime minimization
  European Journal of Operational Research, Vol. 222, No. 1
- New approximation algorithms for two-machine flow shop total completion time problem
- A composite heuristic for the no-wait flow shop scheduling
- A Genetic-based Algorithm to Find Better Estimation of Non-Dominated Solutions for a Bi-objective Re-entrant Flowshop Scheduling Problem with Outsourcing
  IFAC Proceedings Volumes, Vol. 45, No. 6
- An Improved Immune Algorithm for Manufacturing Scheduling
  15 March 2012 | Advanced Materials Research, Vol. 488-489
- Worst-case and numerical analysis of heuristic algorithms for flowshop scheduling problems with a time-dependent learning effect
  Information Sciences, Vol. 184, No. 1
- An Efficient Meta-heuristic Based on Self-control Dominance Concept for a Bi-objective Re-entrant Scheduling Problem with Outsourcing
- A linear time approximation algorithm for permutation flow shop scheduling
  Theoretical Computer Science, Vol. 416
- Worst-case analysis for flow shop scheduling problems with an exponential learning effect
  21 December 2017 | Journal of the Operational Research Society, Vol. 63, No. 1
- Worst-case behavior of simple sequencing rules in flow shop scheduling with general position-dependent learning effects
  23 June 2011 | Annals of Operations Research, Vol. 191, No. 1
- Two-machine flowshop scheduling with truncated learning to minimize the total completion time
  Computers & Industrial Engineering, Vol. 61, No. 3
- Computational complexity and solution algorithms for flowshop scheduling problems with the learning effect
  Computers & Industrial Engineering, Vol. 61, No. 1
- The application of data mining in erw weld pipe scheduling based on decision tree
- Multi-objective optimization algorithms for flow shop scheduling problem: a review and prospects
  21 December 2010 | The International Journal of Advanced Manufacturing Technology, Vol. 55, No. 5-8
- Minimizing total completion time in two-stage hybrid flow shop with dedicated machines
  Computers & Operations Research, Vol. 38, No. 7
- A novel imperialist competitive algorithm for bi-criteria scheduling of the assembly flowshop problem
  International Journal of Production Research, Vol. 49, No. 11
- Job Shop Scheduling
  14 January 2011
- New high performing hybrid particle swarm optimization for permutation flow shop scheduling problem with minimization of makespan
- An evolutionary approach using fuzzy greedy initialization to permutation flow-shop scheduling with the makespan criterion
- New heuristics for flow shop problem to minimize makespan
  21 December 2017 | Journal of the Operational Research Society, Vol. 61, No. 6
- A fuzzy greedy heuristic for permutation flow-shop scheduling
  21 December 2017 | Journal of the Operational Research Society, Vol. 61, No. 5
- Flow shops with WIP and value added costs
  12 September 2009 | Journal of Scheduling, Vol. 13, No. 1
- Towards an improved resolution of radiotherapy, scheduling
- Bicriteria Scheduling Problem on the Two-Machine Flowshop Using Simulated Annealing
- Two-machine flowshop scheduling problem with bounded processing times to minimize total completion time
  Computers & Mathematics with Applications, Vol. 59, No. 2
- A Decomposition Algorithm for Bicriteria Job-Shop Scheduling Problem with Discretely Controllable Processing Times
- An efficient hybrid heuristic for makespan minimization in permutation flow shop scheduling
  2 December 2008 | The International Journal of Advanced Manufacturing Technology, Vol. 44, No. 5-6
- The bipartite margin shop and maximum red matchings free of blue–red alternating cycles
  Discrete Optimization, Vol. 6, No. 3
- The payoff of a scheduling model within time delay considerations
- Fifty years of scheduling: a survey of milestones
  21 December 2017 | Journal of the Operational Research Society, Vol. 60, No. sup1
- Minimizing total flow time in permutation flow shop scheduling with improved simulated annealing
- Integrated model for the batch sequencing problem in a multi-stage supply chain: an artificial immune system based approach
  26 November 2008 | International Journal of Production Research, Vol. 47, No. 4
- Two machine flow shop scheduling problem with weighted WIP costs
  Computers & Operations Research, Vol. 36, No. 2
- Scheduling in Flowshops with No-Idle Machines
- Scheduling Practice and Recent Developments in Flow Shop and Job Shop Scheduling
- Analysis of heuristics for the UET two-machine flow shop problem with time delays
  Computers & Operations Research, Vol. 35, No. 10
- (Acyclic) Job Shops are Hard to Approximate
- A Fuzzy Approach to Multi-product Mixed Production Job Shop Scheduling Algorithm
- A new lower bound for flow shop makespan with release dates
- Market-Based Model Predictive Control for Large-Scale Information Networks: Completion Time and Value of Solution
  IEEE Transactions on Automation Science and Engineering, Vol. 5, No. 4
- An efficient heuristic approach to total flowtime minimization in permutation flowshop scheduling
  14 August 2007 | The International Journal of Advanced Manufacturing Technology, Vol. 38, No. 9-10
- A bicriteria flowshop scheduling with a learning effect
  Applied Mathematical Modelling, Vol. 32, No. 9
- A Review and Evaluation of Multiobjective Algorithms for the Flowshop Scheduling Problem
  Gerardo Minella,
  Rubén Ruiz,
  Michele Ciavotta,
  1 August 2008 | INFORMS Journal on Computing, Vol. 20, No. 3
- A state-of-the-art review on scheduling with learning effects
  European Journal of Operational Research, Vol. 188, No. 2
- Worst-case analysis for flow shop scheduling with a learning effect
  International Journal of Production Economics, Vol. 113, No. 2
- A two-stage multiple-machine assembly scheduling problem for minimizing sum of completion times
  International Journal of Production Economics, Vol. 113, No. 2
- The tricriteria flowshop scheduling problem
  16 February 2007 | The International Journal of Advanced Manufacturing Technology, Vol. 36, No. 11-12
- The two-stage assembly flowshop scheduling problem with bicriteria of makespan and mean completion time
  22 February 2007 | The International Journal of Advanced Manufacturing Technology, Vol. 37, No. 1-2
- On the geometry, preemptions and complexity of multiprocessor and shop scheduling
  1 December 2007 | Annals of Operations Research, Vol. 159, No. 1
- Polynomial time algorithms for the UET permutation flowshop problem with time delays
  Computers & Operations Research, Vol. 35, No. 2
- Exact, Heuristic and Meta-heuristic Algorithms for Solving Shop Scheduling Problems
- A Genetic Algorithm for the Two Machine Flow Shop Problem
- Flow shop scheduling problems with deteriorating jobs on no-idle dominant machines
  European Journal of Operational Research, Vol. 183, No. 1
- Some properties of optimal schedules for the Johnson problem with preemption
  Journal of Applied and Industrial Mathematics, Vol. 1, No. 3
- A multicriteria flowshop scheduling problem with setup times
  Journal of Materials Processing Technology, Vol. 186, No. 1-3
- Scheduling in Job Shops
- Flow Shop Scheduling
- Indirect Solution Representations
- A note on flow shop scheduling problems with a learning effect on no-idle dominant machines
  Applied Mathematics and Computation, Vol. 184, No. 2
- Minimizing maximum completion time in a proportionate flow shop with one machine of different speed
  European Journal of Operational Research, Vol. 176, No. 2
- Bidirectional Flow Shop Scheduling with Multi-Machine Capacity and Critical Operation Sequencing
- A bicriteria flowshop scheduling problem with setup times
  Applied Mathematics and Computation, Vol. 183, No. 2
- Two-machine flowshop scheduling to minimize mean flow time under linear deterioration
  International Journal of Production Economics, Vol. 103, No. 2
- Two-machine flowshop scheduling problem to minimize total completion time with bounded setup and processing times
  International Journal of Production Economics, Vol. 103, No. 1
- Minimizing sum of completion times and makespan in master-slave systems
  IEEE Transactions on Computers, Vol. 55, No. 8
- Three-machine flowshop with two operations per job to minimize makespan
  Computers & Industrial Engineering, Vol. 50, No. 3
- Job Shop Scheduling with Unit Processing Times
  Nikhil Bansal,
  Tracy Kimbrel,
  Maxim Sviridenko,
  1 May 2006 | Mathematics of Operations Research, Vol. 31, No. 2
- Designing PTASs for MIN-SUM scheduling problems
  Discrete Applied Mathematics, Vol. 154, No. 4
- Performance guarantees for flowshop heuristics to minimize makespan
  European Journal of Operational Research, Vol. 169, No. 3
- A branch-and-bound algorithm for three-machine flowshop scheduling problem to minimize total completion time with separate setup times
  European Journal of Operational Research, Vol. 169, No. 3
- Subsequence Packing: Complexity, Approximation, and Application
- Scheduling multi-stage parallel-processor services to minimize average response time
  21 December 2017 | Journal of the Operational Research Society, Vol. 57, No. 1
- Approximation schemes for job shop scheduling problems with controllable processing times
  European Journal of Operational Research, Vol. 167, No. 2
- Algorithms with performance guarantees for flow shops with regular objective functions
  IIE Transactions, Vol. 37, No. 12
- Two-machine flowshop scheduling with job class setups to minimize total flowtime
  Computers & Operations Research, Vol. 32, No. 11
- Flow-shop scheduling with a learning effect
  21 December 2017 | Journal of the Operational Research Society, Vol. 56, No. 11
- A SIMPLE LOWER BOUND FOR TOTAL COMPLETION TIME MINIMIZATION IN A TWO-MACHINE FLOWSHOP
  20 November 2011 | Asia-Pacific Journal of Operational Research, Vol. 22, No. 03
- A branch-and-cut algorithm for scheduling of projects with variable-intensity activities
  9 February 2005 | Mathematical Programming, Vol. 103, No. 3
- A heuristic approach to minimize expected makespan in open shops subject to stochastic processing times and failures
  28 June 2006 | International Journal of Flexible Manufacturing Systems, Vol. 17, No. 3
- APPROXIMATION ALGORITHMS FOR FLEXIBLE JOB SHOP PROBLEMS
  20 November 2011 | International Journal of Foundations of Computer Science, Vol. 16, No. 02
- Scheduling Multiple Flows on Parallel Disks
- New Heuristics to Minimize the Mean Flow Time for Static Permutation Flowshop Problems
  Journal of King Saud University - Engineering Sciences, Vol. 18, No. 1
- Total flowtime and makespan for a no-wait m -machine flowshop with set-up times separated
  21 December 2017 | Journal of the Operational Research Society, Vol. 55, No. 6
- A branch‐and‐bound algorithm for the three‐machine flowshop scheduling problem with bicriteria of makespan andtotal flowtime
  5 May 2004 | International Transactions in Operational Research, Vol. 11, No. 3
- Flowshop scheduling problem to minimize total completion time with random and bounded processing times
  21 December 2017 | Journal of the Operational Research Society, Vol. 55, No. 3
- A New Dispatching Rule for the Stochastic Single-Machine Scheduling Problem
  1 March 2004 | SIMULATION, Vol. 80, No. 3
- Logistics scheduling: Analysis of two-stage problems
  Journal of Systems Science and Systems Engineering, Vol. 12, No. 4
- Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity
  European Journal of Operational Research, Vol. 149, No. 2
- The two- and m-machine flowshop scheduling problems with bicriteria of makespan and mean flowtime
  European Journal of Operational Research, Vol. 147, No. 2
- Scheduling Requests on Multi-Stage Multi-Server to Increase Quality of Service
- Lerneffekte in der Ablaufplanung
- On Minimizing Average Weighted Completion Time: A PTAS for the Job Shop Problem with Release Dates
- Resource constraints machine scheduling: a genetic algorithm approach
- The complexity of cyclic shop scheduling problems
  1 January 2002 | Journal of Scheduling, Vol. 5, No. 4
- Approximation algorithms for shop scheduling problems with minsum objective
  1 January 2002 | Journal of Scheduling, Vol. 5, No. 4
- Evolving toward an Optimal Scheduling Solution through Adaptivity
  Journal of Parallel and Distributed Computing, Vol. 62, No. 7
- New heuristics to minimize total completion time in m-machine flowshops
  International Journal of Production Economics, Vol. 77, No. 1
- A worst-case analysis of the three-machine flow shop scheduling
  Journal of Information and Optimization Sciences, Vol. 23, No. 2
- Workforce planning in synchronous production systems
  European Journal of Operational Research, Vol. 136, No. 3
- Scheduling manufacturing systems for delayed product differentiation in agile manufacturing
  International Journal of Production Research, Vol. 40, No. 11
- A flowshop scheduling algorithm to minimize total weighted completion time
- Sequencing three-stage flexible flowshops with identical machines to minimize makespan
  27 April 2007 | IIE Transactions, Vol. 33, No. 11
- A note on scheduling flowshops with flexible stage ordering
  European Journal of Operational Research, Vol. 129, No. 1
- Scheduling manufacturing systems in an agile environment
  Robotics and Computer-Integrated Manufacturing, Vol. 17, No. 1-2
- Scheduling batches with simultaneous job processing for two-machine shop problems
  1 January 2001 | Journal of Scheduling, Vol. 4, No. 1
- A Hybrid Evolutionary Approach for Multicriteria Optimization Problems: Application to the Flow Shop
  6 July 2001
- Scheduling in Flow and Open Shops
- Scheduling in Job Shops
- An efficient branch-and-bound algorithm for the two-machine bicriteria flowshop scheduling problem
  Journal of Manufacturing Systems, Vol. 20, No. 2
- Flow shop and open shop scheduling with a critical machine and two operations per job
  European Journal of Operational Research, Vol. 127, No. 1
- Comparison of Heuristics for Solving a Flowshop Problem
  IFAC Proceedings Volumes, Vol. 33, No. 17
- Heuristics for the two-stage job shop scheduling problem with a bottleneck machine
  European Journal of Operational Research, Vol. 123, No. 2
- Makespan minimization in the two‐machine flowshop batch scheduling problem
  31 January 2000 | Naval Research Logistics (NRL), Vol. 47, No. 2
- Approximation Algorithms for Flexible Job Shop Problems
  12 April 2007
- Minimizing the number of late jobs for the two-machine unit-time job-shop scheduling problem
  Discrete Applied Mathematics, Vol. 98, No. 3
- Complexity of mixed shop scheduling problems: A survey
  European Journal of Operational Research, Vol. 120, No. 2
- Using chaos-parallel evolutionary programming to solve the flow-shop scheduling problem
- Minimizing Total Completion Time in a Two-Machine Flowshop: Analysis of Special Cases
  J. A. Hoogeveen,
  T. Kawaguchi,
  1 November 1999 | Mathematics of Operations Research, Vol. 24, No. 4
- Polynomial time approximation algorithms for machine scheduling: ten open problems
  Journal of Scheduling, Vol. 2, No. 5
- Two-machine flowshop scheduling with bicriteria problem
  Computers & Industrial Engineering, Vol. 36, No. 3
- Scheduling of client‐server applications
  24 August 2006 | International Transactions in Operational Research, Vol. 6, No. 4
- Deterministic job-shop scheduling: Past, present and future
  European Journal of Operational Research, Vol. 113, No. 2
- A Simple Heuristic for m-Machine Flow-Shop and its Applications in Routing-Scheduling Problems
  Igor Averbakh,
  Oded Berman,
  1 February 1999 | Operations Research, Vol. 47, No. 1
- Stochastically minimizing total flowtime in flowshops with no waiting space
  European Journal of Operational Research, Vol. 113, No. 1
- A Linear Time Approximation Scheme for the Job Shop Scheduling Problem
- A heuristic algorithm for two‐machine re‐entrant shop scheduling
  Annals of Operations Research, Vol. 86, No. 0
- A new approximation algorithm for UET-scheduling with chain-type precedence constraints
  Computers & Operations Research, Vol. 25, No. 9
- Reduction of job-shop problems to flow-shop problems with precedence constraints
  European Journal of Operational Research, Vol. 109, No. 1
- Some results of the worst-case analysis for flow shop scheduling
  European Journal of Operational Research, Vol. 109, No. 1
- 雙機流程型工廠動態排程之研究
  Journal of the Chinese Institute of Industrial Engineers, Vol. 15, No. 4
- A tabu search approach to machine scheduling
  European Journal of Operational Research, Vol. 106, No. 2-3
- Makespan minimization in preemptive two machine job shops
  Computing, Vol. 60, No. 1
- A new constructive heuristic for the flowshop scheduling problem
  European Journal of Operational Research, Vol. 105, No. 1
- A Review of Machine Scheduling: Complexity, Algorithms and Approximability
- A survey of factory control algorithms that can be implemented in a multi-agent heterarchy: Dispatching, scheduling, and pull
  Journal of Manufacturing Systems, Vol. 17, No. 4
- Scheduling Tasks in Master-Slave Parallel Processing Systems
  IFAC Proceedings Volumes, Vol. 30, No. 19
- Scheduling permutation flow shops using the Lagrangian relaxation technique
  Annals of Operations Research, Vol. 70, No. 0
- Maschinenbelegungsplanung
- Shop scheduling problems under precedence constraints
  Annals of Operations Research, Vol. 69, No. 0
- Scheduling in network flow shops
  Journal of Global Optimization, Vol. 9, No. 3-4
- The job shop scheduling problem: Conventional and new solution techniques
  European Journal of Operational Research, Vol. 93, No. 1
- Scheduling Permutation Flow Shops Using the Lagrangian Relaxation Technique
  IFAC Proceedings Volumes, Vol. 29, No. 1
- An exchange heuristic imbedded with simulated annealing for due-dates job-shop scheduling
  European Journal of Operational Research, Vol. 91, No. 1
- A fast tabu search algorithm for the permutation flow-shop problem
  European Journal of Operational Research, Vol. 91, No. 1
- Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds
  3 June 2005
- Minimizing total completion time in a two-machine flowshop: Analysis of special cases
  3 June 2005
- Scheduling in Flow and Open Shops
- Scheduling in Job Shops
- Job shop scheduling: an experimental investigation of the performance of alternative scheduling rules
  27 April 2007 | Production Planning & Control, Vol. 7, No. 1
- Shop scheduling problems with multiprocessor tasks on dedicated processors
  Annals of Operations Research, Vol. 57, No. 1
- An efficient algorithm for a job shop problem
  Annals of Operations Research, Vol. 57, No. 1
- Job shop scheduling heuristics for sequence dependent setups
  Computers & Industrial Engineering, Vol. 29, No. 1-4
- Minimizing makespan for flow shop scheduling by combining simulated annealing with sequencing knowledge
  European Journal of Operational Research, Vol. 85, No. 3
- Production control in the food processing industry
  International Journal of Operations & Production Management, Vol. 15, No. 8
- Asymptotic optimality of statistical multiplexing in pipelined processing
  Queueing Systems, Vol. 21, No. 1-2
- A Study of On-Line Scheduling Two-Stage Shops
- An inherently parallel method for heuristic problem-solving. I. General framework
  IEEE Transactions on Parallel and Distributed Systems, Vol. 6, No. 10
- An inherently parallel method for heuristic problem-solving. II. Example applications
  IEEE Transactions on Parallel and Distributed Systems, Vol. 6, No. 10
- Minimizing makespan in hybrid flowshops
  Operations Research Letters, Vol. 16, No. 3
- An effective heuristic method for generalized job shop scheduling with due dates
  Computers & Industrial Engineering, Vol. 26, No. 4
- Two-machine ordered flowshop scheduling under random breakdowns
  Mathematical and Computer Modelling, Vol. 20, No. 2
- Job-shop scheduling with convex models of operations
  Mathematical and Computer Modelling, Vol. 20, No. 2
- A note on worst-case analysis of approximation algorithms for a scheduling problem
  European Journal of Operational Research, Vol. 74, No. 1
- A new adaptively weighted combinatorial dispatching rule for complex scheduling problems
  Computer Integrated Manufacturing Systems, Vol. 7, No. 1
- Scheduling Multiprocessor Flow Shops
- Static Shop Scheduling
- Performance of scheduling algorithms for no-wait flowshops with parallel machines
  European Journal of Operational Research, Vol. 70, No. 3
- Deterministic scheduling in computing and manufacturing systems: a survey of models and algorithms
  Mathematics and Computers in Simulation, Vol. 35, No. 5
- The permutation flow shop problem with sum-of-completion times performance criterion
  Naval Research Logistics, Vol. 40, No. 6
- New results in the worst-case analysis for flow-shop scheduling
  Discrete Applied Mathematics, Vol. 46, No. 1
- FMS scheduling and control: Learning to achieve multiple goals
  Expert Systems with Applications, Vol. 6, No. 3
- Scheduling heuristic for the n-jobm-machine flow shop
  Omega, Vol. 21, No. 2
- Optimal scheduling of cooperative tasks in a distributed system using an enumerative method
  IEEE Transactions on Software Engineering, Vol. 19, No. 3
- Static Shop Scheduling
- Maschinenbelegungsplanung
- Chapter 9 Sequencing and scheduling: Algorithms and complexity
- Les problèmes d'ordonnancement
  29 March 2011 | RAIRO - Operations Research, Vol. 27, No. 1
- A synergistic approach to manufacturing systems control using machine learning and simulation
  Journal of Intelligent Manufacturing, Vol. 3, No. 1
- Job Shop Scheduling
- Application of an inherently parallel heuristic methodology to flow-shop scheduling
- Branch and bound algorithm for the flow shop with multiple processors
  European Journal of Operational Research, Vol. 51, No. 1
- On the complexity of generalized due date scheduling problems
  European Journal of Operational Research, Vol. 51, No. 1
- Cyclic sequencing problems in the two-machine permutation flow shop: Complexity, worst-case, and average-case analysis
  Naval Research Logistics, Vol. 37, No. 5
- Improved lower bounds for minimizing the sum of completion times of n jobs over m machines in a flow shop
  European Journal of Operational Research, Vol. 44, No. 3
- Inhomogeneous deterministic two-stage queueing systems
  Cybernetics, Vol. 25, No. 3
- Algorithms for end-to-end scheduling to meet deadlines
- Scheduling algorithms for flexible flowshops: Worst and average case performance
  European Journal of Operational Research, Vol. 43, No. 2
- Worst-case analysis of an approximation algorithm for flow-shop scheduling
  Operations Research Letters, Vol. 8, No. 3
- Static allocation of periodic tasks with precedence constraints in distributed real-time systems
- Knowledge-based scheduling in flexible manufacturing systems: An integration of pattern-directed inference and heuristic search
  International Journal of Production Research, Vol. 26, No. 5
- Exponentially distributed jobshop scheduling problems.
  Communications in Statistics. Stochastic Models, Vol. 4, No. 1
- Selected Topics in Scheduling Theory
- Chapter 4 Job shop systems
  Annals of Operations Research, Vol. 7, No. 1
- Scheduling Independent Tasks on Uniform Processors
  SIAM Journal on Computing, Vol. 13, No. 4
- Some new results in flow shop scheduling
  Zeitschrift für Operations Research, Vol. 28, No. 1
- Surrogate duality relaxation for job shop scheduling
  Discrete Applied Mathematics, Vol. 5, No. 1
- Development of On-Line, Real-Time, Scheduling Method for a Computer Aided Manufacturing System
  CIRP Annals, Vol. 32, No. 1
- Scheduling the Open Shop to Minimize Mean Flow Time
  SIAM Journal on Computing, Vol. 11, No. 4
- Recent Developments in Deterministic Sequencing and Scheduling: A Survey
- Scheduling Problems and Combinatorial Programming
- On J -maximal and J -minimal Flow-Shop Schedules
  1 July 1981 | Journal of the ACM, Vol. 28, No. 3
- Scheduling: Bibliography & Review
  International Journal of Physical Distribution & Materials Management, Vol. 10, No. 3
- A Note on Open Shop Preemptive Schedules
  IEEE Transactions on Computers, Vol. C-28, No. 10
- NP-Complete operations research problems and approximation algorithms
  Zeitschrift für Operations Research, Vol. 23, No. 3
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

Volume 26, Issue 1

January-February 1978

Pages 3-208

Article Information

Metrics

Information

Published Online:February 01, 1978

Cite as

Teofilo Gonzalez, Sartaj Sahni, (1978) Flowshop and Jobshop Schedules: Complexity and Approximation. Operations Research 26(1):36-52.

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

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Flowshop and Jobshop Schedules: Complexity and Approximation

Abstract

Volume 26, Issue 1

Article Information

Metrics

Information

Cite as

Sign Up for INFORMS Publications Updates and News