Задача такая:
Имеются три конвейера. Конвейеры работают независимо друг от друга. Изначально на первом конвейере располагаются детали N типов, а второй и третий – пусты. Время обработки детали каждого типа с каждого конвейера задается матрицей Time[1..N, 1..3]. После обработки детали с конвейера k она поступает на конвейер k+1. Деталь после третьего конвейера считается изготовленной. Требуется по начальному расположению деталей на первом конвейере определить время, через которое все детали будут изготовлены.
Помогите, пожалуйста, понять хотя бы алгоритм решения: вообще не могу разобраться , где здесь используется очередь и как, собственно, высчитывается само время обработки.
Что такое "очередь", ее структура и тд... это мне все известно У меня проблема в другом: логика не работает Я все равно не понимаю как находить время: неужели просто последовательно сложить??? конвейеры же работают одновременно: на одном одна деталь обрабатывается, на другом в это же время - другая... всю голову уже сломала Мне почему-то кажется, что время должно как-то по хитрому вычисляться.
когда-то делал подобную задачу для двух конвееров. время там я считал так
если
//t=array[1..3(детали), 1..3(конвейеры)] of real(время)
T:=0; //общее время обработки
T:=t[1,1]+max(t[1,2],t[2,1]);
if t[1,2]>t[2,1] then T:=T+max(t[3,1]-(t[1,2]-t[2,1]), t[2,2])
else T:=T+max(t[3,1],t[2,2]);
if t[1,3]>t[2,2] then T:=T+max(t[3,2]-(t[1,3]-t[2,2]),t[2,3])
else T:=T+max(t[3,2],t[2,3]);
T:=T+t[3,3];
{real time multy-line processing model}
{by Lapp for Belachka}
type
tContent=integer;
tpCell=^tCell;
tCell=record
c:tContent;
p:tpCell
end;
tFifo=record
i,o:tpCell
end;
procedure Fifo(var b:tFifo);
begin
b.i:=nil;
b.o:=nil
end;
procedure Put(var b:tFifo; c:tContent);
begin
with b do if i=nil then begin
New(i);
o:=i
end
else begin
New(i^.p);
i:=i^.p;
i^.p:=nil
end;
b.i^.c:=c
end;
function Get(var b:tFifo; var c:tContent):boolean;
var
p:tpCell;
begin
with b do if o=nil then Get:=false
else begin
c:=o^.c;
p:=o^.p;
if o=i then i:=nil;
Dispose(o);
o:=p;
Get:=true
end
end;
const
Mk=10; {максимум конвееров}
Md=100; {максимум деталей}
var
i,j,Nd,Nk,Dd:integer;
T,T1:real; {реальное время}
TDK:array[1..Md,1..Mk]of real; {матрица времен обработки}
Tk:array[1..Mk]of real; {контрольные времена конвееров}
d:array[1..Mk]of integer; {детали в обработке в наст. время}
K:array[1..Mk]of tFifo; {очереди по конвеерам}
f:text;
begin
for i:=1 to Nk do Fifo(K[i]);
Assign(f,'Ford.txt');
Reset(f);
ReadLn(f,Nk);
ReadLn(f,Nd);
for j:=1 to Nd do begin
for i:=1 to Nk do Read(f,TDK[j,i]);
ReadLn(f)
end;
for j:=1 to Nd do begin
Read(f,i);
Put(K[1],i)
end;
Close(f);
T:=0;
for i:=1 to Nk do Tk[i]:=0;
Dd:=0;
repeat
for i:=1 to Nk do begin
if (T=Tk[i]) and (T>0) then if i<Nk then Put(K[i+1],d[i]) else Inc(Dd);
if (T>=Tk[i]) and Get(K[i],d[i]) then Tk[i]:=T+TDK[d[i],i];
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
until Dd=Nd;
WriteLn(T)
end.
Lapp, большое спасибо!
Вопросы, конечно же, есть...
begin
for i:=1 to Nk do Fifo(K[i]); // почему здесь используется переменная Nk, если ее значение еще не считано из файла?
Assign(f,'Ford.txt');
Reset(f);
ReadLn(f,Nk);
ReadLn(f,Nd);
for j:=1 to Nd do begin
for i:=1 to Nk do Read(f,TDK[j,i]);
ReadLn(f)
end;
for j:=1 to Nd do begin
Read(f,i);
Put(K[1],i)
end;
Close(f);
T:=0;
for i:=1 to Nk do Tk[i]:=0;
Dd:=0; //Dd - это количество уже обработанных деталей, так?
repeat
for i:=1 to Nk do begin
if (T=Tk[i]) and (T>0) then if i<Nk then Put(K[i+1],d[i]) else Inc(Dd);
if (T>=Tk[i]) and Get(K[i],d[i]) then Tk[i]:=T+TDK[d[i],i];
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
until Dd=Nd;
WriteLn(T)
end.
begin
for i:=1 to Nk do Fifo(K[i]); // почему здесь используется переменная Nk, если ее значение еще не считано из файла?
БелАчкА, чтобы лучше разобраться, просто представь себя тем человеком, который следит за конвеерами (я прошу прощения за орфографию, правильно писать "конвейер", но у мя рука не поворачивается такое уродство изображать..) и перекладывает детали с одного К на другой, когда они готовы. Что он делает? Он кладет деталь на конвеер, смотрит в табличку, сколько времени она будет обрабатываться и отмечает это время у себя в блокноте (контрольная точка, КТ). И так с каждым конвеером. Потом идет спать, а будильник заводит на ближайшую КТ.
Дальше зависит от реализации. Если он вместе с КТ отметил и номер конвеера, то он идет прямо к нужному конвееру. Если же он отметил просто время, то он проверяет все конвееры по очереди, начиная с первого, выискивая тот, у которого КТ совпадает с текущим временем. Находит, перекладывает деталь на следующий конвеер (или кладет на склад готовых деталей) и смотрит, есть ди детали в очереди для этого конвеера. Если есть, то загружает его следующей деталью и передвигает его КТ. Так он обходит все К в этот момент, а потом снова идет спать до следующей ТК. Я предпочел второй способ. Первый кажется эффективнее - попробуй его реализовать.
Вот и все . Непыльная работенка. А ты у него ее отбираешь, заменяешь машиной...
Я добавил наглядный вывод всего процесса с использованием псевдографики. Как только его увидишь, все станет понятно . Но при его использовании нужно задавать времена только целыми (я имею в виду, без дробей). Это в принципе не запрещается алгоритмом, но псевдографика не сдюжит..
Еще одно замечание. Эта программа неправильно обрабатывает ситуацию, когда время обработки какой-то детали на одном из конвееров нулевое. Но тут нужно уточнить услови - можно ли сразу перепрыгивать через такой конвеер на следующий (это приведет к изменению порядка следования деталей, что, как мне кажется, не страшно) или нужно все-таки выстоять очередь на нем.
Выкладываю вторую версию .
1. Исправлена ошибка, замеченная тобой выше.
2. Выкинута переменная Work (она не нужна, если начальные КТ задать отрицательными).
3. Добавлены комментарии.
4. Добавлена псевдографика, которая наглядно представляет процесс.
Вот, на всякий случай, еще один входной файл, побольше:
//real time multy-line processing model
//by Lapp for Belachka
//Version 2
type
tContent=integer;
tpCell=^tCell;
tCell=record
c:tContent;
p:tpCell
end;
tFifo=record
i,o:tpCell
end;
procedure Fifo(var b:tFifo);
begin
b.i:=nil;
b.o:=nil
end;
procedure Put(var b:tFifo; c:tContent);
begin
with b do if i=nil then begin
New(i);
o:=i
end
else begin
New(i^.p);
i:=i^.p;
i^.p:=nil
end;
b.i^.c:=c
end;
function Get(var b:tFifo; var c:tContent):boolean;
var
p:tpCell;
begin
with b do if o=nil then Get:=false
else begin
c:=o^.c;
p:=o^.p;
if o=i then i:=nil;
Dispose(o);
o:=p;
Get:=true
end
end;
const
Mk=10; //максимум конвееров (К)
Md=28; //максимум деталей
e=1e-5; //погрешность сравнения
var
i,j,Nd,Nk,Dd:integer;
T,T1:real; //реальное время
TDK:array[1..Md,1..Mk]of real; //матрица времен обработки
Tk:array[1..Mk]of real; //контрольные точки (КТ) всех К
d:array[1..Mk]of integer; //детали в обработке в наст. время
K:array[1..Mk]of tFifo; //очереди ожидания К
f:text;
var //переменные для псевдографики
x:integer; //можно убрать их, а потом убрать все строчки,
s:array[1..Mk]of string; //где ругается компилятор
begin
Assign(f,'Ford.txt');
Reset(f);
ReadLn(f,Nk);
for i:=1 to Nk do Fifo(K[i]);
ReadLn(f,Nd);
for j:=1 to Nd do begin
for i:=1 to Nk do Read(f,TDK[j,i]);
ReadLn(f)
end;
for j:=1 to Nd do begin
Read(f,i);
Put(K[1],i)
end;
Close(f);
T:=0; //время начинается с нуля
for i:=1 to Nk do Tk[i]:=-0.1; //все конвееры к началу уже пустые некоторое время
Dd:=0; //обнуляем конечный результат
repeat //вперед по времени по КТ
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;
//найти максимальную КТ
//это можно заменить просто на T1:=<very_large_value>
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
until Dd=Nd; //до тех пор, когда будут обработаны все детали
WriteLn('T=',T:8:3); //вывод полного времени
for x:=1 to Nk do WriteLn(s[x]); //вывод псевдографики
ReadLn
end.
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
//если время совпадает с КТ, значит на этом конвеере
//закончилась обработка текущей детали.
//для всех, кроме последнего, перекладываем деталь в очередь следующего К
//для последнего просто увеличивает Dd
if (Abs(T-Tk[i])<e) then if i<Nk then Put(K[i+1],d[i]) else Inc(Dd);
//если К свободен, взять деталь из очереди (если там есть что-то)И на втором проходе d уже оказывается заполненным (где надо).
if (T>=Tk[i]-e) and Get(K[i],d[i]) then begin
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];Ее выкидывать никак нельзя!..
Про d поняла, про Т1 нет...
Вот место, где впервые встречается Т1:
for i:=1 to Nk do if T1<Tk[i] then T1:=Tk[i];
for i:=1 to Nk do if T1<Tk[i] then T1:=Tk[i];
Что-то вы перемудрили мне кажется ...
проверил на 2-х примерах, предложенных тут lapp'ом, результат совпадает с результатом его программы
const
n = 4;
type
TWorkTimes = array [1..n, 1..3] of Integer;
function Max(const a, b: Integer): Integer;
begin
if a > b then Max := a else Max := b;
end;
function MaxTime(const wt: TWorkTimes; const i, j, k: Integer): Integer;
var
a, b, c: Integer;
begin
if i = 0 then a := 0 else a := wt[i, 1];
if j = 0 then b := 0 else b := wt[j, 2];
if k = 0 then c := 0 else c := wt[k, 3];
MaxTime := Max(Max(a, b), c);
end;
procedure NextTact(var i, j, k: Integer);
begin
k := j;
j := i;
if (i < n) and (i <> 0) then inc(i)
else i := 0;
end;
function GetTotalTime(wt: TWorkTimes; i, j, k: integer): LongInt;
var
time: LongInt;
begin
if (i = 0) and (j = 0) and (k = 0) then
GetTotalTime := 0
else begin
time := MaxTime(wt, i, j, k);
NextTact(i, j, k);
GetTotalTime := time + GetTotalTime(wt, i, j, k);
end;
end;
var
WT: TWorkTimes = (
(1, 2, 3),
(2, 1, 1),
(5, 2, 1),
(2, 1, 5)
);
begin
writeln(GetTotalTime(WT, 1, 0, 0));
end.
klem4, еще раз прошу тебя ответить на вопрос (извиняюсь за цитирование самого себя):
а это у меня не предусмотрено, то есть всегда поток такой: 1, 2, 3, 4, ..., N
можно сделать в принципе ...
Все, я окончательно растерялась... не знаю, куда смотреть
klem4, спасибо за новую версию решения, хоть она еще не адаптирована к задаче.
БелАчкА, как дела? Все понятно уже?