Планирование работы в цехе
- Планирование рабочего места (JSP) — задача оптимизации в области компьютерных наук и исследований операций.
- Задача JSP: минимизировать makespan — общую продолжительность расписания выполнения n заданий на m машинах.
- В JSP каждое задание состоит из набора операций, которые должны выполняться в определенном порядке.
- Гибкий технологический процесс: каждая операция может быть выполнена на любом станке из заданного набора.
- JSP является одной из наиболее известных задач комбинаторной оптимизации.
- Существует множество вариантов решения JSP, включая использование дубликатов станков, машин с настройками и многокритериальной оптимизации.
- NP-твердость: JSP является NP-сложной задачей, так как TSP является частным случаем JSP с одним заданием.
- Дизъюнктивный граф — популярная модель для описания задач планирования рабочего времени в цехе.
Полный текст статьи: