Flow-shop scheduling: Difference between revisions

Revision as of 13:35, 28 December 2015

Latest revision as of 06:52, 19 April 2025

(44 intermediate revisions by 28 users not shown)

Line 1:

{{Short description|Class of computational problem}}

'''Flow shop scheduling''' problems, are a class of [[Scheduling (production processes)|scheduling]] problems with a [[workshop]] or [[group shop]] in which the flow control shall enable an appropriate sequencing for each job and for processing on a set of [[machine]]s or with other [[resource]]s ''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 [[Manufacturing|production]] facilities as to [[computing]] designs.

[[File:Flow Shop Ordonnancement.JPEG|thumb|Flow Shop Ordonnancement]]

'''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==

There are n''m'' machines and m''n'' jobs. Each job contains exactly n''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.

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''m''-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 timespanmakespan. <ref>{{cite web | url=http://posh-wolf.herokuapp.com/problem | title=posh-wolf website | accessdate=28 December 2015}}</ref>

==Sequencing Performanceperformance Measurementsmeasurements (γ)==

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

# (Average) Flow time, <math>\sum (w_i) F_i </math>

# Makespan, C_max

# (Average) Tardiness, <math>\sum (w_i) T_i </math>

# ....

detailed discussion of performance measurement can be found in [[Behnam Malakooti|Malakooti]](2013).<ref name=Malakooti>Malakooti, B (2013). Operations and Production Systems with Multiple Objectives. John Wiley & Sons. {{ISBN|978-1-118-58537-5}}.</ref>

==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|C_max can be solved optimally by using [[Johnson's Rule]].

==Complexity of flow -shop scheduling==

==Solution Methods==

As presented by Garey et al. (1976),<ref name=Garey>{{cite journal

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]].

| last1=Garey | first1=M. R.

=== Minimizing makespan,C_max ===

| last2=Johnson | first2=D. S.

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>

| last3=Sethi | first3=Ravi

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

| date=1976

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:

| title=The complexity of flowshop and jobshop scheduling

In an optimal schedule, job i precedes job j if ''min{p_i1,p_j2} < min{p_j1,p_i2}''. Where as, p_i1 is the processing time of job i on machine 1 and p_i2 is the processing time of job i on machine 2. Similarly, p_j1 and p_j2 are processing times of job j on machine 1 and machine 2 respectively.<br>

| journal=[[Mathematics of Operations Research]]

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

| volume=1

let,

| issue=2

p_1j=processing time of job j on machine 1<br>

| pages=117–129

p_2j=processing time of job j on machine 2

As| presented by Garey et aldoi=10. (1976),1287/moor.1.2.117}}</ref> 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]].<ref name=Johnson>{{cite journal

<br>

| last1=Johnson's Algorithm<br>| first1=S. M.

| date=1954

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

| title=Optimal two-and three-stage production schedules with setup times included

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>

| journal=Naval Research Logistics Quarterly

Step 3: Form the sequence as follows:<br>

| volume=1

i) The job in set1 go first in the sequence and they go in increasing order of p_1j(SPT)<br>

| issue=1

ii) The jobs in set2 follow in decreasing order of p_2j (LPT). Ties are broken arbitrarily.<br>

| pages=61–68

This type schedule is referred as SPT(1)-LPT(2) schedule.

| doi=10.1002/nav.3800010110}}</ref>

*Taillard provides substantial benchmark problems for scheduling flow shops, open shops, and job shops.<ref name=Taillard>{{cite journal | doi=10.1016/0377-2217(93)90182-M | author=Taillard, E. | title=Benchmarks for basic scheduling problems | journal=European Journal of Operational Research |date=January 1993 | volume=64 | pages=278–285 | issue=2 | url=http://ideas.repec.org/a/eee/ejores/v64y1993i2p278-285.html }}</ref>

=== Other objectives ===

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

==Solution Methodsmethods==

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

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]]<ref (1954)name=Johnson/> but for general case there is no algorithm that guarantee the optimality of the solution.<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_i11i,p_j22j} < min{p_j11j,p_i22i}''. Where as, p_i11i is the processing time of job i on machine 1 and p_i22i is the processing time of job i on machine 2. Similarly, p_j11j and p_j22j are processing times of job j on machine 1 and machine 2 respectively.<br>

For Johnson's algorithm:

:Let p_1j= be the processing time of job j on machine 1<br>

:and p_2j= the processing time of job j on machine 2

Johnson's algorithm:

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>

Step 3:# Form the sequence as follows:<br>

#: (i) The job in set1 go first in the sequence and they go in increasing order of p_1j (SPT)<br>

#: (ii) The jobs in set2 follow in decreasing order of p_2j (LPT). Ties are broken arbitrarily.<br>

This type schedule is referred as SPT(1)-LPT–LPT(2) schedule.

TheA detailed discussion of the available solution methods are provided by [[Behnam Malakooti|Malakooti]] (2013).<ref name=Malakooti/>

==See also==

* [[Open-shop scheduling]]

* [[Job-shop scheduling]]

==References==

{{Reflist}}

{{Refbegin}}

* {{cite journal | doi=10.1016/0377-2217(93)90182-M | author=Taillard, E. | title=Benchmarks for basic scheduling problems | journal=European Journal of Operational Research |date=January 1993 | volume=64 | pages=278–285 | issue=2 | url=http://ideas.repec.org/a/eee/ejores/v64y1993i2p278-285.html }}

* 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.

*http://faculty.ksu.edu.sa/ialharkan/IE428/Chapter_4.pdf

{{Refend}}

==External links==

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

*[http://www.adaptivebox.net/CILib/code/fspcodes_link.html Flowshop Scheduling Problem Solvers]

{{Scheduling problems}}

[[Category:Operations research]]

[[Category:Scheduling (computing)]]

[[Category:OperationsOptimal researchscheduling]]

[[Category:Workflow technology]]

[[Category:NP-hardEngineering problemsmanagement]]