Новий підхід до вирішення задачі "Мінімізація сумарного зваженого запізнення при виконанні незалежних завдань з директивними строками на одному приладі"

Based on the problem properties research, a new approach to its solution is offered and an effective approximate algorithm based upon it is developed. Conditions for optimal solution to be found in polynomial time are formulated. When these conditions are not satisfied, the truncation rules that all...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2019
Hauptverfasser:	Pavlov, A. A., Misjura, E. B.
Format:	Artikel
Sprache:	Russisch
Veröffentlicht:	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2019
Online Zugang:	https://journal.iasa.kpi.ua/article/view/176500
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	System research and information technologies
Завантажити файл:

Institution

System research and information technologies

_version_	1867334394738376704
author	Pavlov, A. A. Misjura, E. B.
author_facet	Pavlov, A. A. Misjura, E. B.
author_institution_txt_mv	[ { "author": "A. A. Pavlov", "institution": null }, { "author": "E. B. Misjura", "institution": null } ]
author_sort	Pavlov, A. A.
baseUrl_str	http://journal.iasa.kpi.ua/oai
collection	OJS
datestamp_date	2019-08-21T15:53:44Z
description	Based on the problem properties research, a new approach to its solution is offered and an effective approximate algorithm based upon it is developed. Conditions for optimal solution to be found in polynomial time are formulated. When these conditions are not satisfied, the truncation rules that allow to decrease the time for solving the task essentially are offered. This algorithm allowed to get exact solutions for a series of problems with a number of variables essentially more than 50. Optimal values of the criterion function got by this algorithm for test examples were congruent with criterion function values got by known methods.
first_indexed	2025-07-17T10:26:15Z
format	Article
fulltext	© А.А. Павлов, Е.Б. Мисюра Системні дослідження та інформаційні технології, 2002, 2 7 TIДC НОВІ МЕТОДИ В СИСТЕМНОМУ АНАЛІЗІ, ІНФОРМАТИЦІ ТА ТЕОРІЇ ПРИЙНЯТТЯ РІШЕНЬ УДК 519.854.2 НОВЫЙ ПОДХОД К РЕШЕНИЮ ЗАДАЧИ «МИНИМИЗАЦИЯ СУММАРНОГО ВЗВЕШЕННОГО ОПОЗДАНИЯ ПРИ ВЫПОЛНЕНИИ НЕЗАВИСИМЫХ ЗАДАНИЙ С ДИРЕКТИВНЫМИ СРОКАМИ ОДНИМ ПРИБОРОМ» А.А. ПАВЛОВ, Е.Б. МИСЮРА На основании исследования свойств данной задачи предложен новый подход к ее решению и разработанный на его основе эффективный приближенный алгоритм. Сформулированы условия, при выполнении которых оптимальное решение достигается за полиномиальное время. При невыполнении этих условий предлагаются правила отсечений, позволяющие существенно сократить время решения задачи. Данный алгоритм позволил получить точные решения для ряда задач с числом переменных существенно большим 50-ти. Оптимальные значения функционала, полученные данным алгоритмом для тестовых примеров, совпали со значениями функционала, рассчитанными другими известными методами. ПОСТАНОВКА И ТЕОРЕТИЧЕСКОЕ ИССЛЕДОВАНИЕ СВОЙСТВ ЗАДАЧИ Задано множество независимых заданий { }njjjJ ,...,, 21= , каждое из которых состоит из одной операции. Для каждого задания известны jl — длительность выполнения; jω — весовой коэффициент и jD — директивный срок выполнения. Задания поступают в систему одновременно в момент времени njd j ,1,0 == . Прерывания не допускаются. Необходимо построить расписание выполнения заданий для одного прибора, минимизирующее суммарное взвешенное опоздание при выполнении заданий: ( )∑ = −= n j jjj DC,f 1 0maxω , (1) где Cj — момент завершения выполнения задания j. Задача суммарного взвешенного опоздания привлекает внимание ученых на протяжении многих лет. Получение точного решения этой задачи усложнено чрезмерными вычислительными требованиями, ведь задача с 50 заданиями — это барьер, который практически невозможно преодолеть. Павлов А.А., Мисюра Е.Б. ISSN 1681–6048 System Research & Information Technologies, 2002, 2 8 Лоулер [9] показал, что данная задача (1\| \|ΣωiTi, где Ti — опоздание относительно директивного срока) является NP-трудной в сильном смысле и предложил псевдополиномиальный алгоритм для задачи суммарного опоздания 1\| \|ΣTi (все веса равны 1). Различные перечислительные методы решения были предложены как для взвешенных, так и для невзвешенных случаев. Эммонс [6] предложил несколько правил предпочтения, ограничивающих поиск оптимального решения в задаче 1\| \|ΣTi. Правила Эммонса используются как в алгоритмах ветвей и границ, так и в алгоритмах динамического программирования (Фишер [7] и Поттс и Вассенгов [10, 11]). Ринной Кен и другие [13] расширили эти результаты на задачу взвешенного опоздания. Рачамадугу [12] определил условие, характеризующее смежные работы в оптимальной последовательности для задачи 1\| \|ΣωiTi. Чемберс и др. [5] развили новые эвристические правила предпочтения и эвристику гибкой декомпозиции. В [3] показано, что наиболее эффективная нижняя граница при решении задачи взвешенного опоздания как по качеству, так и по потреблению времени — линейный метод нижней границы Поттса и Вассенгова [10], полученный из Лагранжевой релаксации ограничений на возможности машины. Хугевен и Ван де Вельд [8] переформулировали задачу, используя слабые переменные, и показали, что могут быть получены более эффективные Лагранжевы нижние границы. Шварц [14] доказал существование специального упорядочения для задачи опоздания–опережения для одного прибора со штрафами, независящими от работ, в которых расстановка двух смежных работ в оптимальном расписании зависит от их времени запуска. Шварц и Лью [15] представили двухступенчатый механизм декомпозиции для задачи 1\| \|ΣωiTi, в которой штрафы за опоздание пропорциональны временам обработки. В [4] представлено новое правило предпочтения для наиболее общего случая задачи суммарного взвешенного опоздания. Предложенное правило охватывает и расширяет результаты Эммонса и обобщения Ринноя Кена и др., рассматривая упорядочения, зависящие от времени, между каждой парой работ. Ниже предлагается новый подход к решению задачи 1\| \|ΣωiTi и разработанный на его основе алгоритм, который позволил получить точные решения для ряда задач с числом переменных существенно большим 50-ти. Результаты исследования свойств задачи и алгоритмы ее решения, описанные ниже, являются развитием работ [1, 2]. Введем ряд определений. Определение 1. Резервом времени ][ gjR задания ][gj называется величи- на ][][][ ggg jCjDjR −= . Определение 2. Перестановкой называется процедура переноса задания ][gj на позицию k (k > g) и, одновременно, заданий, зани- мающих позиции g + 1, g + 2 ,..., k – 1, k на позиции g, g + 1 ,..., k – 1, соответственно. Новый подход к решению задачи «Минимизация суммарного взвешенного опоздания… Системні дослідження та інформаційні технології, 2002, 2 9 Определение 3. Интервалом перестановки задания j[g] на позицию k называется множество заданий, находящихся на позициях g + 1, g + 2 ,..., k – 1, k до выполнения перестановки. Определение 4. Встраиванием называется процедура переноса задания j[g] на позицию p (g > p) и, одновременно, заданий p, p + 1 ,..., g – 1 на позиции p + 1, р + 2,..., g – 1, g, соответственно. Определение 5. Интервалом встраивания ][gjI задания j[g] называется множество заданий, стоящих до встраивания на позициях p, p + 1 ,..., g – 1, где p определяется из условия ( ) . 11 1 ][][][][ ∑∑ − = − −= ≤−< g pi jjj g pi j iggi lDCl (2) Если же условие (2) не выполняется ни для одной позиции, то p = 1. Таким образом, штраф по заданию j на позиции p должен быть равным нулю или минимальным. Определение 6. Задание j[g] называется запаздывающим в последо- вательности σ, если для него выполняется условие C jD j gg ][][ < , где g — позиция, которую задание j занимает в последовательности σ. Определение 7. Последовательностью упσ (сигма упорядоченная) называется последовательность заданий множества J, nj ,1= , в которой задания упорядочены по убыванию приоритетов jj l/ω , т.е. ≥∀ jj lij / :, ω ijlii <≥ ,/ω . Утверждение 1. Если в последовательности упσ запаздывающим заданиям не предшествуют задания с резервом времени, то не существует переносов заданий, приводящих к улучшению целевой функции. Доказательство. Пусть в последовательности упσ для заданий, стоящих на позициях i = s,1 , выполняется 0 ][][ ≥− ii jDjC , а для заданий, занимающих позиции i = ns ,1+ , выполняется 0 ][][ ≤− ii jDjC . Очевидно, что переносы, которые могли бы привести к уменьшению целевой функции, возможны только для заданий, занимающих позиции i = s,1 . Докажем, что не существует перестановок, приводящих к уменьшению f. Пусть в последовательности σ позиции [ ] glsgl <∈ ,,1, . Выполним перестановку задания j[l] на позицию [g]. Значение целевой функции на интервале [l, g] до перестановки равно: ( ) ][][][ iii jj g li j DCf −= ∑ = ω . После перестановки с учетом предположения, что задания, занимавшие позиции l + 1, l + 2, ... , g – 1, g, перестали запаздывать (т.е. пусть до Павлов А.А., Мисюра Е.Б. ISSN 1681–6048 System Research & Information Technologies, 2002, 2 10 перестановки выполнялось ][][][ lii jjj lDC ≤− , gli ,1+= ): ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ −+=′ ∑ += g li jjjj lill DlCf 1 ][][][][ ω , ][ljC — момент окончания выполнения задания ][lj до перестановки; ∑ += + g li jj il lC 1 ][][ — момент окончания выполнения задания ][lj после перестановки. Необходимо доказать, что 0≤′− ff : ( ) ( )−−+−=′− ∑ += g li jjjjjj iiilll DCDCff 1 ][][][][][][ ωω ( ) ≤−−=⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ −+− ∑∑∑ +=+=+= g li jjjj g li jj g li jjj iliiilill lDCDlC 111 ][][][][][][][][][ ωωω ≤ ( )∑∑∑ +=+=+= −=− g li jjjj g li jj g li jj illiilli llll 111 ][][][][][][][][ ωωωω ≤ 0 в силу того, что gli ll l l i i j j j j ,1 , ][ ][ ][ ][ +=≤ ωω . Докажем, что не существует встраиваний, приводящих к увеличению f. Значение целевой функции до встраивания равно ( )∑ = −= g pi ijijij DCf ][][][ ω , [ ]spg ,1, ∈ . После встраивания задания j[g] на позицию p с учетом того, что после встраивания задание j[g] перестанет запаздывать, т.е. ( ) ∑ − = ≤− 1 ][][][ g pi jjj igg lDC , значение целевой функции равно: ( ) ][][][ 1 ][ ijgjij g pi ij DlCf −+=′ ∑ − = ω , где ][ijC — момент окончания выполнения заданий j[i] до выполнения процедуры встраивания задания j[g] 1,, −=∀ gpii ; ][][ gi jj lC + — момент окончания выполнения заданий j[i] после выполнения процедуры встраивания задания j[g]. Новый подход к решению задачи «Минимизация суммарного взвешенного опоздания… Системні дослідження та інформаційні технології, 2002, 2 11 Необходимо доказать, что 0≤′− ff : ( ) ( )−−+−=′− ∑ − = 1 ][][][][][ g pi jjjjj iiggg DCDCff ω ( )=−+− ∑ − = 1 ][][][][ g pi jjjj igii DlCω ( ) ∑∑∑ − = − = − = −≤−−= 111 ][ ][][][][][][][][ g pi jj g pi jj g pi jijjjj giiggggg lllDC ωωωω = = ( )∑ − = − 1 ][][][][ g pi jjjj giig ll ωω ≤ 0 в силу того, что 1, ][][ ][ ][ −=∀≤ gpi ll ig g j ij j j ωω . Утверждение 2. Встраивание запаздывающего задания j[g] на позицию f < p не может привести к улучшению целевой функции. Доказательство. В соответствии с определением 5, позиция p определяется как позиция, на которой штраф по заданию j[g] становится равным нулю. Встраивание задания j[g] на любую позицию f < p приводит к увеличению его резерва и перемещает задания, стоящие на позициях f, f +1,..., p –1, на позиции f +1, f +2 ,..., p. Такое перемещение приводит к увеличению целевой функции, если для какого-либо задания на 1, −pf выполняется хотя бы одно из условий: 1) для задания 1,,][ −∈ pfij i выполняется ][][ ii jj DC ≥ , т.е. задание j[i] является запаздывающим и в результате встраивания штраф по нему увеличивается на величину ][][ gi jj lω ; 2) для задания 1,,][ −∈ pfij i выполняется ][][ ii jj DC < и − ][ijD ][][ gi jj lC <− , т.е. задание j[i] до встраивания задания j[g] не запаздывало, но в результате встраивания станет запаздывать со штрафом ( ) . ][][][][ gii jjjij lDC +−ω Если ни для одного из заданий 1,,][ −∈ pfij i не выполняется ни одно из перечисленных условий, то целевая функция не ухудшается, но и не может быть улучшена в результате встраивания ][gj на позицию pf < , т.к. штраф на позиции p по заданию ][gj равен нулю. Павлов А.А., Мисюра Е.Б. ISSN 1681–6048 System Research & Information Technologies, 2002, 2 12 Утверждение 3. Пусть в последовательности yпσ 1,1,][ −=∀ pij i 0 ][ ≤ ijR . Обозначим ее уп1σ . Запаздывающее задание j[g] в после- довательности уп1σ в результате выполнения встраивания ( ][gjI = 1, −gp ) может занять более раннюю позицию, что приведет к улучшению целевой функции только в том случае, если в последовательности уп1σ хотя бы у одного из заданий на интервале встраивания ][gjI есть резерв времени, больший нуля. Доказательство. Для доказательства данного утверждения выведем условия, при выполнении которых в результате процедуры встраивания значение целевой функции уменьшается, т.е. выполняется 0>ff ′− . Пусть для задания j[z] (p < z < g) выполняется неравенство ][][ zz jj CD > , для остальных заданий ][gjIi ∈ ][][ ii jj CD ≤ . Согласно утверждениям 1 и 2, встраивание, которое может улучшить f, должно быть выполнено на позицию z . Встроим задание j[g] на позицию z: ( ) ( )∑∑ += − = −+−= g zi jjij z pi jjj iiiii DCDCf 1 ][ 1 ][][][][][ ωω ; ( )+−+⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ −−=′ ∑∑ − = − = 1 ][ 1 ][][][][][][ ,0max z pi jjijj g zi jjj iigigg DCDlCf ωω + ( ) ( ) ][][][][][][][ ,0max 1 1 ][ zgzzigi jjjj g zi jjjij DlCDlC −++−+∑ − += ωω ; ( ) ( )∑∑ += − = −+−=′− g zi jjij z pi jjj iiiii DCDCff 1 ][ 1 ][][][][][ ωω – ( )∑ − = −− 1 ][ ][][ z pi jjij ii DCω ( )∑ − += −− 1 1 ][ ][][ g zi jjij ii DCω −− ∑ − += 1 1 ][ ][ g zi jij g lω ( ) ][][][][ ,0max zgzz jjjj DlC −+−ω =⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ −−− ∑ − = 1 ][][][][ ,0max g zi jjjj gigg DlCω ( )−−+−= ∑ − += ][][][][ ][ 1 1 gggi jjgj g zi jj DCl ωω Новый подход к решению задачи «Минимизация суммарного взвешенного опоздания… Системні дослідження та інформаційні технології, 2002, 2 13 ( )=−+−⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ −−− ∑ − = ][][][][][][][][ ,0max,0max 1 zgzzgigg jjjj g zi jjjj DlCDlC ωω ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ −= ∑ − = 1 ][][][][ ,min g zi jjjj iggg lDCω ∑ − += −− 1 1 ][][ g zi jj gi lω ⎟ ⎠ ⎞⎜ ⎝ ⎛ −+− ][][][][ ,0max zgzz jjjj DlCω = = ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ − ∑ − = 1 ][][][][ ,min g zi jjjj iggg lDCω ( )[ ]∑ − = −− 1 ][][][][ ,min,0max g zi jjjj gigi lRlω . Таким образом, в результате выполнения процедуры встраивания задания ][gj на позицию z значение целевой функции изменяется на величину: −⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ −=′− ∑ − = 1 ][][][][ ,min g zi jjjj iggg lDCff ω ( )[ ]∑ − = −− 1 ][][][][ ,min,0max g zi jjjj gigi lRlω . (3) Следовательно, улучшение целевой функции возможно только в том случае, если на интервале встраивания ][gjI есть резерв, больший нуля. В случае отсутствия резервов выражение (3) принимает отрицательное значение, т.к. приоритет задания ][gj ниже приоритета заданий на интервале встраивания. Заметим, что если существует несколько заданий kz с резервами времени на [p, g–1], то выражение (3) при встраивании задания ][gj на одну из позиций kz примет вид: −⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ −=′− ∑ − = 1 ][][][][ ,min g zi jjjj k iggg lDCff ω ( )[ ]∑ − = −− 1 ][][][][ ,min,0max g zi jjjj k gigi lRlω . (4) Утверждение 4. Если в последовательности упσ ни для одного из запаздывающих заданий j[g] нет предшествующих заданий j[i], 1,1 −= gi , для которых выполняется Павлов А.А., Мисюра Е.Б. ISSN 1681–6048 System Research & Information Technologies, 2002, 2 14 0 ][][ >− ii jj CD , ][][][ ggi jjj lDD −> , то не существует перестановок и встраиваний, приводящих к улучшению целевой функции. Доказательство. Встраивание. Встроим задание j[g] на позицию p (см. определение 5). Учитывая условие утверждения, что не существует предшествующих заданий j[s], для которых 0 ][][ >− ss jj CD и > ][sjD ][][ gg jj lD −> , получим, что встраивание j[g] произойдет на интервале 1, −gp , на котором для любого задания j[i] выполняется 0 ][][ ≥− ii jj DC , 1, −= gpi . Пусть 0 ][][ =− ii jj DC , 1, −= gpi . Тогда ( ),][][][ ggg jjj DCf −= ω ( ) ∑∑ − = − = =−+=′ 11 ][][][][][][ g pi jj g pi jjjj giigii lDlCf ωω , ( ) ∑ − = −−=′− 1 ][][][][][ g pi jjjjj giggg lDCff ωω ≤ ∑∑ − = − = − 11 ][][][][ g pi jj g pi jj giig ll ωω = = ( ) 0 1 ][][][][ ≤−∑ − = g pi jjjj giig ll ωω , т.к. gi ll g g i i j j j j <∀≥ ][ ][ ][ ][ ωω . Доказательство для случая ][][ ii jj DC − > 0 аналогично. Перестановки. Возможны перестановки задания с нулевым резервом времени и задания с ненулевым резервом. Рассмотрим все возможные случаи. 1. Пусть 0 ][][ >− ss jj CD , ][][][ ggs jjj lDD −≤ и задание j[g] после перестановки запаздывает, т.е. ][][][ gsg jjj DlC >− . В этом случае ( ) ][][][ ggg jjj DCf −= ω , ( ) ( ) ][][][][][][][ sgsgsgg jjjjjjj DCDlCf −+−−=′ ωω . ( ) ( ) ( )=−−−−−−=′− ][][][][][][][][][][ sgsgsggggg jjjjjjjjjj DCDlCDCff ωωω Новый подход к решению задачи «Минимизация суммарного взвешенного опоздания… Системні дослідження та інформаційні технології, 2002, 2 15 = ⎟ ⎠ ⎞⎜ ⎝ ⎛ −− ][][][][][ sjjjjj DCl gssg ωω ≤ ⎟ ⎠ ⎞⎜ ⎝ ⎛ +−− ][][][][][ ][ ggssg jgjjjjj lDCl ωω ≤ ≤ ][][][][ gssg jjjj ll ωω − ≤ 0, т.к. gs ll s s g g j j j j <≤ , ][ ][ ][ ][ ωω . 2. Пусть 0 ][][ >− ss jj CD , ][][][ ggs jjj lDD −≤ и задание j[g] после перестановки не запаздывает, т.е. ][][][ sgg jjj lDC ≤− . Здесь ( ) .][][][ sgs jjj DCf −=′ ω ( ) ( ) ][][][][][][ sgsggg jjjjjj DCDCff −−−=′− ωω ≤ ≤ ( )( ) ][][][][ sggg jjjj lCC −−ω – ( )( ) ][][][][ gggs jjjj lDC −−ω = = ( ) ][][][][][][ gggssg jjjjjj lDCl +−−ωω ≤ ][][][][ gssg jjjj ll ωω − ≤ 0, т.к. ][ ][ ][ ][ s s g g j j j j ll ωω ≤ , gs < . 3. Пусть 0 ][][ =− ss jj CD , ][][][ ggs jjj lDD −≤ и задание ][gj после перестановки запаздывает. Тогда ( ) ( ) ∑ += −−−−−=′− g si jjjjjjjjj isgsggggg lDlCDCff 1 ][][][][][][][][][ ωωω = = ][][ sg jj lω ∑ − += −− 1 1 ][][][][ g si jjjj isgs ll ωω ≤ ≤ ][][ sg jj lω ][][ gs jj lω− ≤ 0, т.к. ][ ][ ][ ][ s s g g j j j j ll ωω ≤ , gs < . 4. Пусть 0 ][][ =− ss jj CD , ][][][ ggs jjj lDD −≤ и задание j[g] после перестановки не запаздывает, т.е. ][][][ sgg jjj lDC ≤− . В этом случае ( ) ≤−−=′− ∑ += g si jjjjj isggg lDCff 1 ][][][][][ ωω 0 1 ][][][][ ≤− ∑ += g si jjjj issg ll ωω аналогично п.3. Павлов А.А., Мисюра Е.Б. ISSN 1681–6048 System Research & Information Technologies, 2002, 2 16 Следовательно, так как для запаздывающего задания j[g] нет предшествующих заданий, имеющих резервы на интервале переноса задания j[g], то не существует перестановок, приводящих к уменьшению значения функционала. На основании доказанных утверждений сформулируем необходимые условия для перемещения запаздывающих заданий на более ранние позиции, при котором значение функционала уменьшается за счет использования существующих резервов. Утверждение 5. Пусть в последовательности упσ j[g] — запаздывающее задание. Уменьшение значения функционала при перемещении j[g] на более ранние позиции в результате перестановок и встраиваний возможно только при выполнении одного из следующих условий: 1. ∃ j[i], Pmin ≤ i ≤ g \| ][ijr > 0. На интервале переноса задания j[g] есть задания с резервами времени, где Pmin — позиция, на которой штраф по заданию j[g] минимален (или равен нулю). 2. ∃ j[q], q < g, Dj[q] > Сj[g] . В последовательности упσ на позиции q, предшествующей позиции g, есть задание с резервом времени, перестановка которого после задания j[g] уменьшает штраф по заданию j[g]. Задание j[q] остается незапаздывающим. 3. ∃ j[q], q < g, Cj[g] – lj[g] < Dj[q] < Cj[g] . Существует незапаздывающее задание j[q], директивный срок которого больше момента начала выполнения задания j[g], но меньше момента окончания задания j[g]. При этом ( ) ( ) 0,min ][][][][][][][ >−−− qqggqgg jjjjjjj DClDC ωω . Следовательно, перестановка задания j[q] после задания j[g] приведет к уменьшению значения функционала, за счет использования резерва задания ][qj . 4. ∀i \| Pmin ≤ i ≤ g \| rj[i] ≤ 0, но ∃ j[k], k < Pmin \| Dj[k] > Cj[Pmin] . На интервале перестановки задания j[g] резервы отсутствуют, но существует задание j[k], k < Pmin, директивный срок которого больше Cj[Pmin] , следовательно, при перестановке задания j[k]на позицию Pmin образуется резерв на интервале переноса задания j[g]. Условие 4 не выполняется и ∀i \| Pmin ≤ i ≤ g \| rj[i] ≤ 0, но ∃ j[k], k < Pmin \| Dj[k] > Cj[k] , Dj[k] > Cj[Pmin] – lj[Pmin] , Dj[k] > Dj[g] – lj[g] . На интервале переноса задания j[g] резервы отсутствуют, но существует незапаздывающее задание j[k], k < Pmin с директивным сроком, большим самого позднего момента начала выполнения задания j[g], при котором задание j[g] станет незапаздывающим, и, следовательно, существуют перестановки и встраивания, которые могут привести к образованию резервов на интервале переноса задания j[g]. Новый подход к решению задачи «Минимизация суммарного взвешенного опоздания… Системні дослідження та інформаційні технології, 2002, 2 17 В соответствии с утверждением 3, уменьшение значения функционала при встраивании задания ][gj на более раннюю позицию возможно только при наличии резервов на интервале встраивания. Выполнение одного из условий 1–5 означает, что на интервале встраивания задания ][gj существуют резервы (условия 1–3) или они будут образованы в результате перестановок (условия 4, 5). При невыполнении условий 4, 5 перестановка заданий, занимающих позиции 1,1 min −P , на интервал встраивания задания ][gj , приведет к запаздыванию этих заданий, и т.к. они имеют более высокий приоритет, чем ][gj , то встраивание задания ][gj приведет к увеличению значения функционала. Следовательно, если не выполняется ни одно из условий 1–5, то не существует встраиваний задания ][gj на более ранние позиции, приводящих к улучшению целевой функции. Следствие. Пусть в последовательности упσ число запаздывающих заданий nз > 1. Тогда, если в последовательности упσ ни для одного из запаздывающих заданий ][gj нет предшествующих заданий j[s], s < g, для которых выполняется хотя бы одно из условий 1–5, то последовательности упσ отвечает оптимальное значение функционала. Пусть в последовательности упσ запаздывающее задание j[g] в результате встраивания заняло позицию Pmin = m. Пометим его * ][mj , а полученную последовательность )( ][gjσ . Утверждение 6. Запаздывающее задание j[k], k = g,m 1+ в последова- тельности )( ][gjσ может быть встроено на более раннюю позицию, что приведет к улучшению целевой функции только в том случае, если хотя бы у одного предшествующего задания есть резерв времени, либо (в случае отсутствия резервов) только в результате перестановки * ][mj после задания j[k]. Доказательство. Доказательство в случае наличия резервов приведено в утверждениях 3 и 5. Рассмотрим случай, когда в последовательности )( ][gjσ нет резервов. Очевидно, что среди заданий на интервале 11 −k, перестановка на позицию k возможна только для задания * ][mj , т.к. ∀ i = 11 −k, Dj[i] – Cj[i] ≤ 0, а для всех непомеченных заданий ][ ][ ][ ][ k k i i j j j j ll ωω ≥ , 1,1 −= ki . Выполним перестановку на позицию k задания * ][mj . Значение целевой функции до переноса: Павлов А.А., Мисюра Е.Б. ISSN 1681–6048 System Research & Information Technologies, 2002, 2 18 ( )∑ = −= k mi jjj iii DCf ][][][ ,0maxω = ∑ = ⎟ ⎠ ⎞⎜ ⎝ ⎛ − k mi jjj iii DC ][][][ ω . После переноса * ][mj на позицию k: ( )∑∑ +=+= −−+⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ −+=′ k mi jjjjj k mi jjj miiimimm lDCDlCf 11 ][][][][][][][][ ,0maxωω , где ][mjC — момент окончания выполнения задания * ][mj до перестановки. Докажем, что ff ′− может быть больше нуля: ( ) ( ) ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ −+−=′− ∑ += k mi jjjjjj iiimmm DCDCff 1 ][][][][][][ ωω – – ( ) ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ −−+⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ −+ ∑∑ +=+= k mi jjjjj k mi jjj miiimimm lDCDlС 11 ][][][][][][][][ ,0maxωω = = ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ +−−− ∑ += ][][][][][][ 1 mimmmm j k mi jjjjj DlCDCω + + ( ) ( )[ ]∑ += −−−− k mi jjjjjj miiiii lDCDC 1 ][][][][][][ ,0maxω = = ( )( )∑ += −− k mi jjjjjj imiimi lDCl 1 ][][][][][][ ,min ωω . (5) Проанализируем выражение (5). Разобьем сумму (5) на две части. Пусть P — множество заданий на k,m 1+ , которые после перестановки * ][mj перестали запаздывать. Следовательно, P: { }. ][][][ iim jjj DCl −≥ Пусть Q — множество заданий на ,km 1+ , которые после перестановки * ][mj остались запаздывающими. Следовательно, Q: { } ][][][ iim jjj DCl −< . Тогда выражение (5) примет вид ( ) ∑∑ ∈∈ ⎟ ⎠ ⎞⎜ ⎝ ⎛ −+⎟ ⎠ ⎞⎜ ⎝ ⎛ −− Qj jjjj Pj jjjjj i immi i imiii lllDС ][ ][][][][ ][ ][][][][][ ωωωω . (6) Новый подход к решению задачи «Минимизация суммарного взвешенного опоздания… Системні дослідження та інформаційні технології, 2002, 2 19 Разделим обе части выражения (6) на ][][ mi jj ll : [ ] [ ] [ ] ∑∑ ∈∈ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ −+⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ − Qj j j j j Pj j j j j j i m m i i i m m i i i llll ][ ][ ][ ][ ][ ][ ][ ][ ωωω ξ ω , (7) где ][ ][][ ][ m ii i j jj j l DC − =ξ , причем ]1,0[: ][][ ∈∀ iji j ξ . Задания на интервале km ,1+ имеют более высокий (или равный) приоритет, чем приоритет задания * ][mj , и следовательно, полученное значение выражения (7) может быть больше нуля и перестановка задания * ][mj на позицию k может привести к уменьшению f. Определение 8. Процедурой свободной перестановки называется процедура перестановки задания j[k] на позицию q (k < q) при условии ][][ qk jj CD ≥ , ]1[][ + < qk jj CD и хотя бы для одного задания на интервале qk ,1+ выполняется qki CD ii jj ,1, ][][ +=< . Таким образом, свободная перестановка задания k выполняется на позицию с максимальным номером, на которой задание k не будет запаздывать. Очевидно, что в результате выполнения всех свободных перестановок в последовательности упσ значение целевой функции уменьшается. При выполнении одной свободной перестановки значение целевой функции уменьшается на величину ∑ ∈ ⎟ ⎠ ⎞⎜ ⎝ ⎛ − zi jjjj iiki DCl ][][][][ ,minω , где { }qki DCjZ ii jji ,1, ][][][ +=>= . Примечание к определению 8. При выполнении нескольких свободных перестановок, во избежание зацикливания, начинать следует с задания, имеющего максимальный директивный срок, т.е. просматривать незапаздывающие задания по убыванию их директивных сроков. Определение 9. Последовательность заданий, полученную в результате выполнения всех свободных перестановок в последовательности упσ , назовем спσ . Утверждение 7. Утверждения 1–5 справедливы для последователь- ности спσ . Павлов А.А., Мисюра Е.Б. ISSN 1681–6048 System Research & Information Technologies, 2002, 2 20 Доказательство. Выделим различия между последовательностями упσ и спσ и покажем, что эти различия не нарушают доказательств приведенных выше утверждений. При доказательстве утверждений 1–5 основными приемами являлись перестановки и встраивания. Для перестановок доказательства утверждений аналогичны, если вместо упσ использовать спσ , по таким причинам: • все задания на интервале перестановки сдвигаются на более ранние позиции и, следовательно, штраф их уменьшается. При этом, задания, нарушающие последовательность упσ (перенесенные в результате свобод- ных перестановок), имеют штраф, равный нулю и поэтому могут быть исключены из рассмотрения как в f, так и в f ' ; • для запаздывающих заданий в последовательности спσ приоритетная упорядоченность сохраняется и, следовательно, приоритет задания, которое переставляется, больше приоритета любого из заданий на интервале перестановки. Процедура встраивания для последовательности спσ аналогична процедуре встраивания для последовательности упσ , т.к. приоритет встраиваемого задания в спσ всегда ниже или равен приоритету любого из заданий на интервале встраивания, что обусловливает необходимость для выполнения процедуры встраивания наличия резервов у заданий, занимающих более ранние позиции. Таким образом, утверждения 1–5 верны и для последовательности спσ . На интервале встраивания в последовательности спσ могут находиться задания, перенесенные в результате свободных перестановок и нарушающие приоритетную упорядоченность. Поэтому все задания, следующие за встраиваемым заданием, необходимо переупорядочить в соответствии с их приоритетами и для запаздывающих заданий в этой последовательности в свою очередь проверять возможность переноса на более ранние позиции за счет резервов незапаздывающих заданий. Таким образом, условие встраивания упσ (3), справедливое для последовательности упσ , в последовательности спσ не выполняется. Утверждение 8. Для последовательности спσ не существует перестановок и встраиваний, приводящих к улучшению целевой функции, если выполняется хотя бы одно из условий: а) ni CD ii jj ,1,0 ][][ =∀≥− ; б) li CD ii jj ,1,0 ][][ =∀≤− , nli CD ii jj ,1,0 ][][ +=∀≥− ; в) ni CD ii jj ,1,0 ][][ =∀≤− ; г) li CD ii jj ,1,0 ][][ =∀≥− (множество R), CD ii jj ,0 ][][ ≤− nli ,1+=∀ (множество Z). Новый подход к решению задачи «Минимизация суммарного взвешенного опоздания… Системні дослідження та інформаційні технології, 2002, 2 21 Для каждого задания j[k], принадлежащего множеству заданий с резервами (R) и каждого задания j[g], принадлежащего множеству запаздывающих заданий (Z), выполняется: ][][][ ggk jjj IDD −≤ , ZgRk ∈∈ , . Пункт а) не требует доказательства, т.к. f = 0. Доказательство пунктов б), в), г) аналогично доказательству утверждений 1, 3 и 4. Следствие. При выполнении хотя бы одного из условий, сформули- рованных в утверждении 8, в последовательности спσ достигается оптимальное значение функционала. Определение 10. Запаздывающее задание j[g] в последовательности спσ называется конкурирующим, если в этой последовательности найдется хотя бы одно предшествующее задание j[l], для которого выполняются условия ][][][ ggl jjj lDD −> и 0 ][][ >− ll jj CD . Определение 11. Последовательностью kσ называется последователь- ность, полученная из спσ в результате выполнения ряда перестановок и встраиваний, направленных на оптимальное использование резервов времени незапаздывающих заданий. Используются следующие типы перестановок и встраиваний. Перестановки: а) заданий, для которых резерв времени больше нуля; б) заданий, использовавших резервы в результате перестановок и встраиваний, если за ними следуют запаздывающие задания высшего или равного приоритета. Перестановки осуществляются, если при их выполнении значение функционала уменьшается. Встраивания: а) при наличии резервов на интервале встраивания; б) при образовании резервов на интервале встраивания в соответствии с условиями 4 и 5, сформулированными в утверждении 5. Правила выполнения перестановок и встраиваний в последователь- ности kσ приведены ниже. Введем правила пометки заданий в последовательности kσ при выполнении перестановок и встраиваний. В этой последовательности * обозначены задания, которые были запаздывающими в последовательности спσ и в результате выполнения перестановок и встраиваний переместились на более ранние позиции, использовав резервы времени предшествующих заданий, ** — задания, Павлов А.А., Мисюра Е.Б. ISSN 1681–6048 System Research & Information Technologies, 2002, 2 22 ранее помеченные , которые в результате последующих перестановок переместились на более поздние позиции (но эти позиции не соответствуют приоритетам этих заданий). За заданиями, помеченными , ** в последовательности kσ следуют запаздывающие задания с высшим приоритетом. Рассмотрим структуру последовательности kσ . Каждому заданию в этой последовательности соответствует номер задания и номер позиции. В исходной последовательности упσ задания пронумерованы по убыванию их приоритетов. На следующих итерациях присвоенная нумерация заданий сохраняется (меняются только номера позиций, занимаемых заданиями). Следовательно, в последовательности kσ чем меньше номер задания, тем выше его приоритет. Приоритетную упорядоченность нарушают задания, помеченные , , которые в результате перестановок и встраиваний использовали резервы времени предшествующих заданий и переместились с позиций, соответствующих их приоритетам на более ранние позиции, что позволило улучшить значение целевой функции. Приоритетную упорядоченность в последовательности kσ нарушают также задания, которые в результате свободных перестановок переместились на более поздние позиции. Все остальные задания упорядочены в соответствии с их приоритетами. Таким образом, последовательность kσ от последовательности спσ отличают только задания, помеченные , *, которые переместились на более ранние позиции. Справедливы следующие утверждения. Утверждение 9. Если на итерации k в последовательности kσ для запаздывающего задания j[g] существует предшествующее задание ][lj такое, что выполняются условия ][][][ ggl jjj lCD −> ; ⎟ ⎠ ⎞⎜ ⎝ ⎛ −>⎟ ⎠ ⎞⎜ ⎝ ⎛ − ][][][][][][][ ,min lglgglg jjjjjjj DCDCl ωω , то перестановка задания j[l] на позицию g приводит к уменьшению целевой функции. Доказательство. Для доказательства утверждения выведем условия перестановки, при выполнении которых уменьшается целевая функция, т.е. 0>′− ff : ( )∑ = −= g li jjj iii DCf ][][][ ,0maxω . После перестановки j[l] на позицию g Новый подход к решению задачи «Минимизация суммарного взвешенного опоздания… Системні дослідження та інформаційні технології, 2002, 2 23 ( ) ( ) ][][][][][][][ ,0max,0max 1 iliilgl jjj g li jjjj DlCDCf −−+−=′ ∑ += ωω ; ( ) ( )−−−−=′− ∑ = ][][][][][][ ,0max lgliii jjj g li jjj DCDCff ωω – ( ) ( )+−−=−−∑ += ][][][][][][][ 1 ,0max lglilii jjj g li jjjj DCDlC ωω + ( ) ( )∑∑ +=+= −−−− g li jjjij g li ijjij ilii DlCDC 1 ][ 1 ][][ ][][][][ ,0max,0max ωω . Пусть все задания 11 −+ , gli = не запаздывают до переноса, т.е. 0 ][][ <− ijj DC i . Тогда ( ) ( ) −−+−−=′− ][][][][][][ ggglgl jjjjjj DCDCff ωω ( ) =−−− ][][][][ ,0max glgg jjjj DlCω = ( ) ( ) 0,min ][][][][][][][ >−+−− gglglgl jjjjjjj DClDC ωω . Таким образом, если выполнено условие ⎟ ⎠ ⎞⎜ ⎝ ⎛ −>⎟ ⎠ ⎞⎜ ⎝ ⎛ − ][][][][][][][ ,min lglgglg jjjjjjj DCDCl ωω , то при перестановке задания j[l] на позицию g происходит уменьшение целевой функции. Сформулируем необходимые условия для перемещения в последовательности kσ запаздывающих заданий на более ранние позиции, при которых значение функционала уменьшается за счет существующих и освободившихся резервов. Утверждение 10. Пусть в последовательности kσ j[g] — запазды- вающее задание. Уменьшение значения функционала при перемещении j[g] на более ранние позиции возможно только при выполнении одного из следующих условий: 1. ∃ j[i], Pmin ≤ i ≤ g \| ][ijr > 0. На интервале переноса задания j[g] есть задания с резервами времени, где minP — позиция, на которой штраф по заданию j[g] минимален (или равен нулю). 2. >−−><∃ ),(min;,, ][][][][][][][][ gglgggl jjjjjjjl DClICDglj ω Павлов А.А., Мисюра Е.Б. ISSN 1681–6048 System Research & Information Technologies, 2002, 2 24 )( ][][][ lgl jjj DC −> ω . (8) Существует незапаздывающее задание j[l], директивный срок которого больше момента начала выполнения задания j[g]. При этом выполняется условие (8). 3. ∀ i \| Pmin ≤ i ≤ g \| rj[i] ≤ 0, но ∃ j[k], k < Pmin \| Dj[k] > Cj[Pmin]. 4. ∀ i \| Pmin ≤ i ≤ g \| rj[i] ≤ 0, но ∃ j[k] , k < Pmin \| Dj[k] > Cj[k] , Dj[k] > Cj[Pmin] – – lj[Pmin], Dj[k] > Dj[g] – lj[g] . 5. ∀ i \| i = 1,1 −g , rj[i] ≤ 0, но ∃ j [l] , l < g, ][ ][ ][ ][ g g l l j j j j ll ωω ≤ . 6. ∀i \| i = 1,1 −g , rj[i] ≤ 0, но ∃ j[m] (j[m]*), m < g. Аналогично утверждению 5, выполнение одного из условий 1–4 означает, что на интервале встраивания задания ][gj существуют резервы (условия 1, 2) или они будут образованы в результате перестановок (условия 3, 4). Выполнение условий 5 или 6 означает, что в последовательности kσ присутствуют задания, использовавшие резервы на интервале встраивания задания ][gj , и перемещение их на более поздние позиции приведет к образованию резервов на этом интервале. Если не выполняется ни одно из условий 1–6, то перемещение задания ][gj на более ранние позиции приведет к увеличению значения функционала. Следствие. Пусть в результате выполнения алгоритма построена оптимальная подпоследовательность на интервале k,1 . Если для каждого из запаздывающих заданий на интервале nk ,1+ не выполняется ни одно из условий 1–6, то последовательность kσ оптимальна. Число итераций предлагаемого алгоритма определяется количеством конкурирующих заданий. На каждой итерации проверяется возможность использования резервов времени предшествующих заданий очередным конкурирующим заданием и строится оптимальное расписание рассматриваемой последовательности. На первой итерации строится оптимальное расписание для заданий на интервале 1,1 g , где j[g1] — первое запаздывающее конкурирующее задание в последовательности спσ . На следующей итерации рассматривается последовательность заданий на интервале 2,1 g , где j[g2] — следующее запаздывающее конкурирующее задание. Пусть уже выполнена k–1 итерация и построено оптимальное расписание для последовательности заданий на интервале 1,1 −k , переходим к очередному запаздывающему конкурирующему заданию j[k] и строим оптимальное расписание для подпоследовательности kσ , включающей задания на интервале k,1 . Проверяется возможность Новый подход к решению задачи «Минимизация суммарного взвешенного опоздания… Системні дослідження та інформаційні технології, 2002, 2 25 уменьшения значения функционала за счет использования заданием j[k] существующих резервов времени или резервов, полученных в результате перестановок заданий с метками (или заданий меньшего приоритета) на более поздние позиции. На каждой итерации значение функционала уменьшается или остается неизменным. Примечание. Необходимо различать конкурирующие запаздывающие задания, определенные в последовательности спσ , и задания, запаздывание которых относительно их директивных сроков возникло в процессе выполнения перестановок и встраиваний. Справедливы следующие утверждения, доказательство которых очевидно. Утверждение 11. Запаздывающее задание j[g] на k-й итерации может занять более раннюю позицию, что приведет к улучшению целевой функции, только в том случае, если хотя бы у одного задания j[k] на интервале 1,1 −g есть резерв и: ][][][ ggk jjj lDD −> , либо (в случае отсутствия резервов) на интервале 1,1 −g есть задания с метками или задания с меньшим (или равным) значением приоритета. Утверждение 12. Пусть в последовательности спσ для конкурирующих заданий j[k], j[r]∈J выполняется: , ][][ rk jj ll ≤ ][][ rk jj ωω ≥ , ][][ rk jj DD ≤ . В оптимальном расписании задание ][kj будет предшествовать заданию ][rj . Утверждение 13. Неконкурирующие задания в последовательности kσ не могут занять более ранние позиции, чем позиции, занимаемые ими в спσ . Утверждение 14. Пусть уже построена оптимальная подпоследова- тельность на интервале 1,1 −g . Запаздывающее конкурирующее задание j[g] на k-й итерации не может быть перемещено на более раннюю позицию и исключается из числа конкурентноспособных, если на интервале 1,1 −g ни у одного из заданий нет резервов, отсутствуют непомеченные задания с меньшим или равным значением приоритета и для всех помеченных заданий выполняется: ][ ][ gi jj ωω ≥ , , ][* ][ gi jj ll ≤ i = 1,1 −g . Утверждение 15. Если в последовательности kσ конкурирующее задание j[g] в результате выполнения перестановок и встраиваний не использовало существующие резервы, минимальное значение функционала соответствует позиции g, занимаемой этим заданием, на интервале 1,1 −g отсутствуют непомеченные задания с меньшим или равным значением Павлов А.А., Мисюра Е.Б. ISSN 1681–6048 System Research & Information Technologies, 2002, 2 26 приоритета и нет заданий, помеченных , , то задание j[g] исключается из множества конкурирующих заданий. ОПИСАНИЕ АЛГОРИТМА Предлагаемый алгоритм решения рассматриваемой задачи состоит из двух этапов — предварительного этапа (алгоритм А0) и этапа оптимизации (алгоритм А1). Алгоритм А0 (предварительный этап) 1. Упорядочить задания по убыванию их приоритетов — отношения wj / lj. Полученную последовательность обозначить упσ . Проверить условия утверждения 5. Если в последовательности упσ ни для одного из запаздывающих заданий нет предшествующих заданий, для которых выполняется хотя бы одно из условий 1–5, то последовательность упσ оптимальна, конец алгоритма. Иначе перейти на п.2. 2. Выполнить свободные перестановки в последовательности упσ , начиная с задания с максимальным директивным сроком. 2.1. Определить множество заданий Y: Y = {k: Dj[k] ≥ Cj[q] ; Dj[k] ≤ Cj[q+1] ; k, q = n,1 , k < q, ∃ j[i]: Dj[i] < Cj[i] , i = qk ,1+ }. 2.2. Найти задание j[k'] с максимальным директивным сроком из множества Y. Если Y = ∅, то перейти на п.2.4. 2.3. Выполнить перестановку задания j[k'] на соответствующую ему позицию q' и исключить j[k'] из множества Y. Перейти на пункт 2.2. 2.4. Проверить условия а), б), в), г) утверждения 8. Если выполняется хотя бы одно из этих условий, последовательность спσ оптимальна, конец алгоритма. Иначе определить множество конкурирующих заданий и перейти к блоку оптимизации. В результате выполнения алгоритма А0 любая произвольная после- довательность заданий приводится к последовательности спσ . Алгоритм А1 (этап оптимизации) Алгоритм состоит из k однотипных итераций, где k — количество конкурирующих заданий. На каждой итерации проверяется возможность использования резервов времени незапаздывающих заданий очередным конкурирующим заданием и порожденными в результате его перестановок новыми запаздывающими заданиями. В результате выполнения каждой итерации значение функционала уменьшается (или остается неизменным). Новый подход к решению задачи «Минимизация суммарного взвешенного опоздания… Системні дослідження та інформаційні технології, 2002, 2 27 Пусть прg — позиция предшествующего задания, которое рассматри- валось на предыдущей итерации (на первой итерации прg = 0). 1. Найти очередное запаздывающее задание ][gj на интервале ng ,1+пр . Если это задание конкурирующее — начало новой итерации. Если такого задания нет, то конец, иначе проверить для задания ][gj условия утверждения 10. Если выполняется хотя бы одно из условий 1–6, перейти на п.2, иначе если задание ][gj не принадлежит исходному множеству конкурирующих заданий, установить gg =пр , перейти на п.1. Если же задание ][ gj — конкурирующее, проверить условия утверждения 14. При выполнении этих условий задание ][gj исключается из множества конкурирующих заданий. Установить gg =пр , перейти на п.1. Если g = n, то конец алгоритма, текущая последовательность оптимальна. 2. Выполнить все свободные перестановки на интервале g,1 , начиная с задания с максимальным директивным сроком. 3. Если в результате выполнения п.2 задание j[g] перестало запаздывать, переместившись на позицию нg , то установить прg = нg и перейти на п.1, иначе — на п.4. 4. Найти задание j[l] (l < g), для которого выполняется: Dj[l] ≥ Cj[g] – lj[g]; ωj[l](Cj[g] – Dj[l]) < ωj[g] min (lj[l], Cj[g] – Dj[g] ). Если найдено хотя бы одно задание, отвечающее этим условиям, перейти на п. 5, иначе — на п.7. 5. Выполнить перестановку задания j[l] на позицию g. Пометить задание j[g] знаком . 6. Если j[g] перестало запаздывать, то установить нпр gg = и перейти на п.1, иначе — на п.2. 7. Найти позицию p, на которой штраф по заданию j[g] станет минимальным или равным нулю. 8. Проверить, есть ли на интервале 1, −gp резервы, если да, то перейти на п.9, иначе — на п.12. 9. Проверить условие: lj[g] > lj[p]. Если это условие выполняется, перейти на п.11, иначе — на п.10. 10. Встроить задание j[g] на позицию p, если эту позицию занимает непомеченное задание с резервом. Перейти на п.14. Если же эту позицию занимает задание, помеченное * (*), или задание высшего приоритета без резерва, встроить задание j[g] на позицию p+1. Перейти на п.12. Павлов А.А., Мисюра Е.Б. ISSN 1681–6048 System Research & Information Technologies, 2002, 2 28 11. Встроить задание j[g] на позицию p+1. 12. Найти на интервале 1,1 −p задание j[s], для которого справедливо: Dj[s] > Cj[s]; Dj[s] > Dj[g] – lj[g]; Dj[s] > Cj[p–1]. (9) Если такие задания найдены, перейти на п.13. Иначе если п.12 выполнялся после п.8, перейти на п.16, если после п.10, перейти на п.14. 13. Используя резервы заданий, удовлетворяющих условию (9), а также резерв задания j[p], определить новую позицию нp , на которой штраф по заданию j[g] минимален (или равен нулю). Если такая позиция найдена ( pp <н ), установить нpp = , перейти на п.8. Иначе перейти на п.14. 14. Пометить задание j[g], занявшее в результате выполнения встраивания новую позицию, знаком . Задания, следующие за этим заданием, упорядочить в соответствии с их приоритетами, уничтожив все метки. 15. Установить 1−= нпр gg . Перейти на п.1. 16. Найти на интервале 1,1 −g непомеченное задание ][rj , для которого выполняется: ][ ][ ][ ][ g g r r j j j j ll ωω ≤ . (10) Проверить условие ( ) ( )∑ = −<− g ri jjjjjj iiirgr DCDC ][][][][][][ ωω , (11) ∀ i, для которых ][ ][ ][ ][ r r i i j j j j ll ωω ≥ . Если условие (11) выполняется, перейти к п.17, иначе найти следующее задание, отвечающее условиям (10), (11). Если такое задание не найдено, перейти на п.22. 17. Запомнить текущую последовательность, обозначив ее σФ. 18. Выполнить перестановку задания j[r] после задания j[g]. 19. Установить 1пр −= rg , перейти на п.1. 20. Переупорядочить задания на интервале 1,1 −g по изложенным правилам, проверяя возможность перемещения на более раннюю позицию для каждого задания на этом интервале. 21. Определить значение функционала полученной последователь- ности нσ и сравнить его со значением функционала последовательности σФ. Если значение целевой функции не уменьшилось, возвратиться к последовательности σФ, перейти на п.16, выполняя его для задания j[g]. Новый подход к решению задачи «Минимизация суммарного взвешенного опоздания… Системні дослідження та інформаційні технології, 2002, 2 29 Иначе если в последовательности нσ задание j[g] перестало запаздывать, установить нпр gg = . Перейти на п.1. Если же j[g] запаздывает, перейти на п.2. 22. Найти задание * ][mj ( ** ][mj ) на интервале 1,1 −g . В первую очередь анализируется задание, помеченное * (*) последним. Если такое задание не найдено, перейти на п.27, иначе на п.23. 23. Проверить условие [ ] ( )∑ = −<⎟ ⎠ ⎞ ⎜ ⎝ ⎛ − g mi jjjjjj iiimkm DCDC ][][][ ][ * ][ ,0maxωω , (12) где k = g, если [ ] [ ]g g m m j j j j ll ωω ≤ * ][ * ][ , иначе k = s, где s+1 — позиция первого непомеченного задания, приоритет которого меньше приоритета задания * ][mj ( ** ][mj ), s > m . В случае выполнения условия (12) перейти на п.24, иначе найти следующее задание, обозначенное , *, для которого выполняется это условие. Если такие задания не найдены, перейти на п.27. 24. Запомнить текущую последовательность заданий, обозначив ее σФ. 25. Выполнить перестановку задания * ][mj ( ** ][mj ): а) после задания j[g], если ][ ][ * ][ * ][ g g m m j j j j ll ωω ≤ ; б) на позицию k, определенную выше и соответствующую приоритету задания * ][mj , если ][ ][ * ][ * ][ g g m m j j j j ll ωω > . Установить 1нпр −= gg , где нg — новая позиция задания j[g] после перестановки * ][mj , перейти на п.1 и переупорядочить задания на интервале g,1 по изложенным правилам. 26. Определить значение функционала полученной последователь- ности нg и сравнить его со значением функционала последовательности σФ. Если значение целевой функции не уменьшилось, возвратиться к последовательности σФ, перейти на п.22. В случае уменьшения значения Павлов А.А., Мисюра Е.Б. ISSN 1681–6048 System Research & Information Technologies, 2002, 2 30 целевой функции в последовательности нσ обозначение * снимается с задания * ][mj , если в результате перестановок это задание заняло позицию в соответствии с его приоритетом. Иначе это задание обозначается *. 27. Установить gg =пр , перейти на п.1. Если ng =пр , то конец. Разработанным алгоритмом был просчитан ряд тестовых примеров. Оптимальные значения функционала, полученные данным алгоритмом, совпали со значениями функционала, полученными известными методами. Ниже приводятся результаты по двум тестовым примерам, которые в литературе относятся к числу нерешенных. Для них известны неулучшаемые значения функционала, полученные в результате решения лучшими известными алгоритмами. В результате решения предложенным алгоритмом значения функционала совпадают с известными. Исходные данные по примерам 1 и 2 приведены в табл. 1 и 2 соответственно. После каждой таблицы приведена полученная оптимальная последовательность выполнения заданий оптσ и значение функцио- нала оптf . Т а б л и ц а 1 . Исходные данные для примера 1 j 1 2 3 4 5 6 7 8 9 10 lj 37 71 18 74 62 92 61 59 73 63 Dj 655 263 510 495 668 392 574 325 588 554 ωj 1 7 6 6 8 6 2 5 9 6 j 11 12 13 14 15 16 17 18 19 20 lj 7 63 72 48 60 62 90 62 2 38 Dj 666 634 397 356 649 241 429 290 687 533 ωj 2 6 10 9 3 1 6 9 5 5 j 21 22 23 24 25 26 27 28 29 30 lj 88 75 94 73 51 9 74 54 96 39 Dj 410 686 402 633 562 431 548 601 643 521 ωj 10 7 1 4 4 2 10 4 8 6 j 31 32 33 34 35 36 37 38 39 40 lj 61 71 65 95 48 15 31 57 9 84 Dj 332 267 586 482 466 600 468 541 489 247 ωj 2 3 1 9 1 10 10 5 5 3 Оптимальная последовательность оптσ : 14, 2, 18, 8, 13, 21, 26, 37, 39, 3, 30, 27, 36, 20, 11, 19, 5, 9, 10, 12, 34, 22, 38, 29, 4, 25, 28, 17, 6, 24, 15, 32, 40, 7, 31, 1, 35, 16, 33, 23. Значение функционала оптf = 77 122. Новый подход к решению задачи «Минимизация суммарного взвешенного опоздания… Системні дослідження та інформаційні технології, 2002, 2 31 Т а б л и ц а 2 . Исходные данные для примера 2 j 1 2 3 4 5 6 7 8 9 10 lj 21 61 84 72 97 9 27 31 61 38 Dj 1098 871 1082 1002 1233 1005 807 929 794 1124 ωj 9 3 7 8 2 7 1 6 8 8 j 11 12 13 14 15 16 17 18 19 20 lj 6 97 43 18 34 86 66 34 66 78 Dj 961 843 1110 1016 828 1214 933 982 933 1167 ωj 4 3 5 10 10 7 8 1 1 4 j 21 22 23 24 25 26 27 28 29 30 lj 43 88 98 20 76 94 66 23 59 87 Dj 801 1125 875 1220 1013 884 1012 1149 867 870 ωj 8 5 6 2 6 10 3 7 6 9 j 31 32 33 34 35 36 37 38 39 40 lj 47 65 77 13 57 89 5 35 55 3 Dj 808 1199 1248 873 1032 970 795 1181 1081 1134 ωj 3 5 2 9 9 4 6 2 8 8 j 41 42 43 44 45 46 47 48 49 50 lj 9 33 40 83 45 2 49 67 59 52 Dj 1041 1102 1170 794 1050 795 1203 1246 1024 813 ωj 4 5 6 3 2 10 3 3 3 2 Оптимальная последовательность оптσ : 46, 37, 6, 34, 11, 14, 41, 1, 15, 8, 21, 39, 9, 17, 4, 26, 30, 31, 23, 29, 35, 42, 25, 3, 40, 10, 28, 43, 13, 24, 16, 32, 47, 38, 22, 20, 49, 2, 27, 36, 48, 45, 50, 7, 44, 12, 18, 33, 5, 19. Значение функционала оптf = 43 504. Для сокращения времени решения задачи возможно ограничение числа выполняемых итераций. В этом случае отклонение полученного частного решения от оптимального определяется следующим образом: ( ) ( ) max опт fff k ∆≤− σσ . Здесь ( ) ( )kk fff σσ max −=∆ , ( )kf σ* — нижняя оценка ( )оптσf , т.е. ( ) ( )опт* σσ ff k ≤ . Значение ( )kf σ* определяется на основе анализа резервов незапаздывающих заданий последовательности kσ и запаздываний конкурирующих заданий в этой последовательности, по которым не выполнялись итерации алгоритма. Алгоритм также позволяет в результате введения правил декомпозиции и дополнительных условий отсечения неперспективных вариантов строить быстродействующие эффективные эвристические алгоритмы со значением показателя качества, незначительно отличающимся от оптимального. Павлов А.А., Мисюра Е.Б. ISSN 1681–6048 System Research & Information Technologies, 2002, 2 32 ЛИТЕРАТУРА 1. Павлов О.А., Аксьонова Л.О., Місюра О.Б., Вакуленко О.С. Дослідження властивостей та алгоритм розв'язання важкорозв'язуваної комбінаторної задачі «Мінімізація сумарного зваженого запізнення виконання незалежних завдань одним приладом»; Нац. техн. ун-т України «Київ. політехн. ін-т» — Київ, 2001. — 63 с. — Деп. в ДНТБ України 8.10.2001, № 165–Ук2001. 2. Павлов А.А., Мисюра Е.Б., Михайлов В.В. Исследование задачи минимизации суммарного взвешенного момента окончания выполнения множества заданий с директивными сроками одним прибором / Киев. политехн. ин-т. — Киев, 1993. — 26 с. — Деп. в УкрНИИНТИ 29.06.93, № 1276 — Ук93. 3. Abdul-razaq T. S., Potts C. N., Van Wassenhove L. N. A survey of algorithms for the single-machine total weighted tardiness scheduling problem // Discrete Appl. Math. — 1990. — № 26. — P. 235–253. 4. Akturk, M. S., Yildirim, M. B. A new lower bounding scheme for the total weighted tardiness problem // Computer and Operations Research. — 1998. — 25, N 4. — P. 265–278. 5. Chambers R. J., Carraway R. L., Lowe T. J., Morin T. L. Dominance and decomposition heuristics for single machine scheduling // Operations Research. — 1991. — N 39. — P. 639–647. 6. Emmons H. One machine sequencing to minimize certain functions of job tardiness // Operations Research. — 1969. — N 17. — P. 701–715. 7. Fisher M. L. A dual algorithm for the one-machine scheduling problem // Math. Programming — 1976. — N 11. — P. 229–251. 8. Hoogeveen J. A., Van de Velde S. L. Stronger Lagrangian bounds by use of slack variables: applications to machine scheduling problems // Math. Prog. — 1995. — N 70. — P. 173–190. 9. Lawler E. L. A «pseudopolynomial» algorithm for sequencing jobs to minimize total tardiness // Annual Discrete Math. — 1977. — N 1. — P. 331–342. 10. Potts C. N., Van Wassenhove L.N. A branch and bound algorithm for total weighted tardiness problem // Operations Research. — 1985. — N 33. — P. 363–377. 11. .Potts C. N., Van Wassenhove L.N. Dynamic programming and decomposition approaches for the single machine total tardiness problem // European Journal of Operational Research. — 1987. — N 32. — P. 405–414. 12. Rachamadugu R.M.V. A note on weighted tardiness problem // Operations Research. — 1987. — N 35. — P. 450–452. 13. Rinnooy Kan A.H.G., Lageweg B.J., Lenstra J.K. Minimizing total costs in one- machine scheduling // Operations Research. — 1975. — N 23. — P. 908–927. 14. Szwarc W. Adjacent orderings in single machine scheduling with earliness and tardiness penalties // Naval Research Logistics. — 1993. — N. 40. — P. 229-243. 15. Szwarc W. and Liu J.J. Weighted tardiness single machine scheduling with proportional weights // Management Science. — 1993. — N 39. — P. 626–632. Поступила 11.03.2002
id	journaliasakpiua-article-176500
institution	System research and information technologies
keywords_txt_mv	keywords
language	Russian
last_indexed	2025-07-17T10:26:15Z
publishDate	2019
publisher	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
record_format	ojs
resource_txt_mv	journaliasakpiua/40/1ad3735b4f5cb8ff96dd5026aa114a40.pdf
spelling	journaliasakpiua-article-1765002019-08-21T15:53:44Z A new approach to solving the problem: "Minimization of total weighted tardiness when fulfilling independent tasks in due times at one machine" Новый подход к решению задачи "Минимизация суммарного взвешенного опоздания при выполнении независимых заданий с директивными сроками одним прибором" Новий підхід до вирішення задачі "Мінімізація сумарного зваженого запізнення при виконанні незалежних завдань з директивними строками на одному приладі" Pavlov, A. A. Misjura, E. B. Based on the problem properties research, a new approach to its solution is offered and an effective approximate algorithm based upon it is developed. Conditions for optimal solution to be found in polynomial time are formulated. When these conditions are not satisfied, the truncation rules that allow to decrease the time for solving the task essentially are offered. This algorithm allowed to get exact solutions for a series of problems with a number of variables essentially more than 50. Optimal values of the criterion function got by this algorithm for test examples were congruent with criterion function values got by known methods. На основании исследования свойств данной задачи предложен новый подход к ее решению и разработанный на его основе эффективный приближенный алгоритм. Сформулированы условия, при выполнении которых оптимальное решение достигается за полиномиальное время. При невыполнении этих условий предлагаются правила отсечений, позволяющие существенно сократить время решения задачи. Данный алгоритм позволил получить точные решения для ряда задач с числом переменных существенно большим 50-ти. Оптимальные значения функционала, полученные данным алгоритмом для тестовых примеров, совпали со значениями функционала, рассчитанными другими известными методами. На підставі дослідження властивостей даної задачі запропоновано новий підхід до її розв’язання і розроблено на його основі ефективний наближений алгоритм. Сформульовано умови, при виконанні яких оптимальне рішення досягається за поліноміальний час. При невиконанні цих умов пропонуються правила відсікань, що дозволяють суттєво скоротити час розв’язання задачі. Даний алгоритм дозволив одержати точні рішення для ряду задач з числом змінних суттєво більшим 50-ти. Оптимальні значення функціонала, отримані даним алгоритмом для тестових прикладів, збіглися зі значеннями функціонала, отриманими відомими методами. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2019-08-21 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/176500 System research and information technologies; No. 2 (2002); 7-32 Системные исследования и информационные технологии; № 2 (2002); 7-32 Системні дослідження та інформаційні технології; № 2 (2002); 7-32 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/176500/176261 Copyright (c) 2021 System research and information technologies
spellingShingle	Pavlov, A. A. Misjura, E. B. Новий підхід до вирішення задачі "Мінімізація сумарного зваженого запізнення при виконанні незалежних завдань з директивними строками на одному приладі"
title	Новий підхід до вирішення задачі "Мінімізація сумарного зваженого запізнення при виконанні незалежних завдань з директивними строками на одному приладі"
title_alt	A new approach to solving the problem: "Minimization of total weighted tardiness when fulfilling independent tasks in due times at one machine" Новый подход к решению задачи "Минимизация суммарного взвешенного опоздания при выполнении независимых заданий с директивными сроками одним прибором"
title_full	Новий підхід до вирішення задачі "Мінімізація сумарного зваженого запізнення при виконанні незалежних завдань з директивними строками на одному приладі"
title_fullStr	Новий підхід до вирішення задачі "Мінімізація сумарного зваженого запізнення при виконанні незалежних завдань з директивними строками на одному приладі"
title_full_unstemmed	Новий підхід до вирішення задачі "Мінімізація сумарного зваженого запізнення при виконанні незалежних завдань з директивними строками на одному приладі"
title_short	Новий підхід до вирішення задачі "Мінімізація сумарного зваженого запізнення при виконанні незалежних завдань з директивними строками на одному приладі"
title_sort	новий підхід до вирішення задачі "мінімізація сумарного зваженого запізнення при виконанні незалежних завдань з директивними строками на одному приладі"
url	https://journal.iasa.kpi.ua/article/view/176500
work_keys_str_mv	AT pavlovaa anewapproachtosolvingtheproblemquotminimizationoftotalweightedtardinesswhenfulfillingindependenttasksinduetimesatonemachinequot AT misjuraeb anewapproachtosolvingtheproblemquotminimizationoftotalweightedtardinesswhenfulfillingindependenttasksinduetimesatonemachinequot AT pavlovaa novyjpodhodkrešeniûzadačiquotminimizaciâsummarnogovzvešennogoopozdaniâprivypolneniinezavisimyhzadanijsdirektivnymisrokamiodnimpriboromquot AT misjuraeb novyjpodhodkrešeniûzadačiquotminimizaciâsummarnogovzvešennogoopozdaniâprivypolneniinezavisimyhzadanijsdirektivnymisrokamiodnimpriboromquot AT pavlovaa novijpídhíddoviríšennâzadačíquotmínímízacíâsumarnogozvaženogozapíznennâprivikonannínezaležnihzavdanʹzdirektivnimistrokaminaodnomupriladíquot AT misjuraeb novijpídhíddoviríšennâzadačíquotmínímízacíâsumarnogozvaženogozapíznennâprivikonannínezaležnihzavdanʹzdirektivnimistrokaminaodnomupriladíquot AT pavlovaa newapproachtosolvingtheproblemquotminimizationoftotalweightedtardinesswhenfulfillingindependenttasksinduetimesatonemachinequot AT misjuraeb newapproachtosolvingtheproblemquotminimizationoftotalweightedtardinesswhenfulfillingindependenttasksinduetimesatonemachinequot

Новий підхід до вирішення задачі &quot;Мінімізація сумарного зваженого запізнення при виконанні незалежних завдань з директивними строками на одному приладі&quot;

Institution

Ähnliche Einträge

Новий підхід до вирішення задачі "Мінімізація сумарного зваженого запізнення при виконанні незалежних завдань з директивними строками на одному приладі"