Очередь, Задача с тремя конвейерами Опции

[БелАчкА]

Задача такая:

Имеются три конвейера. Конвейеры работают независимо друг от друга. Изначально на первом конвейере располагаются детали N типов, а второй и третий – пусты. Время обработки детали каждого типа с каждого конвейера задается матрицей Time[1..N, 1..3]. После обработки детали с конвейера k она поступает на конвейер k+1. Деталь после третьего конвейера считается изготовленной. Требуется по начальному расположению деталей на первом конвейере определить время, через которое все детали будут изготовлены.

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

[БелАчкА]

По очень простой причине: у меня было 4 часа ночи..

Ну что же Вы так? Конвейеры могли бы и подождать, полноценный сон важнее...

Первый кажется эффективнее - попробуй его реализовать.

Как только полностью разберусь со вторым, попытаюсь это сделать

Lapp, вот за это отдельное огромное спасибо! Правда, очень помогло...

Код

T=  47.000
aaabbccccceeeeehhhhhhhhffffaaagggggg
---aab----cc---ee------hhhhhf-aa----gg
-----aaab---c----e----------hhhhhfffffaaag
--------aabbbcc---eee------------hhhh-f--aagg
----------a--bbbbbc--eeee------------h-f---a-gg

Прогресс на лицо: процентов 90 уже понятно . Но есть еще вопросы:

Здесь используются элементы d[i] массива d... но чем он у нас заполнен? он же пустой... или я туплю

for i:=1 to Nk do begin      //цикл по конвеерам в каждой КТ
      //если время совпадает с КТ, значит на этом конвеере
      //закончилась обработка текущей детали.
      //для всех, кроме последнего, перекладываем деталь в очередь следующего К
      //для последнего просто увеличивает Dd
      if (Abs(T-Tk[i])<e) then if i<Nk then Put(K[i+1],d[i]) else Inc(Dd);
      //если К свободен, взять деталь из очереди (если там есть что-то)
      if (T>=Tk[i]-e) and Get(K[i],d[i]) then begin
        for x:=Round(Tk[i]) to Round(T)-1 do s[i]:=s[i]+'-';       //псевдографика
        //отметить КТ для этого К, как время окончания обработки детали
        Tk[i]:=T+TDK[d[i],i];
        for x:=1 to Round(TDK[d[i],i]) do s[i]:=s[i]+Char(96+d[i]) //псевдографика
      end
    end;

Далее...

  for i:=1 to Nk do if T1<Tk[i] then T1:=Tk[i];
    //найти минимальную КТ, бОльшую текущего времени (т.е. следующую)
    for i:=1 to Nk do if (T<Tk[i]) and (Tk[i]<T1) then T1:=Tk[i];
    //продвигаем текущее время вперед
    T:=T1

(?)Переменной T1 не было присвоено начальное значение. Я так понимаю, что если делать таким образом: T1:=<very_large_value>, то этого не требуется. А если как в проге, то возникает (?).

[Lapp]

Ну что же Вы так? Конвейеры могли бы и подождать, полноценный сон важнее...

Такие уж Мы... программеры - что с Нас взять?..

Как только полностью разберусь со вторым, попытаюсь это сделать

Поторапливайся.. Руки-то чешутся! Еле сдерживаюсь..

Здесь используются элементы d[i] массива d... но чем он у нас заполнен? он же пустой... или я туплю

Вот тут мы действительно используем d. Но мы в эту строчку гарантированно не заходим на первом проходе цикла (поскольку Т=0, а Тk<0).

      //если время совпадает с КТ, значит на этом конвеере
      //закончилась обработка текущей детали.
      //для всех, кроме последнего, перекладываем деталь в очередь следующего К
      //для последнего просто увеличивает Dd
      if (Abs(T-Tk[i])<e) then if i<Nk then Put(K[i+1],d[i]) else Inc(Dd);

А вот тут мы заполняем массив d (обрати внимание, что второй параметр в Get описан как var):

      //если К свободен, взять деталь из очереди (если там есть что-то)
      if (T>=Tk[i]-e) and Get(K[i],d[i]) then begin

И на втором проходе d уже оказывается заполненным (где надо).

(?)Переменной T1 не было присвоено начальное значение. Я так понимаю, что если делать таким образом: T1:=<very_large_value>, то этого не требуется. А если как в проге, то возникает (?).

Не совсем так. Слова "этого не требуется" относятся только к первой строчке из двух. Эта строчка нужна, чтоб положить в Т1 зачение, заведомо не меньшее, чем следующая КТ:

    for i:=1 to Nk do if T1<Tk[i] then T1:=Tk[i];

Теперь смотри: если Т1 было маленьким, то ему присвоится значение. Если оно было большим - то и присваивать не нужно . Так что с любым начальным значением Т1 мы получим желаемый результат. А вот вторая строчка выполняет реальную работу: ищет следующую КТ:

    for i:=1 to Nk do if (T<Tk[i]) and (Tk[i]<T1) then T1:=Tk[i];

Ее выкидывать никак нельзя!..
Я понятно ответил?