Ефективний точний ПДС-алгоритм розв’язання задачі про сумарне запізнювання для одного приладу

The effective exact algorithm is presented in this article for total tardiness problem solution when processing independent tasks with due dates on one machine. The algorithm is based on the new approach to the solution of problems with due dates, the main point of the approach is the optimal utiliz...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2019
Автори:	Pavlov, A. A., Misura, E. B.
Формат:	Стаття
Мова:	Російська
Опубліковано:	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2019
Онлайн доступ:	https://journal.iasa.kpi.ua/article/view/171527
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	System research and information technologies
Завантажити файл:

Репозитарії

System research and information technologies

_version_	1867334367696650240
author	Pavlov, A. A. Misura, E. B.
author_facet	Pavlov, A. A. Misura, E. B.
author_institution_txt_mv	[ { "author": "A. A. Pavlov", "institution": null }, { "author": "E. B. Misura", "institution": null } ]
author_sort	Pavlov, A. A.
baseUrl_str	http://journal.iasa.kpi.ua/oai
collection	OJS
datestamp_date	2019-06-25T17:03:13Z
description	The effective exact algorithm is presented in this article for total tardiness problem solution when processing independent tasks with due dates on one machine. The algorithm is based on the new approach to the solution of problems with due dates, the main point of the approach is the optimal utilization of untardy jobs' slack times. The algorithm allows to get solutions that are qualitatively grater than known results.
first_indexed	2025-07-17T10:25:19Z
format	Article
fulltext	© А.А. Павлов, Е.Б. Мисюра, 2004 30 ISSN 1681–6048 System Research & Information Technologies, 2004, № 4 TIДC АВТОМАТИЗОВАНІ СИСТЕМИ УПРАВЛІННЯ УДК 519.854.2 ЭФФЕКТИВНЫЙ ТОЧНЫЙ ПДС-АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ О СУММАРНОМ ЗАПАЗДЫВАНИИ ДЛЯ ОДНОГО ПРИБОРА А.А. ПАВЛОВ, Е.Б. МИСЮРА Предложен эффективный точный алгоритм решения задачи о суммар- ном запаздывании при выполнении независимых заданий с директив- ными сроками одним прибором. Алгоритм основан на новом подходе к решению задач с директивными сроками и заключаетcя в оптимальном использовании резервов времени незапаздывающих заданий. Его эф- фективность качественно превышает эффективность известных алго- ритмов. ВВЕДЕНИЕ Рассматривается модель задачи о суммарном запаздывании для одного при- бора в предположении, что известно множество независимых заданий },...,,{ 21 njjjJ = , каждое из которых состоит из одной операции. При этом также известны длительность jl и директивный срок выполнения jD . Зада- ния поступают в систему одновременно в момент времени njd j ,1,0 == . Прерывания не допускаются. Необходимо построить расписание выполне- ния заданий для одного прибора, минимизирующее суммарное опоздание при их выполнении, ( )∑ = −= n j jj D,Cf 1 0max , где jC — момент завершения выполнения задания j . Обзор методов решения этой задачи приведен в работе [1]. Согласно Ду и Люнгу [2], задача является NP-сложной. Эммонс [3] раз- работал правила доминантности, которые были применены в алгоритмах ветвей и границ [4 – 6] и в алгоритмах динамического программирования [4, 7 – 10]. Алгоритм динамического программирования Шрейга и Бейкера [9] находится в категории второго поколения, так как он решает задачи с количеством заданий до 50 для 101 ≤≤ kl . Лоулер [11] обнаружил, что зада- Эффективный точный ПДС-алгоритм решения задачи о суммарном запаздывании … Системні дослідження та інформаційні технології, 2004, № 4 31 ча может быть декомпозирована на подзадачи путем определения позиции работы с наибольшим временем выполнения в оптимальной последователь- ности. Затем он представил правило для уменьшения списка возможных по- зиций. Этот список в дальнейшем укорачивается правилами Поттса и Ван Вассенгова [7], Шварца [12]. Последние алгоритмы третьего поколения Поттса и Ван Вассенгова [7, 8] комбинируют результат Лоулера [11]: снача- ла разбить задачу на подзадачи допустимой размерности, а затем решить каждую подзадачу динамическим алгоритмом Шрейга и Вейкера [9]. Они были способны решить задачи с количеством заданий до 100 при 1001 ≤≤ kl . Поттс и Ван Вассенгов [8, с. 413] указывают на то, что для ре- шения задач с более чем 100 заданиями необходим новый подход. Для решения данной задачи созданы конструктивные и декомпозици- онные эвристики. Наиболее известные из них исследуются в работе [13], где показано, что все они представляют очень плохие нижние границы коэф- фициентов аппроксимации: их нижние границы, по меньшей мере, линей- но зависят от размерности задачи. В статье [1] рассматривается алгоритм четвертого поколения, который эффективно решает задачи с количеством заданий до 150. Самый современный точный метод Щварца, Гроссо и Кросе [14] может решать задачи с размерностью до 500 работ. Мы предлагаем эффективный точный ПДС-алгоритм (алгоритм с поли- номиальной и экспоненциальной составляющими) решения задачи, осно- ванный на новом подходе к решению задач с директивными сроками, кото- рый заключается в оптимальном использовании резервов времени незапаздывающих заданий, позволяющий решать задачи с числом заданий, существенно большим 500. Идея нашего подхода заключается в исследовании свойств рассматри- ваемых классов труднорешаемых задач, доказательстве положений, правил, позволяющих разработать единый принцип вычислений, и на их основе по- строении ПДС-алгоритмов [15, 16]. Эти алгоритмы основаны на выделении полиномиальной составляющей алгоритма и получении условий, когда экс- поненциальная составляющая может декомпозировать начальную задачу на подзадачи меньшего размера. Для каждого такого алгоритма выводятся ло- гико-аналитические условия (p-условия), которые проверяются в процессе решения произвольной индивидуальной труднорешаемой задачи, и в случае их выполнения данная задача точно решается полиномиальным подалго- ритмом. Экспоненциальный подалгоритм содержит строго определенные логико-аналитические условия (d-условия). При их выполнении в процессе решения задача строго декомпозируется на подзадачи меньшего размера. Таким образом, новым в предложенном подходе является выделение по- линомиально разрешимых подклассов труднорешаемых комбинаторных задач не путем введения соответствующих ограничений в постановки задач, а на ос- нове анализа процесса решения произвольных индивидуальных задач. Качественное отличие разработанных алгоритмов от существующих — статистическая значимость (высокая частота получения) точных решений задач большой размерности за приемлемое время, что открывает широкие возможности для решения реальных практических труднорешаемых задач. А.А. Павлов, Е.Б. Мисюра ISSN 1681–6048 System Research & Information Technologies, 2004, № 4 32 ТЕОРЕТИЧЕСКОЕ ОБОСНОВАНИЕ В статье [17] изложен новый подход к решению задачи «Минимизация сум- марного взвешенного опоздания при выполнении независимых заданий с директивными сроками одним прибором» и приведен алгоритм, который позволил получить точные решения для задач с числом переменных, суще- ственно большим 50. Рассмотрим случай, когда веса для всех заданий рав- ны 1. Введем следующие определения [17]. Определение 1. Резервом времени ][gjr задания ][gj называется вели- чина ][][][ ggg jjj CDr −= . Определение 2. Перестановкой называется процедура одновременного переноса задания ][gj на позицию k ( gk > ) и заданий, занимающих пози- ции kkgg ,1,...,2,1 −++ соответственно на позиции 1,...,1, −+ kgg . Определение 3. Интервалом перестановки задания ][gj на позицию k называется множество заданий, находящихся на позициях ...,2,1 ++ gg kk ,1,... − до выполнения перестановки. Определение 4. Встраиванием называется процедура одновременного переноса задания ][gj на позицию p ( pg > ) и заданий 1,...,1, −+ gpp со- ответственно на позиции ggpp ,1,...,2,1 −++ . Определение 5. Интервалом встраивания ][gjI задания ][gj называется множество заданий, стоящих до встраивания на позициях 1,...,1, −+ gpp , где p определяется из условия ∑∑ − = − −= ≤−< 11 1 ][][][][ g pi jjj g pi j iggi lDCl . (1) Если же условие (1) не выполняется ни для одной позиции, то 1=p . Таким образом, опоздание по заданию j на позиции p должно быть равно нулю или минимально. Определение 6. Задание ][gj называется запаздывающим в последова- тельности σ, если для него выполняется условие ][][ gg jj CD < , где g — по- зиция, которую задание j занимает в последовательности σ . Определение 7. Последовательностью упσ (сигма упорядоченная) на- зывается последовательность заданий множества J , nj ,1= , в которой за- дания упорядочены по неубыванию длительностей jl , т.е. ij llij ≤∀ :, , ij < . Справедливы следующие утверждения [17]. Утверждение 1. Если в последовательности упσ запаздывающим за- даниям не предшествуют задания с резервом времени, то не существует пе- реносов заданий, приводящих к улучшению целевой функции. Эффективный точный ПДС-алгоритм решения задачи о суммарном запаздывании … Системні дослідження та інформаційні технології, 2004, № 4 33 Доказательство. Пусть в последовательности упσ для заданий, стоя- щих на позициях si ,1= , выполняется 0 ][][ ≥− ii jj DC , а для заданий, зани- мающих позиции nsi ,1+= , выполняется 0 ][][ ≤− ii jj DC . Очевидно, что переносы, которые могли бы привести к уменьшению целевой функции, возможны только для заданий, занимающих позиции si ,1= . Докажем, что не существует перестановок, приводящих к уменьшению f . Пусть в последовательности σ позиции glsgl <∈ ,,1, . Выполним пере- становку задания ][lj на позицию [g]. Значение целевой функции на интер- вале gl, до перестановки ( )∑ = −= g li jj ii DCf ][][ . После перестановки с учетом предположения, что задания, занимавшие позиции ggll ,1,...,2,1 −++ , перестали запаздывать (т.е. пусть до перестановки выполнялось ][][][ lii jjj lDC ≤− , gli ,1+= ) ][][][ 1 lil j g li jj DlCf −+=′ ∑ += , где ][ljC — момент окончания выполнения задания ][lj до перестановки; ∑ += + g li jj il lC 1 ][][ — момент окончания выполнения заданий ][lj после пере- становки. Необходимо доказать, что 0≤′− ff . ( ) =⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ −+−−+−=′− ∑∑ +=+= ][][][][][][][ 11 liliill j g li jj g li jjjj DlCDCDCff ( ) ≤−−= ∑∑ +=+= g li j g li jj iii lDC 11 ][][][ ( ) 0 1 ][][ ≤−∑ += g li jj il ll в силу того, что glill il jj ,1 , ][][ +=≤ . Докажем, что не существует встраиваний, приводящих к увеличению f . Значение целевой функции до встраивания ( )∑ = −= g pi jj ii DCf ][][ , [ ]spg ,1, ∈ . После встраивания задания ][gj на позицию p с учетом того, что ][gj перестанет запаздывать, т.е. ∑ − = ≤− 1 ][][][ g pi jjj igg lDC , значение целевой функ- ции А.А. Павлов, Е.Б. Мисюра ISSN 1681–6048 System Research & Information Technologies, 2004, № 4 34 ( )∑ − = −+=′ 1 ][][][ g pi jjj igi DlCf , где ][ijC — момент окончания выполнения заданий ][ij до выполнения процедуры встраивания задания ][gj 1,, −=∀ gpii ; ][][ gi jj lC + — момент окончания выполнения заданий ][ij после выполнения процедуры встраива- ния ][gj . Необходимо доказать, что 0≤′− ff . ( ) ( )≤−+−−+−=′− ∑∑ − = − = 11 ][][][][][][][ g pi jjj g pi jjjj igiiigg DlCDCDCff ( ) 0 1 ][][ ≤−≤ ∑ − = g pi jj gi ll в силу того, что ∑ − = ≤− 1 ][][][ g pi jjj igg lDC , 1, ][][ −=∀≥ gpill ig jj . ■ Утверждение 2. Встраивание запаздывающего задания ][gj на пози- цию pf < не может привести к улучшению целевой функции. Доказательство. В соответствии с определением 5, на позиции p опо- здание по заданию ][gj становится равным нулю. Встраивание задания ][gj на любую позицию pf < приводит к увеличению его резерва и перемещает задания, стоящие на позициях 1,...,1, −+ pff , на позиции pff ,...,2,1 ++ . Такое перемещение приводит к увеличению целевой функции, если для ка- кого-либо задания на 1, −pf выполняется хотя бы одно из условий: 1) для 1,,][ −∈ pfij i выполняется ][][ ii jj DC ≥ , т.е. задание ][ij явля- ется запаздывающим, и в результате встраивания опоздание по нему увели- чивается на величину ][gjl ; 2) для 1,,][ −∈ pfij i выполняется ][][ ii jj DC < и ][][][ gi jjij lCD <− , т.е. ][ij до встраивания задания ][gj не запаздывало, но в результате встраива- ния станет запаздывать на величину ][][][ gii jjj lDC +− . Если ни для одного из заданий ][ij , 1, −∈ pfi не выполняется ни одно из перечисленных условий, то целевая функция не ухудшается, но и не улучшается в результате встраивания ][gj на позицию pf < , так как опо- здание на позиции p по заданию ][gj равно нулю. ■ Утверждение 3. Пусть в последовательности упσ 1,1,][ −=∀ pij i , 0 ][ ≤ ijr . Обозначим ее уп1σ . Запаздывающее задание ][gj в последователь- Эффективный точный ПДС-алгоритм решения задачи о суммарном запаздывании … Системні дослідження та інформаційні технології, 2004, № 4 35 ности уп1σ в результате выполнения встраивания ( ][gjI 1, −= gp ) может занять более раннюю позицию, что улучшит целевую функцию только в том случае, если в последовательности уп1σ хотя бы у одного из заданий на ин- тервале встраивания ][gjI есть резерв времени, больший нуля. Доказательство. Выведем условия, при выполнении которых в резуль- тате процедуры встраивания значение целевой функции уменьшается, т.е. выполняется 0>ff ′− . Пусть для ][zj ( gzp <≤ ) выполняется ][][ zz jj CD > , для остальных за- даний ][gjIi ∈ ][][ ii jj CD ≤ . Согласно утверждениям 1 и 2, встраивание, ко- торое может улучшить f , должно быть выполнено на позицию z . Встроим задание ][gj на позицию z . ( ) ( )∑∑ += − = −+−= g zi jj z pi jj iiii DCDCf 1 1 ][][][][ , ( )+−+⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ −−=′ ∑∑ − = − = 11 ][][][][][ ,0max z pi jjj g zi jj iigig DCDlCf ( ) ( ) ][][][][][][ ,0max 1 1 zgzigi jjj g zi jjj DlCDlC −++−++ ∑ − += , ( ) ( )∑∑ += − = −+−=′− g zi jj z pi jj iiii DCDCff 1 1 ][][][][ ( )−−− ∑ − = 1 ][][ z pi jj ii DC ( ) ( ) ( )−−+−−−−−− ∑ − += ][][][][][][ 0max1 1 1 zgzgii jjjj g zi jj Dl,ClzgDC ( ) ( )−−+−−−=⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ −−− ∑ − = ][][][][][][ 1,0max 1 ggggig jjj g zi jjj DClzgDlC ( )=−+−⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ −−− ∑ − = ][][][][][][ 0max,0max 1 zgzgig jjj g zi jjj Dl,CDlC ( ) ( ) ][][][][][][ ,0max1,min 1 zggigg jjj g zi jjj rllzglDC −−−−−⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ −= ∑ − = . (2) Заметим: если существует несколько заданий Zzk ∈ с резервами вре- мени на 1, −gp , то выражение (2) при встраивании ][gj на одну из позиций kz примет вид ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ −=′− ∑ − = 1 ][][][ ,min g zi jjj k igg lDCff ( )[ ]∑ − = −− 1 ][][][ ,min,0max g zi jjj k gig lrl , (3) А.А. Павлов, Е.Б. Мисюра ISSN 1681–6048 System Research & Information Technologies, 2004, № 4 36 где ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ − ∑ − = 1 ][][][ ,min g zi jjj igg lDC — уменьшение опоздания по заданию ][gj в результате встраивания на позицию z . Определяется величиной опоздания и длиной интервала встраивания и не зависит от длительности выполнения самого задания; ( )[ ]∑ − = − 1 ][][][ ,min,0max g zi jjj gig lrl — увеличение опоздания зада- ний на интервале встраивания в результате выполнения процедуры встраи- вания ][gj на позицию z . Определяется наличием резерва на этом интерва- ле. Следовательно, улучшение целевой функции возможно только в том случае, если на интервале встраивания ][gjI есть резерв, больший нуля. В случае отсутствия резервов выражение (3) принимает отрицательное зна- чение, так как длительность выполнения ][gj больше длительности заданий на интервале встраивания. ■ Пусть в последовательности уп1σ ][gj — первое запаздывающее зада- ние. За ним следуют ][ij , ngi ,1+= , 0 ][][ ≤− ii jj CD . Для ][zj , gzp << вы- полняется ][][ zz jj CD > . Для остальных заданий ][][ gjk Ij ∈ , ][][ kk jj CD ≤ . Обозначим эту последовательность уп2σ . Утверждение 4. Если в последовательности уп2σ в результате проце- дуры встраивания ][gj на позицию z значение функционала уменьшилось, и для всех ][kj ∈ ][gjI станет справедливо 0 ][ ≤ kjr , то полученная последова- тельность оптимальна. Доказательство. Для всех ][sj , 1,1 −= ps , 0 ][ ≤ sjr по определению по- следовательности уп1σ . Для всех ][ij , ngi ,1+= выполняется ][][ gi jj ll ≥ . По- сле встраивания ][gj на позицию z справедливо ∀ ][kj ∈ ][gjI 0 ][ ≤ kjr , следо- вательно, встраивание задания ][ij , ngi ,1+= на позицию z приведет, в соответствии с (3), к увеличению потерь по заданиям, смещенным на более поздние позиции в результате выполнения процедуры встраивания и, таким образом, к ухудшению значения функционала. ■ Утверждение 5. Если в последовательности уп2σ при проверке воз- можности встраивания задания ][gj на позицию z значение функционала ухудшится, то не существует перестановок и встраиваний, приводящих к уменьшению значения функционала, и последовательность уп2σ опти- мальна. Доказательство. В результате выполнения встраивания задания ][gj на позицию z справедливо 0<′− ff . Таким образом, существующих резер- вов на позиции z недостаточно для выполнения встраивания ][gj . Но Эффективный точный ПДС-алгоритм решения задачи о суммарном запаздывании … Системні дослідження та інформаційні технології, 2004, № 4 37 ∀ ][ij , ngi ,1+= , ][][ gi jj ll ≥ . Следовательно, не существует перестановок и встраиваний, приводящих к уменьшению значения функционала. ■ Утверждение 6. Если в последовательности упσ ни для одного из за- паздывающих заданий ][gj нет предшествующих заданий ][ij , 1,1 −= gi , для которых выполняется 0 ][][ >− ii jj CD , ][][ gi jj DD > , то не существует перестановок и встраиваний, приводящих к улучшению целевой функции. Доказательство. Встраивание. Задание ][gj встроим на позицию p (см. определение 5). Учитывая условие утверждения, что не существует предшествующих заданий ][sj , для которых 0 ][][ >− ss jj CD и ][][ gs jj DD > , получаем, что встраивание ][gj произойдет на интервале 1, −gp , на кото- ром для любого задания ][ij выполняется 0 ][][ ≥− ii jj DC , 1, −= gpt . (4) Пусть в выражении (4) 0 ][][ =− ii jj DC , 1, −= gpt . Тогда ][][ gg jj DCf −= , ( )∑ − = −+=′ 1 ][][][ g pi jjj igi DlCf , ( ) ( ) 0 11 ][][][][][][][ ≤−≤−+−−=′− ∑∑ − = − = g pi jj g pi jjjjj giigigg llDlCDCff , так как gill gi jj <∀≤ ][][ . Доказательство для случая 0 ][][ >− ii jj DC аналогично. Перестановки. Возможны перестановки задания с нулевым и ненуле- вым резервами времени. Рассмотрим все возможные случаи. 1. Пусть 0 ][][ >− ss jj CD , ][][ gs jj DD ≤ и задание ][gj после перестанов- ки запаздывает, т.е. ][][][ gsg jjj DlC >− . В этом случае ][][ gg jj DCf −= , ( ) ( ) ][][][][][ sggsg jjjjj DCDlCf −+>−=′ , ( ) ( ) ( )=−−−−−−=′− ][][][][][][][ sggsggg jjjjjjj DCDlCDCff ( ) ( ) 0 ][][][][][ ][ ≤−−≤−−= ggsgs jjjsjjj DClDCl , так как ][][][ sgg jjj lDC >− . А.А. Павлов, Е.Б. Мисюра ISSN 1681–6048 System Research & Information Technologies, 2004, № 4 38 2. Пусть 0 ][][ >− ss jj CD , ][][ gs jj DD ≤ и задание ][gj после перестанов- ки не запаздывает, т.е. ][][][ sgg jjj lDC ≤− . ][][ sg jj DCf −=′ . ( ) ( ) 0 ][][][][ ≤−−−=′− sggg jjjj DCDCff , так как ][][ gs jj DD ≤ . 3. Пусть 0 ][][ =− ss jj CD , ][][ gs jj DD ≤ и задание ][gj после перестанов- ки запаздывает, тогда ( ) =−=−−−−−=′− ∑∑ +=+= g si jsj g si jjjjjj iigsggg lllDlCDCff 1 ][ 1 ][][][][][][][ 0 ][][][][][ 1 1 ≤−<−−= ∑ − += gsigs jj g si jjj lllll , так как gsll gs jj <≤ , ][][ . 4. Пусть 0 ][][ =− ss jj CD , ][][ gs jj DD ≤ и задание ][gj после перестанов- ки не запаздывает, т.е. ][][][ sgg jjj lDC ≤− . В этом случае 0 11 ][][][][][ ≤−≤−−=′− ∑∑ +=+= g si jj g si jjj isigg lllDCff аналогично п. 3. Следовательно, так как для запаздывающего задания ][gj нет предше- ствующих заданий, имеющих резервы на интервале переноса ][gj , то не су- ществует перестановок, приводящих к уменьшению значения функционала. ■ Следствие 1. Если в последовательности упσ на интервале встраива- ния запаздывающего задания ][gj , определяемом позициями 1, −gp , резер- вы отсутствуют, то ][gj сможет занять более раннюю позицию, что приве- дет к уменьшению значения функционала только в том случае, если в последовательности упσ на интервале 1,1 −p есть задания ][kj , для кото- рых справедливо 0 ][][ >− kk jj CD , ][][ gk jj DD > . В этом случае резервы на интервале встраивания ][gj могут быть образованы в результате перестано- вок заданий ][kj на более поздние позиции. Следствие 2. Если в последовательности упσ для каждого ][kj , при- надлежащего множеству R заданий с резервами, и каждого ][gj , принадле- жащего множеству Y запаздывающих заданий, выполняется ][][ gk jj ll ≤ , ][][ gk jj DD ≤ , то не существует перестановок и встраиваний, приводящих к уменьшению значения функционала. Эффективный точный ПДС-алгоритм решения задачи о суммарном запаздывании … Системні дослідження та інформаційні технології, 2004, № 4 39 Утверждение 7. Если в последовательности упσ для запаздывающего задания ][gj существует предшествующее ][kj такое, что выполняются ус- ловия ][][][ ggk jjj lCD −> , ( ) ][][][][][ ,min kgggk jjjjj DCDCl −>− , то перестановка ][kj на позицию g приводит к уменьшению целевой функ- ции. Доказательство. Для доказательства утверждения выведем условия перестановки, при выполнении которых уменьшается целевая функция, т.е. 0>′− ff . ( )∑ = −= g ki jj ii DCf ][][ ,0max . После перестановки ][kj на позицию g ( ) ( ) ][][][][][ ,0max,0max 1 ikikg jjj g ki jj DlCDCf −−+−=′ ∑ += , ( ) ( )−−−−=′− ∑ = ][][][][ ,0max kgii jj g ki jj DCDCff ( ) ( )+−−=−−− ∑ += ][][][][][ 1 ,0max kgiki jj g ki jjj DCDlC ( ) ( )∑∑ +=+= −−−−+ g ki jjj g ki jj ikiii DlCDC 11 ][][][][][ ,0max,0max . Пусть все задания 11 −+ , gki = не запаздывают до переноса, т.е. 0 ][][ <− ii jj DC . Тогда ( ) ( ) ( )=−−−−+−−=′− ][][][][][][][ ,0max gkgggkg jjjjjjj DlCDCDCff ( ) ( ) 0,min ][][][][][ >−+−−= ggkkg jjjjj DClDC . Таким образом, если выполняется условие ( ) ][][][][][ ,min kgggk jjjjj DCDCl −>− , то при перестановке ][kj на позицию g происходит уменьшение целевой функции. ■ На основании доказанных утверждений сформулируем необходимые условия для перемещения запаздывающих заданий на более ранние пози- А.А. Павлов, Е.Б. Мисюра ISSN 1681–6048 System Research & Information Technologies, 2004, № 4 40 ции, при котором значение функционала уменьшается путем использования существующих резервов. Утверждение 8. Пусть в последовательности упσ ][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 , но меньше момента окончания ][gj . При этом ( ) ( ) 0,min ][][][][][ >−−− qgqgg jjjjj DClDC . Следовательно, перестановка задания ][qj после ][gj приведет к уменьшению значения функционала за счет использования резерва ][qj . 4. 0\|\| ][min ≤≤≤∀ ijrgiPi , но ][kj∃ , ][][ \|min gk jj DDPk >< , 0 ][ > kjr . На интервале перестановки задания ][gj резервы отсутствуют, но существу- ет задание ][kj , minPk < , директивный срок которого больше ][gjD и резерв больше нуля. Выполнение одного из условий 1–4 означает, что на интервале встраи- вания задания ][gj существуют резервы (условия 1–3) или они будут обра- зованы в результате перестановок (условие 4). При невыполнении условия 4 перестановка заданий, занимающих позиции 1,1 min −P , на интервал встраи- вания задания ][gj приведет к запаздыванию этих заданий, и так как они имеют меньшую длительность, чем ][gj , то встраивание задания ][gj приве- дет к увеличению значения функционала. Следовательно, если не выполня- ется ни одно из условий 1–4, то не существует встраиваний задания ][gj на более ранние позиции, улучшающих целевую функцию. ■ Следствие. Пусть в последовательности упσ число запаздывающих заданий 1з >n . Тогда, если в последовательности упσ ни для одного из за- Эффективный точный ПДС-алгоритм решения задачи о суммарном запаздывании … Системні дослідження та інформаційні технології, 2004, № 4 41 паздывающих заданий ][gj нет предшествующих заданий ][sj , gs < , для которых выполняется хотя бы одно из условий 1–4 , то последовательности упσ отвечает оптимальное значение функционала. Пусть в последовательности },,,{ ][]2[]1[ уп njjj …=σ запаздывающее задание ][gj в результате встраивания заняло позицию mP =min . Пометим его * ][mj , а полученную последовательность — )( ][gjσ . Утверждение 9. Запаздывающее задание ][kj , ,gmk 1+= в последова- тельности )( ][gjσ может быть встроено на более раннюю позицию, что при- ведет к улучшению целевой функции только в том случае, если хотя бы у одного предшествующего задания есть резерв времени либо (в случае от- сутствия резервов) только в результате перестановки * ][mj после ][kj . Доказательство. Доказательство в случае наличия резервов приведено в утверждениях 3 и 8. Рассмотрим случай, когда в последовательности )( ][gjσ нет резервов. Очевидно, что среди заданий на интервале 11 −k, перестановка на позицию k возможна только для задания * ][mj , так как 11 −=∀ ,ki , 0 ][][ ≤− ii jj CD , а для всех непомеченных заданий [ ] [ ]ki jj ll ≤ , 11 −= ,ki . Выполним перестановку на позицию k задания * ][mj . Значение целевой функции до перестановки [ ] [ ]( ) [ ] [ ]( )∑∑ == −=−= k mi jj k mi jj iiii DCDCf ,0max . После переноса * ][mj на позицию k [ ] [ ] [ ] [ ] [ ] [ ]( )∑∑ +=+= −−+−+=′ k mi jjjj k mi jj miimim lDCDlCf 11 ,0max , где [ ]mjC — момент окончания выполнения задания * ][mj до перестановки. Докажем, что ff ′− может быть больше нуля. [ ] [ ] [ ] [ ]( )−−+−=′− ∑ += k mi jjjj iimm DCDCff 1 [ ] [ ] [ ] [ ] [ ] [ ]( ) = ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ −−+−+− ∑∑ +=+= k mi jjjj k mi jj miimim lDCDlC 11 ,0max [ ] [ ] [ ] [ ] [ ] ++−−−= ∑ += mimmm j k mi jjjj DlCDC 1 А.А. Павлов, Е.Б. Мисюра ISSN 1681–6048 System Research & Information Technologies, 2004, № 4 42 [ ] [ ] [ ] [ ] [ ]( )[ ]=−−−−+ ∑ += k mi jjjjj miiii lDCDC 1 ,0max [ ] [ ] [ ]( ) [ ][ ]∑ += −−= k mi jjjj iiim lDCl 1 ,min . (5) Проанализируем выражение (5). Разобьем сумму (5) на две части. Пусть P — множество заданий на ,km+1 , которые после перестановки * ][mj уже не запаздывают, следовательно, [ ] [ ] [ ]{ } iim jjj DClP −≥: ; Q — множество заданий на ,km+1 , которые после перестановки * ][mj оста- лись запаздывающими и, следовательно, [ ] [ ] [ ]{ } iim jjj DClQ −<: . Выражение (5) примет вид [ ] [ ] [ ][ ] [ ] [ ][ ]∑∑ ∈∈ −+−− Qj jj Pj jjj i im i iii lllDC ][][ . (6) Так как справедливо ][ij∀ , k,m+i 1= , * ][][ mi jj ll ≤ , то полученное значе- ние выражения (6) может быть больше нуля и перестановка задания * ][mj на позицию k может привести к уменьшению .f ■ Утверждение 10. Пусть в последовательности )( ][gjσ задания ][lj , ng+l ,1= запаздывающие, и у всех предшествующих заданий ][ij , gi ,1= , 0 ][ ≤ ijr . В этом случае в оптимальной последовательности задания ][lj ос- танутся на занимаемых позициях на интервале ng+ ,1 . Справедливость этого утверждения основывается на том факте, что ][lj∀ , ng+l ,1= выполняется [ ] [ ]gl jj ll ≥ . Резервы последовательности упσ (исходной последовательности до встраивания задания ][gj на позицию m ) в последовательности )( ][gjσ использованы заданием меньшей длительно- сти ][gj . Следовательно, встраивание ][lj , ng+l ,1= на более ранние пози- ции приведет к увеличению потерь по заданиям, перемещаемым на более поздние позиции, и к ухудшению целевой функции. ■ Определение 8. Процедурой свободной перестановки называется про- цедура перестановки задания ][kj на позицию q ( qk < ) такую, что ][][ qk jj CD ≥ , ]1[][ + < qk jj CD , если хотя бы для одного задания на интервале qk ,1+ выполняется Эффективный точный ПДС-алгоритм решения задачи о суммарном запаздывании … Системні дослідження та інформаційні технології, 2004, № 4 43 qkiCD ii jj ,1 , ][][ +=< . Таким образом, свободная перестановка k выполняется на позицию с максимальным номером, на которой k не будет запаздывать. Очевидно, что в результате выполнения всех свободных перестановок в последовательно- сти упσ значение целевой функции уменьшается. При выполнении одной свободной перестановки значение целевой функции уменьшается на величину ( )∑ ∈ − zi jjj iik DCl ][][][ ,min , где { }qkiDCjZ ii jji ,1 , ][][][ +=>= . Примечание к определению 8. При выполнении нескольких свободных перестановок во избежание за- цикливания начинать следует с задания, имеющего максимальный дирек- тивный срок, т.е. просматривать незапаздывающие задания по убыванию их директивных сроков. Определение 9. Последовательность заданий, полученную в результате выполнения всех свободных перестановок в последовательности упσ , назо- вем спσ . Утверждение 11. Утверждения 1, 2, 4 – 8 справедливы для последова- тельности спσ . Доказательство. Выделим различия между последовательностями упσ и спσ . Покажем, что эти различия не нарушают доказательств приведенных выше утверждений. При доказательстве утверждений 1, 2, 4 – 8 основными приемами являлись перестановки и встраивания. Для перестановок доказательства утверждений аналогичны, если вме- сто упσ использовать спσ , по следующим причинам: • Все задания на интервале перестановки сдвигаются на более ранние позиции и, следовательно, их запаздывание уменьшается. При этом задания, нарушающие последовательность упσ (перенесенные в результате свобод- ных перестановок), имеют запаздывание, равное нулю, и поэтому могут быть исключены из рассмотрения как в f , так и в f ′ . • Для запаздывающих заданий в последовательности спσ упорядо- ченность в соответствии с длительностями сохраняется и, следовательно, длительность задания, которое переставляется, меньше длительности любо- го из заданий на интервале перестановки. Процедура встраивания для последовательности спσ аналогична про- цедуре встраивания для упσ , так как длительность встраиваемого задания в спσ всегда больше или равна длительности любого из заданий на интервале встраивания, что обусловливает необходимость для выполнения процедуры встраивания наличия резервов у заданий, занимающих более ранние пози- ции. А.А. Павлов, Е.Б. Мисюра ISSN 1681–6048 System Research & Information Technologies, 2004, № 4 44 Таким образом, утверждения 1, 2, 4 – 8 верны и для последовательности спσ . ■ На интервале встраивания в последовательности спσ могут находиться задания, перенесенные в результате свободных перестановок и нарушающие упорядоченность в соответствии с длительностями. Поэтому все задания, следующие за встраиваемым, необходимо переупорядочить в соответствии с их длительностями, и для запаздывающих заданий в этой последовательно- сти, в свою очередь, проверять возможность переноса на более ранние по- зиции за счет резервов незапаздывающих заданий. Таким образом, условие встраивания (3), справедливое для последова- тельности упσ , в спσ не выполняется. Утверждение 12. Для последовательности спσ не существует переста- новок и встраиваний, приводящих к улучшению целевой функции, если вы- полняется хотя бы одно из условий: а) niCD ii jj ,1 ,0 ][][ =∀≥− ; б) liCD ii jj ,1 ,0 ][][ =∀≤− , nliCD ii jj ,1 ,0 ][][ +=∀≥− ; в) niCD ii jj ,1 ,0 ][][ =∀≤− ; г) для каждого задания ][kj , принадлежащего множеству заданий с ре- зервами )(R , и каждого задания ][gj , принадлежащего множеству запазды- вающих заданий )(Y , выполняется YgRkllDD gkgk jjjj ∈∈∀≤≤ , , ][][][][ . Пункт а) не требует доказательства, так как 0=f . Доказательство пунктов б), в), г) аналогично доказательству утверждений 1, 3 и 6. ■ Следствие. При выполнении хотя бы одного из условий, сформулиро- ванных в утверждении 12, в последовательности спσ достигается опти- мальное значение функционала. Определение 10. Запаздывающее задание ][gj в последовательности спσ называется конкурирующим, если в ней найдется хотя бы одно пред- шествующее задание ][lj , для которого выполняются условия ][][ gl jj DD > и 0 ][][ >− ll jj CD . Определение 11. Последовательностью kσ называется последователь- ность, полученная из спσ в результате выполнения перестановок и встраи- ваний с целью оптимизации использования резервов времени незапазды- вающих заданий. Используются следующие типы перестановок и встраиваний. Перестановки заданий: а) для которых резерв времени больше нуля; б) использовавших резервы в результате перестановок и встраиваний. Эффективный точный ПДС-алгоритм решения задачи о суммарном запаздывании … Системні дослідження та інформаційні технології, 2004, № 4 45 Перестановки осуществляются, если при их выполнении значение функционала уменьшается. Встраивания: а) при наличии резервов на интервале встраивания; б) при образовании резервов на интервале встраивания в соответствии с условием 4, сформулированным в утверждении 8. Правила выполнения перестановок и встраиваний в последовательно- сти kσ приведены ниже. Введем правила пометки заданий в последовательности kσ при вы- полнении перестановок и встраиваний. В этой последовательности * обозначены задания, которые были запаз- дывающими в последовательности спσ и в результате выполнения переста- новок и встраиваний переместились на более ранние позиции, использовав резервы времени предшествующих заданий; ** помечены задания, ранее помеченные , которые в результате последующих перестановок перемести- лись на более поздние позиции (но эти позиции не соответствуют упорядо- ченности по длительностям этих заданий). За заданиями, помеченными или *, в последовательности kσ следуют запаздывающие задания с мень- шей длительностью. Рассмотрим структуру последовательности kσ . Каждому заданию в ней соответствует номер задания и номер позиции. В исходной последова- тельности упσ задания пронумерованы по неубыванию их длительностей. На следующих итерациях присвоенная нумерация сохраняется (меняются только номера позиций, занимаемых заданиями). Следовательно, в последо- вательности kσ чем меньше номер задания, тем меньше его длительность. Упорядоченность в соответствии с длительностями нарушают задания, по- меченные или *, которые в результате перестановок и встраиваний ис- пользовали резервы времени предшествующих заданий и переместились с позиций, соответствующих их длительностям, на более ранние позиции, что позволило улучшить значение целевой функции. Упорядоченность в соответствии с длительностями в последовательно- сти kσ нарушают также задания, которые в результате свободных переста- новок переместились на более поздние позиции. Все остальные задания упорядочены в соответствии с их длительностями. Таким образом, структуру последовательности kσ от последователь- ности спσ отличают только задания, помеченные или *, которые пере- местились на более ранние позиции. Сформулируем необходимые условия для перемещения в последова- тельности kσ запаздывающих заданий на более ранние позиции, при кото- ром значение функционала уменьшается за счет существующих и освобо- дившихся резервов. Утверждение 13. Пусть в последовательности kσ ][gj — запазды- вающее задание. Уменьшение значения функционала при перемещении ][gj А.А. Павлов, Е.Б. Мисюра ISSN 1681–6048 System Research & Information Technologies, 2004, № 4 46 на более ранние позиции возможно только при выполнении хотя бы одного из следующих условий: 1. ][ij∃ , giP ≤≤min \| 0\| ][ > ijr , ][][ gi jj DD > . На интервале встраивания задания ][gj есть задания ][ij , для которых ][][ gi jj DD > ; minP — позиция, где запаздывание по заданию ][gj минимально (или равно нулю). 2. ][qj∃ , gq < , ][][ gq jj CD > . 3. ][lj∃ , ][][][ , ggl jjj lCDgl −>< , ( ) −>− ][][][][ ,min gggl jjjj CDCl ][ljD− . 4. 0\|\| ][min ≤≤≤∀ ijrgiPi , но ][kj∃ , ][][ \|min gk jj DDPk >< . 5. 1,1\| −=∀ gii , 0 ][ ≤ ijr , но ][mj∃ ( ** ][mj ), gm < . Аналогично утверждению 8, выполнение одного из условий 1–4 озна- чает, что на интервале встраивания задания ][gj существуют резервы (усло- вия 1–3) или они будут образованы в результате перестановок (условие 4). Выполнение условия 5 означает, что в последовательности kσ присутству- ют задания, использовавшие резервы на интервале встраивания ][gj , и пере- мещение их на более поздние позиции приведет к образованию резервов на этом интервале. Если не выполняется ни одно из условий 1–5, то перемеще- ние ][gj на более ранние позиции приведет к увеличению значения функ- ционала. ■ Следствие. Пусть в результате выполнения алгоритма построена опти- мальная подпоследовательность на интервале k,1 . Если для каждого из за- паздывающих заданий на интервале nk ,1+ не выполняется ни одно из ус- ловий 1–5, то последовательность kσ оптимальна. Число итераций предлагаемого алгоритма определяется количеством конкурирующих заданий. На каждой итерации проверяется возможность использования резервов времени предшествующих заданий очередным кон- курирующим заданием и строится оптимальное расписание рассматривае- мой последовательности. На первой итерации строится оптимальное распи- сание для заданий на интервале 1,1 g , где ][ 1gj — первое запаздывающее конкурирующее задание в последовательности спσ . На следующей итера- ции рассматривается последовательность заданий на интервале 2,1 g , где ][ 2gj — следующее запаздывающее конкурирующее задание. Пусть уже выполнена 1−k итерация и построено оптимальное расписание для после- довательности заданий на интервале 1,1 −k . Переходим к очередному за- паздывающему конкурирующему заданию ][kj и строим оптимальное рас- писание для подпоследовательности kσ , включающей задания на интервале Эффективный точный ПДС-алгоритм решения задачи о суммарном запаздывании … Системні дослідження та інформаційні технології, 2004, № 4 47 k,1 . Проверим возможность уменьшения значения функционала за счет ис- пользования заданием ][kj существующих резервов времени или резервов, полученных в результате перестановок заданий с метками (или заданий с большей длительностью) на более поздние позиции. На каждой итерации значение функционала уменьшается или остается неизменным. Примечание. Необходимо различать конкурирующие запаздывающие задания, определенные в последовательности спσ , и задания, запаздывание которых относительно их директивных сроков возникло в процессе выпол- нения перестановок и встраиваний. Следующие утверждения, доказательство которых очевидно, позволят определить и исключить бесперспективные перестановки и встраивания. Утверждение 14. Запаздывающее задание ][gj на k -й итерации может занять более раннюю позицию, что приведет к улучшению целевой функции только в том случае, если хотя бы у одного задания ][kj на интервале 1,1 −g есть резерв и выполняется ][][ gk jj DD > либо (в случае отсутствия резервов) на интервале 1,1 −g есть задания с метками. В противном случае ][rj ис- ключается из множества конкурирующих. Утверждение 15. Пусть в последовательности kσ для запаздывающих заданий Jjj rk ∈][][ , выполняется , ][][ rk jj ll ≤ ][][ rk jj DD ≤ . Тогда в оптимальном расписании задание ][kj будет предшествовать ][rj [7]. Утверждение 16. Неконкурирующие задания в последовательности kσ не могут занять более ранние позиции, чем позиции, занимаемые ими в спσ . Утверждение 17. Пусть уже построена оптимальная подпоследователь- ность на интервале 1,1 −g . Запаздывающее конкурирующее задание ][gj на k -й итерации не может быть перемещено на более раннюю позицию и ис- ключается из числа конкурентоспособных, если на интервале 1,1 −g ни у од- ного из заданий нет резервов, и для всех помеченных заданий выполняется ][* ][ gi jj ll ≤ , 1,1 −= gi . Утверждение 18. Если в последовательности kσ конкурирующее задание ][gj в результате выполнения перестановок и встраиваний не использовало существующие резервы, минимальное значение функционала соответствует позиции g , занимаемой этим заданием, то задания ][rj , ngr ,1+= , для кото- рых ][][ gr jj DD ≥ , в оптимальной последовательности не могут занять позицию более раннюю, чем g . А.А. Павлов, Е.Б. Мисюра ISSN 1681–6048 System Research & Information Technologies, 2004, № 4 48 Утверждение 19. Если в последовательности kσ конкурирующее задание ][gj в результате выполнения перестановок и встраиваний не использовало существующие резервы, минимальное значение функционала соответствует позиции g , занимаемой этим заданием, а ][rj∀ , ngr ,1+= , ][][ gr jj DD ≥ и ][][ rr jj DC ≥ , то задания ][rj исключаются из множества конкурирующих, и последовательность kσ оптимальна. Утверждение 20. Пусть на итерации k , выполняющейся для очередно- го конкурирующего запаздывающего задания ][gj , для всех ][lj , 11 −g,l = справедливо [ ] [ ]ll jj CD ≤ , для всех * ][lj выполняется ][* ][ gl jj ll ≤ , и на интервале g, n резервы отсутствуют. Тогда запаздывающие задания, занимающие по- зиции g, n , исключаются из множества конкурирующих, а последовательно- сти kσ отвечает оптимальное значение функционала. Утверждение 21. Пусть на итерации k в последовательности kσ конку- рирующее задание ][gj в результате выполнения перестановок и встраиваний заняло позицию s . Если на интервале , s1 резервы отсутствуют, то конкури- рующие задания ][rj , ngr ,1+= , для которых ][][ gr jj DD ≥ , в оптимальном расписании не смогут занять более раннюю позицию, чем s . Утверждение 22. Пусть на итерации k в последовательности kσ конку- рирующее задание ][gj в результате выполнения перестановок и встраива- ний заняло позицию s , оставаясь запаздывающим, и пусть для всех ][rj , ngr ,1+= выполняется ][][ gr jj DD ≥ и ][][ rr jj CD ≤ . Тогда эти задания в оп- тимальном расписании не смогут занять более раннюю позицию, чем s , и если на интервале ns, резервы отсутствуют, то последовательность kσ оптималь- на. Утверждение 23. Если на интервале встраивания очередного запазды- вающего задания ][gj есть задание ][rj , для которого ][][ gr jj DD < , ][][ gr jj ll < , то интервал встраивания ][gj определится позициями 1,1 −+ gr . Утверждение 24. Если в последовательности упσ ][ij∀ , 1,1 −= gi , где ][gj — первое запаздывающее задание, выполняется ][][ gi jj lr < и задания ][ij , ngt ,1+= — запаздывающие, то задача решается посредством полиномиальной составляющей предлагаемого алгоритма. Утверждение 25. Пусть ][gj — первое запаздывающее задание в по- следовательности спσ . Если на интервале встраивания ][gj все задания упо- рядочены в соответствии с длительностями и ][sj∀ , ngs ,1+= , выполняет- Эффективный точный ПДС-алгоритм решения задачи о суммарном запаздывании … Системні дослідження та інформаційні технології, 2004, № 4 49 ся ][][ ss jj CD < и ][][ gs jj DD > , то задача решается посредством полино- миальной составляющей предлагаемого алгоритма. ОПИСАНИЕ АЛГОРИТМА Предлагаемый алгоритм решения рассматриваемой задачи состоит из двух этапов — предварительного (алгоритм А0) и оптимизации (алгоритм А1). Алгоритм А0 (предварительный этап) 1. Упорядочить задания по неубыванию их длительностей jl . Полу- ченную последовательность обозначить упσ . Проверить условия утвержде- ния 8. Если в последовательности упσ ни для одного из запаздывающих заданий нет предшествующих заданий, для которых выполняется хотя бы одно из условий 1–4 , то последовательность упσ оптимальна. Конец алго- ритма. Иначе перейти на п.2. 2. Выполнить свободные перестановки в последовательности упσ , на- чиная с задания с максимальным директивным сроком. 2.1. Определить множество заданий W. nqkCDCDkW qkqk jjjj ,1,;;:{ ]1[][][][ =≤≥= + , qk < , ][][ :][ ii jji CDj <∃ , qki ,1+= }. 2.2. Найти задание ][kj ′ с максимальным директивным сроком из мно- жества W . Если ∅=W , то получена последовательность спσ . Перейти на п.2.4. 2.3. Выполнить перестановку задания ][kj ′ на соответствующую ему позицию q′ и исключить ][kj ′ из множества W . Перейти на п. 2.2. 2.4. Проверить условия а), б), в), г) утверждения 12. Если выполняется хотя бы одно из этих условий, то последовательность спσ оптимальна. Ко- нец алгоритма. Иначе определить множество конкурирующих заданий K и перейти к этапу оптимизации. Алгоритм А1 (этап оптимизации) Алгоритм состоит из k однотипных итераций, где k — количество конку- рирующих заданий. На каждой итерации проверяется возможность исполь- зования резервов времени незапаздывающих заданий очередным конкури- рующим заданием и порожденными в результате его перестановок новыми запаздывающими заданиями. В результате выполнения каждой итерации значение функционала уменьшается (или остается неизменным). Пусть прg — позиция предшествующего задания, которое рассматри- валось на предыдущей итерации (на первой итерации 0пр =g ). А.А. Павлов, Е.Б. Мисюра ISSN 1681–6048 System Research & Information Technologies, 2004, № 4 50 1. Найти очередное запаздывающее задание ][gj на интервале ng ,1пр + . Если запаздывающее задание не найдено, то конец. Иначе если это задание неконкурирующее — перейти на п.2, а если конкурирующее — проверить условия утверждений 14, 17, 18–20, 22, позволяющие исключить задание ][gj из множества конкурирующих заданий. Если в результате за- дание ][gj не исключено из множества конкурирующих, перейти на п.2. Иначе установить gg =пр . Перейти на п.1. Если ng = , то конец алгоритма, текущая последовательность оптимальна. 2. Выполнить все свободные перестановки на интервале g,1 , начиная с задания с максимальным директивным сроком. 3. Если в результате выполнения п.2 задание ][gj перестало запазды- вать, переместившись на позицию нg , то установить нпр gg = и перейти на п.1, иначе на п.4. 4. Найти задание ][lj ( gl < ), для которого выполняется ][][][ ggl jjj lCD −≥ , ( ) ][][][][][ ,min lgllg jjjjj DClDC −<− . Если найдено хотя бы одно задание, отвечающее этим условиям, пе- рейти на п.5, иначе на п.7. 5. Выполнить перестановку задания ][lj на позицию g . Если ][gj пере- стало запаздывать, то перейти на п.6, иначе на п. 2. 6. Если после п.2 выполнялись пп.4, 5 для задания ][gj более одного раза, то задания, следующие за ][gj , упорядочить в соответствии с их дли- тельностями, уничтожив все метки. Установить нпр gg = и перейти на п.1. 7. Найти позицию p, на которой запаздывание по заданию ][gj станет минимальным или равным нулю. Если такая позиция найдена, перейти на п.8, иначе на п.13. 8. Если на интервале встраивания задания ][gj , определяемом позициями 1, −gp , есть задание ][sj , для которого ][][ gs jj DD < , ][][ gs jj ll < , то интер- вал встраивания задания ][gj определится позициями gs ,1+ . 9. Проверить, есть ли на интервале 1,1 −g задания ][sj , для которых 0 ][][ >− ss jj CD , ][][ gs jj DD > . Если да, то перейти на п.10, иначе устано- вить gg =пр и перейти на п.1. 10. Встроить задание ][gj на позицию p (или при выполнении п.8 на позицию 1+s ). Если эту позицию занимает задание, помеченное * или *, Эффективный точный ПДС-алгоритм решения задачи о суммарном запаздывании … Системні дослідження та інформаційні технології, 2004, № 4 51 встроить ][gj на позицию 1+p и перейти на п.11. Если в результате выпол- нения процедуры встраивания ][gj осталось на занимаемой позиции g , пе- рейти на п.13. 11. Пометить задание ][gj , занявшее в результате выполнения встраи- вания новую позицию, знаком . Задания, следующие за ним, упорядочить в соответствии с их длительностями, уничтожив все метки. 12. Если 0 ][ ≥ gjr , установить нпр gg = , иначе 1нпр −= gg . Перейти на п.1. 13. Найти задание * ][mj ( ][mj ) на интервале 1,1 −g . Если ][gj — конку- рирующее, то неконкурирующие задания )( ][ * ][ mm jj не рассматриваются. Не рассматриваются также задания, для которых [ ] )( ** ][ * ][ mmg jjj lll > и [ ] > gjD )( ** ][ * ][ mm jj DD> . В первую очередь анализируется задание, помеченное * или ** последним, затем предпоследним и т.д. Если помеченное задание не най- дено, перейти на п.18, иначе на п.14. 14. Проверить условие [ ] [ ]( )∑ = −<− g mi jjjkj iim DCDC ,0max* ][][ , (7) где gk = , если [ ] * ][mg jj ll ≤ , иначе sk = , где 1+s — позиция первого непо- меченного задания, длительность которого больше * ][mj ( ** ][mj ), ms > . В случае выполнения условия (7) перейти на п.15, иначе найти сле- дующее задание, помеченное или *, для которого выполняется это усло- вие. Если такие задания не найдены, перейти на п.18. 15. Запомнить текущую последовательность заданий, обозначив ее фσ . 16. Выполнить перестановку задания ][mj ( ** ][mj ): а) после задания ][gj , если [ ] * ][mg jj ll ≤ ; б) на позицию k , определенную в п.14, если [ ] * ][mg jj ll > . Установить 1нпр −= gg , где нg — новая позиция ][gj после переста- новки * ][mj . Перейти на п.1 и переупорядочить задания на интервале g,1 по изложенным правилам. 17. Определить значение функционала полученной последовательности нσ и сравнить его со значением функционала последовательности фσ . Ес- ли значение целевой функции не уменьшилось, возвратиться к фσ и перей- ти на п.13. В случае уменьшения значения целевой функции в последова- тельности нσ обозначение * снимается с задания * ][mj , если в результате перестановок это задание заняло позицию в соответствии с его длительно- стью. Иначе это задание пометим **. А.А. Павлов, Е.Б. Мисюра ISSN 1681–6048 System Research & Information Technologies, 2004, № 4 52 18. Установить gg =пр . Перейти на п.1. Если ng =пр , то конец. Алгоритм построен таким образом, что на каждой итерации строится оптимальное расписание для последовательности kσ заданий ][ij , kgi ,1= , где ][ kgj — очередное конкурирующее задание. На первой итерации рас- сматривается подпоследовательность сп1 σσ ⊂ , содержащая задания, зани- мающие в последовательности спσ позиции 1,1 g , где 1g — позиция перво- го конкурирующего запаздывающего задания. На второй итерации полученная оптимальная последовательность дополняется заданиями ][lj , которые в последовательности спσ занимают позиции 21 ,1 ggl += , и стро- ится оптимальное расписание для этой последовательности. На каждой ите- рации оптимизация осуществляется за счет использования резервов времени незапаздывающих заданий очередным конкурирующим заданием и порож- денными в результате его перестановок новыми запаздывающими задания- ми. Оптимизация выполняется путем перестановок и встраиваний, направ- ленных на улучшение значения функционала на рассматриваемом подмножестве заданий. Исключаются только те перестановки, которые за- ведомо ухудшают значение функционала. Таким образом строится опти- мальное расписание для всего множества заданий. В процессе решения задачи проверяются условия утверждений 8, 12, 13, 24, 25.Если 8 или 13 не выполняются или выполняются условия хотя бы одного из утверждений 12, 24, 25, то задача решается с помощью полиномиальной со- ставляющей предложенного алгоритма, иначе алгоритм работает по декомпо- зиционной составляющей. В этом случае для каждого запаздывающего задания ][gj определяется интервал встраивания ][gjI , ограниченный позициями 1, −gp , на котором возможно уменьшение значения функционала за счет ре- зервов заданий на этом интервале или резервов, которые могут быть образова- ны заданиями, занимавшими позиции 1,1 −p , в результате выполнения пере- становок. В этом случае необходимо выполнение условий утверждения 6. Таким образом, задача декомпозируется на подзадачи меньшего размера, а в результате проверки условий утверждений 14, 17 – 20, 22 часть конкурирую- щих заданий исключается из множества конкурирующих, что существенно со- кращает число выполняемых итераций. ВЫЧИСЛИТЕЛЬНЫЕ ЭКСПЕРИМЕНТЫ Для оценки работы алгоритма были вручную просчитаны и исследованы тестовые примеры размерности 150≤n , взятые на интернет-странице [18], щедро предоставленной Бахар Йетис Кара. Оптимальные значения функцио- нала, полученные нашим алгоритмом, совпали с описанными в [18] значениями функционала. Ниже приведены результат и анализ хода решения тестового примера, одного из наиболее трудоемких для размерности 150=n . Исходные данные приведены в табл. 1. В этой и последующих табли- цах jT обозначено запаздывание по заданию j : jjj DCT −= . Эффективный точный ПДС-алгоритм решения задачи о суммарном запаздывании … Системні дослідження та інформаційні технології, 2004, № 4 53 Т а б л и ц а 1 . Исходные данные для примера (последовательность упσ ) j 1 2 3 4 5 6 7 8 9 10 Lj 1 1 1 1 2 3 4 4 4 5 Dj 880 1160 1944 2079 1494 754 815 1211 1698 991 Cj 1 2 3 4 6 9 13 17 21 26 Tj 0 0 0 0 0 0 0 0 0 0 j 11 12 13 14 15 16 17 18 19 20 Lj 5 5 5 6 6 7 7 8 8 8 Dj 1508 1760 1795 1299 1579 1370 1861 955 1117 1140 Cj 31 36 41 47 53 60 67 75 83 91 Tj 0 0 0 0 0 0 0 0 0 0 j 21 22 23 24 25 26 27 28 29 30 Lj 8 8 8 9 9 10 10 11 11 12 Dj 1156 1709 1890 970 1386 1023 1516 1361 1749 1116 Cj 99 107 115 124 133 143 153 164 175 187 Tj 0 0 0 0 0 0 0 0 0 0 j 31 32 33 34 35 36 37 38 39 40 Lj 12 13 13 14 14 14 14 15 16 20 Dj 1553 1566 2013 715 883 1281 2066 1246 1230 717 Cj 199 212 225 239 253 267 281 296 312 332 Tj 0 0 0 0 0 0 0 0 0 0 j 41 42 43 44 45 46 47 48 49 50 Lj 21 22 22 24 24 25 25 26 27 27 Dj 1366 1554 1589 1175 1902 773 1655 1155 1046 1744 Cj 353 375 397 421 445 470 495 521 548 575 Tj 0 0 0 0 0 0 0 0 0 0 J 51 52 53 54 55 56 57 58 59 60 Lj 28 29 29 31 31 32 34 38 38 39 Dj 891 990 1865 1416 1556 1684 1516 710 1826 992 Cj 603 632 661 692 723 755 789 827 865 904 Tj 0 0 0 0 0 0 0 117 0 0 J 61 62 63 64 65 66 67 68 69 70 Lj 39 40 40 41 42 42 43 43 46 46 Dj 1535 933 1816 1051 728 1722 1268 1551 1762 1774 Cj 943 983 1023 1064 1106 1148 1191 1234 1280 1326 Tj 0 50 0 13 378 0 0 0 0 0 J 71 72 73 74 75 76 77 78 79 80 Lj 46 47 48 48 50 51 52 52 52 52 Dj 1813 1753 1007 2019 1148 1776 788 810 851 999 Cj 1372 1419 1467 1515 1565 1616 1668 1720 1772 1824 Tj 0 0 460 0 417 0 880 910 921 825 j 81 82 83 84 85 86 87 88 89 90 Lj 52 52 53 54 54 55 55 55 55 56 Dj 1221 1630 1558 852 1995 716 800 962 1495 909 Cj 1876 1928 1981 2035 2089 2144 2199 2254 2309 2365 Tj 655 298 423 1183 94 1428 1399 1292 814 1456 j 91 92 93 94 95 96 97 98 99 100 Lj 56 57 57 58 58 58 59 59 60 61 Dj 1066 1123 1498 1623 1706 1963 1338 1702 2010 1807 Cj 2421 2478 2535 2593 2651 2709 2768 2827 2887 2948 Tj 1355 1355 1037 970 945 746 1430 1125 877 1141 А.А. Павлов, Е.Б. Мисюра ISSN 1681–6048 System Research & Information Technologies, 2004, № 4 54 Окончание табл. 1 j 101 102 103 104 105 106 107 108 109 110 Lj 62 62 63 64 65 67 68 68 71 71 Dj 1297 1583 2084 1357 1544 852 779 1016 1213 1542 Cj 3010 3072 3135 3199 3264 3331 3399 3467 3538 3609 Tj 1713 1489 1051 1842 1720 2479 2620 2451 2325 2067 j 111 112 113 114 115 116 117 118 119 120 Lj 71 72 72 72 72 73 73 73 74 76 Dj 1847 842 1590 1928 2060 824 1677 1699 943 1475 Cj 3680 3752 3824 3896 3968 4041 4114 4187 4261 4337 Tj 1833 2910 2234 1968 1908 3217 2437 2488 3318 2862 j 121 122 123 124 125 126 127 128 129 130 Lj 77 78 78 80 80 81 81 82 84 84 Dj 1619 1373 1789 916 1255 1874 1958 1761 840 1986 Cj 4414 4492 4570 4650 4730 4811 4892 4974 5058 5142 Tj 2795 3119 2781 3734 3475 2937 2934 3213 4218 3156 j 131 132 133 134 135 136 137 138 139 140 Lj 85 85 86 86 89 89 90 91 93 95 Dj 900 1053 1333 1533 906 1614 1137 1376 1737 990 Cj 5227 5312 5398 5484 5573 5662 5752 5843 5936 6031 Tj 4327 4259 4065 3951 4667 4048 4615 4467 4199 5041 j 141 142 143 144 145 146 147 148 149 150 Lj 95 95 96 96 96 97 97 99 100 100 Dj 1250 1719 721 996 1665 2028 2080 1005 1191 1215 Cj 6126 6221 6317 6413 6509 6606 6703 6802 6902 7002 Tj 4876 4502 5596 5417 4844 4578 4623 5797 5711 5787 Значение функционала по последовательности упσ составляет 197658. В табл. 2 приведена последовательность, полученная после выполнения свободных перестановок, — спσ . Т а б л и ц а 2 . Последовательность спσ j 1 2 6 7 8 10 14 18 19 20 Lj 1 1 3 4 4 5 6 8 8 8 Dj 880 1160 754 815 1211 991 1299 955 1117 1140 Cj 1 2 5 9 13 18 24 32 40 48 Tj 0 0 0 0 0 0 0 0 0 0 j 21 24 26 30 34 35 36 38 39 40 Lj 8 9 10 12 14 14 14 15 16 20 Dj 1156 970 1023 1116 715 883 1281 1246 1230 717 Cj 56 65 75 87 101 115 129 144 160 180 Tj 0 0 0 0 0 0 0 0 0 0 j 44 46 48 49 51 52 58 60 62 64 Lj 24 25 26 27 28 29 38 39 40 41 Dj 1175 773 1155 1046 891 990 710 992 933 1051 Cj 204 229 255 282 310 339 377 416 456 497 Tj 0 0 0 0 0 0 0 0 0 0 j 65 73 75 77 78 79 80 81 82 67 Lj 42 48 50 52 52 52 52 52 52 43 Dj 728 1007 1148 788 810 851 999 1221 1630 1268 Cj 539 587 637 689 741 793 845 897 949 992 Tj 0 0 0 0 0 0 0 0 0 0 Эффективный точный ПДС-алгоритм решения задачи о суммарном запаздывании … Системні дослідження та інформаційні технології, 2004, № 4 55 Продолжение табл. 2 j 28 41 16 25 54 5 11 27 57 61 Lj 11 21 7 9 31 2 5 10 34 39 Dj 1361 1366 1370 1386 1416 1494 1508 1516 1516 1535 Cj 1003 1024 1031 1040 1071 1073 1078 1088 1122 1161 Tj 0 0 0 0 0 0 0 0 0 0 j 68 31 42 55 32 15 43 47 56 9 Lj 43 12 22 31 13 6 22 25 32 4 Dj 1551 1553 1554 1556 1566 1579 1589 1655 1684 1698 Cj 1204 1216 1238 1269 1282 1288 1310 1335 1367 1371 Tj 0 0 0 0 0 0 0 0 0 0 j 22 66 29 50 72 12 69 70 76 13 Lj 8 42 11 27 47 5 46 46 51 5 Dj 1709 1722 1749 1744 1753 1760 1762 1774 1776 1795 Cj 1379 1421 1432 1459 1506 1511 1557 1603 1654 1659 Tj 0 0 0 0 0 0 0 0 0 0 j 71 63 59 17 53 23 45 3 83 33 Lj 46 40 38 7 29 8 24 1 53 13 Dj 1813 1816 1826 1861 1865 1890 1902 1944 1558 2013 Cj 1705 1745 1783 1790 1819 1827 1851 1852 1905 1918 Tj 0 0 0 0 0 0 0 0 347 0 j 74 84 37 4 85 86 87 88 89 90 Lj 48 54 14 1 54 55 55 55 55 56 Dj 2019 852 2066 2079 1995 716 800 962 1495 909 Cj 1966 2020 2034 2035 2089 2144 2199 2254 2309 2365 Tj 0 1168 0 0 94 1428 1399 1292 814 1456 j 91 92 93 94 95 96 97 98 99 100 Lj 56 57 57 58 58 58 59 59 60 61 Dj 1066 1123 1498 1623 1706 1963 1338 1702 2010 1807 Cj 2421 2478 2535 2593 2651 2709 2768 2827 2887 2948 Tj 1355 1355 1037 970 945 746 1430 1125 877 1141 j 101 102 103 104 105 106 107 108 109 110 Lj 62 62 63 64 65 67 68 68 71 71 Dj 1297 1583 2084 1357 1544 852 779 1016 1213 1542 Cj 3010 3072 3135 3199 3264 3331 3399 3467 3538 3609 Tj 1713 1489 1051 1842 1720 2479 2620 2451 2325 2067 j 111 112 113 114 115 116 117 118 119 120 Lj 71 72 72 72 72 73 73 73 74 76 Dj 1847 842 1590 1928 2060 824 1677 1699 943 1475 Cj 3680 3752 3824 3896 3968 4041 4114 4187 4261 4337 Tj 1833 2910 2234 1968 1908 3217 2437 2488 3318 2862 j 121 122 123 124 125 126 127 128 129 130 Lj 77 78 78 80 80 81 81 82 84 84 Dj 1619 1373 1789 916 1255 1874 1958 1761 840 1986 Cj 4414 4492 4570 4650 4730 4811 4892 4974 5058 5142 Tj 2795 3119 2781 3734 3475 2937 2934 3213 4218 3156 j 131 132 133 134 135 136 137 138 139 140 Lj 85 85 86 86 89 89 90 91 93 95 Dj 900 1053 1333 1533 906 1614 1137 1376 1737 990 Cj 5227 5312 5398 5484 5573 5662 5752 5843 5936 6031 Tj 4327 4259 4065 3951 4667 4048 4615 4467 4199 5041 А.А. Павлов, Е.Б. Мисюра ISSN 1681–6048 System Research & Information Technologies, 2004, № 4 56 Окончание табл. 2 j 141 142 143 144 145 146 147 148 149 150 Lj 95 95 96 96 96 97 97 99 100 100 Dj 1250 1719 721 996 1665 2028 2080 1005 1191 1215 Cj 6126 6221 6317 6413 6509 6606 6703 6802 6902 7002 Tj 4876 4502 5596 5417 4844 4578 4623 5797 5711 5787 Значение функционала по последовательности спσ составляет 191643. В табл. 3 приведена оптимальная последовательность оптσ . Таблица 3. Последовательность оптσ j 1 2 6 7 10 18 24 26 34 35 Lj 1 1 3 4 5 8 9 10 14 14 Dj 880 1160 754 815 991 955 970 1023 715 883 Cj 1 2 5 9 14 22 31 41 55 69 Tj 0 0 0 0 0 0 0 0 0 0 j 40 46 49 51 52 58 60 62 64 77 Lj 20 25 27 28 29 38 39 40 41 52 Dj 717 773 1046 891 990 710 992 933 1051 788 Cj 89 114 141 169 198 236 275 315 356 408 Tj 0 0 0 0 0 0 0 0 0 0 j 78 79 80 65 73 86 87 84 90 88 Lj 52 52 52 42 48 55 55 54 56 55 Dj 810 851 999 728 1007 716 800 852 909 962 Cj 460 512 564 606 654 709 764 818 874 929 Tj 0 0 0 0 0 0 0 0 0 0 j 91 30 21 19 75 92 20 48 44 8 Lj 56 12 8 8 50 57 8 26 24 4 Dj 1066 1116 1156 1117 1148 1123 1140 1155 1175 1211 Cj 985 997 1005 1013 1063 1120 1128 1154 1178 1182 Tj 0 0 0 0 0 0 0 0 3 0 j 38 39 81 36 14 67 28 41 16 25 Lj 15 16 52 14 6 43 11 21 7 9 Dj 1246 1230 1221 1281 1299 1268 1361 1366 1370 1386 Cj 1197 1213 1265 1279 1285 1328 1339 1360 1367 1376 Tj 0 0 44 0 0 60 0 0 0 0 j 54 5 11 27 57 61 31 42 55 32 Lj 31 2 5 10 34 39 12 22 31 13 Dj 1416 1494 1508 1516 1516 1535 1553 1554 1556 1566 Cj 1407 1409 1414 1424 1458 1497 1509 1531 1562 1575 Tj 0 0 0 0 0 0 0 0 6 9 j 15 43 68 47 9 56 22 50 29 12 Lj 6 22 43 25 4 32 8 27 11 5 Dj 1579 1589 1551 1655 1698 1684 1709 1744 1749 1760 Cj 1581 1603 1646 1671 1675 1707 1715 1742 1753 1758 Tj 2 14 95 16 0 23 6 0 4 0 j 13 66 59 17 53 23 45 3 63 69 Lj 5 42 38 7 29 8 24 1 40 46 Dj 1795 1722 1826 1861 1865 1890 1902 1944 1816 1762 Cj 1763 1805 1843 1850 1879 1887 1911 1912 1952 1998 Tj 0 83 17 0 14 0 9 0 136 236 Эффективный точный ПДС-алгоритм решения задачи о суммарном запаздывании … Системні дослідження та інформаційні технології, 2004, № 4 57 Окончание табл. 3 j 33 70 37 4 71 72 74 76 82 83 Lj 13 46 14 1 46 47 48 51 52 53 Dj 2013 1774 2066 2079 1813 1753 2019 1776 1630 1558 Cj 2011 2057 2071 2072 2118 2165 2213 2264 2316 2369 Tj 0 283 5 0 305 412 194 488 686 811 j 85 89 93 94 95 96 97 98 99 100 Lj 54 55 57 58 58 58 59 59 60 61 Dj 1995 1495 1498 1623 1706 1963 1338 1702 2010 1807 Cj 2423 2478 2535 2593 2651 2709 2768 2827 2887 2948 Tj 428 983 1037 970 945 746 1430 1125 877 1141 j 101 102 103 104 105 106 107 108 109 110 Lj 62 62 63 64 65 67 68 68 71 71 Dj 1297 1583 2084 1357 1544 852 779 1016 1213 1542 Cj 3010 3072 3135 3199 3264 3331 3399 3467 3538 3609 Tj 1713 1489 1051 1842 1720 2479 2620 2451 2325 2067 j 111 112 113 114 115 116 117 118 119 120 Lj 71 72 72 72 72 73 73 73 74 76 Dj 1847 842 1590 1928 2060 824 1677 1699 943 1475 Cj 3680 3752 3824 3896 3968 4041 4114 4187 4261 4337 Tj 1833 2910 2234 1968 1908 3217 2437 2488 3318 2862 j 121 122 123 124 125 126 127 128 129 130 Lj 77 78 78 80 80 81 81 82 84 84 Dj 1619 1373 1789 916 1255 1874 1958 1761 840 1986 Cj 4414 4492 4570 4650 4730 4811 4892 4974 5058 5142 Tj 2795 3119 2781 3734 3475 2937 2934 3213 4218 3156 j 131 132 133 134 135 136 137 138 139 140 Lj 85 85 86 86 89 89 90 91 93 95 Dj 900 1053 1333 1533 906 1614 1137 1376 1737 990 Cj 5227 5312 5398 5484 5573 5662 5752 5843 5936 6031 Tj 4327 4259 4065 3951 4667 4048 4615 4467 4199 5041 j 141 142 143 144 145 146 147 148 149 150 Lj 95 95 96 96 96 97 97 99 100 100 Dj 1250 1719 721 996 1665 2028 2080 1005 1191 1215 Cj 6126 6221 6317 6413 6509 6606 6703 6802 6902 7002 Tj 4876 4502 5596 5417 4844 4578 4623 5797 5711 5787 Значение функционала 186307опт =f . В результате решения задачи было выполнено 10 итераций (по задани- ям 83–92, см. табл. 2). Задания 93–150 в процессе решения были исключены из множества конкурирующих, и для них перестановки не выполнялись. Полученная последовательность (табл. 3) оптимальна. Анализ предложенного алгоритма позволил определить, что если число запаздывающих заданий и число заданий с резервами в последовательности спσ приблизительно равны, и при этом с возрастанием длительностей запаздывающих заданий их директивные сроки уменьшаются, то возможно существенное увеличение числа итераций. А.А. Павлов, Е.Б. Мисюра ISSN 1681–6048 System Research & Information Technologies, 2004, № 4 58 ВЫВОДЫ 1. Предложен новый эффективный ПДС-алгоритм для решения NP- сложной задачи составления расписаний по критерию минимизации сум- марного запаздывания выполнения заданий одним прибором относительно директивных сроков. Алгоритм основан на новом подходе к решению задач комбинаторной оптимизации — разработке алгоритмов с полиномиальной и декомпозиционной составляющими. Эти алгоритмы базируются на выделе- нии полиномиальной составляющей алгоритма и получении условий, когда экспоненциальная составляющая декомпозирует начальную задачу на под- задачи. Если условия утверждений 8 или 13 не выполняются или выполняются условия хотя бы одного из утверждений 12, 24, 25, то задача решается с помо- щью полиномиальной составляющей предложенного алгоритма. В противном случае алгоритм работает по декомпозиционной составляющей. В этом случае для каждого запаздывающего задания определяется интервал встраивания, на котором возможно уменьшение значения функционала. Таким образом, задача декомпозируется на подзадачи меньшего размера. Новым в предложенном подходе является выделение полиномиально разрешимых подклассов труднорешаемых комбинаторных задач не путем введения соответствующих ограничений в постановки задач, а на основе анализа процесса решения произвольных индивидуальных задач. 2. Выявлены и обоснованы новые свойства исследуемой задачи, что позволяет получать эффективные решения для задач большой размерности. Расширена область, для которой задача может быть оптимально решена по- линомиальной составляющей нашего алгоритма. На базе предложенного алгоритма может быть построен приближенный быстродействующий алго- ритм. В дальнейшем предполагается определить вычислительную сложность предложенного алгоритма с использованием известной схемы генерации исходных данных [7, 8, 19], выявить новые полиномиально разрешимые подклассы исследуемой задачи и разработать ПДС-алгоритм для случая взвешенного запаздывания. ЛИТЕРАТУРА 1. Shwarz W. and Mukhopadhyay S.K. Decomposition of the single machine total tardi- ness problem // Oper. Res. Lett. — 1996. — № 19. — Р. 243–250. 2. Du J. and Leung J.Y.-T. Minimizing total tardiness on one processor is NP-hard // Math. Oper. Res. — 1990. — № 15. — Р. 483–495. 3. Emmons H. One machine sequencing to minimize certain functions of job tardiness // Oper. Res. — 1969. — № 17. — Р. 701–715. 4. Baker K.R. and Shrage L.E. Finding an optimal sequence by dynamic programming: an extension to precedence-related tasks // Oper. Res. — 1978. — № 26. — Р. 111–120. 5. Fisher M.L. A dual algorithm for the one-machine scheduling problem // Math. Pro- gramming. — 1976. — № 11. — Р. 229–251. 6. Rinnooy Kan A.H.G., Lageweg B.J. and Lenstra J.K. Minimizing total costs in one- machine scheduling // Oper. Res. — 1975. — № 23. — Р. 908–927. Эффективный точный ПДС-алгоритм решения задачи о суммарном запаздывании … Системні дослідження та інформаційні технології, 2004, № 4 59 7. Potts C.N.and Wassenhove Van L.N. A decomposition algorithm for the single ma- chine total tardiness problem // Oper. Res. Lett. — 1982. — № 1. — P. 177–181. 8. Potts C.N. and Wassenhove Van L.N. Dynamic programming and decomposition ap- proaches for single machine total tardiness problem // European J. Oper. Res. — 1987. — № 32. — Р. 405–414. 9. Shrage L. and Baker K.R. Dynamic programming solution of sequencing problems with precedence constraints // Oper. Res. — 1978. — № 26. — Р. 444–449. 10. Srinivasan V. A hybrid algorithm for the one-machine sequencing problem to minimize total tardiness // Naval Res. Logist. Quart. — 1971. — № 18. — Р. 317–327. 11. Lawler E.L. A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness // Ann. Discrete Math. — 1977. — № 1. — Р. 331–342. 12. Szwarc W. Single machine total tardiness problem revisited in: Y.Ijiri (ed.), Creative and Innovative Approaches to the Science of Management, Quorum Books, 1993. — Р. 407–419. 13. Delia Croce F., Grosso A., Paschos V.Т. Lower bounds on the approximation ratios of leading heuristics for the single-machine total tardiness problem // Journal of Scheduling. — 2004. — № 7. — Р. 85–91. 14. Szwarc W., Grosso A. and Delia Croce F. Algorithmic paradoxes of the single ma- chine total tardiness problem // Journal of Scheduling. — 2001. — № 4. — Р. 93–104. 15. Pavlov A., Pavlova L. PDC-algorithms for intractable combinatorial problems. The- ory and methodology of design. — Uzhhorod: Karpatskij region, 1998. — 320 p. 16. Павлов А.А., Теленик С.Ф. Информационные технологии и алгоритмизация в управлении.– Киев: Техніка, 2002. — 344 с. 17. Павлов А.А., Мисюра Е.Б. Новый подход к решению задачи «Минимизация суммарного взвешенного опоздания при выполнении независимых заданий с директивными сроками одним прибором» // Системні дослідження та інформаційні технології. — 2002. — № 2.— С. 7–32. 18. http://www.bilkent.edu.tr/~bkara/start.html. 19. Tansel B., Kara B. and Sabuncuoglu I. An Efficient Algorithm for the Single Machine Total Tardiness Problem // IIE Transactions. — 2001. — 8, № 33. — Р. 661–674. Надійшла 14.05.2004
id	journaliasakpiua-article-171527
institution	System research and information technologies
keywords_txt_mv	keywords
language	Russian
last_indexed	2025-07-17T10:25:19Z
publishDate	2019
publisher	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
record_format	ojs
resource_txt_mv	journaliasakpiua/5b/efce760036a5f463b736790f178b9b5b.pdf
spelling	journaliasakpiua-article-1715272019-06-25T17:03:13Z Effective exact PDC-algorithm for the solution of the total tardiness problem for one machine Эффективный точный ПДС-алгоритм решения задачи о суммарном запаздыванни для одного прибора Ефективний точний ПДС-алгоритм розв’язання задачі про сумарне запізнювання для одного приладу Pavlov, A. A. Misura, E. B. The effective exact algorithm is presented in this article for total tardiness problem solution when processing independent tasks with due dates on one machine. The algorithm is based on the new approach to the solution of problems with due dates, the main point of the approach is the optimal utilization of untardy jobs' slack times. The algorithm allows to get solutions that are qualitatively grater than known results. Предложен эффективный точный алгоритм решения задачи о суммарном запаздывании при выполнении независимых заданий с директивными сроками одним прибором. Алгоритм основан на новом подходе к решению задач с директивными сроками и заключаетcя в оптимальном использовании резервов времени незапаздывающих заданий. Его эффективность качественно превышает эффективность известных алгоритмов. Запропоновано ефективний точний алгоритм розв’язання задачі про сумарне запізнювання при виконанні незалежних завдань з директивними строками одним приладом. Алгоритм засновано на новому підході до розв’язання задач із директивними строками і полягає у оптимальному використанні резервів часу завдань, що не запізнюються. Його ефективність якісно перевищує ефективність відомих алгоритмів. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2019-06-25 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/171527 System research and information technologies; No. 4 (2004); 30-59 Системные исследования и информационные технологии; № 4 (2004); 30-59 Системні дослідження та інформаційні технології; № 4 (2004); 30-59 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/171527/171193 Copyright (c) 2021 System research and information technologies
spellingShingle	Pavlov, A. A. Misura, E. B. Ефективний точний ПДС-алгоритм розв’язання задачі про сумарне запізнювання для одного приладу
title	Ефективний точний ПДС-алгоритм розв’язання задачі про сумарне запізнювання для одного приладу
title_alt	Effective exact PDC-algorithm for the solution of the total tardiness problem for one machine Эффективный точный ПДС-алгоритм решения задачи о суммарном запаздыванни для одного прибора
title_full	Ефективний точний ПДС-алгоритм розв’язання задачі про сумарне запізнювання для одного приладу
title_fullStr	Ефективний точний ПДС-алгоритм розв’язання задачі про сумарне запізнювання для одного приладу
title_full_unstemmed	Ефективний точний ПДС-алгоритм розв’язання задачі про сумарне запізнювання для одного приладу
title_short	Ефективний точний ПДС-алгоритм розв’язання задачі про сумарне запізнювання для одного приладу
title_sort	ефективний точний пдс-алгоритм розв’язання задачі про сумарне запізнювання для одного приладу
url	https://journal.iasa.kpi.ua/article/view/171527
work_keys_str_mv	AT pavlovaa effectiveexactpdcalgorithmforthesolutionofthetotaltardinessproblemforonemachine AT misuraeb effectiveexactpdcalgorithmforthesolutionofthetotaltardinessproblemforonemachine AT pavlovaa éffektivnyjtočnyjpdsalgoritmrešeniâzadačiosummarnomzapazdyvannidlâodnogopribora AT misuraeb éffektivnyjtočnyjpdsalgoritmrešeniâzadačiosummarnomzapazdyvannidlâodnogopribora AT pavlovaa efektivnijtočnijpdsalgoritmrozvâzannâzadačíprosumarnezapíznûvannâdlâodnogopriladu AT misuraeb efektivnijtočnijpdsalgoritmrozvâzannâzadačíprosumarnezapíznûvannâdlâodnogopriladu

Ефективний точний ПДС-алгоритм розв’язання задачі про сумарне запізнювання для одного приладу

Репозитарії

Схожі ресурси