"Look-ahead” Sequencing Rule ( Last Part )

ASSIGNMENT METHOD

There are some specific rules defined for specific cases. For example, if you have ‘n’ operations to be processed on ‘n’ resources. This problem typically forms a problem of [n x n] matrix.

Under the given situation one has to find an optimal assignment for minimizing total processing time, with an assumption that one resource shall perform only one operation.

The problem considers that all machines are not identical; this essentially means one operation has different processing time on different resources.

There exists a good old Assignment method which optimally solves the [n x n] matrix while minimizing total processing time.

Such cases may be rare, as under practical conditions, it may not be advisable to use all resource simultaneously. Only the point of information is that under such condition, we have a very simple and optimal solution to deal with. One can think of applying assignment method to various other situations as well.

Please note that Assignment Method only works for Minimization problems.

Problem can be illustrated in the form of n x n matrix, as given below:

The matrix shows the processing time or cost of assignment or similar information, for which the objective function is to minimize total value.


By assignment method, the optimal allocation shall be:

Therefore the optimal solution of operations assignment is:


Total optimal processing time is 6 + 5 + 4 + 6 = 21.


JOHNSON’S RULE

There is another interesting case, where there is serial operations one after the other, for each operation. Each sun operation can be performed on one of the resources. In this case, Johnson’s rule is applicable and gives the optimum result to minimize the make span.

In this case the two operations are to be performed in serial [one after the other] on two serial resources.

Objective:

To sequence n jobs through two processing facilities to minimize the make span [Total processing time] given that all jobs follows the same pattern through the resources / facility.

Problem Illustration:



Algorithm:

1] List the operations time for each job on both processing facility.

2] Select the SPT from the list and identify the job.

3] If the SPT is for first processing facility, schedule the corresponding job as early as possible. If it is for second processing facility, schedule the job as late as possible.

4] Repeat steps 2 and 3 until all the jobs are scheduled.

5] Compute the make span.

For comparison purpose, let us assume that the random sequence is as per the job number. This means the random sequence for processing is J1 – J2 – J3 – J4 – J5.

The Johnson’s rule calculates the sequence as J5 – J1 – J3 – J4 – J2.

With the above calculations, we can generate the following diagram for resource loading / operation processing:


Random Sequence:.