DP34 流水線調度問題 Assembly Line Scheduling @geeksforgeeks

A car factory has two assembly lines, each with n stations. A station is denoted by S_i,j where i is either 1 or 2 and indicates the assembly line the station is on, and j indicates the number of the station. The time taken per station is denoted by a_i,j. Each station is dedicated to some sort of work like engine fitting, body fitting, painting and so on. So, a car chassis must pass through each of the n stations in order before exiting the factory. The parallel stations of the two assembly lines perform the same task. After it passes through station S_i,j, it will continue to station S_i,j+1 unless it decides to transfer to the other line. Continuing on the same line incurs no extra cost, but transferring from line i at station j – 1 to station j on the other line takes time t_i,j. Each assembly line takes an entry time e_i and exit time x_i which may be different for the two lines. Give an algorithm for computing the minimum time it will take to build a car chassis.

The below figure presents the problem in a clear picture:

The following information can be extracted from the problem statement to make it simpler:

Two assembly lines, 1 and 2, each with stations from 1 to n.A car chassis must pass through all stations from 1 to n in order(in any of the two assembly lines). i.e. it cannot jump from station i to station j if they are not at one move distance.The car chassis can move one station forward in the same line, or one station diagonally in the other line. It incurs an extra cost ti, j to move to station j from line i. No cost is incurred for movement in same line.The time taken in station j on line i is a_{i, j}.S_{i, j} represents a station j on line i.

Breaking the problem into smaller sub-problems:
We can easily find the ith factorial if (i-1)th factorial is known. Can we apply the similar funda here?
If the minimum time taken by the chassis to leave station S_{i, j-1} is known, the minimum time taken to leave station S_{i, j} can be calculated quickly by combining a_{i, j} and t_{i, j}.

T1(j) indicates the minimum time taken by the car chassis to leave station j on assembly line 1.

T2(j) indicates the minimum time taken by the car chassis to leave station j on assembly line 2.

Base cases:
The entry time e_i comes into picture only when the car chassis enters the car factory.

Time taken to leave first station in line 1 is given by:
T1(1) = Entry time in Line 1 + Time spent in station S_1,1
T1(1) = e₁ + a_1,1
Similarly, time taken to leave first station in line 2 is given by:
T2(1) = e₂ + a_2,1

Recursive Relations:
If we look at the problem statement, it quickly boils down to the below observations:
The car chassis at station S_1,j can come either from station S_{1, j-1} or station S_{2, j-1}.

Case #1: Its previous station is S_{1, j-1}
The minimum time to leave station S_1,j is given by:
T1(j) = Minimum time taken to leave station S_{1, j-1} + Time spent in station S_{1, j}
T1(j) = T1(j-1) + a_{1, j}

Case #2: Its previous station is S_{2, j-1}
The minimum time to leave station S1, j is given by:
T1(j) = Minimum time taken to leave station S_{2, j-1} + Extra cost incurred to change the assembly line + Time spent in station S_{1, j}
T1(j) = T2(j-1) + t_{2, j} + a_{1, j}

The minimum time T1(j) is given by the minimum of the two obtained in cases #1 and #2.
T1(j) = min((T1(j-1) + a_{1, j}), (T2(j-1) + t_{2, j} + a_{1, j}))
Similarly the minimum time to reach station S2, j is given by:
T2(j) = min((T2(j-1) + a_{2, j}), (T1(j-1) + t_{1, j} + a_{2, j}))

The total minimum time taken by the car chassis to come out of the factory is given by:
Tmin = min(Time taken to leave station S_i,n + Time taken to exit the car factory)
Tmin = min(T1(n) + x₁, T2(n) + x₂)

Why dynamic programming?
The above recursion exhibits overlapping sub-problems. There are two ways to reach station S_{1, j}:

From station S_{1, j-1}From station S_{2, j-1}

So, to find the minimum time to leave station S_{1, j} the minimum time to leave the previous two stations must be calculated(as explained in above recursion).
Similarly, there are two ways to reach station S_{2, j}:

From station S_{2, j-1}From station S_{1, j-1}

Please note that the minimum times to leave stations S_{1, j-1} and S_{2, j-1} have already been calculated.

So, we need two tables to store the partial results calculated for each station in an assembly line. The table will be filled in bottom-up fashion.

Note:
In this post, the word “leave” has been used in place of “reach” to avoid the confusion. Since the car chassis must spend a fixed time in each station, the word leave suits better.




流水線調度問題，DP的經典例子。到達某一裝配點的貨物既可以由本流水線過來，也可以由另一支流水線過來，取決於哪一個更合算。

以下例子答案：

Output:

35


The bold line shows the path covered by the car chassis for given input values.

Exercise:
Extend the above algorithm to print the path covered by the car chassis in the factory.





package DP;

public class AssemblyLineScheduling {

	public static void main(String[] args) {
		int[][] a = {{4, 5, 3, 2},
                		 {2, 10, 1, 4}};
		int[][] t = {{0, 7, 4, 5},
                		 {0, 9, 2, 8}};
		int[] e = {10, 12};
		int[] x = {18, 7};
		System.out.println(carAssemblyDP(a, t, e, x));
		System.out.println(carAssembly(a, t, e, x));
	}
	
	public static int carAssembly(int[][] a, int[][] t, int[] e, int[] x){
		int n = a[0].length-1;
		return Math.min(carAssemblyRec(a,t, e, x, n, 0) + x[0], 
								carAssemblyRec(a,t, e, x, n, 1) + x[1]);
	}
	
	public static int carAssemblyRec(int[][] a, int[][] t, int[] e, int[] x, int n, int line){
		if(n == 0){
			return e[line] + a[line][0];
		}
		
		int T0 = Integer.MAX_VALUE;
		int T1 = Integer.MAX_VALUE;
		if(line == 0){		// 以下只適用於line0
			T0 = Math.min(carAssemblyRec(a, t, e, x, n-1, 0) + a[0][n],				// 從本線路過來的
								carAssemblyRec(a, t, e, x, n-1, 1) + t[1][n] + a[0][n]);	// 從另一條線路過來的
		}else if(line == 1){		// 以下只適用於line1
			T1 = Math.min(carAssemblyRec(a, t, e, x, n-1, 1) + a[1][n],				// 從本線路過來的
								 carAssemblyRec(a, t, e, x, n-1, 0) + t[0][n] + a[1][n]);	// 從另一條線路過來的
		}
		
		return Math.min(T0, T1);
	}

	public static int carAssemblyDP(int[][] a, int[][] t, int[] e, int[] x){
		int n = a[0].length;
		int[] T1 = new int[n];
		int[] T2 = new int[n];
		
		T1[0] = e[0] + a[0][0];
		T2[0] = e[1] + a[1][0];
		
		for(int i=1; i




吐槽一下這題的遞歸，一開始我是這樣寫的：
	public static int carAssemblyRec(int[][] a, int[][] t, int[] e, int[] x, int n, int line){
		if(n == 0){
			return e[line] + a[line][0];
		}
		
		int T0 = Math.min(carAssemblyRec(a, t, e, x, n-1, 0) + a[0][n],
								 carAssemblyRec(a, t, e, x, n-1, 1) + t[1][n] + a[0][n]);
		int T1 = Math.min(carAssemblyRec(a, t, e, x, n-1, 1) + a[1][n],
								 carAssemblyRec(a, t, e, x, n-1, 0) + t[0][n] + a[1][n]);
		
		return Math.min(T0, T1);
	}


結果和DP的不一樣，於是在哪裡想了半天哪裡出問題，費了好大功夫，用debugger單步跟蹤才發現原來是忘記加限制條件了！！！

正確寫法應該是：
	public static int carAssemblyRec(int[][] a, int[][] t, int[] e, int[] x, int n, int line){
		if(n == 0){
			return e[line] + a[line][0];
		}
		
		int T0 = Integer.MAX_VALUE;
		int T1 = Integer.MAX_VALUE;
		if(line == 0){		// 以下只適用於line0
			T0 = Math.min(carAssemblyRec(a, t, e, x, n-1, 0) + a[0][n],				// 從本線路過來的
								carAssemblyRec(a, t, e, x, n-1, 1) + t[1][n] + a[0][n]);	// 從另一條線路過來的
		}else if(line == 1){		// 以下只適用於line1
			T1 = Math.min(carAssemblyRec(a, t, e, x, n-1, 1) + a[1][n],				// 從本線路過來的
								 carAssemblyRec(a, t, e, x, n-1, 0) + t[0][n] + a[1][n]);	// 從另一條線路過來的
		}
		
		return Math.min(T0, T1);
	}








http://www.geeksforgeeks.org/dynamic-programming-set-34-assembly-line-scheduling/