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.

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

Sequencing Rules (Part I)

(I) OVERVIEW

Scheduling is a ‘decision making’ process, which forms the core of any manufacturing and service industry. The objective of scheduling is to manage resources and task in the best possible manner. Any problem comprising of following four parameters can be identified as a valid problem for scheduling:

• Task
• Time
• Resource
• Constraint

Better the usage and utilization of resources is, better would be the end result w. r. t. standard manufacturing norms. Scheduling not only gives a good way of task execution but also determines practical delivery dates.

Sequencing rules are one of the key measures to ensure that resource usage is in line with the objectives to be achieved. Sequencing rules sometimes also referred as dispatching rules as well.

Sequencing rule is a rule that prioritizes the jobs waiting for processing on a particular machine. The prioritization scheme normally takes into account the attributes of the job , machine and current time as well.

We can classify the sequencing rule as Static rule and Dynamic rule.

Static Rules are those, which does not change with time and determined by job attributes and / or machine attributes. Dynamic rules are those, which is time dependent.

Another way of defining the classification is Local sequencing rules and Global sequencing rules.

Local rules concern information that is related to the queue where the jobs are waiting or the machine where the job is queued.

Global rules use the information pertaining to other machine also. For example, the processing time of current job on next machine on its route or current queue length at the next machine on its route may be considered.

STANDARD SEQUENCING RULES

There are basic sequencing rules, which are well known and considered to be standard ones. These are namely:

• First In First Out [FIFO] or First Come First Serve [FCFS]
• Shortest Processing Time [SPT]
• Longest Processing Time [LPT]
• Earliest Due Date [EDD]
• Operation Slack [OPS]
• Critical Ratio [CRR]

(I) FIRST IN FIRST OUT [FIFO] OR FCFS
This sequencing rule gives priority to the operation, which comes first to that particular resource. This means, the operation which arrives first in the queue is loaded / dispatched first. The functionality of this rule is to try to minimize waiting time as it tries to move the tasks as soon as it arrives.


(II) SHORTEST PROCESSING TIME [SPT]

This sequencing rule orders the tasks in the increasing value of processing time. This means, the task with the smallest processing time is scheduled first and subsequent tasks in ascending order of processing time. This rule maximizes throughput by minimizing the total completion times.


(III) LONGEST PROCESSING TIME [LPT]
This sequencing rule is opposite to the SPT rule. LPT creates a sequence based on descending order of processing time. This means, the task with the longest processing time is dispatched first and later other tasks are scheduled sin the decreasing order of processing time values. LPT rule creates an environment for work balancing, especially for parallel machine case.


(IV) EARLIEST DUE DATE [EDD]
As name suggests, this rule works on the due date of the tasks. The task with the earliest due date is scheduled first and other task in the ascending order of the due dates. The core objective of applying this rule is to minimize the delay / lateness.

(V) OPERATION SLACK [OPS]

This rule gives priority to the operation with minimum slack. The operation slack is computed as the difference between the total remaining time and the remaining processing time (i.e. process time plus setup time).

OPS = (Total remaining time) – (scheduled setup and running time remaining)
OPS = (Due date) – (scheduled setup and running time remaining) – (Today’s date)
OPS = (Time remaining) – (work remaining)

This rule could be applied at the end of production, where the client due date becomes relatively important. Jobs are sequenced in ascending order of CR (i.e. Critical Ratio).



Jobs with CR of less than one, exactly one and more than one are respectively behind schedule, on schedule and ahead of schedule.

The following table illustrates the comparison between these sequencing rule, which gives us a good overview data.