Flow Shop Scheduling Algorithm & CPP Code
Flow Shop Scheduling Algorithm
Brief:-
Flow Shop Scheduling Problem in general sense is a problem in which we are given some processes with their start time and finish time , in the given set of process we need to find out the list of process which we will select so that the process time is utilised to the maximum. The main complication in this process is that the time of the process set may overlap , and in those overlapping time we need to select the best path so that we have the processor idle for the minimum time.Note:
We can skip whichever process we want to skip, and select a process which may give us the best process utilisation. We assume T(Px) denotes time utilised by process x.Simple Wrong Approach:-
- Pick the process which arrives first :- If we pick the process which arrived first , then there may be some process which might lead to better process utilisation.
- Pick the process with highest time consumption :- There may come a case where there might be many small process overlapping the max time consuming process , which on addition would give better process utilisation, In this case T(P1) + T(P3) > T(P2).
Correct Approach:-
Guess all the paths possible and pick the best path amongst them , Optimally. (Assuming path means possible set of processes which we can group together).
How can we guess "Optimally"?
Assume the given problem as a graphical problem, suppose we start from a fixed node P0 with weight 1 and from there we can take multiple pathways , if we choose P1 then we cannot choose P2 and so on. We can optimise the path visits by skipping all the nodes , appearing before common node and tracing the path. By doing this , we are not starting over again and again instead we are selecting a node , moving ahead and selecting again until we reach an end. After reaching the end we take note of the total time, and move one step back, select the traversed node and do the same process again and again. While doing this, we move backwards in a minimal way. This process can be better understood by using stacks.
Suppose, we have a problem for job scheduling as given in fig(a). Assume we have an empty stack and an empty queue. In the stack each process might be selected or unselected. The process of traversing will look as in fig(b). The notation inside the process is (Process Number , Selected/Unselected ). (1 for Selected, 0 for Unselected).
Note:- We will always assume that we are starting with P0 , which starts at 0 and ends at 1, and starting there we can have multiple paths or sets. i.e. P0 will always be part of a set. In the final outcome , removing P0 from the set and subtracting 1 from the process time will give the best set.
Suppose, we have a problem for job scheduling as given in fig(a). Assume we have an empty stack and an empty queue. In the stack each process might be selected or unselected. The process of traversing will look as in fig(b). The notation inside the process is (Process Number , Selected/Unselected ). (1 for Selected, 0 for Unselected).
Algorithm:
- Push the process P0 into the stack.
- Push all the closest next possible processes into the stack and then select the topmost process.
- Repeat 1 and 2 until there is no process left to push. i.e. we reach leaf, After reaching leaf , Calculate the total time utilised for the selected process , Clear the Queue and Insert the selected process into the queue, iff current utilisation of time is greater than previous time in queue.
- Pop until we see an unselected process , select it and repeat from 1. If we do not find any process with 0 i.e. unselected, then display the queue as the final set of the processes which if selected gives best processor utilisation.
Note:- We will always assume that we are starting with P0 , which starts at 0 and ends at 1, and starting there we can have multiple paths or sets. i.e. P0 will always be part of a set. In the final outcome , removing P0 from the set and subtracting 1 from the process time will give the best set.
