For the n jobs and m machines JSSP as shown below.
| Job | Processing time | |||||
| Machine 1 | Machine 2 | … | Machine k | … | Machine m | |
| J1 | T11 | T12 | … | T1k | … | T1m |
| J2 | T21 | T22 | … | T2k | … | T2m |
| . | . | . | … | . | … | . |
| Ji | Ti1 | Ti2 | … | Tik | … | Tim |
| . | . | . | … | . | … | . |
| Jn | Tn1 | Tn2 | … | Tnk | … | Tnm |
Table:JSSP (n x m) Modified Johnson's Rule
If any one of the conditions below:
· Min (Ti1) ≥ Max (Tik)
· Min (Tim) ≥ Max (Tik)
Where i = 1, …, n and k = 2, …,(m-1)
is satisfied, then Johnson’s algorithm can be extended in following way.
Create a hypothetical problem with two machines and n jobs as shown below and objective is to obtain optimal sequence for this. Later, the make-span is to be determined for the optimal sequence by using the data of original problem as above.
| Job | Processing time | |
| Machine A | Machine B | |
| J1 | T11 + ∑T1k | ∑T1k + T1m |
| J2 | T21 + ∑T2k | ∑T2k + T2m |
| . | . | . |
| Ji | Ti1 + ∑Tik | ∑Tik + Tim |
| . | . | . |
| Jn | Tn1 + ∑Tnk | ∑Tnk + Tnm |
Table: Hypothetical Problem of Modified Johnson's Rule
Where i = 1, …, n and k = 2, …,(m-1)
Related Posts:
- JOB SHOP SCHEDULING
- Description of Job Shop Scheduling
- Assumptions in static JSSP
- Johnson’s Rule
- Algorithm of Johnson’s Rule
- Illustration for Johnson’s rule
- Limitations of Johnson’s Rule
- What makes scheduling problems hard?
© 2006 Kumaravel & Project Team
No comments :
Post a Comment
Blog authors can delete the comment if it contains the inappropriate contents.