Обозначения для теоретических задач планирования - Notation for theoretic scheduling problems

Удобный обозначения для теоретических задач планирования был представлен Рональд Грэм, Юджин Лоулер, Ян Карел Ленстра и Александр Риннуй Кан в.^[1] Он состоит из трех полей: α, β и γ.

Каждое поле может быть списком слов, разделенных запятыми. Поле α описывает среду машины, β - рабочие характеристики и ограничения, а γ - целевую функцию.

С момента своего появления в конце 1970-х обозначения постоянно расширялись, иногда непоследовательно. В результате сегодня есть некоторые проблемы, которые появляются с различными обозначениями в нескольких статьях.

Машинная среда

Одноэтапные задачи

Каждое задание имеет определенное время обработки.

1: есть одна машина
п: Существуют ${displaystyle m}$ параллельные идентичные машины
Q: Существуют ${displaystyle m}$ параллельные машины с разными заданными скоростями, продолжительность работы ${displaystyle j}$ на машине ${displaystyle i}$ время обработки ${displaystyle p_ {j}}$ делится на скорость ${displaystyle s_ {i}}$ .
р: Существуют ${displaystyle m}$ параллельные, не связанные между собой машины, указаны сроки обработки ${displaystyle p_ {ij}}$ для работы ${displaystyle j}$ на машине ${displaystyle i}$

За этими буквами может следовать количество машин, которое затем фиксируется, здесь ${displaystyle m}$ обозначает фиксированное число. Например, ${displaystyle P2 || C_ {max}}$ проблема назначения каждого из ${displaystyle n}$ данные задания на одну из 2 заданных машин, чтобы минимизировать максимальное общее время обработки на машинах.

Многоступенчатая задача

О: Проблема с открытым магазином. Каждая работа ${displaystyle j}$ состоит из ${displaystyle m}$ операции ${displaystyle O_ {ij}}$ за ${displaystyle i = 1, ldots, m}$ . Операции можно планировать в любом порядке. Операция ${displaystyle O_ {ij}}$ должен быть обработан для ${displaystyle p_ {ij}}$ единиц на машине ${displaystyle i}$ .
F: Проблема с магазином потока. Каждая работа ${displaystyle j}$ состоит из ${displaystyle n_ {j}}$ операции ${displaystyle O_ {ij}}$ за ${displaystyle k = 1, ldots, n_ {j}}$ , которые должны быть запланированы в таком порядке. Операция ${displaystyle O_ {ij}}$ должен быть обработан для ${displaystyle p_ {ij}}$ единиц на машине ${displaystyle i}$ .
J: Проблема с магазином вакансий. Каждая работа ${displaystyle j}$ состоит из ${displaystyle n_ {j}}$ операции ${displaystyle O_ {kj}}$ за ${displaystyle k = 1, ldots, n_ {j}}$ , которые должны быть запланированы в таком порядке. Операция ${displaystyle O_ {kj}}$ должен быть обработан для ${displaystyle p_ {kj}}$ единиц на выделенной машине ${displaystyle mu _ {kj}}$ с ${displaystyle mu _ {kj} eq mu _ {k'j}}$ за ${displaystyle keq k '}$ .

Характеристики работы

Время обработки может быть одинаковым для всех работ ( ${displaystyle p_ {i} = p}$ , или же ${displaystyle p_ {ij} = p}$ ) или даже единичной длины ( ${displaystyle p_ {i} = 1}$ , или же ${displaystyle p_ {ij} = 1}$ ). Предполагается, что все времена обработки являются целыми числами. Однако в некоторых более старых исследовательских работах они считаются рациональными.

${displaystyle r_ {j}}$: для каждого задания дается время выпуска, до которого его нельзя запланировать, по умолчанию - 0.
${displaystyle online-r_ {j}}$: Это онлайн-проблема. Вакансии раскрываются в момент их выпуска. В этом контексте производительность алгоритма измеряется его конкурентное соотношение.
${displaystyle d_ {j}}$: для каждой работы указан срок сдачи. Идея состоит в том, что каждое задание должно завершаться раньше установленного срока, а за задания, которые завершаются с опозданием, есть штрафы. Этот штраф обозначается в объективном значении. Наличие служебной характеристики ${displaystyle d_ {j}}$ подразумевается неявно и не обозначается в названии задачи, если нет некоторых ограничений, например ${displaystyle d_ {j} = d}$ , предполагая, что все сроки выполнения равны некоторой заданной дате.
${displaystyle {ar {d}} _ {j}}$: для каждой работы дается строгий дедлайн. Каждая работа должна быть завершена до установленного срока.
pmtn: Задания могут быть прерваны и возобновлены, возможно, на другом компьютере. Иногда также обозначается как «prmp».
${displaystyle size_ {j}}$: Каждое задание поставляется с несколькими машинами, на которых оно должно быть запланировано одновременно, по умолчанию - 1.

Отношения приоритета

Отношения приоритета могут быть заданы для заданий в форме частичного порядка, что означает, что если i является предшественником i 'в этом порядке, i' может начаться только после завершения i.

пре: Учитывая общее отношение предшествования. Если ${displaystyle iprec j}$ затем время начала ${displaystyle j}$ должно быть не раньше времени завершения ${displaystyle i}$ .
цепи: Заданное отношение предшествования в виде цепочек (входящие и исходящие степени не более 1).
дерево: Дано общее отношение предшествования в виде дерева, либо внутреннее, либо внешнее.
Intree: Дано общее отношение предшествования в форме целого дерева (исходящие степени не более 1).
за пределами: Дано общее отношение предшествования в виде внешнего дерева (степень не более 1).
противостоящий лес: Дано общее отношение приоритета в виде набора внутренних и исходящих деревьев.
sp-график: Задано отношение предшествования в виде последовательного параллельного графа.
ограниченная высота: Задано отношение предшествования, в котором самый длинный направленный путь ограничен константой.
порядок уровней: При заданном отношении предшествования, где каждая вершина данного уровня l (т.е.длина самого длинного направленного пути, начинающегося из этой вершины, равна l), является предшественником всех вершин уровня l-1.
интервальный порядок: Задано отношение приоритета, для которого каждой вершине можно сопоставить интервал в реальной строке, и существует приоритет между x и y тогда и только тогда, когда полуоткрытые интервалы x = [s_x, e_x) и y = [s_y, e_y) таковы, что e_x меньше или равно s_y.
квазиинтервальный порядок: Квазиинтервальные порядки - это суперкласс интервальных порядков, определенных в Moukrim: Optimal scheduling on parallel machines for a new order class, Operations Research Letters, 24 (1): 91-95, 1999.
сверхинтервальный порядок: Сверхинтервальные порядки - это суперкласс квазиинтервальных порядков, определенных в Шардоне и Мукриме: алгоритм Коффмана-Грэма оптимально решает системы задач UET с сверхинтервальными порядками, SIAM Journal on Discrete Mathematics, 19 (1): 109-121, 2005.
Am-заказ: Am-заказы - это суперкласс сверхинтервальных заказов, определенных в Moukrim и Quilliot: соотношение между многопроцессорным планированием и линейным программированием. Заказ, 14 (3): 269-278, 1997.
DC-график: Граф «разделяй и властвуй» - это подкласс последовательно-параллельных графов, определенных в Kubiak et al .: Оптимальность HLF для планирования графов задач UET «разделяй и властвуй» на идентичных параллельных процессорах. Дискретная оптимизация, 6: 79-91, 2009.
2-тусклый частичный порядок: Двумерный частичный порядок - это k-мерный частичный порядок при k = 2.
k-dim частичный порядок: ЧУМ является k-мерным частичным порядком тогда и только тогда, когда он может быть вложен в k-мерное евклидово пространство таким образом, что каждый узел представлен k-мерной точкой, и между двумя узлами i и j существует приоритет, если и только если для любого Размерность координаты i меньше или равна координате j.

При наличии отношения предшествования можно дополнительно предположить задержки во времени. Позволять ${displaystyle S_ {j}}$ обозначают время начала работы и ${displaystyle C_ {j}}$ время его завершения. Тогда отношение предшествования ${displaystyle iprec j}$ подразумевает ограничение ${displaystyle C_ {i} + l_ {ij} leq S_ {j}}$ . Если нет задержки во времени ${displaystyle l_ {ij}}$ указано, то предполагается, что он равен нулю. Временные задержки могут быть положительными или отрицательными числами.

л: задержки во времени, не зависящие от работы. Другими словами ${displaystyle l_ {ij} = l}$ для всех пар работ i, j и данного номера l.
${displaystyle l_ {ij}}$: произвольные временные задержки, зависящие от пары заданий.

Задержки транспорта

${displaystyle t_ {jk}}$: Между завершением операции ${displaystyle O_ {kj}}$ работы ${displaystyle j}$ на машине ${displaystyle k}$ и начало эксплуатации ${displaystyle O_ {k + 1, j}}$ работы ${displaystyle j}$ на машине ${displaystyle k + 1}$ , задержка перевозки не менее ${displaystyle t_ {jk}}$ единицы.
${displaystyle t_ {jkl}}$: Между завершением операции ${displaystyle O_ {kj}}$ работы ${displaystyle j}$ на машине ${displaystyle k}$ и начало эксплуатации ${displaystyle O_ {l, j}}$ работы ${displaystyle j}$ на машине ${displaystyle l}$ , задержка перевозки не менее ${displaystyle t_ {jkl}}$ единицы.
${displaystyle t_ {k}}$: Задержка транспортировки, зависящая от машины. Между завершением операции ${displaystyle O_ {kj}}$ работы ${displaystyle j}$ на машине ${displaystyle k}$ и начало эксплуатации ${displaystyle O_ {k + 1, j}}$ работы ${displaystyle j}$ на машине ${displaystyle k + 1}$ , задержка перевозки не менее ${displaystyle t_ {k}}$ единицы.
${displaystyle t_ {kl}}$: Задержка транспортировки в зависимости от пары машин. Между завершением операции ${displaystyle O_ {kj}}$ работы ${displaystyle j}$ на машине ${displaystyle k}$ и начало эксплуатации ${displaystyle O_ {l, j}}$ работы ${displaystyle j}$ на машине ${displaystyle l}$ , задержка перевозки не менее ${displaystyle t_ {kl}}$ единицы.
${displaystyle t_ {j}}$: Задержка перевозки в зависимости от работы. Между завершением операции ${displaystyle O_ {kj}}$ работы ${displaystyle j}$ на машине ${displaystyle k}$ и начало эксплуатации ${displaystyle O_ {l, j}}$ работы ${displaystyle j}$ на машине ${displaystyle l}$ , задержка перевозки не менее ${displaystyle t_ {j}}$ единицы.

Различные ограничения

rcrc: Рециркуляция, также называемая гибким рабочим местом. Обещание на ${displaystyle mu}$ поднимается и для некоторых пар ${displaystyle keq k '}$ у нас может быть ${displaystyle mu _ {kj} = mu _ {k'j}}$ .
Нет, подождите: Операция ${displaystyle O_ {k + 1, i}}$ должен начаться именно тогда, когда работа ${displaystyle O_ {k, i}}$ завершает. Иногда также обозначается как «nwt».
без простоя: Ни одна машина не простаивает между двумя казнями.
${displaystyle size_ {j}}$: Многопроцессорные задачи на идентичных параллельных машинах. Выполнение работы ${displaystyle j}$ делается одновременно на ${displaystyle size_ {j}}$ параллельные машины.
${displaystyle fix_ {j}}$: Многопроцессорные задачи. Каждая работа ${displaystyle j}$ дается с набором машин ${displaystyle fix_ {j} substeq {1, ldots, m}}$ , и требует одновременного выполнения всех этих машин. Иногда также обозначается «MPT».
${displaystyle M_ {j}}$: Универсальные машины. Каждая работа ${displaystyle j}$ нужно запланировать на одной машине из заданного набора ${displaystyle M_ {j} substeq {1, ldots, m}}$ . Иногда также обозначается "M_j".

Объективные функции

Обычно цель состоит в том, чтобы минимизировать некоторую объективную ценность. Одно отличие - это обозначение ${displaystyle sum U_ {j}}$ где цель состоит в том, чтобы максимизировать количество заданий, которые завершаются раньше установленного срока. Это также называется пропускная способность. Целевое значение может быть суммой, возможно, взвешенной по некоторым заданным приоритетным весам. ${displaystyle w_ {j}}$ за работу.

-: Отсутствие объективной ценности обозначается одиночным тире. Это означает, что проблема состоит просто в создании выполнимого расписания, удовлетворяющего всем заданным ограничениям.
${displaystyle C_ {j}}$: Это означает время завершения работы ${displaystyle j}$ .
${displaystyle F_ {j}}$: В время потока задания - это разница между временем его завершения и временем выпуска, т.е. ${displaystyle F_ {j} = C_ {j} -r_ {j}}$ .
${displaystyle L_ {j}}$: Опоздание. Каждая работа ${displaystyle j}$ дается срок ${displaystyle d_ {j}}$ . Опоздание на работу ${displaystyle j}$ определяется как ${displaystyle C_ {j} -d_ {j}}$ . Иногда ${displaystyle L_ {max}}$ используется для обозначения возможности решения проблемы со сроками. Действительно, при использовании двоичного поиска сложность версии технико-экономического обоснования эквивалентна минимизации ${displaystyle L_ {max}}$ .
${displaystyle U_ {j}}$: Пропускная способность. Каждой работе дается срок ${displaystyle d_ {j}}$ . Для заданий, выполняемых один раз, существует единичная прибыль, т.е. ${displaystyle U_ {j} = 1}$ если ${displaystyle C_ {j} leq d_ {j}}$ и ${displaystyle U_ {j} = 0}$ иначе. Иногда значение ${displaystyle U_ {j}}$ в литературе инвертируется, что эквивалентно при рассмотрении версии решения проблемы, но имеет огромное значение для приближений.
${displaystyle T_ {j}}$: Опоздание. Каждая работа ${displaystyle j}$ дается срок ${displaystyle d_ {j}}$ . Опоздание с работой ${displaystyle j}$ определяется как ${displaystyle T_ {j} = max {0, C_ {j} -d_ {j}}}$ .
${displaystyle E_ {j}}$: Раньше. Каждая работа ${displaystyle j}$ дается срок ${displaystyle d_ {j}}$ . Ранняя работа ${displaystyle j}$ определяется как ${displaystyle E_ {j} = max {0, d_ {j} -C_ {j}}}$ . Эта цель важна для своевременное планирование.

Примеры

Адаптирован из ^[1]

1 | пре | ${displaystyle L_ {max}}$: одна машина, общее ограничение приоритета, минимизация максимальной задержки.

R | pmtn | ${displaystyle sum C_ {i}}$: переменное количество несвязанных параллельных машин, позволяющее прерывать работу и минимизировать общее время завершения.

J3 | ${displaystyle p_ {ij}}$ | ${displaystyle C_ {max}}$: Цех с 3 станками с единичным временем обработки, минимизирующим максимальное время выполнения.

P | ${displaystyle size_ {j}}$ | ${displaystyle C_ {max}}$: ${displaystyle m}$ параллельно идентичные машины, каждое задание поставляется с несколькими машинами, на которых оно должно быть запланировано одновременно, что сводит к минимуму максимальное время выполнения (см. также проблема планирования параллельных задач ).