Алгоритм джонсона

[Mr.Dmitry]

Здравствуйте, возник такой вопрос. У меня есть задание

Разработать приложение для составления расписания системы конвейерного типа (задача Джонсона).
Входными данными являются количество машин и работ. Результат выполнения программы: расписание в форме таблицы, суммарное время простоев по каждой машине и время завершения всех работ.

На сколько я понимаю задача Джонсона решается для 2 машин. Но если выходными данными является кол-во машин и работ, то это подразумевает что машин может быть больше 2 и соответственно решить задачу при помощи алгоритма Джонсона уже не получиться.
Вопрос: Я что то не правильно понял или задание сформулировано не правильно?

[p51x]

На сколько я понимаю задача Джонсона решается для 2 машин.

Нет, это просто частный удобный для показа случай.

Гуглите обобщенная задача Джонсона.

[Mr.Dmitry]

Сообщение от p51x

Нет, это просто частный удобный для показа случай.

Гуглите обобщенная задача Джонсона.

Занимаюсь гуглением сегодня весь день, результата 0 (

нашел на википедии

А именно

Для решения задачи на двух машинах найден полиномиальный по времени алгоритм Джонсона

В случае более двух машин эта задача является NP-трудной, но разработано множество эвристических полиномиальных по времени приближённых алгоритмов

То есть я к тому что даже википедия говорит что для решения с 3 и более машинами существуют другие эврестические алгоритмы. Если ты знаешь как реализовать алгоритм Джонсона можешь им поделиться? )

[p51x]

Не другие, а просто эвристические полиномиальные по времени приближённые алгоритмы.

Я ж вам дал ключевые слова для гугления. Читайте и выбирайте метод
http://www.mathnet.ru/php/archive.ph...ption_lang=rus
http://www.mathnet.ru/php/archive.ph...ption_lang=rus

[Mr.Dmitry]

Не могли бы вы немного помочь с задачей джонсона для 2 машин?

Сделал такой код

Type TMinus=array[0..3] of integer;
....
function TMain.Minus: TMinus;
var
 min,min1,i:integer;
 machine1,machine2:Tminus;
begin
min:=25;
min1:=25;
//Минимальное число 1 машины
for i := 0 to length(matrix[0])-1 do
 begin
  if (matrix[0,i]>0) and (matrix[0,i]<min) then
  begin
   min:=matrix[0,i];
   Machine1[0]:=matrix[0,i];
   Machine1[1]:=matrix[1,i];
   Machine1[2]:=i;
   Machine1[3]:=0;
  end;
 end;
//Минимальное число 2 машины
for i := 0 to length(matrix[0])-1 do
begin
 if (matrix[1,i]>0) and (matrix[1,i]<min1) then
 begin
  min1:=matrix[1,i];
  Machine2[0]:=matrix[0,i];
  Machine2[1]:=matrix[1,i];
  Machine2[2]:=i;
  Machine2[3]:=1;
 end;
end;
if min<=min1 then
 begin
  Result[0]:=Machine1[0];
  Result[1]:=Machine1[1];
  Result[2]:=Machine1[2];
  Result[3]:=Machine1[3];
 end
else
 begin
  Result[0]:=Machine2[0];
  Result[1]:=Machine2[1];
  Result[2]:=Machine2[2];
  Result[3]:=Machine2[3];
 end;
matrix[0,Result[2]]:=0;
matrix[1,Result[2]]:=0;
Result[2]:=Result[2]+1;
end;
procedure TMain.OptimizationJhonson;
var
 i,j:integer;
 MinusMatrix:TMinus;
 M:Tmatrix;
 Tmax, Cmax:integer;
begin
SetLength(m, 4,length(matrix[0]));
for i := 0 to length(matrix[0])-1 do
begin
 minusMatrix:=minus();
 m[0,i]:=MinusMatrix[0];
 m[1,i]:=MinusMatrix[1];
 m[2,i]:=MinusMatrix[2];
 m[3,i]:=MinusMatrix[3];
end;
for i := 0 to length(m[0])-1 do
begin
if m[3,i]=0 then
 begin
  StringGrid2.Cells[i+1,0]:=inttostr(m[2,i]);
  StringGrid2.Cells[i+1,1]:=inttostr(m[0,i]);
  StringGrid2.Cells[i+1,2]:=inttostr(m[1,i]);
 end;
end;
for i := 0 to length(m[0])-1 do
begin
if m[3,i]=1 then
 begin
  StringGrid2.Cells[StringGrid2.ColCount-i,0]:=inttostr(m[2,i]);
  StringGrid2.Cells[StringGrid2.ColCount-i,1]:=inttostr(m[0,i]);
  StringGrid2.Cells[StringGrid2.ColCount-i,2]:=inttostr(m[1,i]);
 end;
end;
end;

Вроде бы все считается, но иногда в StrinGrid2 попадают пустые ячейки. НЕ понимаю почему (

[Mr.Dmitry]

Блин помогите сделать последний рывок и доделать эти задания. Не могу сделать задачу Джонсона для 2 машин. А именно правильно вывести данные в таблицу и все потом посчитать. и РАСПИСАНИЙ ДЛЯ СИСТЕМ из ПАРАЛЛЕЛЬНЫХ МАШИН

[Виктория3272]

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