Assembly Line Scheduling
If we take an example of a car factory, there are two assembly lines. In an assembly line, we can assemble and repair the parts of a car. Now, suppose that we have to build a new car from this factory. So, we have to go through one of the assembly lines. In each assembly line, there are many stations. Every station has its own work so, we cannot miss one station. But it is possible to jump from station of one assembly line to the very next station of another assembly line. In every station there are some time taken and to transfer from one station to another, it also takes some time. You have to find minimum time to complete the car. There will be a given time for each station.
Concept behind the solution
Here, we will use recursion and DP. By recursion, we can divide the problem into smaller sub problems. After that it is easy to find out the solution. It is obvious that there will be occurred some repeating sub problems so; we will use dynamic programming to find out optimised solution. Check the following code to understand the things well.
Code:
// C++ program to find minimum possible time to complete the car
#include <bits/stdc++.h>
using namespace std;
#define ASLINE 2
#define STATIONNUM 4
int min(int a, int b)
{
return a < b ? a : b;
}
int asemblecarfun(int a[][STATIONNUM],
int t[][STATIONNUM],
int *e, int *x)
{
int T1[STATIONNUM], T2[STATIONNUM], i;
T1[0] = e[0] + a[0][0];
T2[0] = e[1] + a[1][0];
for (i = 1; i < STATIONNUM; ++i)
{
T1[i] = min(T1[i - 1] + a[0][i],
T2[i - 1] + t[1][i] + a[0][i]);
T2[i] = min(T2[i - 1] + a[1][i],
T1[i - 1] + t[0][i] + a[1][i]);
}
return min(T1[STATIONNUM - 1] + x[0],
T2[STATIONNUM - 1] + x[1]);
}
int main()
{
int a[][STATIONNUM] = {{4, 5, 3, 2},
{2, 10, 1, 4}};
int t[][STATIONNUM] = {{0, 7, 4, 5},
{0, 9, 2, 8}};
int e[] = {10, 12}, x[] = {18, 7};
cout << asemblecarfun(a, t, e, x);
return 0;
}
// C program to find minimum possible time to complete the car
#include <stdio.h>
#define ASLINE 2
#define STATIONNUM 4
int min(int a, int b) { return a < b ? a : b; }
int asemblecarfun(int a[][STATIONNUM], int t[][STATIONNUM], int *e, int *x)
{
int T1[STATIONNUM], T2[STATIONNUM], i;
T1[0] = e[0] + a[0][0];
T2[0] = e[1] + a[1][0];
for (i = 1; i < STATIONNUM; ++i)
{
T1[i] = min(T1[i-1] + a[0][i], T2[i-1] + t[1][i] + a[0][i]);
T2[i] = min(T2[i-1] + a[1][i], T1[i-1] + t[0][i] + a[1][i]);
}
return min(T1[STATIONNUM-1] + x[0], T2[STATIONNUM-1] + x[1]);
}
int main()
{
int a[][STATIONNUM] = {{4, 5, 3, 2},
{2, 10, 1, 4}};
int t[][STATIONNUM] = {{0, 7, 4, 5},
{0, 9, 2, 8}};
int e[] = {10, 12}, x[] = {18, 7};
printf("%d", asemblecarfun(a, t, e, x));
return 0;
}
// JAVA program to find minimum possible time to complete the car
import java.io.*;
class bn
{
static int ASLINE = 2;
static int STATIONNUM = 4;
static int min(int a, int b)
{
return a < b ? a : b;
}
static int asemblecarfun(int a[][], int t[][], int e[], int x[])
{
int T1[]= new int [STATIONNUM];
int T2[] =new int[STATIONNUM] ;
int i;
T1[0] = e[0] + a[0][0];
T2[0] = e[1] + a[1][0];
for (i = 1; i < STATIONNUM; ++i)
{
T1[i] = min(T1[i - 1] + a[0][i],
T2[i - 1] + t[1][i] + a[0][i]);
T2[i] = min(T2[i - 1] + a[1][i],
T1[i - 1] + t[0][i] + a[1][i]);
}
return min(T1[STATIONNUM-1] + x[0],
T2[STATIONNUM-1] + x[1]);
}
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}, x[] = {18, 7};
System.out.println(asemblecarfun(a, t, e, x));
}
}
# Python program to find minimum possible time to complete the car
def asemblecarfun (a, t, e, x):
STATIONNUM = len(a[0])
T1 = [0 for i in range(STATIONNUM)]
T2 = [0 for i in range(STATIONNUM)]
T1[0] = e[0] + a[0][0] # time taken to leave
T2[0] = e[1] + a[1][0] # time taken to leave
for i in range(1, STATIONNUM):
T1[i] = min(T1[i-1] + a[0][i],
T2[i-1] + t[1][i] + a[0][i])
T2[i] = min(T2[i-1] + a[1][i],
T1[i-1] + t[0][i] + a[1][i] )
return min(T1[STATIONNUM - 1] + x[0],
T2[STATIONNUM - 1] + x[1])
a = [[4, 5, 3, 2],
[2, 10, 1, 4]]
t = [[0, 7, 4, 5],
[0, 9, 2, 8]]
e = [10, 12]
x = [18, 7]
print(asemblecarfun(a, t, e, x))// C# program to find minimum possible time to complete the car
using System;
class bn {
static int STATIONNUM = 4;
static int min(int a, int b)
{
return a < b ? a : b;
}
static int asemblecarfun(int [,]a, int [,]t,
int []e, int []x)
{
int []T1= new int [STATIONNUM];
int []T2 =new int[STATIONNUM] ;
int i;
T1[0] = e[0] + a[0,0];
T2[0] = e[1] + a[1,0];
for (i = 1; i < STATIONNUM; ++i)
{
T1[i] = min(T1[i - 1] + a[0,i],
T2[i - 1] + t[1,i] + a[0,i]);
T2[i] = min(T2[i - 1] + a[1,i],
T1[i - 1] + t[0,i] + a[1,i]);
}
return min(T1[STATIONNUM-1] + x[0],
T2[STATIONNUM-1] + x[1]);
}
public static void Main ()
{
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};
Console.Write(asemblecarfun(a, t, e, x));
}
}
// PHP program to find minimum possible time to complete the car
<?php
$ASLINE = 2;
$STATIONNUM = 4;
function asemblecarfun($a, $t,
$e, $x)
{
global $NUM_LINE,
$STATIONNUM;
$T1 = array();
$T2 = array();
$i;
$T1[0] = $e[0] + $a[0][0];
$T2[0] = $e[1] + $a[1][0];
for ($i = 1;
$i < $STATIONNUM; ++$i)
{
$T1[$i] = min($T1[$i - 1] + $a[0][$i],
$T2[$i - 1] + $t[1][$i] +
$a[0][$i]);
$T2[$i] = min($T2[$i - 1] + $a[1][$i],
$T1[$i - 1] + $t[0][$i] +
$a[1][$i]);
}
return min($T1[$STATIONNUM - 1] + $x[0],
$T2[$STATIONNUM - 1] + $x[1]);
}
$a = array(array(4, 5, 3, 2),
array(2, 10, 1, 4));
$t = array(array(0, 7, 4, 5),
array(0, 9, 2, 8));
$e = array(10, 12);
$x = array(18, 7);
echo asemblecarfun($a, $t, $e, $x);
?>
// A JavaScript program to find minimum possible time to complete the car
<script>
const ASLINE = 2;
const STATIONNUM = 4;
function min(a, b)
{
return a < b ? a : b;
}
function asemblecarfun(a, t, e, x)
{
let T1 = new Array(STATIONNUM);
let T2 = new Array(STATIONNUM);
let i;
T1[0] = e[0] + a[0][0];
T2[0] = e[1] + a[1][0];
for (i = 1; i < STATIONNUM; ++i)
{
T1[i] = min(T1[i - 1] + a[0][i],
T2[i - 1] + t[1][i] + a[0][i]);
T2[i] = min(T2[i - 1] + a[1][i],
T1[i - 1] + t[0][i] + a[1][i]);
}
return min(T1[STATIONNUM - 1] + x[0],
T2[STATIONNUM - 1] + x[1]);
}
let a = [[4, 5, 3, 2],
[2, 10, 1, 4]];
let t = [[0, 7, 4, 5],
[0, 9, 2, 8]];
let e = [10, 12], x = [18, 7];
document.write(asemblecarfun(a, t, e, x));
</script>
Output:
35