"Look-ahead” Sequencing Rule ( Part II )

LOOK AHEAD HEURISTIC

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.