close

Вход

Забыли?

вход по аккаунту

?

Эффективное построение множества расписаний с минимальным суммарным временем завершения работ.

код для вставкиСкачать
б) поток сохраняется в каждой вершине, за исключением истока s и стока t.
УДК 658.52.011.56
ЭФФЕКТИВНОЕ ПОСТРОЕНИЕ
МНОЖЕСТВА РАСПИСАНИЙ С
Поток оптимален, если его величина равна n, а его
стоимость cost =
МИНИМАЛЬНЫМ СУММАРНЫМ
ВРЕМЕНЕМ ЗАВЕРШЕНИЯ РАБОТ
СКАКАЛИНА Е.В.
Предлагается эффективный алгоритм построения всех
расписаний с минимальным суммарным временем
завершения n работ, выполняемых на m неидентичных машинах.
В [1] предложен метод построения множества всех
оптимальных решений следующей задачи.
Требуется найти минимум функции
¦
F0 S
1d k d n
1dsd n d m
ES k s ,
(1)
где S S 1 , S 2 ,..., S k ,..., S n ? перестановка из n
строк матрицы [E ij0 ] num ; E 0 ? целые неотрицательij
ные числа,
­°E 0 , ???? S ?
® ij
°?f, else .
ES k s
i&s
j,
Изложенные здесь результаты связаны с представлением матрицы [E ij0 ] num , n<m, в качестве входных
данных задачи о потоке минимальной стоимости в
транспортной сети N специального вида, изображенной на рис.1.
Любая дуга (i, j) сети N имеет единичную пропускную способность, а элемент Eij0 определяет стоимость переноса единицы потока из узла i в узел j.
Пропускные способности дуг (s, x 0 ) и (y 0 , t)
равны соответственно n и m единицам.
1
1
m n
¦ ¦ E ij0 h(i, j) минимальна на мно-
j=1i 1
жестве всех потоков величины n.
Очевидно, что решением задачи в постановке (1)
является поток минимальной стоимости в транспортной сети N.
Хорошо известный алгоритм определения потока
минимальной стоимости для транспортной сети N
состоит в последовательном построении потоков
h 0 0, h 1 1 , ..., h p p, p d n [2]. Поток h p 1
находится выделением пути (x 0 , i1 , j1 ,...i r , j r , y 0 ) ,
вдоль которого он увеличивается на единицу. При
этом стоимость потока h p1 минимальна среди
всех потоков, равных p+1. Временная сложность
алгоритма определяется величиной O(mn 2 n 3 ).
Алгоритм решения задачи (1), оцениваемый большей трудоёмкостью, чем процедура из [2], обладает
тем достоинством, что определяет все потоки минимальной стоимости. Отсюда следует возможность сформулировать и эффективно решить более
общую задачу, чем та, для решения которой разработана процедура из [2].
Рассмотрим систему из m параллельных неидентичных машин, предназначенных для выполнения
n одноэтапных работ, n>m. Пусть [E ij ] num обозначает матрицу, в которой есть E ij время выполнения
работы j на машине i, i 1, m , j 1, n .
Определим расписание выполнения n работ на m
машинах, как последовательность
3
(S1,S 2 ,...,Si ,...Sm ) ,
в которой перестановка Si задаёт порядок работ,
назначенных на машину i. Пусть в расписании П
работа j, выполняемая машиной i, завершается в
момент времени fij(П). Для расписания П найдём
суммарное время выполнения n работ на m параллельных неидентичных машинах, равное
mwft( 3 )
n m
¦ ¦ f ij (?) .
j 1i 1
s
x
i
y
j
t
(2)
Требуется построить расписание П* c минимальным
суммарным временем завершения работ.
В [2] показано, что искомое расписание П* находится в результате выполнения процедуры определения потока минимальной стоимости в транспортной сети N, которая строится для матрицы
m
n
C
Рис.1
Для каждой дуги транспортной сети N определим
поток как такую функцию h, что
а) h(s, x 0 ) , h ( y 0 , t ) Џ{0,1, ! , n}, h (i, j) ,
h ( x 0 , i}, h ( j, y 0 ) Џ{0,1} ;
44
Є[ E ij ] є
«
»
«[2E ij ]»
«........ »
«
»
«[nEij ]»
¬
ј
c mn строками и n столбцами, где [rEij ] обозначает
матрицу, образованную из [ E ij ]mun умножением
каждого её элемента на r.
РИ, 2001, № 3
Рассмотрим, как, применяя алгоритм решения
задачи (1), можно построить за полиномиальное
время все расписания П* с минимальным суммарным временем завершения работ.
Определим матрицу
B
CT [[E ij ]T ,[2E ij ]T ,..., [rEij ]T ,..., [nE ij ]T ]]
и обозн ачим её
j 1, mc, m c nm.
эл ементы
E 0ij ,
i 1, n,
Пусть матрица B является входом алгоритма решения задачи (1), а перестановка
S
*
(E * ,E * , E *
)
S (1) S ( 2) S ( mc)
есть одно из её оптимальных решений. Тогда
значение E
S ( l)
*
E 0pq , pdn, в задаче построения
расписаний ? вносит вклад в mwft( ? * ) при
условии, что работа p выполняется последней на
соотве тствующе й
машине .
Зн ачен ие
E
S ( k )
E 0rs
Чтобы применить алгоритм решения задачи (1) для
нахождения всех оптимальных расписаний ? *
задачи (2), образуем из [E ij ] 2u6 матрицу
Є4 2 8 4 12 6 16 8 20 10 є
«6 3 12 6 18 9 24 12 30 15 »
«
»
[E ij0 ]5u10 «5 5 10 10 15 15 20 20 25 25»
«
».
«2 1 4 2 6 3 8 4 10 5 »
«3 2 6 4 9 6 12 8 15 10 »
¬
ј
Рассмотрим допустимое решение:
0
0
0
,E024 ,E32
,E046 , E058 ), E11
S (E11
0
E 32
2E rs , rdn, представляет собой слагае-
мое в mwft( ? * ) в предположении, что работа r
завершается предпоследней на соответствующей
машине, и так далее. Таким образом, решению
S соответствует решение П*, и алгоритм решения
задачи (1) корректно находит все решения задачи
минимизации (2 ).
В общем случае допустимое расписание
3 (S1 ,S 2 ,...S i ,...S m ) задачи (2), в котором блок Si
представляет собой последовательность элементов
i-й строки матрицы [E ij ] num , строится из допустимого решения S задачи (1) с помощью следующей
процедуры.
S01. Входные данные задачи (2): [E ij ] mun ? матрица,
в которой элемент E ij равен времени выполнения
работы j на машине i; S ? допустимое решение
задачи (1), представленное перестановкой n строк
t 0
матрицы B C [Erl ]
num'
, mc nm ; если E0rl Џ S и
E 0pq Џ S , то rzp, lzq, k=1.
S02. Пока kdn, определить индекс i блока Si ,
которому принадлежит элемент Eij , соответствующий элементу E 0kl Џ S ; индекс i находится с помощью соотношений
E 0kl
Є 4 6 5 2 3є
«
» . Расписание П
¬ 2 3 5 1 2ј
является последовательностью ( S1 ,S 2 ) , содержащей две перестановки: перестановка S1 задаёт порядок выполнения работ, назначенных на первую
машину, а S 2 указывает, какие работы и в какой
очерёдности выполняются на второй машине.
[E ij ] 2u5
Пусть
rE ij , k = j, r 1, n l
rm i ' , 0 d i ' d m ;
при этом i=m, E ij Џ S m , если ic =0, и i=ic , E ij Џ S i
в противном случае; k=k+1.
S03. Упорядочить элементы каждого набора, полученного на шаге S02, по убыванию значений
коэффициентов r, связывающих параметры E 0kl и
E ij ; в результате получим все m блоков допустимого
решения 3 ( S1 ,S 2 ,...S i ,...S m ) задачи (2). Следует
отметить, что в решении 3 (S1 ,S 2 ,...S i ,...S m ) допустимы пустые блоки.
Обратимся к примеру, иллюстрирующему связь
задачи построения расписаний в постановке (2) с
задачей нахождения всех оптимальных решений (1).
РИ, 2001, № 3
5 , E 046
0
3 , E 58
4 , E 024
6,
8
задачи в постановке (1). Решению S соответствует
расписание 3 (S1 , S 2 ) задачи в постановке (2), где
S1 (E11 ) , а S 2 определяется перестановкой
(E 25 , E 24 , E 22 , E 23 ) . Таким образом, для расписания
П, представленного на рис. 2, сумма моментов
окончания работ, длительности выполнения которых определяются из матрицы [E ij ]2u5 , оказывается
равной
mwft (3 )
(E 25 E 25 E 24 E25 E24 E 22 E 25
E 24 E 22 E 23 E11 ) 15.
E11 4
E 25
2
E24 1
E 22 3
E 23 5
Рис. 2
Приведенные рассуждения являются обоснованием корректного применения схемы минимизации
функции (1) для решения обобщения задачи (2),
состоящего в построении множества всех расписаний с наименьшей суммой моментов завершения
заданной совокупности работ.
Следующий алгоритм находит все расписания П* за
полиномиальное время.
Sc1. [E ij ] mun ? входные данные задачи (2), где E ij ?
время выполнения работы j на машине i.
Sc2. Из [E ij ] mun образовать матрицу
B [E ij ]T ,[2E ij ]T ,..., [rE ij ]T , }, [nEij ]T ]
0
с n строками и mc=mn столбцами; B [E rl ]num' исходная матрица задачи минимизации функции (1).
Sc3. Выполнить шаги S1-S4 алгоритма построения
допустимого решения для исходных данных, представленных матрицей B [E 0rl ]
' .
num
45
Sc4. Построить множество всех решений S из n
компонент, доставляющих минимум функции (1).
Sc5. Для каждого полученного решения S выполнить процедуру построения соответствующего оптимального расписания 3 * S1 , S2 ,..., Sm ) .
Оценим трудоёмкость предлагаемого алгоритма.
Процесс преобразования последовательности S в
расписание П* выполняется за время, оцениваемое
в худшем случае величиной O(n nlog 2 n) . Если в
результате работы алгоритма построено L перестановок S длины n, то на выполнение шага Sc5
потребуется O(L(n nlog 2 n)) элементарных действий. Отсюда следует, что временная сложность
задачи построения всех оптимальных в смысле (2)
расписаний определяется объёмом вычислений для
нахождения решений S . Таким образом, трудоёмкость построения множества всех расписаний П*
оценивается величиной O(N max m '4 ) , где N max наибольшее число оптимальных локальных решений, построенных в процессе нахождения всех
перестановок, которые минимизируют (1), mc mn .
УДК 681.5.015:628.21
ВЫБОР ОПТИМАЛЬНОГО
ОБОРУДОВАНИЯ НАСОСНЫХ
СТАНЦИЙ ТРУБОПРОВОДНЫХ
СИСТЕМ ПРИ ПРОЕКТИРОВАНИИ
И РЕКОНСТРУКЦИИ
ДЯДЮН С.В.
Рассматривается задача оптимального подбора состава агрегатов насосных станций при проектировании и
реконструкции. Приводится постановка задачи, предлагается метод её решения. В качестве критерия оптимизации используется минимум суммы капитальных и
эксплуатационных затрат на насосной станции на весь
проектный период.
Повысить качество и эффективность функционирования трубопроводных систем (ТС) возможно
путем разработки и широкого применения ресурсосберегающих технологий проектирования и реконструкций ТС, в основе которого лежит использование современных математических методов и
средств вычислительной техники.
При проектировании ТС необходимо определить
количество и местоположение отдельных подсистем, структуру, а также параметры и переменные
каждой из подсистем так, чтобы обеспечить подачу
целевого продукта (ЦП) всем потребителям в нужных количествах и под заданными давлениями.
Проектирование должно осуществляться с учетом
стохастического характера процессов потребления
ЦП, динамики развития системы, надежности и
большой вероятности возникновения внештатных
ситуаций (аварийное отключение, стихийное бедствие и др.).Все это приводит к необходимости
проектирования ТС, обладающих свойством управляемости по потокораспределению. Очевидно,
что предпочтительным будет вариант, стоимость
которого меньше. Таким образом, проектирование
ТС сводится к выбору из множества возможных
46
Трудоёмкость известного из [2] алгоритма вычисления оптимального потока в сети N, сответсвующего расписанию П*, оценивается меньшей величиной, равной O(mn 2 n 3 ) .
Расхождение в оценках объясняется платой за
поиск всех оптимальных решений П*.
Литература 1. Панишев А.В., Скрипина И.В., Скакалина
Е.В. Эффективное построение оптимальных решений
в задачах о назначении транспортного типа // Автомобильный транспорт: Сб.науч.тр. Харьков: ХГАДТУ,
2000. Вып. 4. С. 63-65. 2.Теория расписаний и вычислительные машины / Под. ред. Коффмана Э.Г.М.: Наука.
1984. 334с.
Поступила в редколлегию 23.03.2001
Рецензент: д-р техн. наук, проф. Панишев А.В.
Скакалина Елена Викторовна, начальник вычислительного центра ?Нефтегаз?, г.Полтава, соискатель
кафедры информатики Харьковского государственного автомобильно-дорожного университета. Научные
интересы: математическое моделирование; теория
расписаний и ее применение. Адрес: Украина, 36000,
Полтава, ул.Советская, 19.
допустимых вариантов сети оптимального варианта
по критерию стоимости.
Если в процессе оптимального проектирования
применять системный подход, то процесс оптимального проектирования ТС разбивается на ряд
этапов, или уровней детализации [1].
Рассмотрим одну из важных задач оптимального
проектирования ТС ? выбор оптимального состава
оборудования насосных станций (НС) трубопроводных систем. В результате решения задачи предшествующего этапа проектирования ТС ? технико-экономического расчета сети ? определяются не
только оптимальные по критерию минимума суммы капитальных и эксплуатационных затрат значения диаметров труб проектируемой трубопроводной сети, но и оптимальные значения расходов и
давлений на выходах НС для режима максимального потребления ЦП в сети. Эта информация
является входной для решения данной задачи, т.е.
для обеспечения проектных значений режимных
параметров на выходе каждой проектируемой НС
необходимо так подобрать состав насосного оборудования, чтобы при этом достигался минимум
суммы капитальных и эксплуатационных затрат на
НС на весь проектный период [0,Т]. Таким образом, получаемые в результате решения этой задачи
рекомендации по составу насосного оборудования
проектируемой НС должны не только обеспечивать
управляемость СПРВ по потокораспределению, но
и доставлять минимум функции суммы капитальных и энергетических затрат.
В водо- и теплоснабжении широко используются
поля насосов [2,3]-диапазоны изменения рекомендуемой области работы насоса при максимальном
диаметре рабочего колеса насоса. Аналогичные
поля работы насосов можно получить, изменив
число оборотов регулируемого привода, которым
оборудован насос, от максимального до некоторого
минимального. Поля работы насосов можно использовать при анализе допустимых вариантов
количества и типов устанавливаемых агрегатов
РИ, 2001, № 3
Документ
Категория
Без категории
Просмотров
4
Размер файла
223 Кб
Теги
построение, расписание, временем, множества, эффективного, работа, минимальное, суммарных, завершение
1/--страниц
Пожаловаться на содержимое документа