Sequencing Rules (Last Part)

ILLUSTRATION: PARALLEL MACHINE CASE

Parallel machine case is more interesting problem. Let us try to solve a particular problem with different rules defined earlier. We assume here, that parallel machines are identical. Following is the problem defined:

As the machines are identical, we can assign jobs one by one to both machines based on sequence generated.

If the sequence is: 1 – 2 – 3 – 4 – 5 – 6 – 7, then assignment shall be:
Machine 1: 1 – 3 – 5 – 7 and Machine 2: 2 – 4 – 6.

For the previously evaluated sequencing rules, following would be the sequence generated, which would be scheduled on parallel machine(s).

SPT sequence: 5 – 6 – 1 – 7 – 3 – 4 – 2 [Machine 1: 5 – 1 – 3 – 2 and Machine 2: 6 – 7 – 4 ]
EDD sequence: 3 – 5 – 6 – 7 – 4 – 2 – 1 [Machine 1: 3 – 6 – 4 – 1 and Machine 2: 5 – 7 – 2]

CR sequence:


Here, the value of ‘ t ‘ is taken as the end time of the current scheduled job.
Sequence: 3 – 2 – 5 – 6 – 7 – 1 – 4 [Machine 1: 3 – 5 – 7 – 4 and Machine 2: 2 – 6 – 1]

Let us try to draw these three diagrams, and evaluate the criterion as calculated earlier.

A) SPT: [MINIMIZING TOTAL COMPLETION TIME]

Total Cycle Time: 22 units Total delay: 0 + 8 + 4 + 3 + 0+ 0 + 0 = 15 units


B) EDD: [MINIMIZING MAXIMUM LATENESS]

EDD sequence: 3 – 5 – 6 – 7 – 4 – 2 – 1 [Machine 1: 3 – 6 – 4 – 1 and Machine 2: 5 – 7 – 2]

Total Cycle Time: 22 units Total delay: 7 + 2 + 0 + 4 + 0+ 0 + 0 = 13 units.

Here, it may be interesting to find a solution to load EDD sequence with the different assignment rule: “Assign the job to the machine on which cumulative load scheduled is less”. It means, assign the job to the machine which is available early”

Improved EDD sequence: 3 – 5 – 6 – 7 – 4 – 2 – 1 Delay: 3+6+0+0+0+0+0 = 9



C) CRR: [MINIMIZING DELAY]

CRR sequence: 3 – 2 – 5 – 6 – 7 – 1 – 4 [Machine 1: 3 – 5 – 7 – 4 and Machine 2: 2 – 6 – 1]

Total Cycle Time: 20 units Total delay: 3 + 6 + 0 + 0 + 0+ 0 + 0 = 9 units


It can be very well observed that especially on parallel machine case not only sequencing rule is important but the policy, which decides the assignment, also plays equally strong role. Another observation can be that more the balanced load on both machines lower the cycle time and may be lower total delay.

Certainly, on average basis Heuristic EDD provides the best results. Actually, heuristic EDD defined here is nothing but the combination of EDD and LPT as assignment method used tries to balance load on parallel machines.

There is possibility to identify and define composite rules to specific needs, which would give better results in a particular scenario. The composite objective becomes to minimize the total delay and balancing the load. Naturally, the type of sequencing rule to be used depends on the objective(s) of the scheduling environment.