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

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

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

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

Задача синтеза оптимального расписания для системы с параллельными процессорами. Каждую заявку входного потока R = {1, 2,..., n } следует обслужить одним из m идентичных процессоров Π _j (j=1, …, m). Полагаем, что процессор Π _j готов к обслуживанию заявок потока R начиная от целочисленного момента времени T_j (0 = T ₁≤ T₂ ≤.... ≤ T_m). Одновременное обслуживание любым процессором более чем одной заявки считается невозможным; обслуживание каждой заявки осуществляется без прерываний; в момент завершения обслуживания очередной заявки каждый процессор считается готовым к обслуживанию следующей.

Каждая заявка i входного потока характеризуется тремя целочисленными параметрами: t (i) − момент поступления в систему обслуживания (0 = t (1) ≤ t (2) ≤ … ≤ t (n − 1) ≤ t (n)); τ (i) − требуемая продолжительность обслуживания любым из процессоров (τ (i) > 0); a (i) − штраф за единицу времени (такт) пребывания в системе обслуживания.

Если обслуживание заявки i завершается в момент времени t^* (i), то а (i)× (t^* (i) − t (i)) − индивидуальный штраф по данной заявке.

Расписание обслуживания ρ представляет собой кортеж < ρ ¹, ρ ², …, ρ ^m >, где

– последовательность обслуживания заявок процессором Π _j: первой на данном процессоре обслуживается заявка

, второй – заявка

, …, последней – заявка

(j=1, …, m). Каждая заявка потока R входит только в одну из составляющих кортеж последовательностей. Таким образом, v (1) + v (2) + …. + v (m) = n. По смыслу задачи параметры расписания v (j), j=1, …, m, неотрицательны, а равенство v (j’) = 0 означает, что по расписанию ρ процессор Π _j’ не принимает участия в обслуживании заявок потока R.

Обозначим через

соответственно моменты начала и завершения обслуживания заявки при реализации расписания ρ (r=1, v(j), j =1, …, m).

Считаем, что реализация расписания компактна, т.е. имеют место соотношения

Общий штраф U_j (ρ) по заявкам потока R, которые по расписанию ρ обслуживаются процессором Π _j, подсчитывается по формуле

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

Рассмотрим вопрос о решении сформулированной задачи методом динамического программирования. В связи с целочисленностью всех определяющих задачу параметров время считается дискретным.

При обслуживании потока R управленческие решения принимаются для тех моментов времени, когда по меньшей мере один процессор свободен. Каждое решение состоит в выборе заявки, которая немедленно поступает на обслуживание свободным процессором. Если таких процессоров несколько, полагаем, что для обслуживания выбранной заявки назначается свободный процессор с минимальным номером; такой процессор будем называть первым свободным процессором. Текущее состояние в момент принятия решения t определяется как набор F = (t, S, γ ₁, γ ₂, …, γ _m), где S – множество заявок, которые прибыли и ожидают обслуживания, а γ _j – число тактов дискретного времени, оставшихся до освобождения процессора Π _j, j = 1, …, m. Так как t – МПР, по меньшей мере одно из чисел γ _j равно нулю. Выбор очередной обслуживаемой заявки осуществляется из совокупности S.

Через D (t, μ) обозначаем множество заявок, прибывающих в систему обслуживания на временном отрезке [ t + 1, t + μ ], здесь μ – целое неотрицательное число; отметим, что D (t, 1) – совокупность заявок, прибывающих на обслуживание в момент времени t + 1; дополнительно полагаем, что D (t, 0) = ∅. Для любого состояния F = (t, S, γ ₁, γ ₂, …, γ _m), множество S считаем непустым, что обеспечивается обязательным включением в него нулевой (фиктивной) заявки 0 с параметрами а (0) = 0, t (0) = t и τ (0) = = min {θ | D (t, t +θ) ≠ ∅ }. Взятие на обслуживание фиктивной заявки означает простой процессора от момента t до ближайшего момента поступления в систему какой-либо новой заявки потока R. Если поступившая фиктивная заявка не принимается на немедленное обслуживание, то она выпадает из дальнейшего рассмотрения. Как и в случае однопроцессорной системы, иногда принятие на обслуживание фиктивной заявки целесообразно и при наличии в S заявок, не являющихся фиктивными.

Пусть W (t, S, γ ₁, γ ₂, …, γ _m) обозначает минимальную величину суммарного штрафа по заявкам множества S и заявкам, которые поступят в систему обслуживания позднее момента времени t при условии, что (t, S, γ ₁, γ ₂, …, γ _m) – текущее состояние системы.

Предположим, что в состоянии F = (t, S, γ ₁, γ ₂, …, γ _m) из совокупности S выбрана и направлена на немедленное обслуживание первым свободным процессором Π _j заявка i. Тогда следующим моментом принятия решения является t + ω, где ω = = min (γ ₁, γ ₂, …, γ _j _{− 1}, τ (i), γ _j ₊₁, …, γ _m). Отметим, что если в рассматриваемом состоянии F свободны несколько процессоров, то ω = 0 и следующее решение по загрузке принимается в тот же момент времени t. По состоянию на момент t + ω совокупность ожидающих обслуживания заявок состоит из двух подмножеств, S \ { i } и D (t, ω). Таким образом, состояние системы в следующий момент принятия решения характеризуется как набор (t + ω, (S \ { i }) ∪ D (t, ω), γ ₁− ω, γ ₂− ω, …, γ _j _{− 1}− ω, τ (i) − ω, γ _j ₊₁− ω, …, γ _m − ω). В принятых обозначениях рекуррентное соотношение динамического программирования записывается в виде:

здесь j – минимальное значение индекса, при котором компонента γ _j в кортеже (γ ₁, γ ₂, …, γ _j, …, γ _m) равна нулю.

Если в соотношении (26) минимум реализуется при i = i`, то в момент времени t на первый свободный процессор следует направить заявку i` из совокупности S. Направление на обслуживание нулевой заявки означает простой процессора по меньшей мере до следующего момента пополнения множества S прибывающими заявками. Если в момент принятия решения t на первый свободный процессор направляется нулевая заявка, то одновременно такие же нулевые заявки направляются на остальные свободные процессоры.

В силу значительной вычислительной сложности изложенной процедуры для рассматриваемой задачи актуальна разработка реализуемых в приемлемом времени эвристических алгоритмов. Один из таких алгоритмов предложен далее, в гл. 3.

Перейдем к рассмотрению задач обслуживания потока поступающих в дискретном времени заявок R = {1, 2,..., n } в системе, состоящей из двух последовательных процессоров Π _j, j = 1, 2.

Задача синтеза оптимального расписания для системы с двумя последовательными процессорами. В рассматриваемой задаче считаем, что каждая поступающая заявка сначала обслуживается первым, а затем вторым процессором. Полагаем, что первый процессор готов к обслуживанию заявок потока начиная от момента времени 0, а второй процессор − от момента времени Т ₀. Одновременное обслуживание любым процессором более чем одной заявки считается невозможным; обслуживание каждой заявки осуществляется без прерываний, в момент завершения обслуживания очередной заявки каждый процессор считается готовым к обслуживанию следующей. Каждая заявка i потока R характеризуется целочисленными параметрами: t (i) − момент поступления в систему обслуживания (0 = t (1) ≤ t (2) ≤ … ≤ t (n – 1) ≤ t (n)); τ ₁(i) − требуемая продолжительность обслуживания первым процессором (τ ₁(i) > > 0); τ ₂(i) − требуемая продолжительность обслуживания вторым процессором (τ ₂(i) > 0); a (i) − штраф за единицу времени (такт) пребывания в системе обслуживания.

Момент полного завершения обслуживания заявки − это момент завершения ее обслуживания вторым процессором.

Расписание обслуживания ρ представляет собой кортеж < ρ ¹, ρ ²>, где ρ ¹= { i ₁, i ₂, …, i_n } и ρ ²= { j ₁, j ₂, …, j_n } – последовательности индексов заявок, определяющие порядок их обслуживания на первом и втором процессорах соответственно. Пусть t ₁^нач(ρ, i_k) и t ₁*(ρ, i_k) обозначают моменты начала и завершения обслуживания заявки i_k на первом процессоре при реализации расписания ρ; аналогично t ₂^нач(ρ, j_k) и t ₂*(ρ, j_k) − моменты начала и завершения обслуживания вторым процессором заявки j_k при реализации того же расписания, k = 1,..., n.

Считаем, что реализация расписания компактна, т.е. имеют место соотношения

t ₁^нач(ρ, i _k) = max [ t ₁*(ρ, i_k _{− 1)}, t (i_k)], k = 2, 3,..., n;

t ₂^нач(ρ, j_k) = max [ t ₂*(ρ, j_k _{− 1}), t ₁*(ρ, j_k)], k = 2, 3,..., n;

Величина суммарного штрафа по всем заявкам при реализации расписания ρ вычисляется по формуле

Рассматриваемая оптимизационная задача формулируется следующим образом:

Отметим, что в некоторых производственно-транспортных системах возникает специфическая и более простая задача, когда между первым и вторым процессором заявки переставлять нельзя, т.е. последовательности обслуживания заявок на первом и втором процессорах должны совпадать. Данное ограничение является существенным; его наложение, вообще говоря, вызывает рост оптимального значения критерия. Приведем пример. Пусть R = {1, 2}, в момент времени 0 свободны оба процессора, характеристики заявок следующие: t (1) = 0, t (2) = 10; τ ₁(1) = 10, τ ₂(1) = 10, τ ₁(2) = 1, τ ₂(2) = 1; a (1) = 1, a (2) = 10. Легко проверяется, что единственным оптимальным для задачи (27) в общей постановке является расписание < ρ ¹, ρ ²>, где ρ ¹= {1, 2}, а ρ ²= = {2, 1}.

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

Состояние системы определяем как набор F = (t, S ₁, S ₂, d, T, ξ). Здесь t − МПР (в момент времени t по меньшей мере один процессор свободен); S ₁− совокупность заявок, которые к рассматриваемому МПР поступили и ожидают обслуживания первым процессором; S ₂− совокупность заявок, которые к рассматриваемому МПР прошли обслуживание первым процессором и ожидают обслуживания вторым процессором; d − номер процессора, который в момент времени t свободен (d равно 1 или 2); Т − число тактов дискретного времени, оставшегося до освобождения занятого процессора; если Т = 0, то по состоянию на момент времени t свободны оба процессора; ξ − номер заявки, которая в данный момент времени обслуживается первым процессором (в случае, когда d = 1, т.е. первый процессор свободен, полагаем ξ = 0).

Через W (t, S ₁, S ₂, d, T, ξ) обозначим минимальную величину суммарного штрафа по заявкам множеств S ₁, S ₂и заявкам, которые поступят позднее момента времени t, для системы, находящейся в состоянии (t, S ₁, S ₂, d, T, ξ); здесь t − момент принятия решения.

Как и ранее, V (t) обозначает совокупность заявок, поступающих на обслуживание в произвольный момент времени t. Таким образом, шестерка (0, V (0), ∅, 1, Т ₀, 0) − это начальное состояние системы, а W (0, V (0), ∅, 1, Т ₀, 0) − искомое оптимальное значение критерия в рассматриваемой задаче (минимально возможное значение суммарного по всем заявкам штрафа). За-пишем рекуррентные соотношения, позволяющие организовать процесс последовательного вычисления значений функции W (t, S ₁, S ₂, d, T, ξ) вплоть до отыскания величины W (0, V (0), ∅, 1, Т ₀, 0).

Вначале отметим, что при t > t (n) значения W (t, ∅, S ₂, 1, 0, 0) вычисляются без затруднений, ибо в таком случае шестерка (t, ∅, S ₂, 1, 0, 0) определяет относящуюся ко второму процессору задачу мастера, оптимальное расписание в которой строится крайне просто (см. п. 1 данной главы).

Далее при записи рекуррентных соотношений, необходимых для вычисления значений функции W (t, S ₁, S ₂, d, T, ξ) на других наборах значений ее аргументов, нам будет удобно использовать функции f (α, T), ϕ (α, T) и ψ (α, β), в которых α и β принимают значения на множестве номеров заявок, а Т − на множестве целых неотрицательных чисел, не превышающих максимальной из заданных для заявок продолжительностей обслуживания первым и вторым процессором. Функция f (α, T) принимает значение 1, если T – τ ₁(α) ≥ 0, и значение 0 в противном случае. Функция ϕ (α, T) принимает значение 1, если T – τ ₂(α) > > 0, и значение 0 в противном случае. Функция ψ (α, β) принимает значение 1, если τ ₁(α) ≤ τ ₂(β), и значение 0 в противном случае. Считаем, что в совокупность S ₁всегда входит нулевая (фиктивная) заявка с продолжительностью обслуживания на первом процессоре 1, а на втором − 0; в совокупность S ₂всегда входит нулевая (фиктивная) заявка с продолжительностью обслуживания на первом процессоре 0, а на втором − 1; штраф по фиктивной заявке всегда нулевой. Кроме того, дополнительно положим, что для отрицательных значений аргумента Т значение функции W(t, S ₁, S ₂, d, T, ξ) равно нулю.

Формулы (28) – (30) являются рекурсивными соотношениями динамического программирования для решения задачи (27).

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

В частной задаче момент времени t называем моментом принятия решения (МПР), если в данный момент свободен первый процессор. Состояние системы − это тройка объектов (t, S, T), где t − МПР; S − совокупность прибывших и по ситуации на момент времени t ожидающих обслуживания на первом процессоре заявок; Т − время, оставшееся (в ситуации на момент t) до освобождения второго процессора от работ по обслуживанию тех заявок, которые уже прошли первый процессор.

Пусть W' (t, S, T) − минимальный суммарный штраф по заявкам множества S и заявкам, которые прибудут на обслуживание позднее момента t, для системы, находящейся в состоянии (t, S, T).

Ясно, что начатая в момент времени t обслуживанием на первом процессоре заявка i из совокупности S на втором процессоре будет начата обслуживанием в момент t + max (τ ₁(i), T); поэтому величина индивидуального штрафа по этой заявке окажется равной a (i)× (t + max(τ ₁(i), T) + τ ₂(i) − t (i)). Cледующим МПР будет t* = t + τ ₁(i); по состоянию на МПР t* до освобождения второго процессора останется max (τ ₁(i), T) + τ ₂(i) − τ ₁(i) единиц времени. Отсюда получаем следующее рекуррентное соотношение:

Итоговым результатом вычислений по этому соотношению является величина W' (0, V (0), T ₀) − оптимальное значение критерия в рассматриваемой частной задаче.