Una fábrica de automóviles tiene dos líneas de montaje, cada una con n estaciones. Una estación se denota con S i, j, donde i es 1 o 2 e indica la línea de montaje en la que se encuentra la estación, y j indica el número de la estación. El tiempo empleado por estación se denota por ai,j . Cada estación está dedicada a algún tipo de trabajo como ajuste de motor, ajuste de carrocería, pintura, etc. Entonces, el chasis de un automóvil debe pasar por cada una de las n estaciones en orden antes de salir de la fábrica. Las estaciones paralelas de las dos líneas de montaje realizan la misma tarea. Después de pasar por la estación Si ,j , continuará hasta la estación Si ,j+1a menos que decida transferirse a la otra línea. Continuar en la misma línea no tiene ningún costo extra, pero hacer transbordo de la línea i en la estación j – 1 a la estación j en la otra línea lleva un tiempo ti , j . Cada línea de montaje tiene un tiempo de entrada e i y un tiempo de salida x i que pueden ser diferentes para las dos líneas. Proporcione un algoritmo para calcular el tiempo mínimo que llevará construir el chasis de un automóvil.
La siguiente figura presenta el problema en una imagen clara:
La siguiente información se puede extraer del enunciado del problema para simplificarlo:
- Dos líneas de montaje, 1 y 2, cada una con estaciones de 1 a n.
- El chasis de un automóvil debe pasar por todas las estaciones del 1 al n en orden (en cualquiera de las dos líneas de ensamblaje). es decir, no puede saltar de la estación i a la estación j si no están a una distancia de movimiento.
- El chasis del automóvil puede avanzar una estación en la misma línea o una estación en diagonal en la otra línea. Se incurre en un costo adicional ti, j para trasladarse a la estación j desde la línea i. No se incurre en costo por movimiento en la misma línea.
- El tiempo empleado en la estación j de la línea i es a i, j .
- Si , j representa una estación j en la línea i.
Dividir el problema en subproblemas más pequeños:
podemos encontrar fácilmente el i-ésimo factorial si se conoce el (i-1)-ésimo factorial. ¿Podemos aplicar el mismo fundamento aquí?
Si se conoce el tiempo mínimo que tarda el chasis en salir de la estación Si , j-1 , el tiempo mínimo que tarda en salir de la estación Si , j se puede calcular rápidamente combinando a i, j y ti , j .
T1(j) indica el tiempo mínimo que tarda el chasis del coche en salir de la estación j en la línea de montaje 1.
T2(j) indica el tiempo mínimo que tarda el chasis del coche en salir de la estación j en la línea de montaje 2.
Casos base:
El tiempo de entrada e i aparece en la imagen solo cuando el chasis del automóvil ingresa a la fábrica de automóviles.
El tiempo que se tarda en salir de la primera estación de la línea 1 viene dado por:
T1(1) = Tiempo de entrada en la Línea 1 + Tiempo de permanencia en la estación S 1,1
T1(1) = e 1 + a 1,1
Del mismo modo, el tiempo que se tarda en salir de la primera estación de la línea 2 viene dado por:
T2(1) = e 2 + a 2,1
Relaciones recursivas:
Si observamos el enunciado del problema, rápidamente se reduce a las siguientes observaciones:
El chasis del automóvil en la estación S 1, j puede provenir de la estación S 1, j-1 o de la estación S 2, j-1 .
Caso #1: Su estación anterior es S 1, j-1
El tiempo mínimo para salir de la estación S 1,j viene dado por:
T1(j) = Tiempo mínimo para salir de la estación S 1, j-1 + Tiempo pasado en la estación S 1, j
T1(j) = T1(j-1) + a 1, j
Caso #2: Su estación anterior es S 2, j-1
El tiempo mínimo para salir de la estación S1, j está dado por:
T1(j) = Tiempo mínimo para salir de la estación S 2, j-1 + Costo extra incurrido para cambiar la línea de montaje + Tiempo pasado en la estación S 1, j
T1(j) = T2(j-1) + t 2, j + a 1, j
El tiempo mínimo T1(j) viene dado por el mínimo de los dos obtenidos en los casos #1 y #2.
T1(j) = min((T1(j-1) + a 1, j ), (T2(j-1) + t 2, j + a 1, j ))
De manera similar, el tiempo mínimo para llegar a la estación S2, j viene dado por:
T2(j) = min((T2(j-1) + a 2, j ), (T1(j-1) + t 1, j + a 2, j ))
El tiempo mínimo total que tarda el chasis del coche en salir de la fábrica viene dado por:
Tmin = min(Tiempo que tarda en salir de la estación S i,n + Tiempo que tarda en salir de la fábrica del coche)
Tmin = min(T1(n) + x1 , T2 (n) + x2 )
¿Por qué programación dinámica?
La recursión anterior exhibe subproblemas superpuestos. Hay dos formas de llegar a la estación S 1, j :
- Desde la estación S 1, j-1
- Desde la estación S 2, j-1
Entonces, para encontrar el tiempo mínimo para salir de la estación S 1, j se debe calcular el tiempo mínimo para salir de las dos estaciones anteriores (como se explica en la recursividad anterior).
Del mismo modo, hay dos formas de llegar a la estación S 2, j :
- Desde la estación S 2, j-1
- Desde la estación S 1, j-1
Tenga en cuenta que los tiempos mínimos para salir de las estaciones S 1, j-1 y S 2, j-1 ya se han calculado.
Entonces, necesitamos dos tablas para almacenar los resultados parciales calculados para cada estación en una línea de montaje. La tabla se llenará de abajo hacia arriba.
Nota:
En esta publicación, se ha utilizado la palabra «dejar» en lugar de «alcanzar» para evitar confusiones. Dado que el chasis del automóvil debe pasar un tiempo fijo en cada estación, la palabra dejar se adapta mejor.
Implementación:
C++
// A C++ program to find minimum possible
// time by the car chassis to complete
#include <bits/stdc++.h>
using namespace std;
#define NUM_LINE 2
#define NUM_STATION 4
// Utility function to find a minimum of two numbers
int min(int a, int b)
{
return a < b ? a : b;
}
int carAssembly(int a[][NUM_STATION],
int t[][NUM_STATION],
int *e, int *x)
{
int T1[NUM_STATION], T2[NUM_STATION], i;
// time taken to leave first station in line 1
T1[0] = e[0] + a[0][0];
// time taken to leave first station in line 2
T2[0] = e[1] + a[1][0];
// Fill tables T1[] and T2[] using the
// above given recursive relations
for (i = 1; i < NUM_STATION; ++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]);
}
// Consider exit times and return minimum
return min(T1[NUM_STATION - 1] + x[0],
T2[NUM_STATION - 1] + x[1]);
}
// Driver Code
int main()
{
int a[][NUM_STATION] = {{4, 5, 3, 2},
{2, 10, 1, 4}};
int t[][NUM_STATION] = {{0, 7, 4, 5},
{0, 9, 2, 8}};
int e[] = {10, 12}, x[] = {18, 7};
cout << carAssembly(a, t, e, x);
return 0;
}
// This is code is contributed by rathbhupendra
C
// A C program to find minimum possible time by the car chassis to complete
#include <stdio.h>
#define NUM_LINE 2
#define NUM_STATION 4
// Utility function to find minimum of two numbers
int min(int a, int b) { return a < b ? a : b; }
int carAssembly(int a[][NUM_STATION], int t[][NUM_STATION], int *e, int *x)
{
int T1[NUM_STATION], T2[NUM_STATION], i;
T1[0] = e[0] + a[0][0]; // time taken to leave first station in line 1
T2[0] = e[1] + a[1][0]; // time taken to leave first station in line 2
// Fill tables T1[] and T2[] using the above given recursive relations
for (i = 1; i < NUM_STATION; ++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]);
}
// Consider exit times and return minimum
return min(T1[NUM_STATION-1] + x[0], T2[NUM_STATION-1] + x[1]);
}
int main()
{
int a[][NUM_STATION] = {{4, 5, 3, 2},
{2, 10, 1, 4}};
int t[][NUM_STATION] = {{0, 7, 4, 5},
{0, 9, 2, 8}};
int e[] = {10, 12}, x[] = {18, 7};
printf("%d", carAssembly(a, t, e, x));
return 0;
}
Java
// A java program to find minimum possible
// time by the car chassis to complete
import java.io.*;
class GFG
{
static int NUM_LINE = 2;
static int NUM_STATION = 4;
// Utility function to find minimum of two numbers
static int min(int a, int b)
{
return a < b ? a : b;
}
static int carAssembly(int a[][], int t[][], int e[], int x[])
{
int T1[]= new int [NUM_STATION];
int T2[] =new int[NUM_STATION] ;
int i;
// time taken to leave first station in line 1
T1[0] = e[0] + a[0][0];
// time taken to leave first station in line 2
T2[0] = e[1] + a[1][0];
// Fill tables T1[] and T2[] using
// the above given recursive relations
for (i = 1; i < NUM_STATION; ++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]);
}
// Consider exit times and return minimum
return min(T1[NUM_STATION-1] + x[0],
T2[NUM_STATION-1] + x[1]);
}
// Driver code
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(carAssembly(a, t, e, x));
}
}
// This code is contributed by vt_m
Python3
# Python program to find minimum possible # time by the car chassis to complete def carAssembly (a, t, e, x): NUM_STATION = len(a[0]) T1 = [0 for i in range(NUM_STATION)] T2 = [0 for i in range(NUM_STATION)] T1[0] = e[0] + a[0][0] # time taken to leave # first station in line 1 T2[0] = e[1] + a[1][0] # time taken to leave # first station in line 2 # Fill tables T1[] and T2[] using # above given recursive relations for i in range(1, NUM_STATION): 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] ) # consider exit times and return minimum return min(T1[NUM_STATION - 1] + x[0], T2[NUM_STATION - 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(carAssembly(a, t, e, x)) # This code is contributed by Soumen Ghosh
C#
// A C# program to find minimum possible
// time by the car chassis to complete
using System;
class GFG {
static int NUM_STATION = 4;
// Utility function to find minimum
// of two numbers
static int min(int a, int b)
{
return a < b ? a : b;
}
static int carAssembly(int [,]a, int [,]t,
int []e, int []x)
{
int []T1= new int [NUM_STATION];
int []T2 =new int[NUM_STATION] ;
int i;
// time taken to leave first station
// in line 1
T1[0] = e[0] + a[0,0];
// time taken to leave first station
// in line 2
T2[0] = e[1] + a[1,0];
// Fill tables T1[] and T2[] using
// the above given recursive relations
for (i = 1; i < NUM_STATION; ++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]);
}
// Consider exit times and return
// minimum
return min(T1[NUM_STATION-1] + x[0],
T2[NUM_STATION-1] + x[1]);
}
// Driver code
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(carAssembly(a, t, e, x));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// A PHP program to find minimum
// possible time by the car chassis
// to complete
$NUM_LINE = 2;
$NUM_STATION = 4;
// Utility function to find
// minimum of two numbers
function carAssembly($a, $t,
$e, $x)
{
global $NUM_LINE,
$NUM_STATION;
$T1 = array();
$T2 = array();
$i;
$T1[0] = $e[0] + $a[0][0]; // time taken to leave
// first station in line 1
$T2[0] = $e[1] + $a[1][0]; // time taken to leave
// first station in line 2
// Fill tables T1[] and T2[]
// using the above given
// recursive relations
for ($i = 1;
$i < $NUM_STATION; ++$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]);
}
// Consider exit times
// and return minimum
return min($T1[$NUM_STATION - 1] + $x[0],
$T2[$NUM_STATION - 1] + $x[1]);
}
// Driver Code
$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 carAssembly($a, $t, $e, $x);
// This code is contributed
// by anuj_67.
?>
Javascript
<script>
// A JavaScript program to find minimum possible
// time by the car chassis to complete
const NUM_LINE = 2;
const NUM_STATION = 4;
// Utility function to find a minimum of two numbers
function min(a, b)
{
return a < b ? a : b;
}
function carAssembly(a, t, e, x)
{
let T1 = new Array(NUM_STATION);
let T2 = new Array(NUM_STATION);
let i;
// time taken to leave first station in line 1
T1[0] = e[0] + a[0][0];
// time taken to leave first station in line 2
T2[0] = e[1] + a[1][0];
// Fill tables T1[] and T2[] using the
// above given recursive relations
for (i = 1; i < NUM_STATION; ++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]);
}
// Consider exit times and return minimum
return min(T1[NUM_STATION - 1] + x[0],
T2[NUM_STATION - 1] + x[1]);
}
// Driver Code
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(carAssembly(a, t, e, x));
// This code is contributed by Surbhi Tyagi.
</script>
35
La línea en negrita muestra el camino recorrido por el chasis del automóvil para los valores de entrada dados. Solo necesitamos los dos últimos valores en las arrays auxiliares. Entonces, en lugar de crear dos arrays, podemos usar dos variables.
C++
// A space optimized solution for
// assembly line scheduling
#include <bits/stdc++.h>
using namespace std;
int carAssembly(int a[][4],
int t[][4],
int *e, int *x)
{
int first, second, i;
// Time taken to leave first
// station in line 1
first = e[0] + a[0][0];
// Time taken to leave first
// station in line 2
second = e[1] + a[1][0];
// Fill tables T1[] and T2[] using the
// above given recursive relations
for(i = 1; i < 4; ++i)
{
int up = min(first + a[0][i],
second + t[1][i] +
a[0][i]);
int down = min(second + a[1][i],
first + t[0][i] +
a[1][i]);
first = up;
second = down;
}
// Consider exit times and
// return minimum
return min(first + x[0],
second + x[1]);
}
// Driver Code
int main()
{
int a[][4] = { { 4, 5, 3, 2 },
{ 2, 10, 1, 4 } };
int t[][4] = { { 0, 7, 4, 5 },
{ 0, 9, 2, 8 } };
int e[] = { 10, 12 }, x[] = { 18, 7 };
cout << carAssembly(a, t, e, x);
return 0;
}
// This code is contributed by chitrasingla2001
Java
// A space optimized solution for assembly line scheduling
public class AssemblyLine {
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(carAssembleTime(a, t, e, x));
}
public static int carAssembleTime(int a[][], int t[][],
int e[], int x[]) {
int n = a[0].length;
// time taken to leave first station in line 1
int first = e[0] + a[0][0];
// time taken to leave first station in line 2
int second = e[1] + a[1][0];
for (int i = 1; i < n; i++) {
int up = Math.min(first + a[0][i],
second + t[1][i] + a[0][i]),
down = Math.min(second + a[1][i],
first + t[0][i] + a[1][i]);
first = up;
second = down;
}
first += x[0];
second += x[1];
return Math.min(first, second);
}
}
Python3
# A space optimized solution for assembly # line scheduling in Python3 def carAssembleTime(a, t, e, x): n = len(a[0]) # Time taken to leave first station # in line 1 first = e[0] + a[0][0] # Time taken to leave first station # in line 2 second = e[1] + a[1][0] for i in range(1, n): up = min(first + a[0][i], second + t[1][i] + a[0][i]) down = min(second + a[1][i], first + t[0][i] + a[1][i]) first, second = up, down first += x[0] second += x[1] return min(first, second) # Driver Code 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(carAssembleTime(a, t, e, x)) # This code is contributed by Prateek Gupta
C#
// A space optimized solution for
// assembly line scheduling
using System;
class GFG{
static int carAssembleTime(int[,] a, int[,] t,
int[] e, int[] x)
{
int n = a.GetLength(1);
// Time taken to leave first station in line 1
int first = e[0] + a[0, 0];
// Time taken to leave first station in line 2
int second = e[1] + a[1, 0];
for(int i = 1; i < n; i++)
{
int up = Math.Min(first + a[0, i],
second + t[1, i] + a[0, i]),
down = Math.Min(second + a[1, i],
first + t[0, i] + a[1, i]);
first = up;
second = down;
}
first += x[0];
second += x[1];
return Math.Min(first, second);
}
// Driver Code
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 }, x = { 18, 7 };
Console.WriteLine(carAssembleTime(a, t, e, x));
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// A space optimized solution for assembly line scheduling
function carAssembleTime(a , t , e , x) {
var n = a[0].length;
// time taken to leave first station in line 1
var first = e[0] + a[0][0];
// time taken to leave first station in line 2
var second = e[1] + a[1][0];
for (var i = 1; i < n; i++) {
var up = Math.min(first + a[0][i], second + t[1][i] + a[0][i]),
down = Math.min(second + a[1][i], first + t[0][i] + a[1][i]);
first = up;
second = down;
}
first += x[0];
second += x[1];
return Math.min(first, second);
}
var a = [ [ 4, 5, 3, 2 ], [ 2, 10, 1, 4 ] ];
var t = [ [ 0, 7, 4, 5 ], [ 0, 9, 2, 8 ] ];
var e = [ 10, 12 ], x = [ 18, 7 ];
document.write(carAssembleTime(a, t, e, x));
// This code is contributed by gauravrajput1
</script>
35
Ejercicio:
Amplíe el algoritmo anterior para imprimir la ruta recorrida por el chasis del automóvil en la fábrica.
Referencias:
Introducción a los algoritmos, 3ra edición por Clifford Stein, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
Este artículo fue compilado por Aashish Barnwal . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA