Задача С. Джонсона для двох верстатів

Нехай є два верстати А і В, кожна деталь повинна бути оброблена на верстаті А (при чому в першу чергу), і на верстаті В (у другу чергу). Вважаються відомими часи обробки кожної деталі на кожному верстаті: - час обробки і-ої деталі на верстаті А, - час обробки деталі на верстаті В. Для різних деталей ці часи, взагалі кажучи, різні. Важливими обмеженнями (крім обмеження на послідовність обробки) являються наступні умови: на кожному з верстатів можна одночасно обробляти тільки одну деталь; кожна деталь може оброблятися тільки на одному верстаті; процес обробки не може перериватися. Треба визначити варіант плану запуску деталей, при якому загальний час їх обробки буде мінімальним.

Звичайно, висновок обґрунтування отриманого результату тут не приводиться. Відмітимо лише, що послідовність запуску деталей у виробництво на будь-якому верстаті може бути змінена так, що вона співпадає з послідовністю на іншому верстаті, без збільшення часу виконання плану. Тому в оптимальному рішенні порядок виконання робіт на верстаті А співпадає з порядком виконання робіт на верстаті В. Оскільки на першому верстаті операції можна виконувати без усілякої затримки, оптимізація полягає в мінімізації часу простою другого верстату.

Алгоритм розв'язання задачі простий.

1. Записуються часи робіт:

Номер деталі 1 2 3 4 5

Верстат А 3 4 2 3 1

Верстат В 2 1 3 5 4

• 2. Продивляються усі часи обробки (тобто і для А і для В), і знаходиться мінімальне серед них (і).
• 3. Якщо мінімальний час відноситься до першого верстату (тобто це час , в прикладі ), то деталь з відповідним номером ставиться на обробку першою (деталь №5 буде першою оброблятися на А, а значить, і на В).
• 4. Якщо мінімальний час відноситься до другого верстата (тобто це час ), то деталь з відповідним номером ставиться на обробку останньою (деталь №1 буде оброблятися останньою)
• 5. «Забувають» обрану деталь.
• 6. Повторюють все сказане з деталями, що залишилися.
• 7. Якщо час обробки двох різних деталей на одному верстаті співпадає і цей час менший за час обробки на іншому верстаті, то порядок обробки цих деталей довільний.

Для приведеного прикладу оптимальна послідовність обробки: 5 - 3 - 4 -1 -2, загальний час обробки 16 одиниць часу. Для порівняння: обробка у послідовності 1 - 2 - 3 - 4 - 5 потребує 21 одиниць часу.

Нажаль, вже з 3 верстатами ситуація набагато складніша.