Задача Джонсона
Детермінована задача впорядкування. Час обробки виробів на двох машинах. Побудова математичної моделі та її дослідження. Основні етапи побудови алгоритму. Розрахунок процесу оптимальної обробки виробів на двох машинах. Текст програми, тестові приклади.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | контрольная работа |
| Язык | украинский |
| Дата добавления | 09.05.2014 |
| Размер файла | 119,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
1
Задача Джонсона
1. Детермінована задача впорядкування
Постановка задачі і вибір критерію оптимізації. Нехай маємо декілька виробів, кожний із яких повинен бути оброблений на двох машинах. Припустимо, що відомий час обробки і послідовність обробки кожного виробу на кожній машині (табл. 1). Необхідно вибрати таку послідовність обробки виробів, при якій сумарний час обробки виробів буде мінімальним (або сумарний час очікування обробки виробів на машині).
Виявлення основних особливостей, взаємозв'язку і кількісних закономірностей.
Перерахуємо основні обмеження задачі:
Таблиця 1 - Час обробки виробів на двох машинах
|
Номер виробу |
j |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
Час обробки на першій машині |
t1j |
6 |
4 |
6 |
5 |
7 |
4 |
|
|
Час обробки на другій машині |
t2j |
5 |
2 |
3 |
6 |
6 |
7 |
час переходу виробу від однієї машини до другої незначний, і ним можна знехтувати;
кожний виріб обробляється в певному технологічному порядку;
кожне обслуговування повинно бути завершене раніше, ніж розпочнеться наступне.
Позначимо t1j - час обробки j-го виробу на першій машині, а t2j - час обробки j-го виробу на другій машині.
Зобразимо процес обробки виробу на двох машинах на графіку (Рис.1)
задача джонсон алгоритм програма
Час обробки
на машині 1
Час обробки
на машині 2
Час простою
машини 2
Рисунок 1 - Процес обробки виробів на обох машинах
На малюнку Т - повний час, котрий пройде від початку обробки першого виробу на першій машині до кінця обробки останнього виробу на другій машині.
Побудова математичної моделі. Нехай tпj - час простою другої машини між кінцем виконання роботи по обробці (j - 1) - го виробу на другій машині та початком обробки j-го виробу на тій же самій машині. Тоді сумарний час обробки виробів складає
,
а оскільки сума відома, то належить мінімізувати (у нашому випадку ).
2. Дослідження математичної моделі
Відомий дуже простий алгоритм для знаходження оптимальної послідовності порядку обслуговування m вимог на двох пунктах обслуговування (алгоритм Джонсона). При цьому кожна із вимог має пройти спочатку обслуговування на першому пункті, а потім на другому. Тривалість обслуговування вимог різноманітні. Якщо використати метод прямого перебору, то при наявності m вимог (виробів) та двох пунктів обслуговування (машин) і за умови, що всі види вимог обробляються в однаковому порядку, існує m! можливих варіантів (послідовностей). Для нашого прикладу існує 6! =720 варіантів.
Алгоритм включає такі основні етапи:
Пошук найменшого елемента. Шукаємо в табл. 2 найменший елемент (рівний 2 відноситься до другої машини) і відмічаємо крапкою;
Таблиця 2
|
Номер виробу |
j |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
Час обробки на першій машині |
t1j |
6 |
4 |
6 |
5 |
7 |
4 |
|
|
Час обробки на другій машині |
t2j |
5* |
2* |
3* |
6 |
6 |
7 |
|
|
Номер циклу |
4 |
1 |
2 |
4 |
5 |
3 |
Перестановка виробів. Визначається місцезнаходження елемента. Якщо цей елемент належить до першої машини, то стовпець із зіркою поставити на перше місце, якщо до другої, то поставити на останнє місце календарного плану (табл. 3). При наявності рівних мінімальних елементів в обох рядках виріб із мінімальним часом обробки на першій машині ставиться на перше місце, а на другій машині - на останнє. Якщо ж однакові мінімальні елементи виявляться в першому (другому) рядку, то на перше (останнє) місце ставиться виріб, якому відповідає менший елемент другого (першого) рядка.
Час обробки
на машині 1
Час обробки
на машині 2
Час простою
машини 2
Рисунок 2 - Процес оптимальної обробки виробів на двох машинах
3) Викреслювання з таблиці стовпця, відміченого зіркою, та повернення до п.1 і так далі, поки не буде вичерпаний список усіх виробів. У результаті отримаємо оптимальну послідовність обробки виробів на двох машинах (табл. 3). Остання колонка табл. 2 (номер циклу) показує послідовність викреслювання стовпців для даного прикладу.
Після визначення оптимального порядку обробки виробів на машинах (табл. 3) за графіком визначається час простою і роботи на другій машині, який є мінімальним з усіх можливих (Рис. 2).
У деяких окремих випадках алгоритм Джонсона застосовується і для розв'язання задач упорядкування, що потребують трьох етапів обслуговування. Це можливо зробити, коли виконується одна із таких систем нерівностей:
мінімальний час обробки виробу на першій машині більше або дорівнює максимальному часові обробки виробу на другій машині:
;
j=1, …, m j=1, …, m
мінімальний час обробки виробу на третій машині більший або дорівнює максимальному часові обробки на другій машині:
;
j=1, …, m j=1, …, m.
Після цього складається нова таблиця для суми (t1j+t2j) замість t1j або (t2j+t3j) замість t2j, і до неї застосовується алгоритм Джонсона.
Клас задач, до яких може бути застосований алгоритм Джонсона, обмежений. Рішення ж методом прямого перебору всіх можливих варіантів уже при десяти виробах потребує розгляду більше ніж 3 млн. варіантів. У деяких задачах упорядкування для одержання рішення можна використовувати методи лінійного і динамічного програмування.
Нижче наведені програма мовою Turbo Pascal 7.0 та результати розрахунку оптимального порядку обслуговування вимог із використанням алгоритму Джонсона.
3. Текст програми
{Алгоритм оптимальной обработки изделий на двух машинах (алгоритм Джонсона)
Алгоритм выбирает такой порядок обработки изделий, при котором суммарное время
обработки изделий будет минимальным}
program Algorithm_of_Johnson;
ses crt;
type vec=array [1.50] of integer;
matr=array [1.50,1.2] of integer;
var t,s: matr;
tHP1,tHP2,tKP1,tKP2,lo: vec;
i,j, ii,jj,k,l,smin,n,th1,th2: integer;
{inf - файл исходных данных;
outf - файл результатов}
inf,outf: text;
sw: string;
label 1;
BEGIN {Начало программы}
clrscr;
assign (inf,'a: \test3_in. pas');
reset (inf);
{Ввод количества изделий}
readln (inf,sw);
readln (inf,n);
assign (outf,'a: \rez3. pas');
rewrite (outf);
writeln (outf,' ИСХОДНЫЕ ДАННЫЕ: ');
writeln (outf);
writeln (outf, 'Количество изделий, подлежащих обработке: ',n);
readln (inf,sw);
writeln (outf,'‚Время обработки изделий соответственно на первой и второй машинах');
for i: =1 to n do begin
for j: =1 to 2 do begin
{Ввод времени обработки каждого изделия на 1-ой и 2-ой машинах}
read (inf,t [i,j]);
write (outf,' t (', i,',',j,') =',t [i,j]);
end;
readln (inf); writeln (outf);
end;
close (inf);
writeln (outf,' РЕЗУЛЬТАТЫ ВЫЧИСЛЕНИЙ: ');
writeln (outf);
for i: =1 to n do
for j: =1 to 2 do
s [i,j]: =t [i,j];
k: =1;
l: =1;
1: if t [1,1] >t [1,2] then
begin smin: =t [1,2]; ii: =1; jj: =2 end
else begin smin: =t [1,1]; ii: =1; jj: =1 end;
for i: =2 to n do
for j: =1 to 2 do begin
if t [i,j] <smin then
begin smin: =t [i,j]; ii: =i; jj: =j end;
end;
{lo [i] - порядковый номер цикла обработки i-го изделия}
if jj=1 then begin lo [k]: =ii; k: =k+1 end
else begin lo [n-l+1]: =ii; l: =l+1 end;
t [ii,1]: =10000; t [ii,2]: =10000;
if (l+k) <> (n+2) then goto 1;
{tHP1 [i] - время начала обработки i-го изделия на 1-ой машине;
tHP2 [i] - время начала обработки i-го изделия на 2-ой машине;
tKP1 [i] - время окончания обработки i-го изделия на 1-ой машине;
tKP2 [i] - время окончания обработки i-го изделия на 2-ой машине; }
tHP1 [1]: =0;
tKP1 [1]: =s [lo [1],1];
tHP2 [1]: =tKP1 [1];
tKP2 [1]: =tHP2 [1] +s [lo [1],2];
{th2 - время простоя 2-ой машины}
th2: =tHP2 [1];
for k: =2 to n do begin
tHP1 [k]: =tKP1 [k-1];
tKP1 [k]: =tHP1 [k] +s [lo [k],1];
if tKP2 [k-1] >tKP1 [k] then tHP2 [k]: =tKP2 [k-1]
else begin
tHP2 [k]: =tKP1 [k];
th2: =th2+tKP1 [k] - tKP2 [k-1];
end;
tKP2 [k]: =tHP2 [k] +s [lo [k],2];
end;
th1: =tKP2 [n] - tKP1 [n];
writeln (outf, 'Оптимальный порядок обслуживания требований: ');
for i: =1 to n do
write (outf,' ',lo [i]);
writeln (outf);
writeln (outf, 'Общее время обслуживания требований: ',tKP2 [n]);
writeln (outf,'Время простоя машины 2: ',th2);
close (outf);
writeln ('Конец вычислений');
readln;
end. {Конец вычислений}
4. Тестові приклади
Тест № 1
Количество изделий, подлежащих обработке
8
Время обработки изделий соответственно на первой и второй машинах
6 2
1 2
4 5
10 6
1 3
2 9
7 5
4 1
Результат № 1
ИСХОДНЫЕ ДАННЫЕ:
Количество изделий, подлежащих обработке: 8
Время обработки изделий соответственно на первой и второй машинах
t (1,1) =6 t (1,2) =2
t (2,1) =1 t (2,2) =2
t (3,1) =4 t (3,2) =5
t (4,1) =10 t (4,2) =6
t (5,1) =1 t (5,2) =3
t (6,1) =2 t (6,2) =9
t (7,1) =7 t (7,2) =5
t (8,1) =4 t (8,2) =1
РЕЗУЛЬТАТЫ ВЫЧИСЛЕНИЙ:
Оптимальный порядок обслуживания требований:
2 5 6 3 4 7 1 8
Общее время обслуживания требований: 36
Время простоя машины 2: 3
Тест № 2
Количество изделий, подлежащих обработке 12
Время обработки изделий соответственно на первой и второй машинах
1 2
3 7
4 14
10 11
9 3
12 9
7 15
4 22
1 3
12 8
9 1
7 4
Результат № 2
ИСХОДНЫЕ ДАННЫЕ:
Количество изделий, подлежащих обработке: 12
Время обработки изделий соответственно на первой и второй машинах
t (1,1) =1 t (1,2) =2
t (2,1) =3 t (2,2) =7
t (3,1) =4 t (3,2) =14
t (4,1) =10 t (4,2) =11
t (5,1) =9 t (5,2) =3
t (6,1) =12 t (6,2) =9
t (7,1) =7 t (7,2) =15
t (8,1) =4 t (8,2) =22
t (9,1) =1 t (9,2) =3
t (10,1) =12 t (10,2) =8
t (11,1) =9 t (11,2) =1
t (12,1) =7 t (12,2) =4
РЕЗУЛЬТАТЫ ВЫЧИСЛЕНИЙ:
Оптимальный порядок обслуживания требований:
1 9 2 3 8 7 4 6 10 12 5 11
Общее время обслуживания требований: 100
Время простоя машины 2: 1
Тест № 3
Количество изделий, подлежащих обработке
6
Время обработки изделий соответственно на первой и второй машинах
6 5
4 2
6 3
5 6
7 6
4 7
Результат № 3
ИСХОДНЫЕ ДАННЫЕ:
Количество изделий, подлежащих обработке: 6
Время обработки изделий соответственно на первой и второй машинах
t (1,1) =6 t (1,2) =5
t (2,1) =4 t (2,2) =2
t (3,1) =6 t (3,2) =3
t (4,1) =5 t (4,2) =6
t (5,1) =7 t (5,2) =6
t (6,1) =4 t (6,2) =7
РЕЗУЛЬТАТЫ ВЫЧИСЛЕНИЙ:
Оптимальный порядок обслуживания требований:
6 4 5 1 3 2
Общее время обслуживания требований: 34
Время простоя машины 2: 5
Размещено на Allbest.ru
...Подобные документы
Формалізація моделі виробничої діяльності підприємства. Рішення за допомогою Excel. Алгоритм розрахунку моделі. Побудова моделі рішення за допомогою "С++". Знаходження оптимальної програми функціонування підприємства. Розробка коду програми.
контрольная работа [720,1 K], добавлен 12.06.2015Розробка фільтру для обробки цифрових сигналів. Блок обробки реалізується на цифрових мікросхемах середньої ступені інтеграції. Аналіз вхідного сигналу, ідеального сигналу та шуму. Обґрунтування вибору фільтрів та алгоритму обробки вхідного сигналу.
курсовая работа [504,4 K], добавлен 18.09.2010Проектування і програмування обробки деталей на верстатах з числовим програмним управлінням. Проектування технологічної оперції обробки заготовки: вибір інструменту, ескізи наладок. Керуюча програма обробки деталей "кришка" та "вал". Верифікація програми.
курсовая работа [1,7 M], добавлен 29.11.2011Концепція суперскалярної організації процесорів. Ознаки повноцінного суперскалярного процесора в моделі Pentium Pro. Етапи протікання процесу виконання програми в Pentium II. Вузли добування і розшифровки команд. Конвеєр обробки команд розгалуження.
реферат [59,8 K], добавлен 08.09.2011Розробка математичної моделі, методів обробки, визначення діагностичних ознак та методу імітаційного моделювання кардіоінтервалограми для моніторингу адаптивно-регулятивних можливостей організму людини з захворюваннями серця при фізичних навантаженнях.
автореферат [74,9 K], добавлен 29.03.2009Аналіз основних операцій спецпроцесора обробки криптографічної інформації, його синтез у модулярній системі числення та дослідження математичної моделі надійності. Виведення аналітичних співвідношень для оцінки ефективності принципу кільцевого зсуву.
дипломная работа [1,8 M], добавлен 15.10.2013Методи первинної обробки даних - згладжування та характеристика сплайнів. Загальна характеристика об'єктно-орієнтованої мови Java. Принципи побудови графічного інтерфейсу. Розробка алгоритму програми та інтерфейсу користувача програмного продукту.
дипломная работа [3,3 M], добавлен 10.10.2013Опис програми Grapher, призначеної для математичної і графічної обробки даних, що описуються одновимірною функцією. Процес побудови графіка. Запис файлу даних мовою програмування Pascal. Моделювання вигляду апроксимаційних кривих та дискретних точок.
лабораторная работа [539,4 K], добавлен 23.09.2009Побудова інформаційно-математичної моделі та алгоритм задачі. Визначення структури даних. Розробка інтерфейсу програми з користувачем. Складання коду програми. Реалізація проекту у візуальному середовищі. Тестування та інструкція з експлуатації програми.
курсовая работа [1,3 M], добавлен 14.04.2009Коротка характеристика реле. Побудова моделі реле постійного струму. Розрахунок матриць інциденцій та оберненої матриці. Аналіз напруг за допомогою кривої намагнічення. Розрахунок індуктивність котушки для опису перехідного процесу. Лістинг програми.
контрольная работа [279,8 K], добавлен 19.01.2011Побудова інформаційно-математичної моделі задачі. Визначення структури даних. Розробка інтерфейсу програми з користувачем. Реалізація проекту у візуальному середовищі. Аналіз та тестування програми. Розгляд результатів та інструкція з експлуатації.
курсовая работа [4,2 M], добавлен 07.05.2009Теоретичні основи та приклади економічних задач лінійного програмування. Розробка математичної моделі задачі (запис цільової функції і системи обмежень) і програмного забезпечення її вирішення за допомогою "Пошуку рішень" в Excel симплекс-методом.
курсовая работа [993,9 K], добавлен 10.12.2010Синтез аналогової та структурної схеми цифрового фільтру. Опис програми обробки інформації. Оцінка верхньої фінітної частоти вхідного аналогового сигналу. Структурна схема та алгоритм функціонування пристрою мікропроцесорної обробки аналогової інформації.
курсовая работа [710,9 K], добавлен 12.03.2010Задання режиму роботи погромного лічильника. Дослідження базової схеми ТТЛ та побудова тригера. Розрахунок керуючого сигналу на виході позики кінцевого лічильника двох послідовно з'єднаних реверсивних лічильників за 51-тим синхронізуючим сигналом.
контрольная работа [1,5 M], добавлен 14.12.2012Створення програми, в якій є можливість вибрати три режими: редактор питань, перегляд рекордів гри та пункт для того щоб, розпочати нову гру. Побудова інформаційно-математичної моделі задачі. Розробка інтерфейсу програми з користувачем, її тестування.
дипломная работа [2,7 M], добавлен 28.10.2014Розробка програми "Авто" для введення та збереження інформації про власників та їхні автомобілі. Побудова математичної моделі. Критерії вибору та пошуку даних. Структура введених та збережених у файлах програми даних. Алгоритм основної програми та її код.
курсовая работа [20,3 K], добавлен 07.10.2010Модель обробки файлів растрових зображень. Середній квадрат яскравості. Фільтри для виділення перепадів і границь. Опис та обґрунтування вибору складу технічних та програмних засобів. Опис інтерфейсу програми. Зображення діалогового вікна програми.
курсовая работа [664,3 K], добавлен 30.06.2009Створення програми для виконання найпростіших функцій календаря за допомогою Borland DELPHI 2007. Аналіз процесу обробки інформації і побудова функціональних діаграм. Розробка інтерфейсу користувача, форм вводу-виводу інформації, основних алгоритмів.
курсовая работа [1,3 M], добавлен 01.06.2013Теорія обчислювальних систем. Режим обробки, що визначає порядок функціонування системи. Клас оброблюваних задач і порядок їхнього надходження в систему. Порядок ідентифікації обчислювальної системи. Математично задача синтезу обчислювальної системи.
реферат [33,7 K], добавлен 08.09.2011Задача на пошук найкоротшої відстані, маршруту і шляху холостого пробігу машин. Обгрунтування вибору методу та алгоритм розв'язання задачі. Опис математичної моделі задачі. Інтерфейс та лістинг программи. Заповнення таблиці суміжності для заданого графу.
курсовая работа [315,5 K], добавлен 26.05.2015
