Цель работы: освоить методы решения задач теории расписаний (задачи о шлюзе и о двух станках).
Задание 1. Решить задачу о шлюзе: пять судов, выстроившихся в очередь к шлюзу в порядке их прибытия. Определить порядок их шлюзование. Данные о времени шлюзования и ущерб от простоя представлены в таблице.
№ судна | 1 | 2 | 3 | 4 | 5 |
Время шлюзования | 45 | 36 | 28 | 24 | 72 |
Ущерб от простоя | 5 | 12 | 7 | 4 | 3 |
Решение.
Создаем таблицу
Выделяем блок B1:F4. Вкладка Данные кнопка Сортировка
Замечание. Если появилась “сортировка по столбцам” нажать кнопку параметры и выбрать “ столбцы диапазона”.
Задание 2.Составьте программу на Паскале для решения задачи о шлюзе и протестируйте ее на данных и задания 1.
Задание 3. Вычислите календарное время обработки деталей на двух станках. Исходные данные представлены в таблице (см ниже). Используйте программу на Паскале (алгоритм Джонсона), приведенную ниже.
Program Jonson;
Var T, P: array [1..5, 1..3] of real; min: real; i, j, ki, kj, m, L, f: integer;
Begin
//ввод массива исходных данных по строкам
|
|
Writeln('введите исходные данные по строчно');
for i:=1 to 5 do
begin
for j:=1 to 3 Do Read(T[i,j]);
Readln;
end;
m:=5;
//Задаем начальные значения для текущей позиции начала и конца списка обработки
f:=1; L:=m;
while m>0 do
begin
min:=T[1,2];
for i:=1 to m do
for j:=2 to 3 do
//поиск минимального времени обработки деталей
if T[i,j]<=min then
begin min:=T[i,j]; ki:=i; kj:=j; end;
//Перестановка детали в конец (если kj=3)
//или в начало списка обработки деталей
if kj=3 then
begin
for j:=1 to 3 do P[L,j]:=T[ki,j];
L:=L-1;
end
else
begin
for j:=1 to 3 do P[f,j]:=T[ki,j];
f:=f+1;
end;
//исключение ki-й строки в массиве Т из дальнейшего рассмотрения
if ki<m then
begin
for i:=ki to m-1 do
for j:=1 to 3 do
T[i,j]:=T[i+1,j]
end;
m:=m-1;
end;
//Вывод результата
Writeln('Первый столбец матрицы содержит оптимальный порядок обработки деталей');
for i:=1 to 5 do
begin
for j:=1 to 3 do Write(P[i,j],' ');
Writeln
End
end.
№ детали | Время обработки детали на первом станке | Время обработки детали на втором станке |
1 | 12 | 5 |
2 | 9 | 8 |
3 | 7 | 6 |
4 | 9 | 8 |
5 | 2 | 10 |