2. Consider the following 11-job 2-machine scheduling problem in which all jobs

Question

2. Consider the following 11-job 2-machine scheduling problem in which all jobs are available at time zero, and makespan is the measure of performance to be minimized. Job Route Processing Time on M/C A3 910 11 Processing Time on M/CB 4 (a) Determine the optimal schedule, and its makespan value (b) Now assume that the manufacturing environment is "open shop", not the "job shop. That is, the routes of the jobs are not known in advance. Determine an optimal schedule to minimize the makespan, and illustrate it on a Gantt chart.

Explanation / Answer

We have to first establish 4 different sets-

{A} - Set of jobs only on machine A

{B} - Set of jobs only on machine B

{AB} - Set of jobs only on machine A followed by machine B

{BA} - Set of jobs only on machine B followed by machine A

Therefore we have the following sets

{A} - {3, 6}

{B} - {8, 11}

{AB} - {1, 5, 9}

{BA} - {2, 4, 7, 10}

Now we have to sequence jobs in the sets as per Johnson's rule. Johnsons rule has the following steps-

1. Select the job with the shortest activity time. If that activity time is for the first work center, then schedule the job first. If that activity time is for the second work center then schedule the job last. Break ties arbitrarily.

2. Eliminate the shortest job from further consideration.

3. Repeat steps 1 and 2, working towards the center of the job schedule until all jobs have been scheduled.

Therefore the sequence comes as follows -

{AB} - {1, 9, 5}

{BA} - {4, 2, 7, 10}

{A} - {6, 3}

{B} - {11, 8}

Combined the 4 sets without changing order in any set as per the following rules -

Machine A : Jobs in {A,B} before jobs in {A} before jobs in {B,A}

Machine B : Jobs in {B,A} before jobs in {B} before jobs in {A,B}

Therefore sequence for Machine A - {1, 9, 5, 6, 3, 4, 2, 7, 10}

and sequence for Machine B - {4, 2, 7, 10, 11, 8, 1, 9, 5}

Machine A works for 40 hours and Machine B for 39 hours (adding the times of all jobs in a particular machine)

Makespan is 40 hours

For part (b) we will assume that each job starts at machine A and then goes to machine B. Again applying Johnson's rule we get the following sequence - {6, 1, 3, 10, 7, 8, 2, 9, 5, 4, 11}

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.