График работы магазина

Планирование рабочих мест или проблема рабочих мест ( JSP ) - это проблема оптимизации в информатике и исследованиях операций . Это вариант оптимального планирования работы . В общей задаче планирования заданий нам дается n заданий J ₁ , J ₂ , ..., J _n с разным временем обработки, которые необходимо запланировать на m машинах с различной вычислительной мощностью, пытаясь свести к минимуму время выполнения.– общая длина расписания (то есть, когда все задания закончили обработку). В особом варианте, известном как планирование рабочих мест, каждое задание состоит из набора операций O ₁ , O ₂ , ..., O _n , которые необходимо обрабатывать в определенном порядке (известном как ограничения приоритета ). У каждой операции есть определенная машина , на которой она должна быть обработана, и только одна операция в задании может быть обработана в данный момент времени. Распространенным послаблением является гибкая мастерская, где каждая операция может выполняться на любой машине из заданного набора (машины в каждом наборе идентичны).

Название первоначально произошло от планирования заданий в магазине вакансий , но эта тема имеет широкое применение за пределами этого типа экземпляров. Эта задача является одной из самых известных задач комбинаторной оптимизации и была первой задачей, ^{конкурентный} анализ которой был представлен Грэмом в 1966 году. ^[2]

В стандартной нотации с тремя полями для задач оптимального планирования работы вариант Job-Shop обозначается буквой J в первом поле. Например, задача, обозначенная как « J3|| » ${\ displaystyle p_ {ij}}$ , представляет собой производственную задачу с тремя машинами с единичным временем обработки, где цель состоит в том, чтобы минимизировать максимальное время выполнения. ${\ Displaystyle С _ {\ макс}}$

Поскольку задача коммивояжера является NP-трудной , задача о магазине с настройкой, зависящей от последовательности, очевидно, также является NP-трудной, поскольку TSP является частным случаем JSP с одной работой (города — это машины, а продавец — это работа). ^{[ нужна ссылка ]}

Дизъюнктивный граф ^[5] является одной из популярных моделей, используемых для описания экземпляров задачи планирования рабочих мест. ^[6]

Пусть и два конечных множества . Из-за промышленного происхождения проблемы они называются машинами , а рабочие места . ${\ Displaystyle М = \ {М_ {1}, М_ {2}, \ точки, М_ {м} \}}$ ${\ Displaystyle J = \ {J_ {1}, J_ {2}, \ точки, J_ {п} \}}$ ${\ Displaystyle \ Displaystyle М_ {я}}$ ${\ Displaystyle \ Displaystyle J_ {J}}$