Задачи теории расписаний. Методы решения: комбинаторный подход, эвристический и комбинаторный методы

Комбинаторный подход

Сводится к целенаправленной перестановке пар работ в некоторой исходной последовательности, пока не будет получено оптимальное nln близкое к оптимальному решение.

Вспомним сначала определения таких понятиях, как задачи класса Р, эффективные алгоритмы и NP -полные задачи.

Под «эффективным алгоритмом» понимается алгоритм, для которого число требуемых шагов растет как полином от размера входной задачи. Задачи, имеющие эффективные (полиномиальные) алгоритмы решения, принадлежат классу Р -задач.

Класс NP -задач обладает следующими свойствами:

- никакую NP -полную задачу нельзя решить никакими известными полиномиальными алгоритмами;

- если существует полиномиальный алгоритм для какой-нибудь NP -полной задачи, то существуют полиномиальные алгоритмы для всех NP -полных задач.

Практическое значение понятия NP -полноты состоит в следующем: такие задачи по существу труднорешаемы с вычислительной точки зрения, они не поддаются эффективному алгоритмическому решению и для алгоритма, корректно решающего NP -полную задачу, потребуется в худшем случае экспоненциальное количество времени и, следовательно, он не будет применим на практике ни к каким, за исключением очень малых, задачам.