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

Optimal binary search tree in DSA

Implementation // A simple way of the recursive implementation of the optimal search that we will perform on the binary tree.   #include <bits/stdc++.h> using namespace std; // we have to create a basic utility...

8 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.

B Tree in Data Structure

Data management is called database management. A data model is a system that stores, manages, and optimizes computer resources. Data processing is not just about data storage. Almost every app...

9 minutes read.

CSS Text-indent

Text-indent The Text-indent property of CSS is used to set any first line’s indentation inside a text’s block. It describes the horizontal space amount that puts establish before the text line. It...

3 minutes read.

Queue Data Structure

Queue in DS: The queue is a non-primitive and linear data structure. It works on the principle of FIFO (First In First Out). That is, the element that is added...

4 minutes read.

Binary Tree Implementation Using Arrays

Implementation Converting a binary tree into a list of arrays is one interesting problem. Let us see that in depth. In this section, we will see the implementation of the binary Trees...

4 minutes read.

Convert a Binary Tree into a Binary Search Tree

Implementation #include <stdio.h>   #include <stdlib.h>       //creating a node of the binary tree.  struct __nod{       int record;       struct __nod *Lft;       struct __nod *Rt;   };       // presenting the root of the binary tree.   struct...

5 minutes read.

Binary Search Tree

Binary Search Tree: A binary search tree is a type of tree in which every node is organized in the sorted order. It is also called an ordered binary tree. Properties...

4 minutes read.

Equal Sum

Find an element in array such that the sum of left array is equal to the sum of right array You have been given an array of numbers. You have to...

4 minutes read.

Vertical Order Traversal of Binary Tree

Implementation #include <iostream> #include <vector> #include <map> using namespace std; // representing the primary model of a binary tree node. struct _nod { int ky; _nod *Lft, *Rt; }; // establishing a new function representing the new binary tree node. struct _nod*...

5 minutes read.

What Is Graph Data Structure

A graph is generally a set of vertices and edges or border that is mainly used to join these vertices. A graph is basically pictured as a cyclic tree in...

7 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.

Stack Using Linked List

In the linked list implementation of the stack, we use a linked list as the primitive data structure to create the stack. It is called the dynamic implementation of the...

6 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.

Create a binary search tree

Implementation In this section of the article, we will see the usage and mechanism of how we will create a given binary tree. Let's observe these in more depth and then...

7 minutes read.

Counts the number of times a given element occurs in a Linked List

Counts the number of times a given element occurs in a Linked List This article will explain how we can count the occurrences of a particular element in a list. Here,...

3 minutes read.

Binary Tree in Data Structures

What is a Binary Tree in Data Structures? The term binary itself means bi, which implies two of anything. So very clearly, we know we present the trees in the form...

6 minutes read.

Recursion in Fibonacci

Fibonacci heap is considered to be a particular execution of the heap data structure that ultimately helps in making use of not just any number but the Fibonacci numbers. It...

3 minutes read.

Linear Queue VS Circular Queue

What is Queue? A queue is one of the important linear data structures extensively used in various computer applications. It is based on the FIFO (First In First Out) principle. It...

9 minutes read.

Data Structure Infix to Prefix Conversion

Infix to Prefix Conversion In present time, we use the infix expression in our daily life but the computers are not able to understand this format because they need to keep...

4 minutes read.