Question

There are 5 jobs that have to be scheduled in a two-machine job shop system. The processing time and the sequence of the required operations of these jobs on the two machines are shown in the table below. For example, job A needs 6 hours on machine 1 (M1) and 4 hours on machine 2 (M2), and it has to be processed on M1 and then M2. You have to use the shortest processing time (SPT) rule to schedule the waiting jobs at either M1 or M2. Assume that all jobs are available at time zero and the material handling time is negligible compared to the processing time. Develop the Gantt chart of scheduling these jobs on both machines using the SPT rule and estimate the makes pan of the developed schedule and the average flow time. The processing time and the sequence of the jobs Job Processing time (hours) Sequence of operations M1 M2 A 6 4 M1-M2 B 4 7 M2-M1 C 3 6 M1-M2 D 4 5 M2-M1 E 7 8 M1-M2 There are 5 jobs that have to be scheduled in a two-machine job shop system. The processing time and the sequence of the required operations of these jobs on the two machines are shown in the table below. For example, job A needs 6 hours on machine 1 (M1) and 4 hours on machine 2 (M2), and it has to be processed on M1 and then M2. You have to use the shortest processing time (SPT) rule to schedule the waiting jobs at either M1 or M2. Assume that all jobs are available at time zero and the material handling time is negligible compared to the processing time. Develop the Gantt chart of scheduling these jobs on both machines using the SPT rule and estimate the makes pan of the developed schedule and the average flow time. The processing time and the sequence of the jobs

Job Processing time (hours) Sequence of operations

M1 M2

A 6 4 M1-M2

B 4 7 M2-M1

C 3 6 M1-M2

D 4 5 M2-M1

E 7 8 M1-M2

Answer 1

As per SPT rule, Machine Sequence problem without fixed order for all jobs can be solved as follow:

Step 1: Find the shortest possible time among the jobs which are not scheduled yet. In the case of tie, choose any one arbitarily

Step 2: If sequence is not in the fixed order for all jobs then group the jobs as per machine sequence. Here we have 2 sequences (M1-M2 & M2-M1) so divide the jobs in two group.

Step 3: After scheduling the job for respective first machine, follow step 1 to schedule the jobs for second machine. Here. first schedule A,C and E for machine 1 then Schedule B and D for machine 1. In the same way, first schedule job B and D for machine 2 and then schedule A,C and E for machine 2.

C has the shortest possible time on the machine 1 (for M1-M2) so first schedule job C on M1 then job A followed by Job E.

B and D has same time on Machine 2. So we can schedule it in any sequence (BD or DB). In the solution, we have considered BD.

Now, we need to schedule ACE on M2 and BD on M1.

Among B and D, D has lower time on M1 then B so sequence will be DB.

Among ACE, only C will be available at the start of 9th hour so C will be the first in the sequence (after BD) followed by A and E.

Sequence on M1: C - A - E - D - B

Sequence on M2: B -D - C - A - E

Gantt Chart:

Optimal make-span time is 28 hours.

Average flow time is 5.6 Hrs (28 hours / 5 jobs)

There will be no idle time for M1 while M2 has idle time of 2 hrs.