Рубрики

Планирование сборочной линии | DP-34

Автомобильный завод имеет две сборочные линии, каждая из которых имеет n станций. Станция обозначается как S i, j, где i равно 1 или 2, и обозначает сборочную линию, на которой находится станция, а j обозначает номер станции. Время, затрачиваемое на одну станцию, обозначается как a i, j . Каждая станция посвящена какой-то работе, такой как подгонка двигателя, подгонка кузова, покраска и так далее. Таким образом, автомобильное шасси должно пройти через каждую из n станций по порядку, прежде чем покинуть завод. Параллельные станции двух сборочных линий выполняют одну и ту же задачу. После того, как он пройдет через станцию S i, j , он продолжит работу до станции S i, j + 1, если не решит перейти на другую линию. Продолжение по той же линии не требует дополнительных затрат, но переход от линии i на станции j — 1 к станции j на другой линии требует времени t i, j . Каждая сборочная линия занимает время входа e i и время выхода x i, которые могут различаться для двух линий. Дайте алгоритм для расчета минимального времени, которое потребуется для сборки шасси автомобиля.

На приведенном ниже рисунке проблема представлена в четкой картине:

Следующая информация может быть извлечена из постановки задачи, чтобы упростить ее:

  • Две сборочные линии, 1 и 2, каждая со станциями от 1 до n.
  • Шасси автомобиля должно проходить через все станции от 1 до n по порядку (на любой из двух сборочных линий). то есть он не может прыгнуть со станции i на станцию j, если они не находятся на расстоянии одного перемещения.
  • Автомобильное шасси может перемещаться на одну станцию вперед на одной линии или на одну станцию по диагонали на другой линии. Это требует дополнительных затрат ti, j для перехода на станцию j из линии i. Никаких затрат за движение по одной и той же линии не взимается.
  • Время, проведенное на станции j на линии i, равно a i, j .
  • S i, j представляет станцию j на линии i.

Разбиение проблемы на более мелкие подзадачи:
Мы можем легко найти i-й факториал, если известен (i-1) -й факториал. Можем ли мы применить подобный фундамент здесь?
Если известно минимальное время, необходимое шасси для выхода из станции S i, j-1 , минимальное время, необходимое для выхода из станции S i, j, может быть быстро рассчитано путем объединения a i, j и t i, j .

T1 (j) указывает минимальное время, которое требуется шасси автомобиля, чтобы покинуть станцию j на конвейере 1.

T2 (j) указывает минимальное время, необходимое шасси автомобиля, чтобы покинуть станцию j на сборочной линии 2.

Базовые случаи:
Время входа в систему e i появляется только тогда, когда автомобильное шасси поступает на автомобильный завод.

Время, необходимое для выхода из первой станции в строке 1, определяется следующим образом:
T1 (1) = время входа в линию 1 + время, проведенное на станции S 1,1
T1 (1) = e 1 + a 1,1
Точно так же время, необходимое для того, чтобы покинуть первую станцию в строке 2, определяется как:
T2 (1) = e 2 + a 2,1

Рекурсивные отношения:
Если мы посмотрим на постановку задачи, она быстро сводится к следующим наблюдениям:
Шасси автомобиля на станции S 1, j может прибыть либо со станции S 1, j-1, либо со станции S 2, j-1 .

Случай № 1: его предыдущая станция — S 1, j-1
Минимальное время для выхода из станции S 1, j определяется как:
T1 (j) = минимальное время, необходимое для выхода из станции S 1, j-1 + время, проведенное на станции S 1, j
T1 (j) = T1 (j-1) + a 1, j

Случай № 2: предыдущая станция S 2, j-1
Минимальное время для выхода из станции S1, j определяется как:
T1 (j) = минимальное время, необходимое для выхода из станции S 2, j-1 + дополнительные расходы, связанные с заменой линии сборки + время, проведенное на станции S 1, j
T1 (j) = T2 (j-1) + t 2, j + a 1, j

Минимальное время T1 (j) определяется минимумом двух, полученных в случаях № 1 и № 2.
T1 (j) = min ((T1 (j-1) + a 1, j ), (T2 (j-1) + t 2, j + a 1, j ))
Аналогичным образом минимальное время для достижения станции S2, j определяется как:
T2 (j) = min ((T2 (j-1) + a 2, j ), (T1 (j-1) + t 1, j + a 2, j ))

Общее минимальное время, необходимое для того, чтобы шасси автомобиля вышло с завода, определяется как:
Tmin = min (Время, необходимое для выхода из станции S i, n + Время, необходимое для выхода с автомобильного завода)
Tmin = min (T1 (n) + x 1 , T2 (n) + x 2 )

Почему динамическое программирование?
Вышеуказанная рекурсия демонстрирует перекрывающиеся подзадачи. Добраться до станции S 1, j можно двумя способами:

  1. Со станции S 1, J-1
  2. Со станции S 2, J-1

Таким образом, чтобы найти минимальное время для выхода из станции S 1, j, необходимо рассчитать минимальное время для выхода из двух предыдущих станций (как объяснено в приведенной выше рекурсии).
Аналогично, есть два способа добраться до станции S 2, j :

  1. Со станции S 2, J-1
  2. Со станции S 1, J-1

Обратите внимание, что минимальное время для выхода из станций S 1, j-1 и S 2, j-1 уже рассчитано.

Итак, нам нужны две таблицы для хранения частичных результатов, рассчитанных для каждой станции в сборочной линии. Стол будет заполнен снизу вверх.

Замечания:
В этом посте слово «отпуск» использовалось вместо слова «охват», чтобы избежать путаницы. Поскольку автомобильное шасси должно проводить фиксированное время на каждой станции, слово «оставить» подходит лучше.

Реализация:

C ++

// Программа на C ++ для поиска минимально возможного
// время на машине шасси, чтобы завершить
#include <bits/stdc++.h>

using namespace std;

#define NUM_LINE 2 
#define NUM_STATION 4 

  
// Утилита для поиска минимум двух чисел

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; 

  

    // время, необходимое для того, чтобы покинуть первую станцию в линии 1

    T1[0] = e[0] + a[0][0]; 

      

    // время, необходимое для выхода из первой станции на линии 2

    T2[0] = e[1] + a[1][0]; 

  

    // Заполняем таблицы T1 [] и T2 [], используя

    // выше заданных рекурсивных отношений

    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]); 

    

  

    // Рассмотрим время выхода и минимум возврата

    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}; 

  

    cout << carAssembly(a, t, e, x); 

  

    return 0; 

  
// Это код, предоставленный rathbhupendra

С

// Программа переменного тока, чтобы найти минимально возможное время для завершения шасси автомобиля
#include <stdio.h>
#define NUM_LINE 2
#define NUM_STATION 4

  
// Утилита для поиска минимум двух чисел

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]; // время, необходимое для того, чтобы покинуть первую станцию в линии 1

    T2[0] = e[1] + a[1][0]; // время, необходимое для выхода из первой станции на линии 2

  

    // Заполняем таблицы T1 [] и T2 [], используя приведенные выше рекурсивные отношения

    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]);

    }

  

    // Рассмотрим время выхода и минимум возврата

    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;

}

Выход:

35

Джава

// Java-программа для поиска минимально возможного
// время на машине шасси, чтобы завершить

import java.io.*;

  

class GFG 

{

    static int NUM_LINE = 2;

    static int NUM_STATION = 4;

      

    // Утилита для поиска минимум двух чисел

    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;

      

        // время, необходимое для того, чтобы покинуть первую станцию в линии 1

        T1[0] = e[0] + a[0][0]; 

          

        // время, необходимое для выхода из первой станции на линии 2

        T2[0] = e[1] + a[1][0];

      

        // Заполняем таблицы T1 [] и T2 [] используя

        // приведенные выше рекурсивные отношения

        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]);

        }

      

        // Рассмотрим время выхода и минимум возврата

        return min(T1[NUM_STATION-1] + x[0], 

                    T2[NUM_STATION-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(carAssembly(a, t, e, x));    

      

    }

}
// Этот код предоставлен vt_m

python3

# Python программа для поиска минимально возможного
# время на машине шасси, чтобы завершить

  

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] # время, необходимое, чтобы уйти

                           # первая станция в линии 1

    T2[0] = e[1] + a[1][0] # время, необходимое, чтобы уйти

                           # первая станция в строке 2

  

    # Заполните таблицы T1 [] и T2 [], используя

    # выше заданных рекурсивных отношений

    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] )

  

    # учитывать время выхода и минимум возврата

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

  
# Этот код предоставлен Soumen Ghosh

C #

// AC # программа для поиска минимально возможного
// время на машине шасси, чтобы завершить

using System;

  

class GFG {

      

    static int NUM_STATION = 4;

      

    // Сервисная функция для поиска минимума

    // из двух чисел

    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;

      

        // время, необходимое для выхода из первой станции

        // в строке 1

        T1[0] = e[0] + a[0,0]; 

          

        // время, необходимое для выхода из первой станции

        // в строке 2

        T2[0] = e[1] + a[1,0];

      

        // Заполняем таблицы T1 [] и T2 [] используя

        // приведенные выше рекурсивные отношения

        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]);

        }

      

        // Учитываем времена выхода и возвращаемся

        // минимум

        return min(T1[NUM_STATION-1] + x[0], 

                    T2[NUM_STATION-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(carAssembly(a, t, e, x)); 

      

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// PHP программа для поиска минимума
// возможное время на машине шасси
// завершить

  

$NUM_LINE = 2;

$NUM_STATION = 4;

  
// Функция поиска
// минимум двух чисел

function carAssembly($a, $t

                     $e, $x)

{

    global $NUM_LINE,

           $NUM_STATION;

    $T1 = array(); 

    $T2 = array();

    $i;

  

    $T1[0] = $e[0] + $a[0][0]; // время ушло

                               // первая станция в строке 1

    $T2[0] = $e[1] + $a[1][0]; // время ушло

                               // первая станция в строке 2

  

    // Заполняем таблицы T1 [] и T2 []

    // используя приведенное выше

    // рекурсивные отношения

    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]);

    }

  

    // Рассмотрим время выхода

    // и вернуть минимум

    return min($T1[$NUM_STATION - 1] + $x[0], 

               $T2[$NUM_STATION - 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 carAssembly($a, $t, $e, $x);

  
// Этот код добавлен
// от anuj_67.
?>


Выход:

35


Жирная линия показывает путь, пройденный шасси автомобиля для заданных входных значений.

Упражнение:
Расширьте приведенный выше алгоритм для печати пути, пройденного автомобильным шасси на заводе.

Ссылки:
Введение в алгоритмы 3-е издание Клиффорд Стейн, Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест

Эта статья составлена Aashish Barnwal . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Планирование сборочной линии | DP-34

0.00 (0%) 0 votes