Введение
Планирование одной машины или планирование одного ресурса — это задача оптимизации в информатике и исследовании операций. Дано n заданий J1, J2, …, Jn с различным временем обработки, которые необходимо запланировать на одной машине таким образом, чтобы оптимизировать определенную целевую функцию, например, пропускную способность. Планирование одной машины является частным случаем планирования на идентичных машинах, которое, в свою очередь, является частным случаем оптимального планирования заданий. Многие задачи, которые в общем случае являются NP-трудными, могут быть решены за полиномиальное время в случае с одной машиной. В стандартной трехпольной нотации для задач оптимального планирования заданий вариант с одной машиной обозначается цифрой 1 в первом поле. Например, "1||" — это задача планирования одной машины без ограничений, где целью является минимизация суммы времен завершения. Задача минимизации длительности выполнения (makespan) 1||, которая является распространенной целью при использовании нескольких машин, тривиальна для одной машины, поскольку длительность выполнения всегда одинакова. Поэтому изучались другие целевые функции.
Минимизация суммы сроков завершения
Проблема 1|| направлена на минимизацию суммы времен завершения. Она может быть решена оптимально по правилу "Наименьшее время обработки первым" (SPT): задачи планируются в порядке возрастания времени их обработки. Проблема 1|| направлена на минимизацию взвешенной суммы времен завершения. Она может быть решена оптимально по правилу "Взвешенное наименьшее время обработки первым" (WSPT): задачи планируются в порядке возрастания отношения, и для нее существуют как точные алгоритмы с экспоненциальным временем работы, так и алгоритм приближения с полиномиальным временем работы.
The problem 1|| aims to minimize the weighted sum of completion times. It can be solved optimally by the Weighted Shortest Processing Time First rule (WSPT): the jobs are scheduled by ascending order of the ratio presents both exact exponential time algorithms and a polynomial time approximation algorithm.
Максимальная пропускная способность
Проблема 1|| стремится минимизировать количество опоздавших задач, независимо от величины опоздания. Она может быть решена оптимально алгоритмом Ходжсона-Мура. Не взвешенный вариант оптимизации, максимизирующий количество задач, завершающихся вовремя, обозначается как 1||, и может быть решен за время с использованием динамического программирования, когда все времена поступления и сроки являются целыми числами. Задача о выполнимости, определяющая, возможно ли завершить все заданные задачи вовремя, может быть решена несколькими алгоритмами, самый быстрый из которых работает за время. Задачи могут иметь интервалы выполнения. Для каждой задачи j задано время обработки tj и время начала sj, поэтому она должна быть выполнена в интервале [sj, sj+tj]. Поскольку некоторые интервалы перекрываются, не все задачи могут быть выполнены. Цель состоит в том, чтобы максимизировать количество выполненных задач, то есть пропускную способность. В более общем случае, каждая задача может иметь несколько возможных интервалов, и каждый интервал может быть связан с разной прибылью. Цель состоит в том, чтобы выбрать не более одного интервала для каждой задачи, чтобы максимизировать общую прибыль. Более подробную информацию можно найти на странице, посвященной планированию интервалов. В более общем плане, задачи могут иметь временные окна, с указанием времени начала и сроков, которые могут быть больше длительности задачи. Каждая задача может быть запланирована в любое время внутри своего временного окна. Бар Ной, Бар Йегуда, Фрейнд, Наор и Шибер представляют (1 ε)/2-аппроксимацию.
Jobs can have execution intervals. For each job j, there is a processing time tj and a start time sj, so it must be executed in the interval [sj, sj+tj]. Since some of the intervals overlap, not all jobs can be completed. The goal is to maximize the number of completed jobs, that is, the throughput. More generally, each job may have several possible intervals, and each interval may be associated with a different profit. The goal is to choose at most one interval for each job, such that the total profit is maximized. For more details, see the page on interval scheduling. More generally, jobs can have time windows, with both start times and deadlines, which may be larger than the job length. Each job can be scheduled anywhere within its time window. Bar Noy, Bar Yehuda, Freund, Naor and Schieber present a (1 ε)/2 approximation.
Работы с непостоянной длиной
Рабочие и машины часто устают после определенного времени работы, что замедляет обработку последующих заданий. С другой стороны, рабочие и машины могут научиться работать эффективнее, что ускоряет обработку последующих заданий. В обоих случаях длительность (время обработки) задания не является фиксированной, а зависит от заданий, обработанных ранее. В такой ситуации даже минимизация максимального времени завершения становится нетривиальной задачей. Существует два основных подхода к моделированию изменения длительности задания. Длительность задания может зависеть от времени его начала. Если длительность слабо возрастает с увеличением времени начала, это называется эффектом ухудшения; если она слабо убывает, то это эффект обучения. Длительность задания также может зависеть от суммы нормального времени обработки предыдущих заданий. Если длительность слабо возрастает с увеличением этой суммы, то это часто называют эффектом старения.