PRODUCTION SCHEDULING Techniques of Scheduling
OPERATIONS MANAGEMENT
TECHNIQUES OF SCHEDULING:
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 1^{st} machine M1 for the P^{th} job.  Place P^{th} job at the beginning of sequence. 
2  Minimum processing time is on 2^{nd} machine M2 for the Q^{th} job.  Place Q^{th} 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 P^{th} job at the beginning of the sequence and Q^{th} 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 
M_{1}  4  6  7  8  9  1 
M_{2}  5  8  1  3  6  10 
Sol:
JOBS 
M1  M2  
TIME IN  TIME OUT  TIME IN  TIME OUT  
J_{6}  0  1  1  11 
J_{1}  1  5  11  16 
J_{2}  5  11  16  24 
J_{5}  11  20  24  30 
J_{4}  20  28  30  33 
J_{3}  28  35  35  36 
 Idle time for M_{1} = Total elapsed time – Total busy time for M1 = 36 – 35 = 1 minute
 Idle time for M_{2} = 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 
Sol: 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 = (20) + (65) + (1513) + (2521) + (4727)
= 2 + 1 + 2 + 4 + 20 = 29 minutes  Idle time for M3 = (3 – 0) = 3 minutes
RELATED VIDEOS: