Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






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

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

Каждая заявка 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)) − индивидуальный штраф по данной заявке.

Расписание обслуживания ρ представляет собой кортеж < ρ 1, ρ 2, …, ρ 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).

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

(22)

r=2, …, v(j) (23)

r = 1, …, v(j) (24)

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

 

j = 1, …, m

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

(25)

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

При обслуживании потока R управленческие решения принимаются для тех моментов времени, когда по меньшей мере один процессор свободен. Каждое решение состоит в выборе заявки, которая немедленно поступает на обслуживание свободным процессором. Если таких процессоров несколько, полагаем, что для обслуживания выбранной заявки назначается свободный процессор с минимальным номером; такой процессор будем называть первым свободным процессором. Текущее состояние в момент принятия решения t определяется как набор F = (t, S, γ 1, γ 2, …, γ 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, γ 1, γ 2, …, γ m), множество S считаем непустым, что обеспечивается обязательным включением в него нулевой (фиктивной) заявки 0 с параметрами а (0) = 0, t (0) = t и τ (0) = = min {θ | D (t, t +θ) ≠ ∅ }. Взятие на обслуживание фиктивной заявки означает простой процессора от момента t до ближайшего момента поступления в систему какой-либо новой заявки потока R. Если поступившая фиктивная заявка не принимается на немедленное обслуживание, то она выпадает из дальнейшего рассмотрения. Как и в случае однопроцессорной системы, иногда принятие на обслуживание фиктивной заявки целесообразно и при наличии в S заявок, не являющихся фиктивными.

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

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

(26)

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

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

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

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

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

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

Расписание обслуживания ρ представляет собой кортеж < ρ 1, ρ 2>, где ρ 1 = { i 1, i 2, …, in } и ρ 2 = { j 1, j 2, …, jn } – последовательности индексов заявок, определяющие порядок их обслуживания на первом и втором процессорах соответственно. Пусть t 1нач(ρ, ik) и t 1*(ρ, ik) обозначают моменты начала и завершения обслуживания заявки ik на первом процессоре при реализации расписания ρ; аналогично t 2нач(ρ, jk) и t 2*(ρ, jk) − моменты начала и завершения обслуживания вторым процессором заявки jk при реализации того же расписания, k = 1,..., n.

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

t 1нач (ρ, i 1) = t (i 1);

t 1нач (ρ, i k) = max [ t 1*(ρ, ik − 1), t (ik)], k = 2, 3,..., n;

t 1*(ρ, ik) = t 1нач (ρ, ik) + τ 1(ik), k = 1, 2,..., n;

t 2нач (ρ, j 1) = max (t 1*(ρ, j 1), Т 0);

t 2нач (ρ, jk) = max [ t 2*(ρ, jk − 1), t 1*(ρ, jk)], k = 2, 3,..., n;

t 2*(ρ, jk) = t 2нач (ρ, jk) + τ 2 (jk), k = 1, 2,..., n.

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

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

(27)

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

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

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

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

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

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

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

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

Для случая Т0 имеем:

(28)

(29)

Для случая Т = 0 имеем:

(30)

Формулы (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 (τ 1(i), T); поэтому величина индивидуального штрафа по этой заявке окажется равной a (i)× (t + max(τ 1(i), T) + τ 2(i) − t (i)). Cледующим МПР будет t* = t + τ 1(i); по состоянию на МПР t* до освобождения второго процессора останется max (τ 1(i), T) + τ 2(i) − τ 1(i) единиц времени. Отсюда получаем следующее рекуррентное соотношение:

(31)

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

 


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.011 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал