What is Assembly Line Scheduling?
We know that in automobile industry, automobiles are produced using assembly lines. There are multiple lines that are working together to produce products. Then a finished auto exits at the end of the line.
The problem is that which line we should choose next from any station that will give best time utilization for company for one auto.
The main goal of assembly line scheduling is to give best route or can say fastest from all assembly line.
In above the diagram we have two main assembly line consider as LINE 1 and LINE 2.
- e[i]: entry time in assembly line i [here i=1,2]
- x[i]: exit time from assembly line i
- a[i,j]: Time required at station S[i,j] (assembly line i, stage j)[i=1 to n] because Every station has some dedicated job that needs to done.
- t[i,j]: Time required to transit from station S[i,j] to the other assembly line.
Normally, once a chassis enters an assembly line, it passes through that line only. The time to go from one station to the next within the same assembly line is negligible.
Occasionally, a special rush order comes in, and the customer wants the automobile to be manufactured as quickly as possible. For the rush orders, the chassis still passes through the n stations in order, but the factory manager may switch the partially-completed auto from one assembly line to the other after any station.
To get jobs done we will use Dynamic Programming.
Objective: To find the optimal scheduling i.e., the fastest way from start to exit.
Note: let fi [j] denotes the fastest way from start to station S[i,j] .
* An optimal solution to a problem is determined using optimal solutions to sub problems (in turn, sub sub problems and so on). The immediate question is, how to break the problem in to smaller sub problems ?
The answer is : if we know the minimum time taken by the chassis to leave station S[i,j−1] then the minimum time taken to leave station S[i,j] can be calculated quickly by combining a[i,j] and t[i,j] .
Final Solution: f optimal = min{f1[n] + x1, f2[n] + x2}.
we can take f1[1] = e1 + a[1,1] and f2[1] = e2 + a[2,1].
Recursive Solution: The chassis at station S[1,j] can come either from station S[1,j−1] or station S[2,j−1] (Since, the tasks done by S[1,j] and S[2,j] are same). But if the chassis comes from S[2,j−1], it additionally incurs the transfer cost to change the assembly line ( like t[2,j-1] ). Thus, the recursion to reach the station j in assembly line i are as follows:
->Algorithm for Assembly line scheduling :
Explanation of algorithm:
If as discussed above we consider 2 assembly line. Then f1[1] and f2[1] is defined as algorithm by adding starting cost and first station cost.
Then applies our recursive solution for n station points.here l1[j] denotes from which assembly line chassis has come.
At the last fopt gives you final solution.
The time complexity of the above dynamic programming implementation of the assembly line scheduling problem is O(n).
