Задачи обслуживания множеств заявок

💸 Как сделать бизнес проще, а карман толще?

Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое раписание, но и напоминать клиентам о визитах тоже. Проблема в том, что средняя цена по рынку за такой сервис — 800 руб/мес или почти 15 000 руб за год. И это минимальный функционал. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!

Имеется множество заявок {1, 2, …, n } и процессор Р, на котором должна пройти обслуживание каждая заявка; процессор не может обслуживать несколько (т.е. более одной) заявок одновременно. Обслуживание каждой заявки (от начала до конца) реализуется без прерываний; переход от обслуживания одной заявки к обслуживанию следующей за ней заявки затрат времени не требует. Обслуживание заявок начинается от момента времени t = 0. Для каждой заявки i известны две характеристики: τ (i) – продолжительность обслуживания на процессоре; а (i) – штраф за единицу времени пребывания в системе обслуживания. Считаем, что τ (i) > 0, а (i) ≥ 0, i = 1, …, n.

Каждое расписание обслуживания определяем как перестановку ρ = (i ₁, i ₂,..., i_n) элементов множества {1, 2,..., n }; заявка i_k в расписании ρ обслуживается k -й по очереди, k = 1. Обозначим через t _нач(ρ, i_k) и t* (ρ, i_k) моменты начала и завершения обслуживания заявки i_k при реализации расписания ρ. Имеют место соотношения:

При реализации расписания ρ величина штрафа W_i (ρ) по произвольной заявке i оказывается равной а (i) t* (ρ, i). Суммарный штраф по всем заявкам, обслуживаемым согласно расписанию ρ, есть

Проблема заключается в синтезе расписания, обеспечивающего минимальное значение суммарного штрафа, т.е. в нахождении

В стандартной для задачи мастера интерпретации считается, что заявки – это сломавшиеся станки, процессор – мастер по их ремонту, а (i) – величина потерь, связанных с каждой единицей времени простоя i- го станка; τ (i) – время, которое мастер должен затратить на ремонт i -го станка, i = 1, …, n.

Предположим, что расписание ρ ⁰= (1, 2,..., n) в задаче (4) является оптимальным. Через ρ ^q обозначим расписание, получаемое из ρ ⁰переменой местами двух соседних заявок, q и q + 1. Очевидно, что для каждого значения i, отличного от q и от q + 1, имеет место t* (ρ ^q, i) = t* (ρ ⁰, i). Поэтому в суммах

отличаются между собой только q -е и (q + 1)-е слагаемые. Легко определяется, что

Так как расписание ρ ⁰– оптимально, записанная разность неположительна. Получаем

Разделив обе части полученного неравенства на положительное произведение τ (q)τ (q + 1), получаем

Неравенство (5) – следствие сделанного предположения об оптимальности расписания ρ ⁰. Из этого неравенства вытекает простейший алгоритм синтеза оптимального расписания в задаче мастера: для каждой заявки i нужно определить показатель μ (i) = а (i)/τ (i), i = 1, …, n, и упорядочить заявки по убыванию значений μ (i). Полученная перестановка является оптимальным расписанием обслуживания имеющегося множества заявок.

Изложенный способ отыскания правила оптимального упорядочения заявок называется перестановочным приемом. Найденный для задачи мастера способ синтеза оптимального расписания именуем μ -правилом. Содержательный смысл его очевиден: чем меньше продолжительность обслуживания заявки и чем больше по этой заявке штраф за единицу времени пребывания в системе, тем раньше она должна обслуживаться.

Отличие рассматриваемой задачи от предыдущей состоит в наличии двух идентичных процессоров, Р ₁и Р ₂. Каждая заявка множества {1, 2, …, n } должна быть обслужена либо первым, либо вторым процессором. Оба процессора считаются готовыми к обслуживанию заявок начиная с момента времени t = 0. Обслуживание одной заявки двумя процессорами считается невозможным. Расписание определяем как пару ρ = (ρ ₁, ρ ₂), где ρ ₁= (i ₁, i ₂, i ₃, …, i_p)-перестановка, определяющая последовательность обслуживания заявок первым процессором, а ρ ₂= (j ₁, j ₂, j ₃, …, j_q)-перестановка, определяющая последовательность обслуживания заявок вторым процессором. Каждая заявка входит либо в первую, либо во вторую перестановку, поэтому р + q = n. Требуется найти расписание, минимизирующее суммарный по всем заявкам штраф.

По аналогии с результатами, полученными для однопроцессорной задачи мастера, можно предположить, что оптимальным является расписание, синтезируемое в соответствии с интерпретируемым следующим образом μ -правилом: упорядочиваем совокупность всех заявок по убыванию показателя μ (i), в этом порядке выполняем их перенумерацию и в этом же порядке направляем на обслуживание освобождающимися процессорами. В синтезируемом расписании процессоры Р ₁и Р ₂сначала должны обслужить заявки 1 и 2 соответственно (все номера заявок – новые), заявка 3 направляется следующей на процессор, который раньше освободится. Точно так же заявка 4 направляется следующей на процессор, который раньше обслужит поступившие ему заявки из совокупности {1, 2, 3}, и т.д.

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

Применением μ -правила в рассматриваемом примере строится расписание ρ ⁰= (ρ ₁, ρ ₂), где ρ ₁= (1, 3) и ρ ₂= (2). В случае реализации этого расписания суммарный штраф по трем заявкам равен 10111. В то же время при реализации расписания ρ ¹= ((1, 2), (3)) будем иметь суммарный штраф, равный 10015. Таким образом, в двухпроцессорной задаче мастера расписание, синтезируемое в соответствии с μ -правилом, оптимальным вообще говоря, не является.

Для синтеза оптимального в двухпроцессорной задаче мастера расписания применим метод динамического программирования. Будем считать, что все заявки пронумерованы в порядке убывания значений показателя μ. Тогда если ρ = (ρ ₁, ρ ₂) – оптимальное расписание, то заявки в каждой из последовательностей ρ ₁= (i ₁, i ₂, i ₃, …, i_p) и ρ ₂= (j ₁, j ₂, j ₃, …, j_q) записаны в порядке возрастания номеров.

При синтезе оптимального расписания для каждой следующей (в порядке возрастания номеров, т.е. по убыванию показателя μ) заявки i + 1 мы должны определить, на какой из двух процессоров ее направить в качестве подлежащей обслуживанию в следующую очередь. При этом все заявки множества {1, 2, …, i } по процессорам уже распределены, известны величины промежутков времени, которое будет потрачено на обслуживание этих заявок первым и вторым процессорами; время работы процессора Р ₁над предписанными ему заявками из совокупности {1, 2, …, i } обозначим Δ. В таком случае время работы процессора Р ₂над заявками из той же совокупности равно

Через W* (i, Δ) обозначим минимально возможную величину суммарного штрафа по заявкам множества {1, 2, …, i }, если на обслуживание направленных на процессор Р ₁заявок из этого множества затрачивается время Δ. Как очевидно,

При значениях аргумента Δ, отличных от нуля и τ (1), определяемая парой (1, Δ) ситуация возникнуть не может; удобно положить

далее для любых нереализуемых ситуаций (i, Δ) из определяемого ниже соотношения (8) будем получать W* (i, Δ) = +∞.

Предположим, что все значения функции W* (i, Δ) для некоторого конкретного значения i уже найдены. Рассмотрим ситуацию в процессе обслуживания, определяемую парой (i + 1, Δ). В случае Δ ≥ τ (i + 1) непосредственно предшествующими для этой ситуации являются две: (i, Δ) и (i, Δ – τ (i + 1)); в случае Δ < < τ (i + 1) непосредственно предшествующей является только ситуация (i, Δ); значение W* (i, Δ – τ (i + 1)), где второй аргумент функции отрицательный, считается равным +∞. Переход от ситуации (i, Δ) к ситуации (i + 1, Δ) предполагает, что обслуживание заявки i + 1 выполняется процессором Р ₂; обслуживание этой заявки начинается в момент времени

Переход от ситуации (i, Δ – τ (i + 1)) к ситуации (i + 1, Δ) предполагает, что обслуживание заявки i + 1 выполняется процессором Р ₁; обслуживание начинается в момент времени Δ – τ (i + 1)) и завершается в момент Δ.

Процедуру вычисления значений функции W* (i, Δ) удобно представлять как процесс заполнения таблицы, строки которой соответствуют значениям параметра i, а столбцы – значениям параметра Δ; в клетку, являющуюся пересечением строки i и столбца Δ, вносится значение W* (i, Δ). Общее число строк таблицы значений функции W* (i, Δ) равно n. Величины W* (i, Δ) требуется определять для значений второго аргумента из множества

Строки таблицы заполняются сверху вниз, в порядке роста значений параметра i. Первая строка заполняется по формулам (6)–(7), остальные – по формуле (8). Отметим, что в силу идентичности процессоров в клетки (i + 1, Δ) и (i + 1,

).вносятся одинаковые числа; если при вычислении значения W* (i + 1, Δ) минимум правой части (8) реализуется на первой (второй) компоненте, то при отыскании величины W* (i + 1,

) минимум правой части (8) реализуется на второй (соответственно первой) компоненте. Оптимальным значением критерия в решаемой задаче является минимальный элемент, внесенный в нижнюю строку таблицы значений функции W* (i, Δ). Если данный элемент находится в столбце Δ ', то общее время работы одного процессора в реализации оптимального расписания равно Δ ', время работы другого процессора равно

Для обеспечения возможности синтеза оптимального расписания в каждую клетку (i + 1, Δ) таблицы кроме значения W* (i + 1, Δ), требуется записывать условный символ, указывающий, на какой компоненте правой части соотношения (8) при вычислении W* (i + 1, Δ) реализуется минимум.

Равенства (6) – (8) – рекуррентные соотношения динамического программирования для решения двухпроцессорной задачи мастера.

Общая задача однопроцессорного обслуживания множества заявок с критерием суммарного штрафа.

Данная задача – обобщение однопроцессорной задачи мастера. Ее отличие от задачи мастера в том, что для каждой заявки i вместо числовой характеристики а (i) задается монотонно возрастающая (в нестрогом смысле) функция индивидуального штрафа ϕ _i (t). Значение этой функции – величина штрафа по заявке i, если обслуживание этой заявки завершается в момент времени t. При реализации расписания ρ величина штрафа W_i (ρ) по произвольной заявке i оказывается равной ϕ _i (t* (ρ, i)), где t* (ρ, i) – момент завершения обслуживания заявки i при реализации расписания ρ. Требуется найти расписание, минимизирующее величину суммарного по всем заявкам штрафа.

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

Рассмотрим ситуацию, когда все функции индивидуального штрафа экспоненциальны:

константа α считается положительной. Реализуя перестановочный прием, легко получаем алгоритм синтеза оптимального расписания: для каждой заявки i, i = 1, …, n, нужно вычислить показатель

далее заявки следует упорядочить по убыванию значений ν (i). Полученная перестановка является оптимальным расписанием обслуживания имеющегося множества заявок. Выделим случай, когда все функции индивидуального штрафа одинаковы: ϕ _i (t) = Ф(t), i = 1, …, n; здесь Ф(t) – произвольная монотонно возрастающая (в нестрогом смысле) функция. Перестановочный прием дает следующий алгоритм синтеза оптимального расписания: заявки следует упорядочить по возрастанию показателя τ (i) – требуемой продолжительности обслуживания; полученная перестановка является оптимальным расписанием.

Перестановочный прием срабатывает, когда знак разности между величинами суммарного штрафа для расписания ρ ⁰= (1, 2,..., n) и для расписания ρ ^q, получаемого из ρ ⁰переменой местами заявок q и q + 1, зависит только от параметров переставляемых заявок. Теорема Кладова–Лившица [23] устанавливает, что перестановочный прием дает способ определения показателя, сортировка по которому приводит к оптимальному расписанию, только для трех случаев:

1) все функции индививидуального штрафа линейны:

2) все функции индививидуального штрафа экспоненциальны:

3) функции индивидуального одинаковы для всех заявок: ϕ _i (t) = Ф(t), i = 1, …, n; здесь Ф(t) – произвольная монотонно возрастающая (в нестрогом смысле) функция.

Теорема Кладова–Лившица доказана в предположении, что функции индивидуального штрафа являются достаточно глад-кими (существуют третьи производные).

Отметим, что в трех перечисленных случаях вычислительная сложность алгоритма построения оптимального расписания (число выполняемых алгоритмом элементарных операций) имеет порядок n lg n, это соответствует сложности процедуры сортировки. Если исходные данные определяют задачу, не подпадающую под какой-либо из перечисленных в теореме Кладова–Лившица случаев, то целесообразным способом ее решения является метод динамического программирования.

Рассмотрим обозначаемую символом Z задачу обслуживания множества заявок N = {1, 2, …, n } в однопроцессорной системе; единственное ограничение, налагаемое на функции индивидуального штрафа – их монотонное возрастание. Считаем, что для каждой заявки i, i = 1, …, n, известны: τ (i) – продолжительность обслуживания на процессоре и ϕ _i (t) – монотонно возрастающая в нестрогом смысле функция индивидуального штрафа; требуется построить расписание обслуживания, обеспечивающее минимальное значение суммарного по всем заявкам штрафа. Пусть S – произвольное подмножество заявок, S ⊆ {1, 2, …, n }. Через Z (S) обозначим частную задачу, получаемую из Z в предположении, что обслуживанию подлежит только совокупность заявок S, а через К (S) – минимально возможный суммарный штраф в частной задаче Z (S). Для одноэлементного множества заявок, как очевидно, имеем:

Сейчас предположим, что все значения функции К (S) для р -элементных множеств S уже найдены, здесь р ∈ {1, 2, …, n –1}. Пусть S* – произвольное (р + 1)-элементное множество заявок. Если считать, что в совокупности S* последней обслуживается заявка j, то величина индивидуального штрафа по этой заявке равна

минимально возможный суммарный по всем заявкам данной совокупности штраф в имеющейся ситуации равен

здесь S* – произвольное подмножество заявок, состоящее не менее, чем из двух элементов. Если минимум правой части (10) достигается при j = q, то последней в подмножестве S* следует обслужить заявку q. Равенства (9)–(10) – рекуррентные соотношения динамического программирования, позволяющие решить задачу Z. Подсчитывая на их основании значения функции К (S*), вычисления выполняются в порядке роста числа элементов в множествах S*, мы в итоге находим величину К (N), т.е. оптимальное значение критерия в решаемой задаче (минимальную величину суммарного штрафа).

Имеется процессор, обслуживанию которым подлежат заявки множества N = {1, 2, 3}. Известно, что τ (1) = 3; τ (2) = 2; τ (3) = 4; ϕ ₁(t) = 2 t ²; ϕ ₂(t) = 3 t; ϕ ₃(t) = t ²+ t. Требуется построить расписание, минимизирующее величину суммарного штрафа.

Далее, пользуясь формулой (10), находим последователь-но:

в левых частях записанных конкретизаций равенства (10) подчеркнуты значения параметра j, обеспечивающие минимальные значения их правых частей. Оптимальное значение критерия в рассматриваемом примере равно 101.

Благодаря сделанным в процессе вычислений подчеркиваниям, легко определяем оптимальную последовательность обслуживания заявок. Действительно, в совокупности {1, 2, 3} последней надо обслужить заявку 2 (именно этот номер был под-черкнут при определении К ({1, 2, 3})). Заявке 2, таким образом, предшествует пара заявок {1, 3}. В совокупности {1, 3} послед-ней надо обслужить заявку 3 (номер 3 был подчеркнут при определении К ({1, 3})). И, наконец, заявка 1 должна быть обслужена первой. Легко подсчитывается, что при реализации построенного расписания величина суммарного штрафа действительно равна 101.

Задача однопроцессорного обслуживания множества заявок с минимаксным критерием.

Имеется множество заявок N = = {1, 2, …, n } и процессор П, на котором должна быть обслужена каждая заявка этого множества; процессор не может обслуживать несколько (более одной) заявок одновременно; переход от обслуживания одной заявки к обслуживанию следующей за ней заявки затрат времени не требует. Обслуживание заявок начинается с момента времени t = 0. Для каждой заявки i известны: τ (i) – продолжительность обслуживания на процессоре; монотонно возрастающая (в нестрогом смысле) функция индивидуального штрафа ϕ _i (t). Если обслуживание заявки i завершает-ся в момент времени t, то ϕ _i (t) – величина штрафа по этой заявке. При реализации расписания ρ моменты завершения обслуживания заявок вычисляются по формулам (1)–(3), величина штрафа W_i (ρ) по произвольной заявке i оказывается равной ϕ _i (t* (ρ, i)), i = 1, …, n. Вводим критерий

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

Очевидно, что обслуживание процессором заявок множества N завершается в момент времени Т = τ (1) + τ (2) + … + τ (n). Под-считаем все значения ϕ _i (Т), i= 1,..., n; пусть ϕ _k (Т) – минимальная из найденных величин. Покажем, что в таком случае имеется оптимальное для задачи (11) расписание, в котором заявка k обслуживается последней. Предположим, что в некотором рас-писании ρ заявка k обслуживается j -й по очереди (j ∈ {1, 2, …, n – 1}), а последней обслуживается заявка р, причем ϕ _k (Т) < ϕ _р (Т). Очевидно, что К (ρ) ≥ ϕ _р (Т) > ϕ _k (Т). Последовательными перестановками заявки k и каждой непосредственно следующей за ней по обслуживанию заявки от расписания ρ переходим к расписанию ρ ', в котором заявка k обслуживается предпоследней. По расписанию ρ ' каждая из заявок множества N \ { k, p } завершается обслуживанием раньше, чем по расписанию ρ; за-явка р завершается обслуживанием в тот же момент времени Т. Заявка k по расписанию ρ ' завершается обслуживанием в момент Т – τ (р), но ϕ _k (Т – τ (р)) ≤ ϕ _k (Т) < ϕ _р (Т). Из изложенного вытекает, что К (ρ ') ≤ К (ρ). От расписания ρ ' перестановкой местами заявок k и р перейдем к расписанию ρ *, в котором заявка k обслуживается последней. По расписанию ρ * каждая из заявок множества N \ { k, p } завершается обслуживанием в тот же момент, что и по расписанию ρ '; заявка р завершается обслуживанием раньше, чем по расписанию ρ '. Заявка k по расписанию ρ * завершается обслуживанием в момент Т, но ϕ _k (Т) < ϕ _р (Т). Из изложенного вытекает, что К (ρ *) ≤ К (ρ '). Мы показали, что в рассматриваемой задаче однопроцессорного обслуживания всегда имеется оптимальное расписание, в котором заявка с минимальным значением индивидуального штрафа в момент времени Т обслуживается последней. Отсюда вытекает следующий алгоритм синтеза оптимального расписания ρ ** = (i ₁, i ₂,..., i_n):

1. Полагаем N = {1, 2, …, n }; Т = τ (1) + τ (2) + … +τ (n); r = n.

2. Для каждой заявки i из N находим значение ϕ _i (Т); пусть ϕ _k (Т) – минимальное из найденных значений (если ϕ _i (Т) минимально при нескольких значениях индекса i, в качестве k берем любое из них).

4. Изымаем из множества N заявку k; значение Т уменьшаем на τ (k); значение параметра r уменьшаем на единицу.

5. Если r =0, искомое расписание построено; в противном случае переходим к п. 2. алгоритма.

Задача однопроцессорного обслуживания множества заявок при наличии директивных сроков.

Считается заданным множество заявок {1, 2, …, n } и процессор П, на котором должна быть обслужена каждая заявка; процессор не может обслуживать несколько (т.е. более одной) заявок одновременно; переход от обслуживания одной заявки к обслуживанию следующей за ней заявки затрат времени не требует. Обслуживание заявок начинается от момента времени t = 0. Для каждой заявки i известны две характеристики: τ (i) – продолжительность ее обслуживания на процессоре; d (i) – директивный срок, не позднее которого обслуживание заявки должно завершиться; здесь τ (i) > 0, d (i) > 0, i =1,..., n. Расписание обслуживания отождествляем с перестановкой ρ = (i ₁, i ₂,..., i_n) элементов множества {1, 2,..., n }; заявка i_k в расписании ρ обслуживается k- й по очереди. Расписание ρ для каждой заявки i однозначно определяет момент завершения ее обслуживания t* (ρ, i). Считаем, что заявка i в расписании ρ обслуживается с соблюдением директивного срока, если t* (ρ, i) ≤ d (i). Проблема заключается в построении расписания, в котором для наибольшего числа заявок директивные сроки соблюдаются.

Сначала рассмотрим частный случай, в котором директивный срок одинаков для всех заявок: d (1) = d (2) = … = d (n) = D. Решаемая задача в данном частном случае путем дополнительного введения одной и той же для всех заявок функции индивидуального штрафа Ф(t) сводится к рассмотренной выше задаче однопроцессорного обслуживания множества заявок с критерием суммарного штрафа. Функция Ф(t) вводится следующим образом:

Благодаря способу задания функции Ф(t), при реализации произвольного расписания ρ суммарный по всем заявкам штраф оказывается равным числу заявок, которые по этому расписанию обслуживаются с нарушением директивного срока D. Решая задачу минимизации суммарного штрафа, мы фактически строим расписание, в котором для наибольшего числа заявок директивный срок соблюдается. Так как функция индивидуального штрафа для всех заявок одна и та же, оптимальное расписание строится просто: заявки следует обслуживать в порядке возрастания характеристики τ (i).

Сейчас задачу обслуживания множества заявок при наличии директивных сроков рассмотрим в изложенной выше общей постановке. Систему директивных сроков { d (1), d (2), …, d (n)} именуем реальной, если существует расписание обслуживания ρ такое, что для каждого i = 1,..., n выполняется неравенство t* (ρ, i) ≤ d (i). Пусть (i ₁, i ₂,..., i_n) – перестановка, перечисляющая заявки в порядке возрастания директивных сроков. Очевидно, что указанная система { d (1), d (2), …, d (n)} реальна тогда и только тогда, когда расписание ρ = (i ₁, i ₂,..., i_n) обеспечивает соблюдение каждого из указанных для заявок сроков.

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

Строим перестановку (i ₁, i ₂,..., i_n), перечисляющую заявки в порядке возрастания директивных сроков. Если при реализации расписания ρ * = (i ₁, i ₂,..., i_n) каждая заявка обслуживается с соблюдением директивных сроков, то расписание ρ * оптимально. В случае, когда при реализации расписания ρ * оказывается нарушенным только один из директивных сроков, это расписание также оптимально.

В остальных случаях действуем по следующему алгоритму:

1) полагаем ρ = ρ *; множество W считаем пустым (далее во множество W будут вноситься заявки, которые по конструируемому расписанию обслуживаются с нарушением директивных сроков);

2) последовательность ρ трактуем как расписание обслуживания входящих в нее заявок;

3) если все входящие в ρ заявки обслуживаются с соблюдением директивных сроков или если последовательность ρ оказалась пустой, то переходим к п. 8; в противном случае – к п. 4.

4) в последовательности ρ находим минимальное q такое, что заявка i_q по расписанию ρ обслуживается с нарушением директивного срока;

5) в совокупности заявок { i ₁, i ₂,..., i_q } находим заявку i_х, продолжительность обслуживания которой максимальна;

6) новую последовательность ρ получаем из предшествующей изъятием из нее заявки i_х (все остальные заявки перечисляются в прежнем порядке); Заявку i_х включаем в множество W.

8) искомое оптимальное расписание ρ ** определяем как последовательность, состоящую из двух частей: последовательность ρ (начальная часть расписания ρ **); перечень элементов множества W в любом порядке (заключительная часть расписания ρ **).

Обоснование изложенного алгоритма выполняется рассуждениями от противного.

Легко определяется, что оценка временной вычислительной сложности алгоритма Сn ², где С – некоторая не зависящая от n константа.

Имеется комплект К, состоящий из деталей D ₁, D ₂, …, D_m; все детали должны быть обработаны на станках S ₁, S ₂, …, S_n. Каждая деталь в процессе обработки должна пройти все станки последовательно, в порядке роста их номеров (индексов). Для каждой детали D_i задано требуемое время τ _ij ее обработки на станке S_j; считаем, что все τ _ij – целые положительные числа, i = 1, …, m, j = 1, …, n. В любой момент времени каждый станок может обрабатывать только одну деталь. Работа каждого станка над любой деталью выполняется без прерываний. Работа над комплектом начинается от момента t = 0, по состоянию на этот момент все станки считаются свободными. Расписание в ЗД- n определяем как кортеж ρ = {ρ ₁, ρ ₂, …, ρ _n }, где ρ _j – номеров деталей, определяющая последовательность их обработки на станке S_j, j = 1, …, n. Требуется найти расписание, при реализации которого момент готовности комплекта (т.е. момент завершения работы станка S_n) оказывается минимальным. Джонсон доказал, что в любой задаче описанного типа всегда имеется оптимальное расписание ρ, в котором одновременно ρ ₁= ρ ₂и ρ _n _–1= ρ _n, т.е. последовательности обработки деталей на первом и втором станках совпадают и последовательности обработки деталей на предпоследнем и последнем станках также совпадают. Отсюда вытекает, что в задачах Джонсона для двух и трех станков всегда имеются оптимальные расписания, в которых последовательности обработки деталей на всех станках одинаковы. Легко строится пример задачи Джонсона для четырех станков, в которой имеется единственное оптимальное расписание и оно предусматривает, что первые два станка проходятся деталями в одной последовательности, а два следующих станка – в последовательности, отличающейся от предыдущей.

Для задач Джонсона с двумя или тремя станками оптимальное расписание конструируется как перестановка ρ элементов множества {1, 2, …, m }, определяющая единую последовательность обработки деталей на всех станках. Синтез оптимального расписания может быть выполнен на основе соответствующим образом построенных соотношений динамического программирования. При этом запись и анализ уравнения динамического программирования для задачи Джонсона с двумя станками дает возможность простого и быстрого определения оптимального расписания.

Для каждой детали D_i считаем, что а_i – требуемое время ее обработки на станке S₁, а b_i – требуемое время ее обработки на станке S₂, i = m, 1. Момент принятия решения (МПР) – это любой момент, когда станок S ₁свободен и требуется определить следующую деталь, которая начиная от данного МПР на нем будет обрабатываться. Каждый МПР характеризуется следующими факторами: М – совокупность деталей, обработка которых пока не начиналась; Т ₂– продолжительность отрезка времени, на котором позднее рассматриваемого МПР станок S ₂еще будет загружен обработкой деталей, уже прошедших станок S ₁. Через F (М, Т ₂) обозначим минимально возможную продолжительность отрезка времени от рассматриваемого МПР до момента завершения изготовления комплекта деталей К. Как очевидно,

– минимальное время, за которое комплект может быть изготовлен. Предположим, что в МПР, характеризуемый парой (М, Т ₂), на обработку станком следует направить деталь D_х, а в следующий МПР – деталь D_у (D_х ∈ M, D_у ∈ M). В таком случае сначала имеем:

F (М, Т ₂) = а_х + F (М \ { D_х }, b_х + max [(Т ₂– а_х), 0]).

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

F (М \ { D_х}, b_х + max [(Т ₂– а_х), 0]) = а_у + F (M \ { D_х, D_у },

К_ху = b_у + max[(b_х + max [(Т ₂– а_х), 0] – а_у), 0]) = b_у + b_х – а_у +

+ max {max[(Т ₂– а_х), 0], а_у – b_х } = b_у + b_х – а_у +

+ max{ Т ₂– а_х, 0, а_у – b_х } = b_у + b_х – а_у – а_x +

+ max{ Т ₂, а_х, а_х + а_у – b_х } = b_у + b_х - а_у – а_x +

max (а_х, а_х + а_у – b_х) > max (а_у, а_х + а_у – b_у),

то детали D_х и D_у имеет смысл поменять местами. Полученное правило можно переписать в виде

а_х + а_у + max (– а_у, – b_х) > а_х + а_у + max (– а_х, – b_у)

Последнее неравенство эквивалентно следующему:

Так получаем следующий алгоритм определения оптимального в ЗД-2 расписания (последовательности обработки деталей). Считаем, что исходная информация по задаче записана в виде матрицы А размера m × 2, в первом столбце которой последовательно, сверху вниз, перечислены времена обработки деталей на первом станке а ₁, а ₂, …, а_m; а во втором столбце также последовательно, сверху вниз, перечислены времена обработки деталей на втором станке b ₁, b ₂, …, b_m. Для записи оптимального расписания выделяем набор W из m изначально пустых, идущих слева направо позиций. Далее руководствуемся инструкцией:

1. Выделить наименьший непомеченный элемент матрицы А (изначально все элементы матрицы А считаются непомеченными).

2. Если выделен некоторый элемент а_i левого столбца, вписать D_i в крайне левую пустую позицию набора W; Если выделен некоторый элемент b_i правого столбца, вписать D_i в крайне правую пустую позицию набора W.

3. Если в наборе W пустых позиций нет, перейти к п. 5; в противном случае – к п. 4.

4. В матрице пометить оба элемента i -й строки; перейти к п. 1.

5. В позициях W зафиксировано оптимальное расписание. Запуск деталей в обработку должен осуществляться в порядке их перечисления (слева направо) в позициях набора W.

Отметим, что выполнение приведенной инструкции не всегда является однозначно определенной процедурой, но любая реализация инструкции строит оптимальное расписание (оптимальное для ЗД-2 расписание, вообще говоря, не единственно).

Задача Джонсона для двух станков определена матрицей

Требуется найти оптимальную последовательность обработки деталей.

В синтезируемом по приведенной инструкции оптимальном расписании последней (минимальным элементом матрицы является единица, стоящая в третьей строке правого столбца) должна обрабатываться деталь D ₃, она записывается в крайне правую позицию набора W. Далее в крайне левую и крайне правую свободные позиции (минимальными непомеченными элементами матрицы оказываются две двойки, в левом и правом столбцах) вписываются детали D ₁и D ₆соответственно. Затем в крайнюю левую и крайнюю правую свободные позиции (минимальными непомеченными элементами матрицы оказываются две тройки, в левом и правом столбцах) вписываются детали D ₅и D ₇соответственно. Далее минимальным непомеченным элементом матрицы оказывается четверка в правом столбце, соответствующая деталь D ₄вписывается в крайне правую свободную позицию набора W. Последней на оставшееся свободным место вносится деталь D ₂. Таким образом устанавливается, что оптимальной является следующая последовательность обработки деталей: D ₁, D ₅, D ₂, D ₄, D ₇, D ₆, D ₃.