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

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

В стандартной 3-позиционной нотации для задач расписания работ, вариант с одной машиной обозначается цифрой 1 в первом поле. Например, «1||» — это задача планирования для одной машины без ограничений, в которой целью является минимизация суммы полных времён.

Задача минимизации времени завершения 1||, которая является распространенной целью для задами с несколькими машинами, тривиальна для одной машины, поскольку время всегда одинаково. По этой причине изучаются другие целевые функции.

Минимизация суммы времён завершения Задача 1|| имеет целью минимизацию суммы времён завершения работ. Задача может быть оптимально решена с помощью правила «наименьшее время обработки первым»: работы упорядочиваются по возрастанию их времени обработки .

Задача 1|| имеет целью минимизацию взвешенной суммы времён завершения работ. Она может быть оптимально решена с помощью правила «взвешенное наименьшее время обработки первым»: работы упорядочиваются по возрастанию отношения .

Задача 1|chains| является обобщением предыдущей задачи для работ с зависимостями в виде цепочек. Она также может быть оптимально решена с помощью соответствующего обобщения правила «взвешенное наименьшее время обработки первым».

Уменьшение издержек от опозданий Задача 1|| имеет целью минимизацию максимального опоздания. Для каждой работы j существует срок выполнения . Если работа завершается после установленного срока, возникает , определяемое как . 1|| может быть оптимально решена с помощью правила «наиболее ранний срок выполнения первым»: работы упорядочиваются по возрастанию их сроков выполнения .

Задача 1|prec| обобщает задачу 1|| двумя путями: во-первых, она допускает произвольные ограничения на предшествование работ; во-вторых, она позволяет каждой работе иметь произвольную функцию стоимости hj, которая зависит от времени завершения работы (опоздание является частным случаем функции стоимости). Максимальная стоимость может быть минимизирована с помощью жадного алгоритма, известного как .

Задача 1|| обобщает задачу 1||, позволяя каждой работе иметь своё собственное время поступления, к которому она становится доступной для выполнения. Наличие времени поступления означает, что в некоторых случаях может быть оптимальным остановить машину, чтобы дождаться ещё не поступившей важной работы. Минимизация максимальной задержки в этой постановке является NP-трудной задачей. На практике задачу можно решить с помощью алгоритма ветвей и границ.

Максимизация прибыли от раннего начала В условиях ограниченного времени, если работа завершается в срок, возможна прибыль pj. В противном случае прибыль отсутствует. Цель — максимизировать прибыль. Планирование для одного станка с ограничениями по срокам является NP-трудной задачей. Сахни предлагает как точные алгоритмы с экспоненциальной временной сложностью, так и полиномиальный аппроксимационный алгоритм.

Максимизация пропускной способности Задача 1|| имеет целью минимизацию числа запаздывающих работ, независимо от величины опоздания. Задача может быть решена оптимально с помощью алгоритма Мура — Ходжсона. Задачу можно интерпретировать как поиск расписания, максимизирующего число вовремя выполненных работ. Это число называют пропускной способностью.

Задача 1|| имеет целью минимизацию вес запозданий работ. Это NP-трудная задача, поскольку специальный случай задачи, в которой все работы имеют один срок завершения (задача обозначается как 1|| ), эквивалентен задаче о рюкзаке .

Задача 1|| обобщает задачу 1||, позволяя различное время поступления для разных работ. Задача NP-трудна, но в случае одинаковой продолжительности всех работ задача может быть решена за полиномиальное время. Существует несколько вариантов задачи:

Вариант взвешенной оптимизации 1|| может быть решён за время . Невесовой вариант оптимизации, максимизирующий число работ, завершающихся вовремя, обозначается 1|| и может быть решён за время с помощью динамического программирования, если времена поступления работ и требуемые времена завершения выражены целыми числами. Вариант принятия решения — определение возможности завершения всех заданных работ вовремя — может быть реше\ён несколькими алгоритмами, самый быстрый из которых работает за время .

Работы могут иметь интервалы выполнения. Для каждой работы j, имеется время выполнения tj и время начала sj, так что работа должна быть выполнена в интервал [sj, sj+tj]. Поскольку некоторые интервалы накладываются, не все работы могут быть выполнены. Целью является максимизация числа выполненных работ, то есть, пропускную способность. В более общем случае каждая работа может иметь несколько возможных интервалов, и каждый интервал может быть связан с различной прибылью. Цель состоит в том, чтобы выбрать не более одного интервала для каждой работы таким образом, чтобы общая прибыль была максимальной. Более подробную информацию можно найти на странице .

В более общем случае, работы могут иметь временные окна, с указанием как времени начала, так и крайних сроков, которые могут быть больше длительности работы. Каждая работа может быть запланирована в любом месте в пределах своего временного окна. Бар-Ной, Бар-Йехуда, Фройнд, Наор и Шибер представили аппроксимацию (1-ε)/2.

Работы с непостоянной длиной Рабочие и машины часто устают после определённого периода работы, что замедляет их при выполнении последующих работ. С другой стороны, рабочие и машины могут обучаться для выполнения своей работы, что ускоряет выполнение следующих работ. В обоих случаях продолжительность выполнения работы не постоянна, а зависит от ранее выполненных работ. В такой ситуации даже минимизация максимального времени завершения становится нетривиальной задачей. Существуют два распространённых подхода к моделированию изменения длительности работ. Продолжительность выполнения работы может зависеть от времени начала работы. Если продолжительность является слабо возрастающей функцией от начала работы, это называется эффектом износа, если же функция слабо убывает, это называется эффектом обучения. Длительность выполнения работы может зависеть от суммы нормальных времён обработки ранее выполненных работ. Если длительность является слабо возрастающей функцией этой суммы, это часто называют эффектом старения.

Длительность, основанная на времени начала Ченг и Дин исследовали минимизацию общей длительности выполнения и минимизацию максимального опоздания, когда фактическая продолжительность выполнения работы j, запланированной на время sj, определяется формулой: , где pj — это обычная продолжительность работы j. Они доказали следующие результаты::

Когда работы могут иметь произвольные конечные сроки выполнения, задача является (сводятся к задачам ); Когда работы могут иметь один из двух сроков выполнения, задача является NP-полной (сводятся к разбиниям). Когда работы могут иметь произвольные моменты готовности к выполнению, задача является (сводится к задаче с произвольными крайними сроками завершения). Когда работы могут иметь один из двух моментов готовности к выполнению, 0 или R, задача является NP-полной.

Кубиак и ван-де-Вельде исследовали минимизацию времени завершения работ при условии, что усталость начинается только после общей даты срока исполнения d. То есть, фактическая продолжительность работы j, запланированной на время sj, определяется выражением . Таким образом, если работа начинается до даты d, её продолжительность не меняется. Если же работа начинается после момента d, продолжительность работы увеличивается со скоростью, зависящей от работы. Они показали, что задача NP-трудна, дали псевдополиномиальный алгоритм, работающий за время , и предложили алгоритм на основе метода ветвей и границ, решающий задачу до 100 работ за приемлемое время. Они также изучили ограничение усталости, когда pj перестают расти, если работа поступает на исполнение после некоторого времени D > d. Для этого случая они предложили два алгоритма с псевдополиномиальным временем работы.

Ченг, Динг и Лин дали обзор некоторых публикаций с эффектом износа, при котором продолжительность работы j, запланированной на момент времени sj, является линейной или кусочно-линейной, а скорость изменения может быть положительной или отрицательной.

Время обработки, основанное на сумме времён обработки Модель старения может быть двух типов: В модели старения на основе позиции время обработки зависит от числа работ, выполненных до данной работы, то есть, от положения работы в последовательности. В модели старения на основе суммарного времени обработки время обработки является слабо возрастающей функцией от суммы нормальных (не затронутых старением) продолжительностей выполнения работ, завершённых до данной работы.

Джи-Бо Ван, Ли-Ян Ван, Дан Ван и Сяо-Юань Ван исследовали модель старения, основанную на сумме времени обработки, где время выполнения работы j, запланированной на позицию v определяется формулой , где — это работа, запланированная на позицию , а α — «характеристика старения» машины. В такой модели максимальное время обработки для перестановки составляет:

Рудек обобщил модель в двух направлениях, позволив усталости отличаться от времени обработки и допустив зависимую от работы характеристику старения:

Здесь f — возрастающая функция, описывающая зависимость усталости от времени обработки, а αj — характеристика старения работы j''. Для этой модели он доказал следующие результаты: Минимизация максимального времени завершения и минимизация максимальной задержки решаются за полиномиальное время. Минимизация максимального времени завершения и минимизация максимальной задержки являются сильно NP-трудными задачами, если некоторые работы имеют сроки выполнения.

См. также

Множество методов решения было применено для решения задач планирования для одной машины. Некоторые из них перечислены ниже. Генетические алгоритмы Нейронные сети Алгоритм имитации отжига Муравьиный алгоритм Поиск с запретами

Примечания

Категория:Оптимальные расписания Категория:NP-полные задачи