Flow shop scheduling
Flow shop scheduling problems, are a class of scheduling problems with a workshop 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.
Formal definition
There are n machines and m jobs. Each job contains exactly n operations. The i-th operation of the job must be executed on the i-th machine. No machine can perform more than one operation simultaneously. For each operation of each job, execution time is specified.
Operations within one job must be performed in the specified order. The first operation gets executed on the first machine, then (as the first operation is finished) the second operation on the second machine, and so on until the n-th operation. Jobs can be executed in any order, however. Problem definition implies that this job order is exactly the same for each machine. The problem is to determine the optimal such arrangement, i.e. the one with the shortest possible total job execution makespan.[1]
Sequencing performance measurements (γ)
The sequencing problem can be stated as determining a sequence S such that one or several sequencing objectives are optimized.
- (Average) Flow time,
- Makespan, Cmax
- (Average) Tardiness,
- ....
detailed discussion of performance measurement can be found in Malakooti(2013).
Complexity of flow shop scheduling
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.
Solution methods
The proposed methods to solve flow shop scheduling problems can be classified as exact algorithm such as Branch and Bound and Heuristic algorithm such as genetic algorithm.
Minimizing makespan, Cmax
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 guarantee the optimality of the solution.
Here is minimization using Johnson's Rule:
The flow shop contains n jobs simultaneously available at time zero and to be processed by two machines arranged in series with unlimited storage in between them. The processing time of all jobs are known with certainty. It is required to schedule n jobs on machines so as to minimize makespan. The Johnson's rule for scheduling jobs in two machine flow shop is given below:
In an optimal schedule, job i precedes job j if min{p1i,p2j} < min{p1j,p2i}. Where as, p1i is the processing time of job i on machine 1 and p2i is the processing time of job i on machine 2. Similarly, p1j and p2j are processing times of job j on machine 1 and machine 2 respectively.
The steps are summarized below for Johnson's algorithms:
let,
p1j=processing time of job j on machine 1
p2j=processing time of job j on machine 2
Johnson's Algorithm
Step 1:Form set1 containing all the jobs with p1j < p2j
Step 2:Form set2 containing all the jobs with p1j > p2j, the jobs with p1j=p2j may be put in either set.
Step 3: Form the sequence as follows:
(i) The job in set1 go first in the sequence and they go in increasing order of p1j(SPT)
(ii) The jobs in set2 follow in decreasing order of p2j (LPT). Ties are broken arbitrarily.
This type schedule is referred as SPT(1)-LPT(2) schedule.
Other objectives
The algorithm is optimal.
The detailed discussion of the available solution methods are provided by Malakooti (2013).
Footnotes
- "posh-wolf website". Retrieved 28 December 2015.
References
- 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
- Posh Wolf - online flow shop solver with real-time visualization