Dynamic Programming: Assembly-line Scheduling
Hey everyone,
In this video I discuss an interesting problem from the book introduction to algorithms by C.L.R.S.
Problem Statement/Definitions
1.You own two lines of N machines each used to produce one part of a car.
2. ith Machine in line 1 is called Mi1 and ith machine in line 2 is called Mi2.
3. ith Machine in line 1 takes Ti1 time to produce part P1 whereas ith machine of line 2 takes Ti2 time.
4. It takes e1 time to put raw material into line 1 machine 1 whereas it takes e2 time to put it in line 2 machine 1.
5. It takes r1 time to get ready car from Nth machine of line 1 whereas it takes r2 time to get ready car from Nth machine of line 2.
6. To go from Mi1 to M(i+1)1 it takes 0 seconds while it takes Si2 time to go from Mi1 to M(i+1)2
7. Si2 represents shift time to go from machine i in line1 to machine i+1 in line 2.
Si1 represents shift time to go from machine i in line2 to machine i+1 in line 1.
8. Starting from the raw material you should produce the car in minimum time possible. ith part should always be manufactured before (i+1)th part.
If you found this useful, do give a like and consider subscribing to the channel.