Студопедия

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

Разделы сайта

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






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






Задача мастера.

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

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

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

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

t нач(ρ, ik) = t* (ρ, ik − 1), k = 2, 3,..., n. (3)

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

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

(4)

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

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

и

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

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

а (q + 1)τ (q) – а (q)τ (q + 1) ≤ 0,

т.е.

а (q)τ (q + 1) ≥ а (q + 1)τ (q).

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

{ а (q)/τ (q)} ≥ { а (q + 1)/τ (q + 1)} (5)

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

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

Двухпроцессорная задача мастера.

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

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

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

Таблица 2.1 Характеристики заявок

  a (i) τ (i) μ (i)
Заявка 1      
Заявка 2      
Заявка 3      

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

Для синтеза оптимального в двухпроцессорной задаче мастера расписания применим метод динамического программирования. Будем считать, что все заявки пронумерованы в порядке убывания значений показателя μ. Тогда если ρ = (ρ 1, ρ 2) оптимальное расписание, то заявки в каждой из последовательностей ρ 1= (i 1, i 2, i 3, …, ip) и ρ 2 = (j 1, j 2, j 3, …, jq) записаны в порядке возрастания номеров.

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

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

W*(1, τ (1)) = W*(1, 0) = a(1)τ (1) (6)

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

W* (1, Δ)= + ∞, если Δ ∉ {0, τ (1)}; (7)

далее для любых нереализуемых ситуаций (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 выполняется процессором Р 2; обслуживание этой заявки начинается в момент времени

и завершается в момент

.

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

Отсюда получаем:

(8)

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

{0, 1, …, },

поэтому общее число столбцов таблицы равно

.

Строки таблицы заполняются сверху вниз, в порядке роста значений параметра 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. При реализации расписания ρ величина штрафа Wi (ρ) по произвольной заявке i оказывается равной ϕ i (t* (ρ, i)), где t* (ρ, i) – момент завершения обслуживания заявки i при реализации расписания ρ. Требуется найти расписание, минимизирующее величину суммарного по всем заявкам штрафа.

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

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

ϕ i (t) = аi ехр (α t) + bi, i = 1, …, n;

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

ν (i) = (1 – ехр (α τ (i))/ аi;

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

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

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

ϕ i (t) = аi t + bi, i = 1, …, n;

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

ϕ i (t) = аi ехр(α t) + bi, i = 1, …, n.

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). Для одноэлементного множества заявок, как очевидно, имеем:

К ({ i }) = ϕ i (τ (i)), iN. (9)

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

,

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

Получаем:

(10)

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

Пример 2.2.

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

По формуле (9) вычисляем:

К ({1}) =ϕ 1(3) = 18; К({2}) = ϕ 2(2) = 6; К({3}) = ϕ 3(4) = 20.

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

К ({1, 2 }) = min{ К ({2}) + ϕ 1(5),

К ({1}) + ϕ 2(5)} = min{6 + 50, 18 + 15} = 33;

К ({1, 3 }) = min{К({3}) + ϕ 1(7),

К ({1}) + ϕ 3(7)} = min{20 + 98, 18 + 56} = 74;

К ({ 2, 3}) = min{ К ({3}) + ϕ 2(6),

К ({2}) + ϕ 3(6)} = min{20 + 18, 6 + 42} = 38;

К ({1, 2, 3}) = min{ К ({2, 3}) + ϕ 1(9), К ({1, 3})+ ϕ 2(9),

К ({1, 2}) + ϕ 3(9)} = min{38 + 162, 74 + 27, 33 + 90} = 101;

в левых частях записанных конкретизаций равенства (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), величина штрафа Wi (ρ) по произвольной заявке i оказывается равной ϕ i (t* (ρ, i)), i = 1, …, n. Вводим критерий

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

(11)

Очевидно, что обслуживание процессором заявок множества 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 1, i 2,..., in):

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

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

3. Полагаем ir = 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 1, i 2,..., in) элементов множества {1, 2,..., n }; заявка ik в расписании ρ обслуживается 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 1, i 2,..., in) – перестановка, перечисляющая заявки в порядке возрастания директивных сроков. Очевидно, что указанная система { d (1), d (2), …, d (n)} реальна тогда и только тогда, когда расписание ρ = (i 1, i 2,..., in) обеспечивает соблюдение каждого из указанных для заявок сроков.

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

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

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

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

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

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

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

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

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

7) переходим к п. 2;

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

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

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

Задача Джонсона для n станков (ЗД-n).

Имеется комплект К, состоящий из деталей D 1, D 2, …, Dm; все детали должны быть обработаны на станках S 1, S 2, …, Sn. Каждая деталь в процессе обработки должна пройти все станки последовательно, в порядке роста их номеров (индексов). Для каждой детали Di задано требуемое время τ ij ее обработки на станке Sj; считаем, что все τ ij – целые положительные числа, i = 1, …, m, j = 1, …, n. В любой момент времени каждый станок может обрабатывать только одну деталь. Работа каждого станка над любой деталью выполняется без прерываний. Работа над комплектом начинается от момента t = 0, по состоянию на этот момент все станки считаются свободными. Расписание в ЗД- n определяем как кортеж ρ = {ρ 1, ρ 2, …, ρ n }, где ρ j – номеров деталей, определяющая последовательность их обработки на станке Sj, j = 1, …, n. Требуется найти расписание, при реализации которого момент готовности комплекта (т.е. момент завершения работы станка Sn) оказывается минимальным. Джонсон доказал, что в любой задаче описанного типа всегда имеется оптимальное расписание ρ, в котором одновременно ρ 1 = ρ 2 и ρ n –1 = ρ n , т.е. последовательности обработки деталей на первом и втором станках совпадают и последовательности обработки деталей на предпоследнем и последнем станках также совпадают. Отсюда вытекает, что в задачах Джонсона для двух и трех станков всегда имеются оптимальные расписания, в которых последовательности обработки деталей на всех станках одинаковы. Легко строится пример задачи Джонсона для четырех станков, в которой имеется единственное оптимальное расписание и оно предусматривает, что первые два станка проходятся деталями в одной последовательности, а два следующих станка – в последовательности, отличающейся от предыдущей.

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

Задача Джонсона для двух станков (ЗД-2).

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

F ({ D 1, D 2, …, Dm }, 0)

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

F (М, Т 2) = ах + F (М \ { Dх }, bх + max [(Т 2 ах), 0]).

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

F (М \ { Dх}, bх + max [(Т 2 ах), 0]) = ау + F (M \ { Dх, Dу },

bу + max[(bх + max [(Т 2 ах), 0] – ау), 0]).

Далее имеем:

F (М, Т 2) = ах + ау + F (M \ { Dх, Dу }, Кху),

где

Кху = bу + max[(bх + max [(Т 2 ах), 0] – ау), 0]) = bу + bх ау +

+ max {max[(Т 2 ах), 0], ау bх } = bу + bх ау +

+ max{ Т 2 ах, 0, ау bх } = bу + bх ау аx +

+ max{ Т 2, ах, ах + ау bх } = bу + bх - ау аx +

+ max{ Т 2, max(ах, ах + ау bх)}.

Оказывается очевидным, что если

max (ах, ах + ау bх) > max (ау, ах + ау bу),

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

ах + ау + max (– ау, – bх) > ах + ау + max (– ах, – bу)

или, что еще проще, как

max (– ау, – bх) > max (– ах, – bу).

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

min(bх, ау) > min(by, аx).

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

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

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

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

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

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

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

Пример 2.3.

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

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

В синтезируемом по приведенной инструкции оптимальном расписании последней (минимальным элементом матрицы является единица, стоящая в третьей строке правого столбца) должна обрабатываться деталь D 3, она записывается в крайне правую позицию набора W. Далее в крайне левую и крайне правую свободные позиции (минимальными непомеченными элементами матрицы оказываются две двойки, в левом и правом столбцах) вписываются детали D 1 и D 6 соответственно. Затем в крайнюю левую и крайнюю правую свободные позиции (минимальными непомеченными элементами матрицы оказываются две тройки, в левом и правом столбцах) вписываются детали D 5 и D 7 соответственно. Далее минимальным непомеченным элементом матрицы оказывается четверка в правом столбце, соответствующая деталь D 4 вписывается в крайне правую свободную позицию набора W. Последней на оставшееся свободным место вносится деталь D 2. Таким образом устанавливается, что оптимальной является следующая последовательность обработки деталей: D 1, D 5, D 2, D 4, D 7, D 6, D 3.

 






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.