Flow shop scheduling

From Wikipedia, the free encyclopedia
  (Redirected from Flow Shop Scheduling Problem)
Jump to: navigation, search

Flow shop scheduling problems, are a class of scheduling problems with a work shop or group shop in which the flow control shall enable an appropriate sequencing for each job and for processing on a set of machines or with other resources 1,2,...,m in compliance with given processing orders. Especially the maintaining of a continuous flow of processing tasks is desired with a minimum of idle time and a minimum of waiting time. Flow shop scheduling is a special case of job shop scheduling where there is strict order of all operations to be performed on all jobs. Flow shop scheduling may apply as well to production facilities as to computing designs.

A special type of flow shop scheduling problem is the permutation flow shop scheduling problem in which the processing order of the jobs on the resources is the same for each subsequent step of processing.

Sequencing Performance Measurements (γ)[edit]

The sequencing problem can be stated as determining a sequence S such that one or several sequencing objectives are optimized.

  1. (Average)Flow time, \sum (w_i) F_i
  2. Makespan,Cmax
  3. (Average) Tardiness, \sum (w_i) T_i
  4. ....

detailed discussion of performance measurement can be found in Malakooti (2013).

Complexity of flow shop scheduling[edit]

As presented by Garey et al. (1976), most of extensions of the flow shop scheduling problems are Np-Hard and few of them can be solved optimally in O(nlogn), for example F2|prmu|Cmax can be solved optimally by using Johnson's Rule (1954).

Solution Methods[edit]

The proposed methods to solve flow shop scheduling problems can be classified to exact methods such as Branch and Bound and dynamic programming, Heuristic algorithms and metaheuristics.

minimizing makespan,Cmax[edit]

F2|prmu|Cmax and F3|prmu|Cmax can be solved optimally by using Johnson's Rule (1954) but for general case there is no algorithm that grantee the optimality of the solution.

Other objectives[edit]

So far, there is no algorithm which can grantee optimal solution.

the detailed discussion of the available solution methods are provided by Malakooti (2013).


  • Taillard, E. (January 1993). "Benchmarks for basic scheduling problems". European Journal of Operational Research 64 (2): 278–285. doi:10.1016/0377-2217(93)90182-M. 
  • Malakooti, B (2013). Operations and Production Systems with Multiple Objectives. John Wiley & Sons. ISBN 978-1-118-58537-5.
  • Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of operations research, 1(2), 117-129.
  • Johnson, S. M. (1954). Optimal two‐and three‐stage production schedules with setup times included. Naval research logistics quarterly, 1(1), 61-68.

External links[edit]

  • Posh Wolf - online flow shop solver with real-time visualization