Content deleted Content added
adding links to references using Google Scholar |
Ira Leviton (talk | contribs) m Fixed typos found with Wikipedia:Typo Team/moss. |
||
Line 10:
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.<ref>{{cite web | url=http://posh-wolf.herokuapp.com/problem | title=posh-wolf website | accessdate=28 December 2015}}</ref>
==Sequencing
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<sub>max</sub>
# (Average) Tardiness, <math>\sum (w_i) T_i </math>
# ....
Line 24:
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, C<sub>max</sub> ===
F2|prmu|C<sub>max</sub> and F3|prmu|C<sub>max</sub> 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>
Line 36:
Johnson's Algorithm<br>
Step 1:Form set1 containing all the jobs with p<sub>1j</sub> < p<sub>2j</sub> <br>
Step 2:Form set2 containing all the jobs with p<sub>1j</sub> > p<sub>2j</sub>, the jobs with p<sub>1j</sub>=p<sub>2j</sub> 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<sub>1j</sub>(SPT)<br>
| |||