OPERATIONS MANAGEMENT
TECHNIQUES OF SCHEDULING:
Following techniques of scheduling are used in Operations Management:
PRIORITY RULES IN SEQUENCING-
When many jobs are waiting before an operational facility, we must have some rule to decide the priority while sequencing. We will understand these rules through an example.
SCHEDULING OF n JOBS ON ONE MACHINE
Example: There are 5 jobs in waiting for getting processed on a machine.
| JOB (In sequence of arrival) |
PROCESSING TIME | DUE DATE |
| J1 | 4 | 6 |
| J2 | 5 | 7 |
| J3 | 3 | 8 |
| J4 | 7 | 10 |
| J5 | 2 | 3 |
-
FIRST COME FIRST SERVE RULE (FCFS):
Arrange the jobs in the order of their arrival.
| JOB ARRIVAL (i) |
PROCESSING TIME (pi) |
DUE DATE (di) |
FLOW TIME (Fi) |
LATENESS OF JOBS (Fi – di) |
| J1 | 4 | 6 | 0 + 4 = 4 | 4 – 6 = -2 = 0 |
| J2 | 5 | 7 | 4 + 5 = 9 | 9 – 7 = 2 |
| J3 | 3 | 8 | 9 + 3 = 12 | 12 – 8 = 4 |
| J4 | 7 | 10 | 12 + 7 = 19 | 19 – 10 = 9 |
| J5 | 2 | 3 | 19 + 2 = 21 | 21 – 3 = 18 |
- Total Flow Time = 4 + 9 + 12 + 19 + 21 = 65 days
- Mean Flow Time = Total Flow Time/ Number of Jobs = 65/5 = 13 days
- Total Lateness of job = 0 + 2 + 4 + 9 + 18 = 35 days
- Average Lateness = Total Lateness/ Number of Jobs = 33/5 = 6.6 days
-
SHORTEST PROCESSING TIME (SPT):
Arrange the jobs in order of their processing time in increasing order.
| JOB ARRIVAL (i) |
PROCESSING TIME (pi) |
DUE DATE (di) |
FLOW TIME (Fi) |
LATENESS OF JOBS (Fi – di) |
| J5 | 2 | 3 | 0 + 2 = 2 | 2 – 3 = -1 = 0 |
| J3 | 3 | 8 | 2 + 3 = 5 | 5 -8 = -3 = 0 |
| J1 | 4 | 6 | 5 + 4 =9 | 9 – 6 = 3 |
| J2 | 5 | 7 | 9 + 5 = 14 | 14 – 7 = 7 |
| J4 | 7 | 10 | 14 + 7 = 21 | 21 – 10 = 11 |
- Total Flow Time = 2 + 5 + 9 + 14 + 21 = 51 days
- Mean Flow Time = Total Flow Time/ Number of Jobs = 51/5 = 10.2 days
- Total Lateness of job = 3 + 7 + 11 = 21 days
- Average Lateness = Total Lateness/ Number of Jobs = 21/5 = 4.2 days
-
EARLIEST DUE DATE (EDD):
Arrange the jobs in order of their due date in increasing order.
| JOB ARRIVAL (i) |
PROCESSING TIME (pi) |
DUE DATE (di) |
FLOW TIME (Fi) |
LATENESS OF JOBS (Fi – di) |
| J5 | 2 | 3 | 0 + 2 = 2 | 2 – 3 = -1 = 0 |
| J1 | 4 | 6 | 2 + 4 = 6 | 6 – 6 = 0 |
| J2 | 5 | 7 | 6 + 5 = 11 | 11 – 7 = 4 |
| J3 | 3 | 8 | 11 +3 = 14 | 14 – 8 = 6 |
| J4 | 7 | 10 | 14 + 7 = 21 | 21 – 10 = 11 |
- Total Flow Time = 2 + 6 + 11 + 14 + 21 = 54 days
- Mean Flow Time = Total Flow Time/ Number of Jobs = 54/5 = 10.8 days
- Total Lateness of job = 0 + 0 + 4 + 6 + 11 = 21 days
- Average Lateness = Total Lateness/ Number of Jobs = 21/5 = 4.2 days
-
LAST COME FIRST SERVE (LCFS):
Arrange the jobs in the reverse order of their arrival.
| JOB ARRIVAL (i) |
PROCESSING TIME (pi) |
DUE DATE (di) |
FLOW TIME (Fi) |
LATENESS OF JOBS (Fi – di) |
| J5 | 2 | 3 | 0 + 2 = 2 | 3 – 3 = 0 |
| J4 | 7 | 10 | 2 + 7 = 9 | 9 – 10 = -1 = 0 |
| J3 | 3 | 8 | 9 + 3 = 12 | 12 – 8 = 4 |
| J2 | 5 | 7 | 12 + 5 = 17 | 17 – 7 = 10 |
| J1 | 4 | 6 | 17 + 4 = 21 | 21 – 6 = 15 |
- Total Flow Time = 2 + 9 + 12 + 17 + 21 = 61 days
- Mean Flow Time = Total Flow Time/ Number of Jobs = 61/5 = 12.2 days
- Total Lateness of job = 0 + 0 + 4 + 10 + 15 = 29 days
- Average Lateness = Total Lateness/ Number of Jobs = 29/5 = 5.8 days
-
SLACK TIME REMAINING (STR):
SLACK TIME = DUE DATE – PROCESSING TIME
Arrange the jobs in order their slack time in increasing order.
| JOB ARRIVAL (i) |
PROCESSING TIME (pi) |
DUE DATE (di) |
FLOW TIME (Fi) |
LATENESS OF JOBS (Fi – di) |
| J5 | 2 | 3 | 0 + 2 = 2 | 2 – 3 = -1 = 0 |
| J1 | 4 | 6 | 2 + 4 = 6 | 6 – 6 = 0 |
| J2 | 5 | 7 | 6 + 5 = 11 | 11 – 7 = 4 |
| J4 | 7 | 10 | 11 + 7 = 18 | 18 – 10 = 8 |
| J3 | 2 | 8 | 18 + 2 = 20 | 20 – 8 = 12 |
- Total Flow Time = 2 + 6 + 11 + 18 + 20 = 57 days
- Mean Flow Time = Total Flow Time/ Number of Jobs = 57/5 = 11.4 days
- Total Lateness of job = 0 + 0 + 4 + 8 + 12 = 24 days
- Average Lateness = Total Lateness/ Number of Jobs = 24/5 = 4.8 days
JOHNSON’S RULE FOR OPTIMAL SEQUENCE OF N JOBS ON 2 MACHINES:
Johnson’s rule gives us the unique methodology to determine the optimal sequence of n jobs on 2 machines.
The principal behind Johnson’s rule of n/2 sequencing problem is minimization of total elapses time by the n jobs. Following steps are followed:
PROBLEM:
We have n jobs that are to be produced on 2 parallel machines. The processing time of all jobs is known. The problem is to sequence the jobs on both the machines so that the total elapsed time is minimized.
STEP 1:
Select the minimum processing time among all the available values of processing times. In case two operations contain least processing time, break the tie arbitrability and select them.
STEP2:
Look at the following five situations and take the decision accordingly.
| S. No. | SITUATION | DECISION |
| 1 | Minimum processing time is on 1st machine M1 for the Pth job. | Place Pth job at the beginning of sequence. |
| 2 | Minimum processing time is on 2nd machine M2 for the Qth job. | Place Qth job at the end of the sequence. |
| 3 | Processing time of two jobs, one on M1 and other on M2 is equal and both are minimum. | Place Pth job at the beginning of the sequence and Qth job at the end of the sequence. |
| 4 | Two jobs are having least processing time on machine 1 (M1). | Sequence any of the two jobs in tie as first and place at the beginning of sequence. Second job of the ties is to be placed next. |
| 5 | Two jobs are having least processing time on machine 2 (M2). | Sequence any of the two jobs in tie as last and place it at the end of sequence. Second job of the tie is to be placed before the first one. |
STEP 3:
Remove the jobs already sequenced in Step 2 and process with the remaining jobs. Repeat Step 1 and Step 2 till all jobs are sequenced.
Example: Processing time of 6 jobs on two machines are given below. Use Johnson’s rule to schedule these job.
| JOB | J1 | J2 | J3 | J4 | J5 | J6 |
| M1 | 4 | 6 | 7 | 8 | 9 | 1 |
| M2 | 5 | 8 | 1 | 3 | 6 | 10 |
Sol:
JOBS |
M1 | M2 | ||
| TIME IN | TIME OUT | TIME IN | TIME OUT | |
| J6 | 0 | 1 | 1 | 11 |
| J1 | 1 | 5 | 11 | 16 |
| J2 | 5 | 11 | 16 | 24 |
| J5 | 11 | 20 | 24 | 30 |
| J4 | 20 | 28 | 30 | 33 |
| J3 | 28 | 35 | 35 | 36 |
- Idle time for M1 = Total elapsed time – Total busy time for M1 = 36 – 35 = 1 minute
- Idle time for M2 = 36 – (5 + 8 + 1 + 3 + 6 +10) = 36 – 33 = 3 minutes.
PROCESS n JOBS ON 3 MACHINES:
For a special n jobs and 3 machines problem, Johnson provided an extension of Johnson algorithm. For this let, tij be the processing time of job i on machine j. Here i = 1,2,3,——n and j = 1,2,3.
At least one of the following conditions must be satisfied before we can use this algorithm.
(i) Minimum (ti1) ≥ Maximum (ti2)
(ii) Minimum (ti3) ≥ Maximum (ti2)
STEP 1:
Take two hypothetical machine R and S. The processing time on R and S is calculated as follows:
tiR = ti1 + ti2
tiS = ti2 + ti3
STEP 2:
Use Johnson algorithm to schedule jobs on machine R and S with tiR and tiS.
EXAMPLE:
6 jobs are to be processed on 3 machines. The processing time is as follows. Find the optimal schedule so that the total elapsed time is minimized.
| JOB | J1 | J2 | J3 | J4 | J5 | J6 |
| M1 | 10 | 3 | 5 | 4 | 2 | 1 |
| M2 | 2 | 4 | 6 | 3 | 1 | 2 |
| M3 | 8 | 6 | 7 | 9 | 7 | 7 |
Solution:
Check for necessary condition
Minimum(ti1) = 1
Maximum(ti2) = 6
Minimum(ti3) = 6
Since Minimum (ti1) ≥ Maximum (ti2) and Minimum (ti3) ≥ Maximum (ti2) are satisfied, the Johnson’s algorithm may be used.
| JOB | J1 | J2 | J3 | J4 | J5 | J6 |
| tiR = ti1 + ti2 | 12 | 7 | 11 | 7 | 3 | 3 |
| tiS = ti2 + ti3 | 10 | 10 | 11 | 12 | 8 | 9 |
Using Johnson’s algorithm the optimum sequence for two machines R and S and six job is:
| J5 | J6 | J2 | J4 | J3 | J1 |
JOBS |
M1 | M2 | M3 | |||
| TIME IN | TIME OUT | TIME IN | TIME OUT | TIME IN | TIME OUT | |
| J5 | 0 | 2 | 2 | 3 | 3 | 10 |
| J6 | 2 | 3 | 3 | 5 | 10 | 17 |
| J2 | 3 | 6 | 6 | 10 | 17 | 23 |
| J4 | 6 | 10 | 10 | 13 | 23 | 32 |
| J3 | 10 | 15 | 15 | 21 | 32 | 39 |
| J1 | 15 | 25 | 25 | 27 | 39 | 47 |
CALCULATION OF IDLE TIME:
- Idle time for M1 = 47 – 25 = 22 minutes
- Idle time for M2 = (2-0) + (6-5) + (15-13) + (25-21) + (47-27)
= 2 + 1 + 2 + 4 + 20 = 29 minutes - Idle time for M3 = (3 – 0) = 3 minutes
RELATED VIDEOS FOR TECHNIQUES OF SCHEDULING: