Sequencing Rules (Part II)

ILLUSTRATION: SINGLE MACHINE CASE

At a particular time t, say five jobs are to be schedule on single machine. The need is to find out a sequence, which will satisfy the objective function.

Here:

Maximum Span: Cmax = [5+6+3+7+2] = 23 and
Due date Factor: R = [20 – 9 ]/23 = 0.478


(I) SPT: [MINIMIZING TOTAL COMPLETION TIME]

We will generate two sequences: one by random order and other by SPT rule and then try to compare what SPT really does.

Let us take random sequence say : 1-2-5-3-4
SPT will generate sequence as : 5-3-1-2-4

Now, to compare we shall generate both the sequences and compare the following observations:

A] Total Cycle time [which obviously will be same] as it is single machine case,
B] Number of jobs completed at any particular time t,
C] Number of late jobs.

RANDOM Sequence: 1-2-5-3-4Total Cycle Time: 23 units Total delay: 0 + 0 + 7 + 3 + 3 = 13 units


SPT Sequence: 5-3-1-2-4

Total Cycle Time: 23 units Total delay: 0 + 2 + 0 + 3 + 0 = 5 units

At any given time t, number of jobs completed in SPT is equal or more than any other sequence. Therefore, number of remaining job in SPT at any given time is equal or less than any other sequence generated.

It can be visualized that SPT tries to minimize total completion time. Certainly, SPT sequence also tries to minimize the WIP, as it tries to finish the job as early as possible.

(II) EDD: [MINIMIZING MAXIMUM LATENESS]

We will try to solve the same problem, and compare again with random sequence, as generated earlier.

RANDOM Sequence: 1-2-5-3-4

Total Cycle Time: 23 units Total delay: 0 + 0 + 7 + 3 + 3 = 13 units


EDD Sequence: 3-5-2-1-4
Total Cycle Time: 23 units Total delay: 1 + 0 + 0 + 3 + 0 = 4 units

As depicted in the table, EDD rule tries to minimize maximum lateness of the job. It may not be interesting to apply EDD with an objective of minimizing throughput time or minimizing WIP.


(III) CRR: [MINIMIZING DELAY]

Let us now calculate CR values for different instances [t = 5, 10, 15 and 20].



RR Sequence: 2-3-5-1-4
Total Cycle Time: 23 units Total delay: 1 + 0 + 0 + 3 + 1 = 5 units