Flow-shop scheduling: Difference between revisions

Revision as of 03:45, 19 June 2021

Revision as of 03:48, 19 June 2021

Line 1:

{{citation style|date=May 2016}}

{{short description|class of computational problem}}

'''Flow shop scheduling''' is an [[optimization problem]] in [[computer science]] and [[Operations Research|operations research]]. It is a variant of [[optimal job scheduling]]. In a general job -scheduling problem, we are given ''n'' jobs ''J''₁, ''J''₂, ..., ''J_n'' of varying processing times, which need to be scheduled on ''m'' machines with varying processing power, while trying to minimize the [[makespan]] - the total length of the schedule (that is, when all the jobs have finished processing). In the specific variant known as ''flow-shop scheduling'', each job contains exactly ''m'' 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.

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 [[Manufacturing|production]] facilities as to [[computing]] designs. A special type of flow shop scheduling problem is the '''permutation flow shop scheduling''' problem in which the [[Process (engineering)|processing]] order of the jobs on the resources is the same for each subsequent step of processing.

In the standard [[Optimal job scheduling|three-field notation for optimal -job -scheduling problems]], the flow-shop variant is denoted by '''F''' in the first field. For example, the problem denoted by " '''F3|<math>p_{ij}</math>|'''<math>C_\max</math>" is a 3-machines flow -shop problem with unit processing times, where the goal is to minimize the maximum completion time.

==Formal definition==

Line 20:

detailed discussion of performance measurement can be found in [[Behnam Malakooti|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-Hardhard and few of them can be solved optimally in O(nlogn), for example F2|prmu|C_max 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 [[Branchbranch and Boundbound]] and [[Heuristicheuristic algorithm]] such as [[genetic algorithm]].

=== Minimizing makespan, C_max ===

F2|prmu|C_max and F3|prmu|C_max 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.<br>

Here is minimization using Johnson's Rule:<br>

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{p_1i,p_2j} < min{p_1j,p_2i}''. Where as, p_1i is the processing time of job i on machine 1 and p_2i is the processing time of job i on machine 2. Similarly, p_1j and p_2j are processing times of job j on machine 1 and machine 2 respectively.<br>

The steps are summarized below for Johnson's algorithms:<br>

Line 36 ⟶ 37:

p_2j=processing time of job j on machine 2

<br>

Johnson's Algorithmalgorithm<br>

Step 1:Form set1 containing all the jobs with p_1j < p_2j <br>

Step 2:Form set2 containing all the jobs with p_1j > p_2j, the jobs with p_1j=p_2j may be put in either set.<br>

Line 61 ⟶ 62:

==External links==

* [http://posh-wolf.herokuapp.com/ Posh Wolf] -– online flow -shop solver with real-time visualization

[[Category:Optimal scheduling]]