Logo
×

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

Related Topics

Identical Linked Lists

Identical Linked Lists In this problem, we have given two linked lists, and we need to check whether the given linked lists are identical or not. Identical means they have the...

4 minutes read.

B+ Tree Program in Q language

A B+ tree is just an improvised version of a self-balancing and well-maintained tree in which all the key values that hold valuable information is present at the bottom, which...

9 minutes read.

Remove duplicates from an unsorted Linked List

Remove duplicates from an unsorted Linked List This article will explain how we can remove duplicates from unsorted linked lists. Here we have given an unsorted singly linked list and will...

3 minutes read.

Given a Binary Tree Check the Zig-Zag Traversal

Implementation // The C++ implementation of the zig-zag traversal method in the O(n) time.  #include <iostream> #include <stack> using namespace std; // creating a binary tree node. struct __nod { int record; struct __nod *Lft, *Rt; }; // creating a...

4 minutes read.

Finding the Minimum and Maximum Value of a Binary Tree

Implementation // Writing a C++ program that will help us find out the maximum and the minimum in a binary tree.  #include <bits/stdc++.h> #include <iostream> using namespace std; // creating a new class tree node. class...

5 minutes read.

Left View of Binary Tree

Implementation // creating a C++ program to print the Left view of the binary tree. #include <bits/stdc++.h> using namespace std; struct Nod { int record; struct Nod *Lft, *Rt; }; // creating a utility function that will eventually help...

4 minutes read.

Reverse the Singly Linked List in C

Reverse the Singly Linked List in C This article has given a singly linked list and will reverse the linked list by changing the links between nodes. Example:                         Input:  2 -> 4...

3 minutes read.

Given a Binary Tree, find its Minimum Depth

Implementation // Creating a C++ program or implementation to search and explore the minimum depth of a given binary tree.  #include<bits/stdc++.h> using namespace std; // Creating a new binary tree node struct __nod { int record; struct __nod*...

5 minutes read.

What is a Tree in Terms of a Graph?

To know the explanation of trees in terms of graphs, we need first to know what trees and graphs are. So let us first learn about trees and graphs. Trees and...

6 minutes read.

Stack Data Structure

The stack is a non-primitive and linear data structure. It works on the principle of LIFO (Last In First Out). That is, the element that is added to the end...

3 minutes read.

Convert Binary Tree into a Threaded Binary Tree

Implementation /*Writing a C++ program that will help us change the binary tree into a threaded binary tree and help us transform. */ #include <bits/stdc++.h> using namespace std; /*Creating the structure of a node...

11 minutes read.

Threaded Binary Tree

The linked form of binary trees wastes storage capacity because more than half of the connection variables have a Missing value. A binary tree has several nodes. Hence n+1 link fields...

8 minutes read.

Implementation of Queue

Implementation of queue: We can implement the queue through the array and linked list. An array is the easiest way to implement the queue. When a queue is created with the...

7 minutes read.

Find all possible words from board

We have been given a dictionary of words and a board of characters from which we can form strings. Now, we have to check if the string is present in...

5 minutes read.

What is the B+ Tree in Data Structures?

We all know that the B+ tree in data structures is nothing but just an extended version of the B tree. It allows the smooth working of all the operations...

7 minutes read.

Introduction to 1D-Arrays

One Dimensional Array Technical Definitions The simplest version of an Array is a One-Dimensional Array, in which the items are stored linearly and may be accessed individually by supplying the index value...

6 minutes read.

AVL Tree

AVL Tree AVL Tree is referred to as self-balanced or height-balanced binary search tree where the difference between heights of its left subtree and right subtree (Balance Factor) can't more than...

25 minutes read.

Intersection Point in Y Shaped Linked Lists in Java

Intersection Point in Y Shaped Linked Lists in Java In this article, we are going to see how to find the intersection point in a Y-shaped linked list. Method 1: We need to...

4 minutes read.

Adding one to the number represented an array of digits

You have given one array, which consists of values which represent the different digits of a number. You have to add 1 to this number and store the result in...

3 minutes read.

Symmetric binary tree

Implementation // writing a C++ program to check whether a given binary tree is symmetric or not. #include <bits/stdc++.h> using namespace std; // creating a binary tree node. struct __Nod { int ky; struct __Nod *Lft, *Rt; }; //...

4 minutes read.