Однією з поширених проблем планування є робочий цех, у якому декілька завдань обробляються на кількох машинах. Кожне завдання складається з послідовності завдань, які повинні бути виконані в заданому порядку, і кожне завдання має бути оброблено на певній машині.
Проблема розкладу робочих місць (JSSP) є NP-складною проблемою, прагнучи знайти майже оптимальні способи розподілу завдань або робочих нарядів між машинами та лініями. Основні цілі включають мінімізацію витрат, затримок, запасів та інших відповідних факторів.
Одна й та сама майстерня може мати завдання з дуже коротким часом дотику і водночас мати завдання з дуже тривалим часом дотику та все між ними. Через точність і/або допуски певні роботи мають виконуватися на певних машинах, що робить планування проблемою.
У загальній задачі планування завдань нам задано n завдань J1, J2, …, Jn із різним часом обробки, які потрібно запланувати на m машин із різною обчислювальною потужністю, при цьому намагаючись мінімізувати робочий діапазон – загальну довжину розклад (тобто, коли всі завдання закінчили обробку).
Проблема планування робочого цеху є НП-твердий це означає, що його клас складності для недетермінованого поліноміального часу є найменш складним, ніж найскладніша проблема в NP. Вхідними даними є скінченна множина J робочих місць і скінченна множина M машин.
Проблема гнучкого планування робочих місць (FJSP) є НП-твердий задача комбінаторної оптимізації, яка має широке застосування в реальному світі. Складність і актуальність FJSP призвели до численних досліджень з його моделювання та вирішення.