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:
1. Arrange the curr_op_list in ascending order of min_esd_op.
2. Is there any operation in curr_op_list: Yes: go to step 3, Else: quit.
3. Schedule the first operation (curr_op) of curr_op_list on current resource. Check if there is any flag. If yes: a] Schedule the curr_op. b] Schedule immediate successor operation from queue_list. [curr_imm_succ]. c] Delete curr_op from curr_op_list and update curr_op_list. d] Delete curr_imm_succ operation from queue_list and update quque_list. [In case of conflict of scheduling multiple operations at same time, SPT rule should be applied, as the objective is to minimize WIP]. e] Go to step 2. Else: Continue.
4. Check for the immediate successor of curr_op. [ succ_op ]. Is succ_op is anteroot node: Yes: Assign the curr_op to current resource and delete the curr_op from curr_op_list. Update curr_op_list. Go to step 2. Else: go to step 6 .
5. Check if there is any predecessor for immediate successor(s)of curr_op in succ_op_list. [ pre_succ_op] If yes: go to step 8. Else: continue.
6. Assign the curr_op to current resource and delete the curr_op from curr_op_list. Update curr_op_list. Go to step 2.
7. Mark the predecessor operation of pre_succ_op from curr_op_list, with a flag as predecessor of current operation. [pre_curr_op]. This means curr_op must be scheduled immediately after the pre_curr_op.
8. Keep curr_op in separate queue_list with flag that it must succeed pre_curr_op. [ succ_curr_op].
Delete curr_op from curr_op_list . Update curr_op_list. Go to step 2.
The above algorithm is considers only partial look ahead policy. One can derive an algorithm with complete look ahead policy. It means one must propagate to all successor levels until anteroot node is reached.
This may result in a complex algorithm with intensive calculations, as many other parameters have to be considered to satisfy desired objective function.
This is a heuristic algorithm and therefore it will provide a feasible solution to the problem, which may not be always good. Another limitation is that it is strictly a local search.
When one tries to analyze the results of the algorithm, it can be derived that one can still improve the result achieved by this algorithm by applying Improvement heuristic, which is given as below:
IMPROVED LOOK AHEAD HEURISTIC
This Improvement heuristic works on concept of exchanging position of immediate pairs based on some constraints. When the sequencing at the current resource is over, you have an order in which the operations are scheduled.
The following heuristic shall try to improve [minimize] the total waiting time of the operations after processing at current resource.
1. Create a sequential list of n operations scheduled on current resource. [ List of N operations, where N = 1, 2, ……,n] Initialize N = 0;
2. Increment value of N by one. [pointer moves to next job] Is there any operation exists: If yes : continue , Else : exit.
3. Select the immediate successor operation from the sequence_list. [Operation with value N+1]
4. For the selected pair: [ pair i j ] Is p [ i ] p [ j ]: If yes: continue, Else: go to step 2.
5. For selected pair : [ pair i j ] Is ( p [ i ] + p [ j ] ) min ( ESD for all successor operations for i ) : If yes: continue. Else : go to step 2.
6. For selected pair : [ pair i j ] a] Exchange the pair positions. b] Update the sequence list. c] Go to step 2.
Sequencing rules are one of the areas where performance improvement is possible in terms of production output, resource usage. Better the usage and utilization of resources is, better would be the end result w. r. t. standard manufacturing norms. This is not only creates a better work flow but also reduces the global operating costs.
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.
It is important to note the different between databases oriented applications and real intelligent applications. In general, database oriented applications always talks about the past – what had happened, whereas intelligent applications talks about the future – what will happen. This result is derived from the past and current state of the environment.
Primarily, this is nothing but generating a solution by “Looking – Ahead”. It would be interesting here to apply the good old concept of ‘Look ahead’ can also be applied to sequencing rule to generate new sequencing rule(s), with predefined objective function(s).
This is essentially a global sequencing, which considers the current resource and looks ahead to successor operations and respective resources to find out an efficient assignment for current resource.
In another knowledge paper we talked about standard sequencing rules, which are applied in general. Here we will try to illustrate sequencing rule, with look-ahead approach to derive heuristic sequencing rule. It would be appropriate to mention here that such heuristic sequencing rules can give better performance result in specific scenarios or environments.
(I) PROBLEM DEFINITION
The good old concept of ‘Look ahead’ can also be applied to sequencing rule to generate new sequencing rule(s), with predefined objective function.This is essentially a global sequencing, which considers the current resource and looks ahead to successor operations and respective resources to find out an efficient assignment for current resource.To illustrate the problem better, let us try to create a sample problem definition:
EXPRESSION OF PROBLEM:
1] Operations J1/10,….,J4/10 are to be scheduled on Wc1. Find out a sequence which shall satisfy a defined objective function, by looking ahead.
2] Next operations of all current operations [J1/10,….,J4/10 ] are operations [ J1/20,…, J4/20 ].
3] Above illustration shows feasible tuple / resources where next operation’s can be carried out. It provides respective processing times and queue lengths on each feasible resource. It is assumed that unit of queue length and processing time is same.
OBJECTIVE:
Find out operation sequence to be processed on current resource in order to achieve desired result. For example, the objective is to move the operation as fast as possible. In other words, try to minimize the WIP, in order to generate better throughput.
INFORMATION AVAILABLE [CALCULATED]:
I] List of the operations to be scheduled on current resource. [ curr_op_list ]
II] List of all immediate successor operations list of curr_op_list. [succ_op_list ]
III] List of all feasible tuples for succ_op_list. [ f_tuple]
IV] Merged calendar for all f_tuple. [cal_tuple]
V] Waiting queue at f-tuple [units same as processing time unit for operations] [ f_t_queue]
VI] Earliest start date for succ_op_list on each f_tuple. [ esd_succ_op ]
VII] Minimum esd_succ_op for succ_op_list. [one value per operation in curr_op_list] min_esd_op
VIII] Precedence constraint among succ_op_list pree_succ_op
Incoplan is a production scheduling and optimization solution. It provides a complete insight to your shop floor. You can predict and track the behaviour of your shop floor. It is a common platform for all concerned to see how production is moving. Incoplan considers all parameters, production resources, constraints attached to it, processes and routings, target dates, material status and it offers a complete production schedule to you. Incoplan is an integrated, reliable, flexible, scalable and quality solution for production scheduling.
Therefore the optimal solution of operations assignment is:
