ПДС-алгоритмы и труднорешаемые задачи комбинаторной оптимизации
Формулируются базовые принципы построения ПДС-алгоритмов. Приводятся обобщения повышения эффективности их использования. Анализируется возможность создания новых ПДС-алгоритмов на основе существующих. Формулюються базові принципи побудови ПДС-алгоритмів. Наводяться узагальнення по підвищенню ефектив...
Gespeichert in:
| Veröffentlicht in: | Системні дослідження та інформаційні технології |
|---|---|
| Datum: | 2009 |
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2009
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/42235 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | ПДС-алгоритмы и труднорешаемые задачи комбинаторной оптимизации / М.З. Згуровский, А.А. Павлов, Е.Б. Мисюра // Систем. дослідж. та інформ. технології. — 2009. — № 4. — С. 14–31. — Бібліогр.: 16 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860221860279484416 |
|---|---|
| author | Згуровский, М.З. Павлов, А.А. Мисюра, Е.Б. |
| author_facet | Згуровский, М.З. Павлов, А.А. Мисюра, Е.Б. |
| citation_txt | ПДС-алгоритмы и труднорешаемые задачи комбинаторной оптимизации / М.З. Згуровский, А.А. Павлов, Е.Б. Мисюра // Систем. дослідж. та інформ. технології. — 2009. — № 4. — С. 14–31. — Бібліогр.: 16 назв. — рос. |
| collection | DSpace DC |
| container_title | Системні дослідження та інформаційні технології |
| description | Формулируются базовые принципы построения ПДС-алгоритмов. Приводятся обобщения повышения эффективности их использования. Анализируется возможность создания новых ПДС-алгоритмов на основе существующих.
Формулюються базові принципи побудови ПДС-алгоритмів. Наводяться узагальнення по підвищенню ефективності їхнього використання. Аналізується можливість створення нових ПДС-алгоритмів на основі існуючих.
Based on the analysis of PDC-algorithms for intractable combinatorial optimization problems, general principles of their building are formulated and generalizations about increasing the effectiveness of their using are given. A possibility of constructing new PDC-algorithms on the basis of the existed ones is analyzed.
|
| first_indexed | 2025-12-07T18:18:49Z |
| format | Article |
| fulltext |
© М.З. Згуровский, А.А. Павлов, Е.Б. Мисюра, 2009
14 ISSN 1681–6048 System Research & Information Technologies, 2009, № 4
TIДC
ТЕОРЕТИЧНІ ТА ПРИКЛАДНІ ПРОБЛЕМИ І
МЕТОДИ СИСТЕМНОГО АНАЛІЗУ
УДК 519.854.2
ПДС-АЛГОРИТМЫ И ТРУДНОРЕШАЕМЫЕ ЗАДАЧИ
КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ
М.З. ЗГУРОВСКИЙ, А.А. ПАВЛОВ, Е.Б. МИСЮРА
Формулируются базовые принципы построения ПДС-алгоритмов. Приводятся
обобщения повышения эффективности их использования. Анализируется воз-
можность создания новых ПДС-алгоритмов на основе существующих.
ВВЕДЕНИЕ
Большая часть дискретных математических моделей, построенных для
анализа, синтеза и функционирования сложных систем, является либо
NP-полными задачами [1], либо не менее сложными. В частности, к классу
NP-полных задач относится подавляющее большинство задач теории
расписаний.
Вычислительная сложность точных алгоритмов решения комбинатор-
ных задач оптимизации из класса NP определяется выражением )2( )(npО ,
где p — полиномиальная функция; n — размерность конкретной системы
однозначной записи задачи. Иными словами, точные алгоритмы решения
таких задач, представляющие модели реальных систем, создают проблему
трансвычислительной сложности [2]. Поэтому практические задачи реша-
ются приближенными либо эвристическими методами. Приближенных ме-
тодов с полиномиальной оценкой сложности, гарантирующих наперед за-
данную точность (в предположении NPP ≠ ), не существует. Эвристические
методы не гарантируют качества решений [1]. Можно также отметить, что в
некоторых случаях ограничения, накладываемые на формулировку задачи
комбинаторной оптимизации из класса NP, приводят к решению по полино-
миальной вычислительной схеме. Например, труднорешаемая задача ком-
бинаторной оптимизации «Минимизация суммарного взвешенного момента
окончания выполнения частично упорядоченного множества заданий при
отношении порядка, заданном ориентированным ацикличным графом» в
случае, когда ориентированный граф является деревом либо последователь-
но-параллельным, точно решается полиномиальным алгоритмом [1].
В работах [3–5] развивается новый подход к построению точных эф-
фективных алгоритмов для труднорешаемых задач комбинаторной оптими-
ПДС-алгоритмы и труднорешаемые задачи комбинаторной оптимизации
Системні дослідження та інформаційні технології, 2009, № 4 15
зации (ПДС-алгоритмы). Под ПДС-алгоритмом понимается точный алго-
ритм, содержащий полиномиальную и декомпозиционную составляющую.
Общая методология построения алгоритма заключается в следующем.
На основе теоретических свойств исследуемой комбинаторной задачи:
а) находятся логико-аналитические условия (p-условия), выполнение
которых в процессе решения ПДС-алгоритмом произвольной индивидуаль-
ной задачи данного класса приводит к нахождению оптимального решения
вычислительной процедурой полиномиальной сложности (при этом заранее
определить, будут ли для произвольной индивидуальной задачи выполнять-
ся эти условия, невозможно);
б) в процессе решения исходная задача декомпозируется на совокуп-
ность задач меньшей размерности.
В теории расписаний на основе этого подхода построены эффективные
точные ПДС-алгоритмы для следующих задач [4–8]:
• Минимизация суммарного запаздывания при выполнении независи-
мых заданий на одном приборе (МСЗ).
• Минимизация суммарного взвешенного момента окончания выпол-
нения частично упорядоченного множества заданий при отношении поряд-
ка, заданном ориентированным ацикличным графом (МВМ).
• Минимизация суммарного запаздывания при выполнении независи-
мых заданий с равными директивными сроками параллельными приборами
(МСЗП).
ПОСТАНОВКА ЗАДАЧИ МСЗ
Дано множество независимых заданий },,{ ,21 njjjJ …= , состоящих из од-
ной операции. Для каждого из них известны длительность jl и директивный
срок jd выполнения. Задания поступают в систему одновременно в момент
времени nja j ,1,0 == . Прерывания не допускаются. Необходимо постро-
ить расписание выполнения заданий для одного прибора, минимизирующее
суммарное опоздание при выполнении заданий.
( )∑
=
−=
n
j
jj d,Cf
1
0max , (1)
где jC — момент завершения выполнения задания j .
Согласно Д. Ду и Д. Люнгу [9], задача является NP-трудной. Обзор из-
вестных методов ее решения приведен в работе [10].
ПОСТАНОВКА ЗАДАЧИ МВМ
Имеется частично-упорядоченное множество заданий },,{ ,21 njjjJ …= ,
которые, начиная с нулевого момента времени, обслуживаются одним при-
бором, без прерываний, не более, чем одно в единицу времени. Каждому
заданию j поставлены в соответствие его длительность 0>jl и вес
М.З. Згуровский, А.А. Павлов, Е.Б. Мисюра
ISSN 1681–6048 System Research & Information Technologies, 2009, № 4 16
jω (произвольное действительное число, в приложении теории расписа-
ния 0> ). Орграф частичного упорядочивания ацикличен.
Необходимо найти последовательность обслуживания заданий, сум-
марный взвешенный момент окончания выполнения работ в которой мини-
мален.
min
1
][][
→=∑
=
n
k
jj kk
Cf ω , (2)
где ∑
=
=
k
s
jj kk
lC
1
][][
— момент завершения выполнения задания, стоящего в
допустимом расписании на k-й позиции.
Эта задача является NP-трудной в сильном смысле и останется таковой,
если все длительности или все веса заданий равны 1. Она разрешима за по-
линомиальное время, если порядок отношений предшествования является
лесом или последовательно-параллельным графом [11].
ПОСТАНОВКА ЗАДАЧИ МСЗП
Дано множество заданий J , число приборов m , для каждого Jj∈ извест-
на длительность выполнения jl . Все задания имеют общий директивный
срок d . Необходимо построить расписание σ выполнения заданий Jj∈ на
m приборах равной производительности такое, чтобы достигался минимум
функционала
∑
∈
−=
Jj
j dCf ])(;0[max)( σσ , (3)
где )(σjC — момент завершения выполнения задания j в последователь-
ности σ .
Предполагается, что все задания множества J поступают на выполне-
ние одновременно и обслуживаются без прерываний.
Сформулированная задача относится к классу NP-трудных задач [1] и
разрешима за псевдополиномиальное время при 2=m .
ОБЩИЕ ПРИНЦИПЫ ПОСТРОЕНИЯ ПДС-АЛГОРИТМОВ
Принадлежность к классу перестановочных расписаний
Критерии (1)–(3) принадлежат к одному и тому же классу, называемому
классом регулярных критериев. Регулярный критерий R является возрас-
тающей функцией момента окончания каждого из n заданий.
Теорема 1 [12]. Для системы 1|n расписание, оптимальное относи-
тельно регулярного критерия, принадлежит классу, исключающему преры-
вания или искусственные простои.
Основным результатом этой теоремы является то, что поиск оптималь-
ного решения должен проводиться в классе перестановочных расписаний
ПДС-алгоритмы и труднорешаемые задачи комбинаторной оптимизации
Системні дослідження та інформаційні технології, 2009, № 4 17
[12], общее количество которых в случае n работ задается одной из !n воз-
можных перестановок их номеров.
Направленность перестановок
Во избежание полного перебора необходимо определить возможность про-
ведения направленных перестановок, позволяющих отсечь бесперспектив-
ные варианты решения. Рассмотрим типы направленных перестановок для
каждой из трех задач.
Задача МСЗ
Справедлива следующая теорема.
Теорема 2 [4]. Если в последовательности, упорядоченной по неубыва-
нию значений длительности заданий (последовательность упσ ), запаздыва-
ющим заданиям не предшествуют задания ][ij , для которых =
][ijr
0
][][
>−=
ii jj Cd , то не существует переносов заданий (перестановок и
встраиваний), приводящих к улучшению целевой функции, где
][][][ iii jjj Cdr −= — резерв времени задания ][ij , а i — позиция, занимае-
мая заданием ][ij в последовательности упσ .
Введем следующие определения.
Определение 1. Перестановкой (EFSR — extraction and forward-shifted
reinsertion — извлечение и повторная вставка со сдвигом вперед) называется
процедура переноса задания ][gj на позицию k )( gk > и одновременно за-
даний, занимающих позиции kkgg ,1,,2,1 −++ … , на позиции …,1, +gg
1, −k… , соответственно.
Определение 2. Интервалом перестановки задания ][gj на позицию k
называется множество заданий, находящихся на позициях …,2,1 ++ gg
kk ,1, −… до выполнения перестановки.
Определение 3. Встраиванием (EBSR — extraction and backward-shifted
reinsertion — извлечение и повторная вставка со сдвигом назад) называется
процедура переноса задания ][gj на позицию p ( pg > ) и одновременно
заданий 1,,1, −+ gpp … на позиции ggpp ,1,,2,1 −++ … , соответственно.
Определение 4. Интервалом встраивания
][gjI задания ][gj называется
множество заданий, стоящих до встраивания на позициях 1,,1, −+ gpp … ,
где p определяется из условия
∑∑
−
=
−
−=
≤−<
11
1
][][][][
g
pi
jjj
g
pi
j iggi
ldCl . (4)
Если же условие (4) не выполняется ни для одной позиции, то 1=p .
Таким образом, опоздание по заданию j на позиции p должно быть мини-
мально или равно нулю.
Справедлива следующая теорема.
М.З. Згуровский, А.А. Павлов, Е.Б. Мисюра
ISSN 1681–6048 System Research & Information Technologies, 2009, № 4 18
Теорема 3 [4]. Пусть в последовательности упσ ][gj — запаздываю-
щее задание. Уменьшение значения функционала при перемещении ][gj на
более ранние позиции в результате перестановок и встраиваний возможно
только при выполнении хотя бы одного из следующих условий:
1. ][ij∃ , 0|
][min ><≤
ijrgiP , ][][ gi jj dd > .
На интервале встраивания задания ][gj есть задания ][ij с резервами
времени, для которых ][][ gi jj dd > . minP — позиция, где запаздывание по
заданию ][gj минимально или равно нулю.
2. ][qj∃ , gq < , ][][ gq jj Cd > .
В последовательности упσ на позиции q , предшествующей позиции g,
есть задание с резервом времени, перестановка которого после задания ][gj
уменьшает опоздание по заданию ][gj . Задание ][qj остается незапазды-
вающим.
3. ][qj∃ , gq < , ][][][][ gqgg jjjj CdlC <<− .
Существует незапаздывающее задание ][qj , директивный срок которо-
го больше момента начала выполнения задания ][gj , но меньше момента его
окончания. При этом выполняется
0)(),(min
][][][][][
>−−−
qgqgg jjjjj dCldC .
Следовательно, перестановка задания ][qj после задания ][gj приведет
к уменьшению значения функционала за счет использования резерва зада-
ния ][qj .
4. 0||
][min ≤<≤∀
ijrgiPi ,
но ][kj∃ , |
][][
|
gk jj Ddpk >< , 0
][
>
kjr , [ ]1][ −
>
pk jj Cd .
На интервале перестановки задания ][gj резервы отсутствуют, но су-
ществует задание ][kj , pk < , директивный срок которого больше
][ gjd и
резерв больше нуля.
Выполнение одного из условий 1–4 означает, что на интервале встраи-
вания задания ][gj существуют резервы (условия 1–3) или они будут обра-
зованы в результате перестановок (условие 4). При невыполнении условия 4
перестановка заданий, занимающих позиции 1,1 −p , на интервал встраива-
ния задания ][gj приведет к запаздыванию этих заданий, и так как они име-
ют меньшую длительность, чем ][gj , то встраивание задания ][gj приведет
к увеличению значения функционала. Следовательно, если не выполняется
ПДС-алгоритмы и труднорешаемые задачи комбинаторной оптимизации
Системні дослідження та інформаційні технології, 2009, № 4 19
ни одно из условий 1–4, то не существует встраиваний задания ][gj на бо-
лее ранние позиции, приводящих к улучшению целевой функции.
Следствие. Пусть в последовательности упσ число запаздывающих
заданий 1з >n . Тогда, если в последовательности упσ ни для одного из за-
паздывающих заданий ][gj нет предшествующих заданий ][sj , gs < , для
которых выполняется хотя бы одно из условий 1–4, то последовательности
упσ отвечает оптимальное значение функционала.
Разработанный ПДС-алгоритм построен на перестановках и встраива-
ниях, направленных на оптимальное использование запаздывающими зада-
ниями резервов времени незапаздывающих заданий. В процессе решения
используются следующие типы перестановок и встраиваний.
• Перестановки (EFSR):
а) заданий, для которых резерв времени больше нуля;
б) заданий, ранее использовавших резервы в результате перестановок и
встраиваний.
Перестановки осуществляются, если при их выполнении значение
функционала уменьшается.
• Встраивания (EBSR):
а) при наличии резервов на интервале встраивания 1, −gp запаздыва-
ющего задания ][gj , где p — позиция встраивания задания ][gj ;
б) если резервы на интервале 1, −gp отсутствуют, при наличии ре-
зервов на интервале 1,1 −p у заданий ][ij , для которых
][][ gl jj dd > ,
][][ ll jj Cd > ,
]1[][ −
>
pl jj Cd .
В качестве примера приведем условия реализации полиномиальной со-
ставляющей алгоритма, полученные на основе исследования свойств после-
довательности упσ .
Теорема 4 [4]. Пусть в последовательности упσ ][gj — первое запаз-
дывающее задание, и выполняется
][
)(max уп
gjlr ≤σ . В этом случае опти-
мальное значение функционала достигается за полиномиальное время с тру-
доемкостью, определяемой функцией )log( nnO .
Задача МВМ
Направленность перестановок основывается на следующей теореме.
Теорема 5 [5]. Оптимальное расписание является P-упорядоченным.
P-упорядоченным расписанием [5] является такая допустимая последо-
вательность заданий, которая обладает следующими свойствами:
а) первым выполняется подмножество JS ⊂1 ( J — множество всех
заданий), имеющее максимально возможный приоритет, т.е.
JUUPSP ⊂∀≥ ,)()( 1 ; (5)
М.З. Згуровский, А.А. Павлов, Е.Б. Мисюра
ISSN 1681–6048 System Research & Information Technologies, 2009, № 4 20
б) подмножество 1S содержит максимально возможное количество за-
даний при условии выполнения неравенства (5);
в) вторым выполняется подмножество 2S , удовлетворяющее свойствам
а) и б) на множестве 1\ SJ , и т.д.
Теорема 6 [5]. Пусть на множестве расписаний P задан функционал
∑
=
=
n
k
jj kk
Cf
1
][][
)П( ω . Тогда для двух произвольных перестановок =′П
)П,П,П,(П (2))()((1) ba= и )П,П,П,(ПП (2))()((1) ab=′′ , принадлежащих P ,
существует функция )П(f , которая удовлетворяет таким свойствам: из ус-
ловия )П()П( )()( ba ff > следует неравенство )П()П( ′′≤′ ff и из
)П()П( )()( ba ff = — равенство )П()П( ′′=′ ff .
Данная функция называется приоритетом перестановки и обозначается
( )
{ } { }
∑∑
∈∈
=
ΠΠ
Π
j
j
j
j lP ω .
Алгоритм основан на перестановках, направленных на построение
P-упорядоченного расписания.
В работе [5] введены понятия цепочек и конструкций общего вида и
определены их свойства. На этой основе разработан ПДС-алгоритм, строя-
щий оптимальное расписание для индивидуальной задачи МВМ, отношения
предшествования которых имеют вид цепочек, простых или сложных
конструкций произвольной степени вложения. Оптимальное расписание
получается также в том случае, если направленные ребра, нарушающие
p-условия алгоритма, не принимают участия в построении оптимального
расписания. Например, когда алгоритм не использует отношения предшест-
вования, нарушающие p-условия при построении множеств максимальных
приоритетов, а сами множества имеют вид цепочек или конструкций произ-
вольного вида. Алгоритм основывается на анализе приоритетов и использо-
вании перестановочного приема для следующих непосредственно друг за
другом структур взаимосвязанных заданий.
Задача МСЗП
Направленность выполнения перестановок определяется на основе та-
ких теорем [6].
Пусть исходное множество заданий J упорядочено по неубыванию
значений длительностей выполнения и разбито на (необязательно непустые)
подмножества ),,,( 21 mJJJ … , попарно не имеющие общих элементов, где
iJ — множество заданий, обслуживаемых i-м прибором, mi ,1= .
Поиск оптимального расписания в соответствии с известной теоремой
[13] можно ограничить рассмотрением расписаний, при которых каждый
прибор обслуживает задания в порядке возрастания их длительностей.
Теорема 7 [6]. Существует оптимальное расписание, при котором вы-
полняются условия:
1. }|,,2,1{ SPSP ∪…∪ = .
ПДС-алгоритмы и труднорешаемые задачи комбинаторной оптимизации
Системні дослідження та інформаційні технології, 2009, № 4 21
2. Если nSP <|| ∪ , то ∑
∈
≥
ii SPj
j dl
∪
и ii SQ \ содержит те и только те
элементы, которые отличаются от iSP +|| ∪ на величину, кратную m ,
mi ,1= , где
∪
mi
iPP
,1=
= , ∪
mi
iSS
,1=
= , ∪
mi
iQQ
,1=
= ,
)(σiP — множество незапаздывающих заданий в расписании прибора i ;
)(σiS — множество запаздывающих заданий в расписании прибора i,
для которых выполняются условия
dS j <
н , dC j > , )(σiSj∈∀ ,
где н
jS — момент начала выполнения задания j;
)(σiQ — множество запаздывающих заданий в расписании прибора i,
для которых выполняются условия
dS j >
н , )(σiQj∈∀ ;
iR — резерв времени прибора i в расписании σ
∑
∈
−=
)(σiPj
ji ldR ;
)(σi∆ — запаздывание в выполнении задания )(σiSf ∈ относительно
директивного срока
∑
∈
−=∆
)()( σσ ∪ ii SPj
ji dl .
Пусть PSΨ — класс расписаний, удовлетворяющий условию теоре-
мы 7; PSP Ψ⊂Ψ — класс расписаний, удовлетворяющий дополнительно
следующим условиям:
1. }|,,2,1{ PP …= .
2. )(maxmin
,1)(
σ
σ
i
mi
j
Sj
Rl
=∈
> .
3. H
j
H
j lk
SS ≤ , если
lk jj ll ≤ , )(, σSjj lk ∈∀ .
Теорема 8 [6]. Если в расписании PΨ∈σ , =∆=Ω ΣΣΣ )}(),({min)( σσσ R
0= , то расписание оптимально.
Величина )(σΣΩ является основной характеристикой расписания, где
)(σΣR , )(σΣ∆ показывают, насколько можно теоретически уменьшить зна-
чение функционала, чтобы получить оптимальное расписание.
Теорема 9 [6]. Расписание с одинаковым числом запаздывающих зада-
ний на приборах (равномерное расписание) является оптимальным.
Перестановки направлены на уменьшение значения )(σΣ∆ на прибо-
рах с бóльшим числом запаздывающих заданий за счет резервов )(σΣR на
приборах с меньшим числом и на построение равномерных расписаний.
М.З. Згуровский, А.А. Павлов, Е.Б. Мисюра
ISSN 1681–6048 System Research & Information Technologies, 2009, № 4 22
Если в процессе решения произвольной индивидуальной задачи вы-
полняются условия, сформулированные в теоремах 8 и 9, то задача решается
полиномиальной составляющей ПДС-алгоритма.
Полиномиальная составляющая всех трех разработанных ПДС-алго-
ритмов определяется только на основе направленных перестановок.
Структура алгоритмов
Разработанные ПДС-алгоритмы решения задач МСЗ, МВМ и МСЗП условно
можно представить в виде следующих основных блоков:
а) упорядочения;
б) построения начального расписания;
в) оптимизации.
В блоке упорядочения выполняется упорядочение заданий в соответст-
вии с их приоритетами (последовательность упσ ). Для заданий с весами и
директивными сроками приоритет задания для всех трех задач в общем
случае определяется отношением jj lω . Чем больше вес задания и меньше
его длительность, тем выше приоритет этого задания.
В задаче МСЗ все веса равны, поэтому упорядочение осуществляется
по неубыванию значений длительности выполнения заданий (последовате-
льности упσ ).
В задаче МВМ все задания упорядочиваются по невозрастанию отно-
шения jj l/ω , и если полученная последовательность допустима по выпол-
нению, то она оптимальна.
В задаче МСЗП, аналогично задаче МСЗ, все задания упорядочиваются
по неубыванию значений их длительностей.
В блоке б) по определенным правилам на основе последовательности
упσ строятся начальные расписания, для которых затем выполняются про-
цедуры оптимизации.
В задаче МСЗ в последовательности упσ выполняются свободные пе-
рестановки, т.е. перестановки незапаздывающих заданий с резервами на бо-
лее поздние позиции таким образом, чтобы эти задания оставались незапаз-
дывающими. Это выполняется только в том случае, если на интервале
перестановки есть запаздывающие задания (последовательность псσ ).
В задаче МВМ строится допустимая по выполнению последователь-
ность заданий.
В задаче МСЗП предварительно распределяются задания по приборам,
следуя правилам, определенным в теореме 7.
Для выполнения блока оптимизации в задаче МСЗП разработана окрес-
тность поиска оптимального решения, полученная с помощью различных
типов перестановок. Поиск оптимального решения по этой окрестности
осуществляется посредством направленных перестановок в соответствии с
условиями теорем 8, 9. Величина )}(),({min σσ ΣΣ ∆R является оценкой по-
лученных решений и показывает, насколько можно теоретически умень-
шить значение функционала, чтобы получить оптимальное решение.
Для выполнения блоков оптимизации исследуемых задач МСЗ и МВМ
разработаны адаптивные алгоритмы поиска оптимального решения, суть
ПДС-алгоритмы и труднорешаемые задачи комбинаторной оптимизации
Системні дослідження та інформаційні технології, 2009, № 4 23
которых состоит в том, что на каждой k-й итерации анализируется решение
1−k -й итерации, на основании чего выбирается дальнейшая стратегия по-
иска.
В задаче МСЗ число итераций алгоритма определяется количеством
конкурирующих заданий.
Определение 5. Запаздывающее задание ][gj в последовательности
спσ называется конкурирующим, если в этой последовательности найдется
хотя бы одно предшествующее задание ][lj , для которого выполняются ус-
ловия
][][ gl jj dd > и 0
][][
>−
ll jj Cd .
На каждой итерации проверяется возможность использования резервов
времени предшествующих незапаздывающих заданий очередным конкури-
рующим заданием и строится оптимальное расписание рассматриваемой
последовательности. На первой итерации строится оптимальное расписание
для заданий на интервале 1,1 g , где ][ 1gj — первое запаздывающее конку-
рирующее задание в последовательности спσ . На следующей итерации рас-
сматривается последовательность заданий на интервале 2,1 g , где ][ 2gj —
следующее запаздывающее конкурирующее задание.
Пусть уже выполнена 1−k итерация и построено оптимальное распи-
сание для последовательности заданий на интервале 1,1 −k . Переходим к
очередному запаздывающему конкурирующему заданию ][kj и строим оп-
тимальное расписание для подпоследовательности kσ , включающей зада-
ния на интервале k,1 . Аналогичные процедуры выполняются до тех пор,
пока не будет рассмотрена вся последовательность спσ и построено опти-
мальное расписание на всем множестве заданий.
Алгоритм решения задачи МВМ также является итерационным. Он ос-
новывается на анализе приоритетов и использовании перестановочного
приема для следующих непосредственно друг за другом подпоследователь-
ностей заданий. Данный алгоритм на каждой k-й итерации строит
P-упорядоченное расписание следующим образом: к оптимальному распи-
санию, полученному на 1−k -й итерации, добавляется очередное запазды-
вающее задание из начальной допустимой последовательности и проводится
последующая оптимизация. В конце последней итерации получаем оптима-
льное решение для всего множества заданий.
Алгоритмы решения задач МСЗ и МВМ построены таким образом, что
на каждой итерации улучшается (или остается равным предыдущему) зна-
чение оптимизируемого функционала. Последнее обстоятельство позволяет
остановить процесс решения при достижении граничного времени и оце-
нить отклонение найденного решения от искомого оптимального, так как
для решенного класса задач получены оценки, величины которых зависят от
текущего решения.
Отметим еще одно свойство разработанных алгоритмов для задач МСЗ
и МВМ. Структура алгоритмов позволяет «загрублять» предлагаемые реше-
ния, т.е. выигрывать во времени за счет потери точности получаемых ре-
М.З. Згуровский, А.А. Павлов, Е.Б. Мисюра
ISSN 1681–6048 System Research & Information Technologies, 2009, № 4 24
зультатов, исключая из алгоритмов те процедуры, которые статистически
лишь незначительно влияют на значение функционала. Это свойство позво-
ляет строить эффективные приближенные решения.
Декомпозиция
В задаче МСЗ [4] на этапе оптимизации последовательность спσ декомпози-
руется на подпоследовательности меньшего размера. Оптимизация осуще-
ствляется на подпоследовательности, ограниченной позицией встраивания
очередного конкурирующего задания и позиции, занимаемой этим заданием
в последовательности спσ . В эту подпоследовательность в процессе реше-
ния могут быть включены только задания, образующие резервы на интерва-
ле встраивания рассматриваемого конкурирующего задания. Таким образом,
реализуется декомпозиция задачи на подзадачи меньшего размера.
В задаче МВМ построение P-упорядоченного расписания заключается в
том, что на каждой итерации k на основе рассматриваемого задания ][kj по
определенным правилам строится структура взаимосвязанных заданий (це-
почка, простая конструкция, вложенная конструкция), которая встраивается
в соответствии с приоритетом в допустимой последовательности на более
ранние позиции, не нарушая допустимости всей последовательности. Ана-
логично строится P-упорядоченное расписание для всего множества зада-
ний, которое в соответствии с определением представлено упорядоченной
подпоследовательностью подмножеств максимальных приоритетов.
Разбиение исходного множества заданий на подмножества максималь-
ных приоритетов является декомпозицией исходной задачи на подзадачи
меньшей размерности и выполняется по полиномиальной вычислительной
схеме [5].
В задаче МСЗП декомпозиция осуществляется на всем множестве зада-
ний при построении начального расписания на подмножестве незапазды-
вающих и запаздывающих заданий с учетом условий, сформулированных в
теореме 7. В соответствии с теоремой 8 выполняются перестановки для
уменьшения )(σΣ∆ на приборах с бóльшим числом запаздывающих зада-
ний за счет резервов )(σΣR на приборах с меньшим числом запаздывающих
заданий и для построения равномерных расписаний [6]. Причем в переста-
новках участвуют только задания, принадлежащие множеству незапазды-
вающих заданий.
КЛАССИФИКАЦИЯ ПДС-АЛГОРИТМОВ
Разработанные ПДС-алгоритмы реализуются по-разному. Существуют два
типа ПДС-алгоритмов.
ПДС-алгоритмы первого типа (задачи МВМ и МСЗП) содержат поли-
номиальную составляющую и приближенный алгоритм и строятся только на
направленных перестановках. В результате решения задачи получаем либо
строго оптимальное решение полиномиальной составляющей алгоритма,
либо приближенное с верхней оценкой отклонения от оптимального (задача
МВМ). В задаче МСЗП задается полиномиальное ограничение на число вы-
ПДС-алгоритмы и труднорешаемые задачи комбинаторной оптимизации
Системні дослідження та інформаційні технології, 2009, № 4 25
числений от размерности задачи, и характеристика )}(),({min σσ ΣΣ ∆R яв-
ляется оценкой отклонения от оптимального значения функционала. При
этом всегда известно, является ли полученное решение точным или при-
ближенным.
ПДС-алгоритм второго типа (задача МСЗ) имеет полиномиальную и
экспоненциальную составляющие. Если в процессе решения произвольной
индивидуальной задачи выполняются логико-аналитические условия, полу-
ченные на основании исследования ее свойств, то данная задача решается
полиномиальным подалгоритмом. Иначе, выполняется экспоненциальное
число вычислений. В процессе решения реализуются следующие отсечения,
позволяющие исключить бесперспективные варианты перестановок и суще-
ственно сократить вычисления экспоненциальной составляющей алгоритма
для получения оптимального решения.
Теорема 10. Необходимые условия для встраивания конкурирующего
задания ][gj в последовательности kσ на позицию p , где p — позиция, на
которой запаздывание по заданию ][gj минимально или равно нулю:
а) наличие резервов на интервале встраивания задания ][gj у заданий
][ij , для которых
][][ gi jj dd > ,
][][ gji Ij ∈ ;
б) если резервы на интервале 1, −gp отсутствуют, наличие резервов на
позициях 1,1 −p у заданий ][ij , для которых
][][ gi jj dd > ,
][][ ii jj Cd > ,
]1[][ −
>
pi jj Cd . (6)
Теорема 11. Если на интервале встраивания задания ][gj находится за-
дание ][kj ,
][][ gk jj dd ≤ , ,
][][ gk jj ll ≤ то интервал ][gj определяется позиция-
ми 1,1 −+ gk .
Теорема 12. Если на позиции p встраивания задания ][gj находится за-
паздывающее задание или задание с нулевым резервом и на позициях
1,1 −p нет заданий, отвечающих условиям (6), то задание ][gj встраивается
на позицию 1+p . При выполнении аналогичных условий на позиции
1+p — на позицию 2+p и т.д. до позиции g .
Теорема 13. Если при выполнении итерации оптимизации для кон-
курирующего задания ][gj для всех предшествующих незапаздывающих
заданий ][ij выполняется
][][ gi jj dd ≤ или на интервале 1,1 −g резервы от-
сутствуют, то задание ][gj остается на занимаемой позиции и подпоследо-
вательность на интервале g,1 оптимальна.
Теорема 14. Если в последовательности kσ при встраивании запазды-
вающего задания ][gj на интервале 1,1 −g нет предшествующих заданий,
для которых ][][ gi jj dd > и ][][ ii jj Cd > , но есть задания *
][mj ( **
][mj ), для
которых *
][mj
l ][)( **
][
gjj
ll
m
> , то оптимизация осуществляется за счет резер-
М.З. Згуровский, А.А. Павлов, Е.Б. Мисюра
ISSN 1681–6048 System Research & Information Technologies, 2009, № 4 26
вов, освобожденных заданиями *
][mj ( **
][mj ) при встраивании их после зада-
ния ][gj
[ ] [ ] [ ]( )∑
=
−<−
g
mi
jjjj iim
dC,dC 0max*[g]
. (7)
Теорема 15. Если конкурирующее задание ][gj в результате выполне-
ния для него итерации оптимизации, определяющей возможность использо-
вания резервов этим заданием, заняло позицию pk > , то следующие за ним
конкурирующие задания ][lj , для которых
][][ gl jj dd ≥ , в оптимальном рас-
писании не смогут занять позицию меньшую, чем 1+k .
Теорема 16. Если конкурирующее задание ][gj в результате выполне-
ния для него итерации оптимизации осталось на исходной позиции и все
задания на позициях ng ,1+ запаздывающие, то задания, для которых
][][ gl jj dd ≥ , ngi ,1+∈ , исключаются из числа конкурирующих.
Теорема 17 [4]. Запаздывающее задание ][gj на k-й итерации может
занять более раннюю позицию, что приведет к улучшению целевой функ-
ции, только в том случае, если хотя бы у одного задания ][kj на интервале
1,1 −g есть резерв и выполняется
][][ gk jj dd > , либо (в случае отсутствия
резервов) на интервале 1,1 −g есть задания с метками.
Теорема 18 [4]. Пусть в последовательности kσ для запаздывающих
заданий ][kj , Jj r ∈][ выполняется ,
][][ rk jj ll ≤
][][ rk jj dd ≤ . Тогда в оптима-
льном расписании задание ][kj будет предшествовать заданию ][rj .
Теорема 19 [4]. Неконкурирующие задания в последовательности kσ
не могут занять более ранние позиции, чем позиции, занимаемые ими в спσ .
Теорема 20. Пусть уже построена оптимальная подпоследовательность
на интервале 1,1 −g . Запаздывающее конкурирующее задание ][gj на k-й
итерации, выполняемой для определения возможности использования ре-
зервов этим заданием, не может быть перемещено на более раннюю пози-
цию, если на интервале 1,1 −g ни у одного из заданий нет резервов и для
всех помеченных заданий выполняется
,
][*
][ gi
jj
ll ≤ 1,1 −= gi .
Теорема 21 [4]. Если в последовательности kσ конкурирующее зада-
ние ][gj в результате выполнения для него итерации оптимизации не испо-
льзовало существующие резервы, минимальное значение функционала соо-
тветствует позиции g, занимаемой этим заданием, и если ][rj∀ , ngr ,1+= ,
][][ gr jj dd ≥ и
][][ rr jj dC ≥ , то задания ][rj исключаются из множества кон-
курирующих, а последовательность kσ оптимальна.
ПДС-алгоритмы и труднорешаемые задачи комбинаторной оптимизации
Системні дослідження та інформаційні технології, 2009, № 4 27
Теорема 22. Пусть на итерации k , выполняющейся для очередного
конкурирующего запаздывающего задания ][gj , для всех ][lj , 11 −, gl = ,
справедливо [ ] [ ]ll jj Cd ≤ , для всех *
][lj выполняется
][*][ gl
jj
ll ≤ и на интервале
, ng резервы отсутствуют. Тогда запаздывающие задания, занимающие по-
зиции g, n , исключаются из множества конкурирующих, а последовательно-
сти kσ отвечает оптимальное значение функционала.
Теорема 23. Если на интервале встраивания конкурирующего задания
][gj есть задание ][rj , для которого
][][ gr jj dd < ,
][][ gr jj ll < , и ][rj опазды-
вает, то осуществляется декомпозиция рассматриваемой подпоследователь-
ности, и при выполнении итерации оптимизации для ][gj задания на интер-
вале r,1 не рассматриваются, а оптимизация осуществляется на интервале
1,1 −+ gr .
Теорема 24. Пусть в последовательности kσ задания ][gj и ][kj конку-
рирующие ( kg < ) и выполняется
[ ] [ ]
нн][][ ppgk jjjj lCdd −<< ( нp — позиция
встраивания задания ][gj ), а на интервале н,1 p резервы отсутствуют. Если в
результате выполнения итерации оптимизации задание ][gj заняло позицию
нps > , то задание ][kj в оптимальном расписании не сможет занять пози-
цию меньшую, чем 1+s .
При невыполнении условия теоремы 10 существующие резервы в по-
следовательности kσ недостаточны для перемещения задания ][gj на более
ранние позиции. Процедура встраивания с последующей оптимизацией для
этого задания не выполняется, что существенно сокращает число выполняе-
мых перестановок. В теоремах 11–13, 15, 18, 23, 24 сформулированы усло-
вия, позволяющие уменьшать интервал встраивания очередного запазды-
вающего задания, и так как процедура оптимизации осуществляется на этом
интервале, соответственно сокращается число перестановок.
Условия теоремы 14 отсекают выполнение процедур встраивания за-
паздывающего задания на более ранние позиции, а оптимизация осуществ-
ляется за счет резервов, освобожденных заданиями, ранее их использовав-
шими, и в выражении (7) определяется возможность выполнения таких
перестановок. При выполнении условий теорем 16, 19, 21, 22 часть конку-
рирующих заданий исключается, так как для этих заданий не выполняются
итерации оптимизации, что сокращает объем вычислений. В теоремах 17 и
20 сформулированы условия, определяющие возможность уменьшения зна-
чения функционала при перемещении запаздывающего задания на более ран-
ние позиции в текущей последовательности.
М.З. Згуровский, А.А. Павлов, Е.Б. Мисюра
ISSN 1681–6048 System Research & Information Technologies, 2009, № 4 28
ПЕРСПЕКТИВЫ РАЗВИТИЯ ПДС-АЛГОРИТМОВ
Свойства ПДС-алгоритма решения задачи МСЗ могут быть использованы
при построении ПДС-алгоритмов для решения задач «Минимизация сум-
марного взвешенного запаздывания при выполнении независимых заданий
на одном приборе» (МСВЗ) и «Минимизация суммарного опережения и за-
паздывания относительно директивных сроков при выполнении независи-
мых задач одним прибором» (О/З).
Для задачи МСВЗ, как и для задачи МСЗ, приоритет определяется от-
ношением jj lω . Поэтому в ПДС-алгоритме будут использоваться те же
типы и правила перестановок с учетом различных весов заданий, что и для
ПДС-алгоритма задачи МСЗ. Это позволит учитывать дополнительные от-
сечения, что существенно сократит трудоемкость алгоритма. ПДС-алгоритм
задачи МСЗ войдет в состав ПДС-алгоритма решения задачи МСВЗ как его
наиболее трудоемкий частный случай.
Алгоритм решения задачи О/З базируется на следующих теоремах.
Обозначим jjj Cdr −= резерв задания j . Очевидно, jj Er = , где
jE — опережение задания j относительно его директивного срока. Следо-
вательно, уменьшение опоздания за счет резервов незапаздывающих зада-
ний приводит к уменьшению функционала О/З.
Теорема 25 [15]. Последовательность, отсортированная по невозраста-
нию значений длительности выполнения, не имеющая опережающих работ,
является оптимальной по критерию О/З.
Теорема 26 [15]. Последовательность, отсортированная по неубыванию
значений длительности выполнения, не имеющая запаздывающих работ, яв-
ляется оптимальной по критерию О/З.
Обозначим }{minmin jrr = ; rN — число заданий с резервами ( 0>jr );
зN — число запаздывающих заданий ( 0≤jr ).
Теорема 27 [16] (использование резервов опережающих заданий). Если в
последовательности σ зNNr > , то при увеличении начала выполнения зада-
ний на величину minr значение функционала О/З уменьшается также на minr .
На каждой итерации при увеличении моментов начала выполнения за-
даний в текущей последовательности на minr при условии зNNr > значе-
ние функционала также уменьшается на minr . При зNNr ≤ получена по-
следовательность Rσ .
Теорема 28 [16] (признак оптимальности последовательности Rσ ). Если
в последовательности Rσ резервы отсутствуют, то она оптимальна по кри-
терию О/З.
Приведенные результаты будут использованы при создании ПДС-
алгоритма решения задачи О/З для определения направленности перестано-
вок, а также при определении условия выполнения полиномиальной состав-
ляющей алгоритма.
ПДС-алгоритмы и труднорешаемые задачи комбинаторной оптимизации
Системні дослідження та інформаційні технології, 2009, № 4 29
СТАТИСТИЧЕСКИЕ ИССЛЕДОВАНИЯ АЛГОРИТМОВ И ПУТИ
ПОВЫШЕНИЯ ИХ ЭФФЕКТИВНОСТИ
Предварительные исследования МСЗ на задачах с размерностью до 1000 за-
даний показали, что данный алгоритм не имеет аналогов среди существующих
алгоритмов и может применяться для задач размерности значительно большей,
чем 500 заданий. Алгоритм не только конструирует оптимальные расписа-
ния для больших задач, но и делает это за приемлемое время.
Для МВМ проведено 7700 испытаний с размерностью до 300 зада-
ний (решались также индивидуальные задачи с размерностью до 1000 зада-
ний). В 70% случаев результирующее расписание теоретически оптимально.
Анализ результатов статистического моделирования показал, что полино-
миальная составляющая ПДС–алгоритма задачи МВМ является статистиче-
ски значимой для моделируемых произвольно индивидуальных задач.
Для МСЗП проведены испытания на задачах с размерностью до 3000
заданий с числом приборов до 30. В 87% случаев результирующее расписа-
ние теоретически оптимально.
Для МВМ и МСЗП дальнейшие исследования проводятся с целью обо-
снования новых логико-аналитических условий для нахождения точного
решения задачи полиномиальной составляющей алгоритма.
Так, для МВМ в работе [5] предложен алгоритм построения оптималь-
ного расписания для индивидуальных задач МВМ, отношения предшество-
вания которых имеют вид цепочек, простых или сложных конструкций с
произвольной степенью вложения. Рассматриваемая индивидуальная задача
МВМ может быть решена за полиномиальное время, когда реализуются ус-
ловия выполнения полиномиальной составляющей ПДС-алгоритма, т.е. в
результате решения исходной индивидуальной задачи алгоритм строит то-
лько структуры, имеющие вид цепочек либо конструкций произвольного
вида.
В работе [7, 14] приведены новые условия полиномиальной состав-
ляющей ПДС-алгоритма задачи МВМ. Доказано, что оптимальное рас-
писание может быть получено за полиномиальное время для множеств мак-
симальных приоритетов, не являющихся в общем случае совокупностью
конструкций.
В работе [8] рассмотрены новые условия полиномиальной составляю-
щей, реализация которых дает точное решение за полиномиальное время.
Выведены дополнительные условия, определенные для задачи, все мно-
жество заданий которой является одним множеством максимального при-
оритета. Предложена модификация полиномиальной составляющей ПДС-
алгоритма, реализующего эти условия.
Для задачи МСЗ дальнейшие исследования будут проводиться по двум
направлениям, дополняющим друг друга.
1. Выделение случаев, когда с учетом декомпозиции реализуется
трудоемкий перебор различных вариантов использования резервов предше-
ствующих заданий конкурирующими заданиями и доказательство эффек-
тивности экспоненциальной составляющей алгоритма на основе эксперимен-
тальных исследований.
М.З. Згуровский, А.А. Павлов, Е.Б. Мисюра
ISSN 1681–6048 System Research & Information Technologies, 2009, № 4 30
2. Выделение случаев, когда с учетом декомпозиции реализуется тру-
доемкий перебор вариантов решения задачи и теоретическое обоснование
расширения области определения полиномиальной составляющей алгорит-
ма в тех случаях, когда экспоненциальная составляющая приводит к незна-
чительному перебору вариантов.
Распараллеливание вычислений
Общим универсальным принципом повышения эффективности ПДС-
алгоритмов является принцип распараллеливания вычислений, позво-
ляющий:
• реализовать выполнение независимых перестановок различных ти-
пов на параллельных процессорах (МСЗП);
• останавливать вычислительный процесс при выполнении одного из ус-
ловий полиномиальной составляющей алгоритма (МСЗ, МСЗП);
• управлять дальнейшим процессом вычислений на основе текущего
анализа результатов параллельных вычислений (МСЗ, МВМ, МСЗП);
• гарантированно уменьшать общее время вычислений (МСЗ, МВМ,
МСЗП).
ЗАКЛЮЧЕНИЕ
Анализируются свойства ПДС-алгоритмов, построенных для отдельных
классов одноэтапных задач теории расписаний, а также общие свойства и
принципиальные отличия алгоритмов. Обосновываются пути их модифика-
ции с целью повышения эффективности. Рассматривается возможность по-
строения новых ПДС-алгоритмов с использованием теоретических свойств
известных.
ЛИТЕРАТУРА
1. Гери М.Р., Джонсон Д.С. Вычислительные машины и труднорешаемые зада-
чи.— М.: Мир, 1982. — 416 с.
2. Згуровський М.З., Панкратова Н.Д. Основи системного аналізу. — Київ: Ви-
давнича група BHV, 2007. — 544 c.
3. Павлов О.А., Павлова Л.О. ПДС-алгоритми для важкорозв’язуємих ком-
бінаторних задач. Теорія і методологія розробки. — Ужгород: Поличка
«Карпатського краю», 1998. — 320 с. (англ. мовою).
4. Павлов А.А., Мисюра Е.Б. Эффективный точный ПДС-алгоритм решения зада-
чи о суммарном запаздывании для одного прибора // Системні дослідження
та інформаційні технології. — 2004. — № 4. — С.30–59.
5. Конструктивные полиномиальные алгоритмы решения индивидуальных задач
из класса NP / А.А. Павлов и др. — Киев: Техніка. — 1993. — 128 с.
6. Павлов А.А., Теленик С.Ф. Информационные технологии и алгоритмизация в
управлении. — Киев: Техніка, 2002. — 344 с.
7. Павлов О.А., Аксьонова Л.О. «Мінімізація сумарного зваженого моменту
закінчення робіт» як перший рівень моделі дрібносерійного виробництва
та способи її розв’язання // Системні дослідження та інформаційні
технології. — 2002. — № 1. — С.119–130.
ПДС-алгоритмы и труднорешаемые задачи комбинаторной оптимизации
Системні дослідження та інформаційні технології, 2009, № 4 31
8. Аксенова Л.А. Новые полиномиальные подклассы труднорешаемой задачи
«Минимизация суммарного взвешенного момента» для множества одного
приоритета // Управляющие системы и машины. — 2002. — № 6. — С. 21–28.
9. Du J. and Leung J.Y.-T. Minimizing total tardiness on one processor is NP-hard //
Math. Oper. Res. — 1990. — № 15. — Р. 483–495.
10. Shwarz W. and Mukhopadhyay S.K. Decomposition of the single machine total tardi-
ness problem // Operations Research Letters. — 1996. — № 19. — Р. 243–250.
11. Lawler E.L. Sequencing jobs to minimize total weighted completion time subject to
precedence constraints // Ann. Discrete Math. — 1978. — № 2. — P. 75–90.
12. Конвей Р.В., Максвелл У.Л. Теория расписаний. — М.: Наука, 1975. — 359 с.
13. Танаев В.С., Шкурба В.В. Введение в теорию расписаний. — М.: Наука,
1975. — 256 с.
14. Павлов А.А., Аксенова Л.А. Новые условия полиномиальной составляющей
ПДС-алгоритма задачи «Минимизация суммарного взвешенного момента»
// Проблемы программирования. — 2001. — № 1–2. — С. 69–75.
15. Ow P.S., Morton T.E. The Single Machine Early: Tardy Problem // Management
Science. — 1989. — 35, № 2. — P. 177–191.
16. Павлов О.А., Місюра О.Б., Мельников О.В. Дослідження властивостей та
розв’язання задачі «Мінімізація сумарного штрафу як за випередження, так
i за запізнення відносно директивних строків при виконанні незалежних
завдань одним приладом» // Вісн. НТУУ «КПІ». Інформатика, управління та
обчислювальна техніка. — 2008. — № 48. — 7 с.
Поступила 29.04.2009
|
| id | nasplib_isofts_kiev_ua-123456789-42235 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1681–6048 |
| language | Russian |
| last_indexed | 2025-12-07T18:18:49Z |
| publishDate | 2009 |
| publisher | Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| record_format | dspace |
| spelling | Згуровский, М.З. Павлов, А.А. Мисюра, Е.Б. 2013-03-13T16:46:49Z 2013-03-13T16:46:49Z 2009 ПДС-алгоритмы и труднорешаемые задачи комбинаторной оптимизации / М.З. Згуровский, А.А. Павлов, Е.Б. Мисюра // Систем. дослідж. та інформ. технології. — 2009. — № 4. — С. 14–31. — Бібліогр.: 16 назв. — рос. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/42235 519.854.2 Формулируются базовые принципы построения ПДС-алгоритмов. Приводятся обобщения повышения эффективности их использования. Анализируется возможность создания новых ПДС-алгоритмов на основе существующих. Формулюються базові принципи побудови ПДС-алгоритмів. Наводяться узагальнення по підвищенню ефективності їхнього використання. Аналізується можливість створення нових ПДС-алгоритмів на основі існуючих. Based on the analysis of PDC-algorithms for intractable combinatorial optimization problems, general principles of their building are formulated and generalizations about increasing the effectiveness of their using are given. A possibility of constructing new PDC-algorithms on the basis of the existed ones is analyzed. ru Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України Системні дослідження та інформаційні технології Теоретичні та прикладні проблеми і методи системного аналізу ПДС-алгоритмы и труднорешаемые задачи комбинаторной оптимизации ПДС-алгоритми та важкорозв’язувані задачі комбінаторної оптимізації PDC-algorithms and intractable combinatorial optimization problems Article published earlier |
| spellingShingle | ПДС-алгоритмы и труднорешаемые задачи комбинаторной оптимизации Згуровский, М.З. Павлов, А.А. Мисюра, Е.Б. Теоретичні та прикладні проблеми і методи системного аналізу |
| title | ПДС-алгоритмы и труднорешаемые задачи комбинаторной оптимизации |
| title_alt | ПДС-алгоритми та важкорозв’язувані задачі комбінаторної оптимізації PDC-algorithms and intractable combinatorial optimization problems |
| title_full | ПДС-алгоритмы и труднорешаемые задачи комбинаторной оптимизации |
| title_fullStr | ПДС-алгоритмы и труднорешаемые задачи комбинаторной оптимизации |
| title_full_unstemmed | ПДС-алгоритмы и труднорешаемые задачи комбинаторной оптимизации |
| title_short | ПДС-алгоритмы и труднорешаемые задачи комбинаторной оптимизации |
| title_sort | пдс-алгоритмы и труднорешаемые задачи комбинаторной оптимизации |
| topic | Теоретичні та прикладні проблеми і методи системного аналізу |
| topic_facet | Теоретичні та прикладні проблеми і методи системного аналізу |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/42235 |
| work_keys_str_mv | AT zgurovskiimz pdsalgoritmyitrudnorešaemyezadačikombinatornoioptimizacii AT pavlovaa pdsalgoritmyitrudnorešaemyezadačikombinatornoioptimizacii AT misûraeb pdsalgoritmyitrudnorešaemyezadačikombinatornoioptimizacii AT zgurovskiimz pdsalgoritmitavažkorozvâzuvanízadačíkombínatornoíoptimízacíí AT pavlovaa pdsalgoritmitavažkorozvâzuvanízadačíkombínatornoíoptimízacíí AT misûraeb pdsalgoritmitavažkorozvâzuvanízadačíkombínatornoíoptimízacíí AT zgurovskiimz pdcalgorithmsandintractablecombinatorialoptimizationproblems AT pavlovaa pdcalgorithmsandintractablecombinatorialoptimizationproblems AT misûraeb pdcalgorithmsandintractablecombinatorialoptimizationproblems |