Детермінована задача впорядкування

Постановка задачі і вибір критерію оптимізації. Нехай маємо декілька виробів, кожний із яких повинен бути оброблений на двох машинах. Припустимо, що відомий час обробки і послідовність обробки кожного виробу на кожній машині (табл. 1). Необхідно вибрати таку послідовність обробки виробів, при якій сумарний час обробки виробів буде мінімальним (або сумарний час очікування обробки виробів на машині).

Виявлення основних особливостей, взаємозв'язку і кількісних закономірностей.

Перерахуємо основні обмеження задачі:

Таблиця 1 — Час обробки виробів на двох машинах.

час переходу виробу від однієї машини до другої незначний, і ним можна знехтувати;

кожний виріб обробляється в певному технологічному порядку;

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

Позначимо t_1j — час обробки j-го виробу на першій машині, а t_2j — час обробки j-го виробу на другій машині.

Зобразимо процес обробки виробу на двох машинах на графіку (Рис.1).

задача джонсон алгоритм програма.

Час обробки на машині 1.

Час обробки на машині 2.

Час простою машини 2.

Рисунок 1 — Процес обробки виробів на обох машинах На малюнку Т — повний час, котрий пройде від початку обробки першого виробу на першій машині до кінця обробки останнього виробу на другій машині.

Побудова математичної моделі. Нехай t_пj — час простою другої машини між кінцем виконання роботи по обробці (j — 1) — го виробу на другій машині та початком обробки j-го виробу на тій же самій машині. Тоді сумарний час обробки виробів складає.

.

а оскільки сума відома, то належить мінімізувати (у нашому випадку).