Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования
Рассмотрен метод минимизации суммарного запаздывания работ на одиночном устройстве на основе определения кратчайшего гамильтонового пути в произвольном полносвязном графе с использованием рангового подхода и правил доминирования. Предложены метрики оценивания улучшения результатов работы алгоритма п...
Saved in:
| Published in: | Электронное моделирование |
|---|---|
| Date: | 2014 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2014
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/100993 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования / С.В. Минухин, Д.С. Ленько // Электронное моделирование. — 2014 — Т. 36, № 2. — С. 57-79. — Бібліогр.: 35 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860190219360272384 |
|---|---|
| author | Минухин, С.В. Ленько, Д.С. |
| author_facet | Минухин, С.В. Ленько, Д.С. |
| citation_txt | Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования / С.В. Минухин, Д.С. Ленько // Электронное моделирование. — 2014 — Т. 36, № 2. — С. 57-79. — Бібліогр.: 35 назв. — рос. |
| collection | DSpace DC |
| container_title | Электронное моделирование |
| description | Рассмотрен метод минимизации суммарного запаздывания работ на одиночном устройстве на основе определения кратчайшего гамильтонового пути в произвольном полносвязном графе с использованием рангового подхода и правил доминирования. Предложены метрики оценивания улучшения результатов работы алгоритма при использовании правил доминирования—относительного уменьшения суммарного запаздывания и числа получаемых локально-оптимальных решений. Приведены результаты вычислительных экспериментов для взвешенного и невзвешенного случаев запаздывания работ с произвольными директивными сроками. Найдены условия, при которых используемый алгоритм позволяет улучшить расписания работ и определить наиболее эффективные правила доминирования.
Розглянуто метод мінімізації сумарного запізнювання робіт на одиночному пристрої на основі визначення найкоротшого гамільтонового шляху в довільному повнозв’язному графі з використанням рангового підходу і правил домінування. Запропоновано метрики оцінювання поліпшення результатів роботи алгоритму при використанні правил домінування — відносного зменшення сумарного запізнювання і кількості одержуваних локально-оптимальних рішень. Наведено результати обчислювальних експериментів для зваженого і незваженого запізнювання робіт з довільними директивними термінами. Визначено умови, при яких досліджуваний алгоритм дозволяє покращити розклад робіт, і знайдено найбільш ефективні правила домінування.
The paper deals with the algorithms of minimizing the total lag of works on a single device on the basis of determining the shortest Hamilton path in the arbitrary graph using the rank approach and the dominance rules. The performance metrics of applying the dominance rules based on the evaluation of locally optimal solutions, obtained on different ranks and the values of relative reduction of total lag in relation to the basic algorithm are proposed. The results of computational experiments for the weighted and unweighted cases for the works with different duration and the types of due dates defined in the research are given. The conditions, under which, the proposed algorithms allow improving the schedule of works are defined and the most effective dominance rules are determined.
|
| first_indexed | 2025-12-07T18:06:08Z |
| format | Article |
| fulltext |
ÓÄÊ 621.398
Ñ.Â. Ìèíóõèí, êàíä. òåõí. íàóê
Õàðüêîâñêèé íàöèîíàëüíûé ýêîíîìè÷åñêèé óíèâåðñèòåò
(Óêðàèíà, 61001, Õàðüêîâ, ïð-ò Ëåíèíà, 9-à,
òåë.: 057 7021831, e-mail: ms_vl@mail.ru),
Ä.Ñ. Ëåíüêî
(Óêðàèíà, Õàðüêîâ, e-mail: dmytrolenko@gmail.com)
Ìåòîä ìèíèìèçàöèè ñóììàðíîãî çàïàçäûâàíèÿ
ðàáîò íà îäèíî÷íîì óñòðîéñòâå íà îñíîâå
ðàíãîâîãî ïîäõîäà è ïðàâèë äîìèíèðîâàíèÿ
Ðàññìîòðåí ìåòîä ìèíèìèçàöèè ñóììàðíîãî çàïàçäûâàíèÿ ðàáîò íà îäèíî÷íîì óñò-
ðîéñòâå íà îñíîâå îïðåäåëåíèÿ êðàò÷àéøåãî ãàìèëüòîíîâîãî ïóòè â ïðîèçâîëüíîì ïîëíî-
ñâÿçíîì ãðàôå ñ èñïîëüçîâàíèåì ðàíãîâîãî ïîäõîäà è ïðàâèë äîìèíèðîâàíèÿ. Ïðåäëî-
æåíû ìåòðèêè îöåíèâàíèÿ óëó÷øåíèÿ ðåçóëüòàòîâ ðàáîòû àëãîðèòìà ïðè èñïîëüçîâàíèè
ïðàâèë äîìèíèðîâàíèÿ — îòíîñèòåëüíîãî óìåíüøåíèÿ ñóììàðíîãî çàïàçäûâàíèÿ è ÷èñëà
ïîëó÷àåìûõ ëîêàëüíî-îïòèìàëüíûõ ðåøåíèé. Ïðèâåäåíû ðåçóëüòàòû âû÷èñëèòåëüíûõ
ýêñïåðèìåíòîâ äëÿ âçâåøåííîãî è íåâçâåøåííîãî ñëó÷àåâ çàïàçäûâàíèÿ ðàáîò ñ ïðîèç-
âîëüíûìè äèðåêòèâíûìè ñðîêàìè. Íàéäåíû óñëîâèÿ, ïðè êîòîðûõ èñïîëüçóåìûé àëãî-
ðèòì ïîçâîëÿåò óëó÷øèòü ðàñïèñàíèÿ ðàáîò è îïðåäåëèòü íàèáîëåå ýôôåêòèâíûå ïðàâèëà
äîìèíèðîâàíèÿ.
Ðîçãëÿíóòî ìåòîä ì³í³ì³çàö³¿ ñóìàðíîãî çàï³çíþâàííÿ ðîá³ò íà îäèíî÷íîìó ïðèñòðî¿ íà
îñíîâ³ âèçíà÷åííÿ íàéêîðîòøîãî ãàì³ëüòîíîâîãî øëÿõó â äîâ³ëüíîìó ïîâíîçâ’ÿçíîìó
ãðàô³ ç âèêîðèñòàííÿì ðàíãîâîãî ï³äõîäó ³ ïðàâèë äîì³íóâàííÿ. Çàïðîïîíîâàíî ìåòðèêè
îö³íþâàííÿ ïîë³ïøåííÿ ðåçóëüòàò³â ðîáîòè àëãîðèòìó ïðè âèêîðèñòàíí³ ïðàâèë äîì³íó-
âàííÿ — â³äíîñíîãî çìåíøåííÿ ñóìàðíîãî çàï³çíþâàííÿ ³ ê³ëüêîñò³ îäåðæóâàíèõ ëî-
êàëüíî-îïòèìàëüíèõ ð³øåíü. Íàâåäåíî ðåçóëüòàòè îá÷èñëþâàëüíèõ åêñïåðèìåíò³â äëÿ
çâàæåíîãî ³ íåçâàæåíîãî çàï³çíþâàííÿ ðîá³ò ç äîâ³ëüíèìè äèðåêòèâíèìè òåðì³íàìè. Âè-
çíà÷åíî óìîâè, ïðè ÿêèõ äîñë³äæóâàíèé àëãîðèòì äîçâîëÿº ïîêðàùèòè ðîçêëàä ðîá³ò, ³
çíàéäåíî íàéá³ëüø åôåêòèâí³ ïðàâèëà äîì³íóâàííÿ.
Ê ë þ ÷ å â û å ñ ë î â à: ðàíãîâûé ïîäõîä, ãàìèëüòîíîâ ïóòü, ðàñïèñàíèå, ñóììàðíîå çàïàç-
äûâàíèå, âðåìåííàÿ ñëîæíîñòü, äèðåêòèâíûé ñðîê, îäèíî÷íîå óñòðîéñòâî, äëèòåëü-
íîñòü, ïðàâèëî äîìèíèðîâàíèÿ.
Äëÿ ñîâðåìåííûõ èíôîðìàöèîííî-êîììóíèêàöèîííûõ ñèñòåì õàðàêòåð-
íî íàëè÷èå áîëüøîãî ÷èñëà ðàçëè÷íûõ òèïîâ ðåñóðñîâ — èíôîðìàöèîí-
íûõ, âû÷èñëèòåëüíûõ è äðóãèõ, óïðàâëåíèå êîòîðûìè òðåáóåò ïîâûøå-
íèÿ ýôôåêòèâíîñòè è ñîâåðøåíñòâîâàíèÿ ñèñòåì óïðàâëåíèÿ ðàñïðåäå-
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 2 57
� Ñ.Â. Ìèíóõèí, Ä.Ñ. Ëåíüêî, 2014
ëåííîé îáðàáîòêîé. Îäíîé èç âàæíåéøèõ çàäà÷ ÿâëÿåòñÿ ðàçðàáîòêà ýô-
ôåêòèâíûõ àëãîðèòìîâ ïîñòðîåíèÿ ëîêàëüíûõ ðàñïèñàíèé âûïîëíåíèÿ
ðàáîò â ñîîòâåòñòâèè ñ âûáðàííûìè êðèòåðèÿìè íà âû÷èñëèòåëüíûõ óñò-
ðîéñòâàõ, òàêèõ, íàïðèìåð, êàê óçëû Ãðèä-ñèñòåì — âû÷èñëèòåëüíûå êëàñ-
òåðû, êëàñòåðû ðàáî÷èõ ñòàíöèé, íåêëàñòåðèçîâàííûå ðåñóðñû.  êà÷åñòâå
òàêèõ êðèòåðèåâ ìîãóò áûòü èñïîëüçîâàíû îãðàíè÷åíèÿ íà âðåìÿ âûïîëíåíèÿ
ïîòîêîâ çàäàíèé èëè áþäæåòíûå ðàñõîäû, â îñíîâó êîòîðûõ ïîëîæåíà ìî-
äåëü ðàáîòû ñ äèðåêòèâíûì ñðîêîì âûïîëíåíèÿ, òðåáóþùàÿ íîâûõ ïîäõîäîâ
ê ðåøåíèþ çàäà÷ ïëàíèðîâàíèÿ.
 ñâÿçè ñ ýòèì ïîëó÷èëè ðàçâèòèå ìåòîäû ïîñòðîåíèÿ ðàñïèñàíèé
âûïîëíåíèÿ ðàáîò, øèðîêî èñïîëüçóåìûå â ïðîìûøëåííîì ïëàíèðîâà-
íèè. Â [1] ïðåäëîæåíà ìîäåëü ðàáîòû âåá-ñåðâåðà, èñïîëüçóþùåãî îäíó
î÷åðåäü ðàáîò. Ýòà ìîäåëü ïîçâîëÿåò äèôôåðåíöèðîâàòü QoS (Quality of
Service) äëÿ ðàçëè÷íûõ êëàññîâ çàïðîñîâ ê âåá-ñåðâèñàì ïî òàêèì ïðèîðè-
òåòàì, êàê âçâåøåííîå íàèìåíüøåå âðåìÿ âûïîëíåíèÿ (WSPT), íàèìåíü-
øèé äèðåêòèâíûé ñðîê (EDD) è äð. Ýòè ïðàâèëà èñïîëüçîâàíû ïðè îöåíêå
QoS äëÿ ñòðàòåãèè FIFO (FCFS) â ìîäåëè Best Effort, â êîòîðîé âåá-çàïðîñ
îïèñûâàåòñÿ ïðèîðèòåòîì, âðåìåíåì ïîñòóïëåíèÿ íà îáðàáîòêó, òðåáóå-
ìîé äëÿ åãî ðåàëèçàöèè ïàìÿòüþ, è äèðåêòèâíûì ñðîêîì âûïîëíåíèÿ.
Áàçîâàÿ ìîäåëü Best Effort âêëþ÷àåò ìíîæåñòâî çàïðîñîâ, î÷åðåäè äëÿ èõ
ñîðòèðîâêè è îæèäàíèÿ çàïðîñîâ â î÷åðåäè äî âðåìåíè èõ îáñëóæèâàíèÿ
íà ñåðâåðå.
 ðàáîòàõ [2—4] ðàññìîòðåíû ïîäõîäû ê ïëàíèðîâàíèþ íåïðåðûâ-
íîãî ïîòîêà ïàêåòîâ çàäàíèé ñ èñïîëüçîâàíèåì ïðàâèë ïðèîðèòåòà íà
ìàøèíàõ (ïðîöåññîðíûõ ýëåìåíòàõ) ðàñïðåäåëåííîé Ãðèä-ñèñòåìû. Íî-
âèçíà ðåøåíèÿ, ïðåäëîæåííîãî â [4—6], çàêëþ÷àåòñÿ â èñïîëüçîâàíèè
ïðàâèëà «íàèáîëåå ðàííèé çàçîð EG (Earliest Gap) — ïåðâûé ñ íàèáîëåå
ðàííèì äèðåêòèâíûì ñðîêîì EDF (Earliest Deadline First)» è çàïðåò íà ïîèñê,
îñíîâàííûé íà èäåå çàïîëíåíèÿ «çàçîðîâ» â òåêóùåì ðàñïèñàíèè ðàáîò.
Ïðàâèëî EG— EDF ïîçâîëÿåò ñòðîèòü ðàñïèñàíèå äëÿ âñåõ ðàáîò ïîñëå-
äîâàòåëüíî, ïðèìåíÿÿ òåõíèêó, ñ ïîìîùüþ êîòîðîé çàïîëíÿþòñÿ ðàíåå
èìåþùèåñÿ çàçîðû — EG — â ðàñïèñàíèè èç ìíîæåñòâà âíîâü ïðèáûâøèõ
ðàáîò.  ñëó÷àå, åñëè çàçîð äëÿ ïîñòóïàþùåé ðàáîòû îòñóòñòâóåò, òî èñ-
ïîëüçóåòñÿ âòîðîå ïðàâèëî — EDF — äëÿ âêëþ÷åíèÿ íîâîé ðàáîòû â
ñóùåñòâóþùåå ðàñïèñàíèå.
Äëÿ ðàñïðåäåëåííîé âû÷èñëèòåëüíîé ñèñòåìû (Ãðèä-ñèñòåìû, êëàñòå-
ðà) èñïîëüçóåòñÿ ìåòîä îïòèìèçàöèè ëîêàëüíûõ ðàñïèñàíèé [7, 8], ïðåäóñ-
ìàòðèâàþùèé ïðèìåíåíèå ðåæèìà ïàêåòíîãî ïëàíèðîâàíèÿ, êîòîðûé ñîñ-
òîèò â ñëåäóþùåì. Èç âõîäíîãî ïîòîêà ðàáîò ôîðìèðóåòñÿ ïóë, ðàçìåð
Ñ.Â. Ìèíóõèí, Ä.Ñ. Ëåíüêî
58 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 2
êîòîðîãî îïðåäåëÿåòñÿ íà îñíîâàíèè õàðàêòåðèñòèê ðàñïðåäåëåííîé ñðå-
äû è ðàáîò. Çàòåì ïëàíèðîâùèê ïëàíèðóåò (íàçíà÷àåò) îïðåäåëåííûå ðå-
ñóðñû äëÿ èõ âûïîëíåíèÿ â ñîîòâåòñòâèè ñ ìîäåëüþ ìåòîäà î íàèìåíüøåì
ïîêðûòèè è îòïðàâëÿåò çàäàíèÿ íà ïîëó÷åííûå òàêèì îáðàçîì ðåñóðñû â
âèäå ìíîæåñòâà ïàêåòîâ, óïîðÿäî÷åííûõ è îðãàíèçîâàííûõ â âèäå î÷å-
ðåäåé, êàæäàÿ èç êîòîðûõ äîëæíà âûïîëíÿòüñÿ íà ðåñóðñå â óñëîâèÿõ
îãðàíè÷åíèé (íà áþäæåò èëè èñïîëüçîâàíèå äèðåêòèâíîãî ñðîêà). Åñëè
îãðàíè÷åíèåì ÿâëÿåòñÿ âðåìÿ âûïîëíåíèÿ èëè äèðåêòèâíûé ñðîê ðàáîòû,
òî ìîæíî èñïîëüçîâàòü ìåòîäû ïîñòðîåíèÿ ðàñïèñàíèÿ âûïîëíåíèÿ çàäà-
íèé íà îäèíî÷íîì óñòðîéñòâå (ïðèáîðå), ó÷èòûâàÿ ñïåöèôèêó ðàáîòû
îïèñàííîãî ìåõàíèçìà ñèñòåìû ïëàíèðîâàíèÿ.
Ýòà çàäà÷à, ñ ôîðìàëüíîé òî÷êè çðåíèÿ, ìîæåò áûòü ñâåäåíà, íàïðè-
ìåð, ê êëàññè÷åñêîé çàäà÷å ìèíèìèçàöèè ñóììàðíîãî (ñðåäíåãî) âçâåøåí-
íîãî è íåâçâåøåííîãî çàïàçäûâàíèÿ ðàáîò íà îäíîì óñòðîéñòâå (ïðèáîðå).
Åå ðåøåíèå âûçûâàåò ïðàêòè÷åñêèé èíòåðåñ îòíîñèòåëüíî îïòèìèçàöèè
(ïîâûøåíèÿ ýôôåêòèâíîñòè) ôóíêöèîíèðîâàíèÿ ëîêàëüíûõ ìåíåäæåðîâ
ðåñóðñîâ ðàñïðåäåëåííûõ ñèñòåì ñ öåëüþ óìåíüøåíèÿ, à âîçìîæíî, è
óñòðàíåíèÿ çàïàçäûâàíèÿ â ñëó÷àÿõ, êîãäà â ìîäåëè, îïèñûâàþùåé ðà-
áîòó, èñïîëüçóåòñÿ äèðåêòèâíûé ñðîê. Ýòî ïîçâîëèò ñíèçèòü ðèñêè, ñâÿ-
çàííûå ñî øòðàôíûìè ñàíêöèÿìè, ïðèâîäÿùèìè ê ýêîíîìè÷åñêèì óáûò-
êàì çàêàç÷èêîâ è ïîëüçîâàòåëåé âû÷èñëèòåëüíûõ ðåñóðñîâ.
 ðàáîòàõ [9—18] ïðèâåäåíû ìåòîäû ðåøåíèÿ çàäà÷è ìèíèìèçàöèè
ñóììàðíîãî çàïàçäûâàíèÿ, à â ðàáîòàõ [19—20] ïðåäëîæåí è èññëåäîâàí
ýôôåêòèâíûé òî÷íûé ïîëèíîìèàëüíîé ñëîæíîñòè àëãîðèòì ðåøåíèÿ çà-
äà÷è ìèíèìèçàöèè ñóììàðíîãî çàïàçäûâàíèÿ îäíèì ïðèáîðîì.  [21]
ïðåäñòàâëåí ìåòîä ìèíèìèçàöèè ñóììàðíîãî âðåìåíè çàïàçäûâàíèÿ (îï-
òèìèçàöèè ïî íàïðàâëåíèþ), îñíîâàííûé íà ïîñòðîåíèè êðàò÷àéøåãî ãà-
ìèëüòîíîâà ïóòè â ïîëíîñâÿçíîì ïðîèçâîëüíîì ãðàôå è ðàíãîâîãî ïîäõîäà ñ
âðåìåííîé ñëîæíîñòüþ O ( )n3 , ãäå n — ÷èñëî ðàáîò (âåðøèí â ãðàôå).
 ðàáîòàõ [22, 23] âûäâèíóòà ãèïîòåçà î òîì, ÷òî â ñëó÷àÿõ, êîãäà íà
ðàíãå ñóùåñòâóåò íåñêîëüêî àëüòåðíàòèâíûõ ïóòåé, èìåþùèõ îäèíàêî-
âóþ äëèíó, íóæíî âûáèðàòü òîò ïóòü, â êîòîðîì ïîñëåäîâàòåëüíîñòü ðàáîò
(âåðøèí), ïðåäøåñòâóþùèõ äàííîé âåðøèíå, óäîâëåòâîðÿåò ïðàâèëó äî-
ìèíèðîâàíèÿ.
Èññëåäóåì ìåòîä è àëãîðèòì ìèíèìèçàöèè ñóììàðíîãî âðåìåíè çà-
ïàçäûâàíèÿ ðàáîò íà îäèíî÷íîì âû÷èñëèòåëüíîì óñòðîéñòâå íà îñíîâå
ïîñòðîåíèÿ êðàò÷àéøåãî ãàìèëüòîíîâà ïóòè â ïðîèçâîëüíîì ãðàôå è ðàí-
ãîâîãî ïîäõîäà ñ èñïîëüçîâàíèåì ïðàâèë äîìèíèðîâàíèÿ è îöåíêè åãî
ýôôåêòèâíîñòè äëÿ ðàáîò ñ ïðîèçâîëüíûìè äèðåêòèâíûìè ñðîêàìè.
Ïîñòàíîâêà çàäà÷è. Ïðåäïîëîæèì, ÷òî íà îäèíî÷íîå óñòðîéñòâî
(âû÷èñëèòåëüíûé ðåñóðñ) ïîñòóïàåò ìíîæåñòâî íåçàâèñèìûõ ðàáîò
Ìåòîä ìèíèìèçàöèè ñóììàðíîãî çàïàçäûâàíèÿ ðàáîò íà îäèíî÷íîì óñòðîéñòâå
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 2 59
J J J Jn�{ , , ..., }1 2 , êàæäàÿ èç êîòî-
ðûõ áóäåò íåïðåðûâíî (áåç ïðåðû-
âàíèé) âûïîëíÿòüñÿ íà íåì. Ïðè
ýòîì èçâåñòíû äëèòåëüíîñòü âûïîë-
íåíèÿ êàæäîãî çàäàíèÿ Lj è äèðåê-
òèâíûé ñðîê åãî âûïîëíåíèÿ d j . Íå-
îáõîäèìî îïðåäåëèòü òàêîé ïîðÿäîê
(ïîñëåäîâàòåëüíîñòü) âûïîëíåíèÿ
âñåõ çàäàíèé, îäíîâðåìåííî ïîñòóïàþùèõ íà óñòðîéñòâî, êîòîðûé ìèíè-
ìèçèðóåò ñóììàðíîå âðåìÿTTS çàïàçäûâàíèÿ âñåõ çàäàíèé âõîäíîé î÷åðåäè,
TT C dS
j S
j j� �
�
�
{ }
max ( , )0 ,
ãäå Cj — âðåìÿ çàâåðøåíèÿ ðàáîòû j. Ìåòîä ðåøåíèÿ ýòîé çàäà÷è, îáî-
çíà÷àåìîé1|| Ti� , ïðåäëîæåí â [21].
Çàäà÷ó ìèíèìèçàöèè (1|| w Ti i� ) ñóììàðíîãî âçâåøåííîãî âðåìåíè
çàïàçäûâàíèÿ íà îäèíî÷íîì óñòðîéñòâå,
TWT C d wS
j S
j j j� �
�
�
{ }
max ( ,( ) )0 ,
ñôîðìóëèðóåì òàê. Ìíîæåñòâî ðàáîò, ïðîèíäåêñèðîâàííûõ îò 1 äî n,
äîëæíî áûòü âûïîëíåíî áåç ïðåðûâàíèé íà îäèíî÷íîì óñòðîéñòâå, îáðà-
áàòûâàþùåì òîëüêî îäíó ðàáîòó â îïðåäåëåííûé ìîìåíò âðåìåíè. Âñå
ðàáîòû ïîñòóïàþò íà óñòðîéñòâî â ìîìåíò âðåìåíè t = 0 (èëè îäíîâðå-
ìåííî). Ðàáîòà õàðàêòåðèçóåòñÿ âðåìåíåì åå îáðàáîòêè Li (èëè ïðîöåñ-
ñîðíûì âðåìåíåì pi), äèðåêòèâíûì ñðîêîì di è âåñîì wi. Äëÿ óäîáñòâà âñå
ðàáîòû óïîðÿäî÷åíû ñîãëàñíî ïðàâèëó EDD, ïîýòîìó di < dj. Åñëè di = dj,
òî pi < pj; åñëè pi = pj, òî wi > wj äëÿ âñåõ i, j (i < j). Åñëè ðàáîòà çàâåðøàåòñÿ
ïîçæå ñâîåãî äèðåêòèâíîãî ñðîêà di, ðåçóëüòàòîì ÿâëÿåòñÿ âçâåøåííûé
øòðàô çà çàïàçäûâàíèå.
Äëÿ îáîñíîâàíèÿ öåëåñîîáðàçíîñòè èñïîëüçîâàíèÿ ïðàâèë äîìèíèðîâà-
íèÿ ðàññìîòðèì ðàáîòó àëãîðèòìà íà îñíîâå ïðîèçâîëüíîãî ïîëíîñâÿçíîãî
ãðàôà ñ ÷åòûðüìÿ âåðøèíàìè, êîòîðûå îïðåäåëÿþò ðàáîòû òåñòîâîé ïîñëåäî-
âàòåëüíîñòè, ñóòü ìåòîäà è èñïîëüçîâàíèå ïðàâèë äîìèíèðîâàíèÿ.
Ïóñòü äëÿ ìíîæåñòâà ðàáîò J1 (4, 7), J2 (5, 6), J3 (3, 7), J4 (3, 4) íåîá-
õîäèìî ïîñòðîèòü îïòèìàëüíîå ðàñïèñàíèå. Êàæäàÿ ðàáîòà J èìååò äâà
ïàðàìåòðà: äëèòåëüíîñòü L è äèðåêòèâíûé ñðîê d. Ñëåäîâàòåëüíî, åå ìîæ-
íî ïðåäñòàâèòü â âèäå J (L, d). Ãðàô, îòîáðàæàþùèé äàííîå ìíîæåñòâî
ðàáîò, ïðåäñòàâëåí íà ðèñ. 1.
Äëÿ ïîÿñíåíèÿ ðàáîòû áàçîâîãî àëãîðèòìà [21] èñïîëüçóåì ìàòðèöó, â
êîòîðîé ñòîëáöàì ñîîòâåòñòâóþò ðàíãè, à ñòðîêàì — ðàáîòû. Äëÿ ýòèõ
Ñ.Â. Ìèíóõèí, Ä.Ñ. Ëåíüêî
60 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 2
(3, 7)J3
J4 (3, 4)
J2 (5, 6)
J
1
(4, 7)
Ðèñ. 1. Ïîëíîñâÿçíûé ãðàô èç ÷åòûðåõ âåð-
øèí (ðàáîò)
Ìåòîä ìèíèìèçàöèè ñóììàðíîãî çàïàçäûâàíèÿ ðàáîò íà îäèíî÷íîì óñòðîéñòâå
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 2 61
Â
åð
ø
è
í
à
Ð
àí
ã
1
Ð
àí
ã
2
Ð
àí
ã
3
Ð
àí
ã
4
J
1
4
7
(
,
)
T
(
)
(
)
1
0
4
7
3
1
�
�
�
�
�
T
(
)
(
)
,
2
5
4
7
2
2
1
�
�
�
�
T
(
)
(
)
,
,
3
8
4
7
5
4
2
1
�
�
�
�
T
T
3
4
2
1
0
2
5
8
1
5
,
,
,
�
�
�
�
�
T
(
)
(
)
,
2
3
4
7
0
3
1
�
�
�
�
T
(
)
(
)
,
,
3
6
4
7
3
4
3
1
�
�
�
�
T
(
)
(
)
,
2
3
4
7
0
4
1
�
�
�
�
T
(
)
(
)
,
,
3
6
4
7
3
3
4
1
�
�
�
�
J
2
5
6
(
,
)
T
(
)
(
)
1
0
5
6
1
2
�
�
�
�
�
T
(
)
(
)
,
2
4
5
6
3
1
2
�
�
�
�
T
(
)
(
)
,
,
3
7
5
6
6
4
1
2
�
�
�
�
T
T
4
3
1
2
0
0
3
9
1
2
,
,
,
�
�
�
�
�
T
(
)
(
)
,
2
3
5
6
2
3
2
�
�
�
�
T
(
)
(
)
,
,
3
6
5
6
5
4
3
2
�
�
�
�
T
T
4
1
3
2
0
0
3
9
1
2
,
,
,
�
�
�
�
�
T
(
)
(
)
,
2
3
5
6
2
4
2
�
�
�
�
T
(
)
(
)
,
,
3
6
5
6
5
3
4
2
�
�
�
�
J
3
3
7
(
,
)
T
(
)
(
)
1
0
3
7
4
3
�
�
�
�
�
T
(
)
(
)
,
2
4
3
7
0
1
3
�
�
�
�
T
(
)
(
)
,
,
3
7
3
7
3
4
1
3
�
�
�
�
T
(
)
(
)
,
2
5
3
7
1
2
3
�
�
�
�
T
(
)
(
)
,
,
3
8
3
7
4
4
2
3
�
�
�
�
T
(
)
(
)
,
2
3
3
7
1
4
3
�
�
�
�
�
J
4
3
4
(
,
)
T
(
)
(
)
1
0
3
1
0
7
4
�
�
�
�
�
T
(
)
(
)
,
2
4
3
4
3
1
4
�
�
�
�
T
(
)
(
)
,
2
5
3
4
4
2
4
�
�
�
�
T
(
)
(
)
,
2
3
3
4
2
3
4
�
�
�
�
Ï
ð
è
ì
å÷
à
í
è
å.
Ï
î
ë
ó
æ
è
ð
í
û
ì
ø
ð
è
ô
òî
ì
â
û
ä
åë
åí
û
î
ï
òè
ì
àë
ü
í
û
å
ï
ó
òè
,
î
ï
ð
åä
åë
ÿ
åì
û
å
àë
ãî
ð
è
òì
î
ì
í
à
ê
àæ
ä
î
ì
ð
àí
ãå
.
Ò
à
á
ëè
ö
à
1
.
Ï
ð
è
ì
åð
ð
à
á
î
ò
û
à
ë
ã
î
ð
è
ò
ì
à
ñî
ã
ë
à
ñí
î
ï
ð
à
â
è
ë
ó
E
D
D
ðàáîò íåîáõîäèìî ïîñòðîèòü ãðàôèê âûïîëíåíèÿ (òàáë. 1). Âåëè÷èíó òå-
êóùåãî çàïàçäûâàíèÿ ðàáîò íà êàæäîì ðàíãå îáîçíà÷èì T J j j jn
( ) ...1 2
, ãäå
J — ÷èñëî ðàíãîâ (ñòîëáöîâ), j j jn1 2, , ..., — âåðøèíû (ðàáîòû), âõîäÿùèå â
òåêóùèé ïóòü ê êàêîé-ëèáî âåðøèíå (ðàáîòå) íà òåêóùåì ðàíãå (ñòîëáöå)
ìàòðèöû. Òàêèì îáðàçîì, ñóììàðíîå çàïàçäûâàíèå âñåõ ðàáîò ÒÒ áóäåò
îïðåäåëÿòüñÿ íà ïîñëåäíåì ðàíãå.
 íà÷àëüíîì ñîñòîÿíèè ðàáîòû íå óïîðÿäî÷åíû, çàïàçäûâàíèå êàæäîé
èç íèõ ðàâíî íóëþ. Â ïåðâîé ñòðîêå ìàòðèöû íàõîäÿòñÿ âñå ïóòè îò ðàáîò
J2, J3, J4 ê ðàáîòå J1, âî âòîðîé — ïóòè îò ðàáîò J1, J3, J4 ê ðàáîòå J2, â òðåòüåé —
ïóòè îò ðàáîò J1, J2, J4 ê ðàáîòå J3, â ÷åòâåðòîé — ïóòè îò ðàáîò J1, J2, J3 ê
ðàáîòå J4. Äàëåå, â ñîîòâåòñòâèè ñ àëãîðèòìîì, íåîáõîäèìî äëÿ êàæäîé
ñòðîêè âûáðàòü ìèíèìàëüíûé ïóòü:
äëÿ ïåðâîé ñòðîêè — T (2)3,1 =3 + (4–7) = 0 è T (2)4,1 = 3 + (4–7) = 0;
äëÿ âòîðîé ñòðîêè — T (2)3,2 = 3 + (5–6) = 2 è T (2)4,2 = 3 + (5–6) = 2;
äëÿ òðåòüåé ñòðîêè — T (2)4,3 = 3 + (3–7) = –1;
äëÿ ÷åòâåðòîé ñòðîêè — T (2)3,4 = 3 + (3–4) = 2.
Ïîñëå ýòîãî íà ðàíãå 3 âûáèðàåì:
â ïåðâîé ñòðîêå — T (3)4,3,1 = 6 + (4–7) = 3 è T (3)3,4,1 = 6 + (4–7) = 3;
âî âòîðîé ñòðîêå — T (3)4,3,2 = 6 + (5–6) = 5 è T (3)3,4,2 = 6 + (5–6) = 5;
â òðåòüåé ñòðîêå — T (3)4,1,3 = 7 + (3–7) = 3;
â ÷åòâåðòîé ñòðîêå — T (3)3,1,4 = 7 + (3–4) = 6.
Äàëåå ñòðîèì ïóòè èç âåðøèí ðàíãà 3 ê âåðøèíàì ðàíãà 4:
äëÿ ïåðâîé ñòðîêè — TT4,3,2,1 = 0 + 0 + 5 + 8 = 13;
äëÿ âòîðîé ñòðîêè — TT4,3,1,2 = 0+0+3+9 = 12 è TT4,1,3,2 = 0+0+3+9 = 12.
Òàêèì îáðàçîì, êðàò÷àéøèé ãàìèëüòîíîâ ïóòü â ãðàôå (ðèñ. 2, â)
âêëþ÷àåò ïîñëåäîâàòåëüíîñòü ðàáîò J4 J3 J1 J2. Êàê ñëåäóåò èç ïðèìåðà,
ôîðìèðóåìûå àëãîðèòìîì íà ðàíãàõ òåêóùèå ïóòè èìåþò îäèíàêîâûå
äëèíû. Îáîñíóåì öåëåñîîáðàçíîñòü ïðèìåíåíèÿ ïðàâèë äîìèíèðîâàíèÿ
äëÿ âûáîðà ëó÷øåãî èç íèõ.
Îáîñíîâàíèå öåëåñîîáðàçíîñòè èñïîëüçîâàíèÿ ïðàâèë äîìèíèðî-
âàíèÿ â áàçîâîì àëãîðèòìå [21]. Ââåäåì ñëåäóþùèå îïðåäåëåíèÿ è ïðåä-
ïîëîæåíèÿ.
Îïðåäåëåíèå 1. Òåêóùåé ïîñëåäîâàòåëüíîñòüþ ðàáîò � ( )R íà ðàíãå
R ñ äëèíîé ðàñïèñàíèÿ T R� ( ) èç ÷àñòíîé ïîñëåäîâàòåëüíîñòè ðàáîò
� � j j jn1 2, ,..., ÿâëÿåòñÿ ïîñëåäîâàòåëüíîñòü, ôîðìèðóåìàÿ íà øàãå, ñîîò-
âåòñòâóþùåì ðàíãó R, è ñîñòîÿùåé èç ðàáîò, âûáðàííûõ àëãîðèòìîì äëÿ
ðàíãà R – 1, è ðàáîòû íà ðàíãå R.
Îïðåäåëåíèå 2. Òåêóùóþ ïîñëåäîâàòåëüíîñòü ðàáîò � ( )R íà ðàíãå
R ñ äëèíîé ðàñïèñàíèÿ T R� ( ) èç ÷àñòíîé ïîñëåäîâàòåëüíîñòè ðàáîò � �
� j j jn1 2, ,..., íàçîâåì «ëó÷øåé», ÷åì òåêóùàÿ ïîñëåäîâàòåëüíîñòü T R�( ),
åñëè âûïîëíÿåòñÿ óñëîâèå T R T R� �( ) ( )�
0 (T R T R� �( ) ( )
).
Ñ.Â. Ìèíóõèí, Ä.Ñ. Ëåíüêî
62 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 2
Îïðåäåëåíèå 3. Òåêóùóþ ïîñëåäîâàòåëüíîñòü ðàáîò � ( )R íà ðàíãå
R ñ äëèíîé ðàñïèñàíèÿ T R�( ) èç ÷àñòíîé ïîñëåäîâàòåëüíîñòè ðàáîò
� � j j jn1 2, ,..., íàçîâåì «ýêâèâàëåíòíîé» òåêóùåé ïîñëåäîâàòåëüíîñòè T R�( ),
åñëè âûïîëíÿåòñÿ óñëîâèå T R T R� �( ) ( )� �0 (T R T R� �( ) ( )� ).
Îïðåäåëåíèå 4. Äëÿ ðàáîò Ji è Jk , çàïëàíèðîâàííûõ íà ïðåäûäóùåì ïî
îòíîøåíèþ ê òåêóùåìó ðàíãå, ïðè óñëîâèè T R T R� �( ) ( )� �0 (îïðåäåëå-
íèå 3) îïòèìàëüíûì ÿâëÿåòñÿ òî ðàñïèñàíèå, â êîòîðîì Ji ïðåäøåñòâóåò Jk
ïî òèïó äîìèíèðîâàíèÿ [24]:
îòíîøåíèå ãëîáàëüíîãî ïðåäøåñòâîâàíèÿ — ðàáîòû ðàñïîëàãàþòñÿ â
îïðåäåëåííîì ïîðÿäêå, êîòîðûé îïðåäåëÿåòñÿ ïî ïðèíÿòûì ïðàâèëàì äî-
ìèíèðîâàíèÿ (íåâçâåøåííûé è âçâåøåííûé ñëó÷àè);
îòíîøåíèå áåçóñëîâíîãî ïðåäøåñòâîâàíèÿ — ðàáîòû ðàñïîëàãàþòñÿ â
òàêîì ïîðÿäêå, ïðè êîòîðîì èõ ïåðåñòàíîâêà óâåëè÷èâàåò êðèòåðèé èëè îïðå-
äåëÿåò âîçìîæíîñòü ïðèìåíåíèÿ îïðåäåëåííîãî ïðàâèëà äîìèíèðîâàíèÿ;
îòíîøåíèå ïðåäøåñòâîâàíèÿ, çàâèñèìîãî îò âðåìåíè, — ðàáîòû ðàñ-
ïîëàãàþòñÿ â òàêîì ïîðÿäêå, ïðè êîòîðîì èõ ïåðåñòàíîâêà óâåëè÷èâàåò
êðèòåðèé èëè îïðåäåëÿåò âîçìîæíîñòü ïðèìåíåíèÿ îïðåäåëåííîãî ïðàâè-
ëà äîìèíèðîâàíèÿ è çàâèñèò îò ìîìåíòà íà÷àëà îáðàáîòêè.
Ïóñòü WT R�( ) — âçâåøåííîå çàïàçäûâàíèå òåêóùåé ïîñëåäîâàòåëü-
íîñòè ðàáîò íà ðàíãå R èç ÷àñòíîé ïîñëåäîâàòåëüíîñòè ðàáîò �, à C max ( )� —
ìàêñèìàëüíîå âðåìÿ çàâåðøåíèÿ ðàáîò â ÷àñòíîé ïîñëåäîâàòåëüíîñòè �.
Äëÿ ïðèâåäåííûõ äàëåå îïðåäåëåíèé èñïîëüçóåì ðåçóëüòàòû ðàáîò
[25—27].
Îïðåäåëåíèå 5. Åñëè C Cmax max( ) ( )� �1 2� — ìàêñèìàëüíûå çíà÷åíèÿ
âðåìåíè çàâåðøåíèÿ ðàáîò â ÷àñòíûõ ïîñëåäîâàòåëüíîñòÿõ �� è � 2,
WT WT( ) ( )� �1 2� , à ��,� 2 — ÷àñòíûå ïîñëåäîâàòåëüíîñòè ðàáîò èç ïîñëå-
Ìåòîä ìèíèìèçàöèè ñóììàðíîãî çàïàçäûâàíèÿ ðàáîò íà îäèíî÷íîì óñòðîéñòâå
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 2 63
(3, 7)
à
â
J3 (3, 7)
J4 (3, 4)
J
2
(5, 6)
J
1
(4, 7)
á
J3 (3, 7)
J4 (3, 4)
J
2
(5, 6)
J
1
(4, 7)
J3
J4 (3, 4)
J
2
(5, 6)
J
1
(4, 7)
Ðèñ. 2. Âûáîð âåðøèíû íà ðàíãå 2 (à), íà
ðàíãå 3 (á), íà ðàíãå 4 (â) (ïîëóæèðíûìè
ñòðåëêàìè óêàçàíû âåðøèíû è ðåáðà,
âêëþ÷åííûå â ãàìèëüòîíîâ ïóòü íà êàæ-
äîì ðàíãå)
äîâàòåëüíîñòè � � j j jn1 2, ,..., , òî ìîæíî â ëþáîì äîïóñòèìîì ðàñïèñàíèè
èñïîëüçîâàòü ïîñëåäîâàòåëüíîñòü ��âìåñòî ïîñëåäîâàòåëüíîñòè � 2 ñ îöåí-
êîé «ïîñëåäîâàòåëüíîñòü �� íå õóæå ïîñëåäîâàòåëüíîñòè � 2 ïî âðåìåíè
çàâåðøåíèÿ âñåõ ðàáîò».
Îïðåäåëåíèå 6. ÅñëèC Cmax max( ) ( )� �1 2
èWT WT( ) ( )� �1 2
, à��,� 2 —
÷àñòíûå ïîñëåäîâàòåëüíîñòè ðàáîò èç ïîñëåäîâàòåëüíîñòè � � j j jn1 2, ,..., ,
òî ìîæíî â ëþáîì äîïóñòèìîì ðàñïèñàíèè èñïîëüçîâàòü ïîñëåäîâàòåëü-
íîñòü�� âìåñòî ïîñëåäîâàòåëüíîñòè� 2 ñ îöåíêîé «ïîñëåäîâàòåëüíîñòü��
ëó÷øå ïîñëåäîâàòåëüíîñòè � 2 ïî âðåìåíè çàâåðøåíèÿ âñåõ ðàáîò».
Äëÿ îöåíêè ïîëó÷àåìûõ ëîêàëüíî-îïòèìàëüíûõ ðåøåíèé ñôîðìóëè-
ðóåì ñëåäóþùèå ïðåäïîëîæåíèÿ.
Ïðåäïîëîæåíèå 1. Äëÿ ðàáîò Ji è Jk , çàïëàíèðîâàííûõ íà ïðîèçâîëü-
íîì ðàíãå R, ðàñïèñàíèå, â êîòîðîì Ji ïðåäøåñòâóåò Jk, ÿâëÿåòñÿ ëîêàëüíî-
îïòèìàëüíûì, åñëè âûïîëíÿåòñÿ íåðàâåíñòâî T Tik ki� � 0 (T Tik ki� ).
Ïðåäïîëîæåíèå 2. Äëÿ ðàáîò Ji è Jk , çàïëàíèðîâàííûõ íà ïðîèçâîëü-
íîì ðàíãå R, ðàñïèñàíèå, â êîòîðîì Ji ïðåäøåñòâóåò Jk , ÿâëÿåòñÿ ëîêàëüíî-
îïòèìàëüíûì, åñëè âûïîëíÿåòñÿ íåðàâåíñòâî WT WTik ki� � 0 (WT WTik ki� ).
Ïðåäïîëîæåíèå 3. Ðàñïèñàíèå ÷àñòíîé ïîñëåäîâàòåëüíîñòè ðàáîò
� � j j jn1 2, ,..., íà ïðîèçâîëüíîì ðàíãå R ÿâëÿåòñÿ (k, R)-îïòèìàëüíûì, åñëè
îíî âêëþ÷àåò k (R k
1) ëîêàëüíî-îïòèìàëüíûõ ðàñïèñàíèé.
Ïðåäïîëîæåíèå 4. Ðàñïèñàíèå ÷àñòíîé ïîñëåäîâàòåëüíîñòè ðàáîò
� � j j jn1 2, , ..., TT ( )� ÿâëÿåòñÿ (k, n)-îïòèìàëüíûì, åñëè îíî âêëþ÷àåò
k n k( )
1 ëîêàëüíî-îïòèìàëüíûõ ðàñïèñàíèé.
Ïðåäïîëîæåíèå 5. Ðàñïèñàíèå ÷àñòíîé ïîñëåäîâàòåëüíîñòè ðàáîò
� � j j jn1 2, ,..., TWT( )� ÿâëÿåòñÿ ( , )k nw -îïòèìàëüíûì, åñëè îíî âêëþ÷àåò
k w (n k w
1) ëîêàëüíî-îïòèìàëüíûõ ðàñïèñàíèé.
Ñ.Â. Ìèíóõèí, Ä.Ñ. Ëåíüêî
64 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 2
Ïðàâèëî Íàçâàíèå Îïèñàíèå
Ôîðìóëà îïðåäåëåíèÿ
ïðèîðèòåòà
Òèï
EDD Earliest Due
Date
Íàèáîëåå ðàííèé
äèðåêòèâíûé ñðîê
min{ }d j Ñòàòè÷åñêîå
MDD Modified Due
Date
Ìîäèôèöèðîâàííûé
äèðåêòèâíûé ñðîê
min{max( , )}p d tj j �
Äèíàìè÷åñêîå
SPT Shortest Pro-
cessing Time
Íàèìåíüøåå ïðîöåñ-
ñîðíîå âðåìÿ
min{ }p j Ñòàòè÷åñêîå
PD Processing Time
(Due Date)
Âðåìÿ âûïîëíåíèÿ
(äèðåêòèâíîãî ñðîêà)
min{ / }p dj j Ñòàòè÷åñêîå
Òàáëèöà 2. Ïðàâèëà äîìèíèðîâàíèÿ äëÿ çàäà÷è ñóììàðíîãî
íåâçâåøåííîãî çàïàçäûâàíèÿ
Ïðàâèëà äîìèíèðîâàíèÿ, èñïîëüçîâàííûå äëÿ íåâçâåøåííîãî çàïàç-
äûâàíèÿ, ïðèâåäåíû â òàáë. 2 [11, 28—30].
Èç òàáë. 1 ñëåäóåò, ÷òî íà ðàíãàõ èìåþòñÿ êîíêóðèðóþùèå ïóòè, èç
êîòîðûõ òðåáóåòñÿ âûáðàòü òîëüêî îäèí, ñëó÷àéíî èëè ñ ïîìîùüþ ïðà-
âèëà äîìèíèðîâàíèÿ, îáåñïå÷èâàþùåãî ëîêàëüíî-îïòèìàëüíîå ðåøåíèå,
èëè ñ ïîìîùüþ «ñòÿãèâàíèÿ» âñåõ ïóòåé ê ñëåäóþùåìó ðàíãó, ò.å. èñ-
ïîëüçîâàíèÿ âñåõ ïîñòðîåííûõ íà òåêóùåì ðàíãå ïóòåé áåç îòñåêàíèÿ íà
ñëåäóþùåì ðàíãå. Åñëè íà êàêîì-ëèáî ðàíãå âåëè÷èíû çàïàçäûâàíèÿ âñåõ
ðàáîò ðàâíû, èñïîëüçóåòñÿ ïðàâèëî äîìèíèðîâàíèÿ EDD.
Íàïðèìåð, íà ðàíãå 3 T (3)4,3,1 = 6 + (4 – 7) = 3 è T (3)3,4,1 = 6 + (4 – 7) = 3.
Âûáèðàåì T (3)4,3,1, òàê êàê d4 < d3. Ïðîöåäóðà ïðîäîëæàåòñÿ äî òåõ ïîð,
ïîêà íå äîñòèãíåò ðàíãà 4, íà êîòîðîì îïðåäåëÿåòñÿ âåëè÷èíà êðàò÷àéøåãî
ãàìèëüòîíîâà ïóòè â ãðàôå ñ ìèíèìàëüíûì çíà÷åíèåì ñóììàðíîãî çàïàç-
äûâàíèÿ. Îíà è áóäåò ñóììàðíûì çàïàçäûâàíèåì ÒÒ, ò.å. èñêîìûì ðåøå-
íèåì çàäà÷è. Òàêèì îáðàçîì, â äàííîì ñëó÷àå îïòèìàëüíûé ïóòü îïðåäå-
ëÿåòñÿ ïîñëåäîâàòåëüíîñòüþ ðàáîò J4, J3, J1, J2 ñ ñóììàðíûì çàïàçäûâàíèåì
TTj j j j4 3 2 1
12� . Ïîñëåäîâàòåëüíîñòü ïîñòðîåíèÿ ãàìèëüòîíîâà ïóòè â ãðàôå
(ñì. ðèñ. 1) íà êàæäîì ðàíãå ïîêàçàíà íà ðèñ. 2.
Ïðèìåðû ðàáîòû àëãîðèòìà ñ èñïîëüçîâàíèåì è áåç èñïîëüçîâàíèÿ
ïðàâèë äîìèíèðîâàíèÿ ïðèâåäåíû â òàáë. 3, à â ñëó÷àå ïîëíîãî ïåðåáîðà —
â òàáë. 4.
Àíàëèç ïîëó÷åííûõ ðåçóëüòàòîâ, ïðèâåäåííûõ â òàáë. 1 è 3, ñâèäå-
òåëüñòâóåò î òîì, ÷òî, èñïîëüçóÿ ïðàâèëà, ìîæíî óìåíüøèòü ñóììàðíîå
çàïàçäûâàíèå ðàáîò. Ïðè ýòîì èñïîëüçîâàíèå ðàçëè÷íûõ ïðàâèë ïðèâîäèò
ê ðàçëè÷íûì ðåçóëüòàòàì ðàáîòû áàçîâîãî àëãîðèòìà. Èñïîëüçîâàíèå ïðà-
âèëà äîìèíèðîâàíèÿ â íåêîòîðûõ ñëó÷àÿõ ïîçâîëÿåò ïîëó÷èòü òî÷íîå
ðåøåíèå (ñì. òàáë. 1, 3, 4).
Ïðè ýêñïåðèìåíòàëüíîì èññëåäîâàíèè àëãîðèòìà â ñëó÷àå âçâå-
øåííîãî çàïàçäûâàíèÿ èñïîëüçîâàíû ïðàâèëà, ïðèâåäåííûå â òàáë. 5
[9—11, 26, 27].
Ïðèìåðû ðàáîòû àëãîðèòìà â ñëó÷àå âçâåøåííîãî çàïàçäûâàíèÿ ñ
èñïîëüçîâàíèåì ïðàâèëà äîìèíèðîâàíèÿ WMDD è áåç åãî èñïîëüçîâàíèÿ
ïðèâåäåíû â òàáë. 6. Äëÿ ôîðìàëèçàöèè ðàáîòû àëãîðèòìà ñ èñïîëüçîâà-
íèåì ïðàâèëà äîìèíèðîâàíèÿ ðàññìîòðèì ïîñëåäîâàòåëüíîñòü åãî ðåàëè-
çàöèè ñ ó÷åòîì ââåäåííûõ ðàíåå ïðåäïîëîæåíèé.
Àëãîðèòì ìèíèìèçàöèè ñóììàðíîãî çàïàçäûâàíèÿ ñ èñïîëüçîâà-
íèåì ïðàâèëà äîìèíèðîâàíèÿ. Äëÿ èñïîëüçîâàíèÿ ïðàâèëà äîìèíèðîâà-
íèÿ îáîáùèì áàçîâûé àëãîðèòì (îïòèìèçàöèè ïî íàïðàâëåíèþ [21]) ñ ó÷å-
òîì ââåäåííûõ ðàíåå ïðåäïîëîæåíèé è îïðåäåëåíèé.
Ø à ã 1. Ôîðìèðóåì ïðîèçâîëüíóþ ïîñëåäîâàòåëüíîñòü ðàáîò èç èñ-
õîäíîãî ìíîæåñòâà. Ýòà ïîñëåäîâàòåëüíîñòü ñîñòàâëÿåò ðàíã 1.
Ìåòîä ìèíèìèçàöèè ñóììàðíîãî çàïàçäûâàíèÿ ðàáîò íà îäèíî÷íîì óñòðîéñòâå
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 2 65
Ñ.Â. Ìèíóõèí, Ä.Ñ. Ëåíüêî
66 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 2
Âåð-
øèíà
Ðàíã 1 Ðàíã 2 Ðàíã 3 Ðàíã 4
Ñ èñïîëüçîâàíèåì ïðàâèëà MDD
J1 4 7( , ) T ( )1 1 � T ( ) ( ),2 5 4 7 22 1 � � � � T ( ) ( ), ,3 8 4 7 54 2 1 � � � � TT4 3 2 1 0 0 5 8 13, , , � � � � �
� � � � �( )0 4 7 3 T ( ) ( ),2 3 4 7 03 1 � � � � T ( ) ( ), ,3 6 4 7 34 3 1 � � � �
T ( ) ( ),2 3 4 7 04 1 � � � � T ( ) ( ), ,3 6 4 7 33 4 1 � � � �
J 2 5 6( , ) T ( )1 2 � T ( ) ( ),2 4 5 6 31 2 � � � � T ( ) ( ), ,3 7 5 6 64 1 2 � � � � TT4 3 1 2 0 0 3 9 12, , , � � � � �
� � � � �( )0 5 6 1 T ( ) ( ),2 3 5 6 23 2 � � � � T ( ) ( ), ,3 6 5 6 54 3 2 � � � � TT4 1 3 2 0 0 3 9 12, , , � � � � �
T ( ) ( ),2 3 5 6 24 2 � � � � T ( ) ( ), ,3 6 5 6 53 4 2 � � � �
J 3 3 7( , ) T ( )1 3 � T ( ) ( ),2 4 3 7 01 3 � � � � T ( ) ( ), ,3 7 3 7 34 1 3 � � � �
� � � � �( )0 3 7 4 T ( ) ( ),2 5 3 7 12 3 � � � � T ( ) ( ), ,3 8 3 7 44 2 3 � � � �
T ( ) ( ),2 3 3 7 14 3 � � � � �
J 4 3 4( , ) T ( )1 4 � T ( ) ( ),2 4 3 4 31 4 � � � �
� � � � �( )0 3 4 1 T ( ) ( ),2 5 3 4 42 4 � � � �
T ( ) ( ),2 3 3 4 23 4 � � � �
Áåç ïðàâèëà äîìèíèðîâàíèÿ
J1 4 7( , ) T ( )1 1 � T ( ) ( ),2 5 4 7 22 1 � � � � T ( ) ( ), ,3 8 4 7 53 2 1 � � � � TT4 3 2 1 0 0 5 8 13, , , � � � � �
� � � � �( )0 4 7 3 T ( ) ( ),2 3 4 7 03 1 � � � � T ( ) ( ), ,3 6 4 7 34 3 1 � � � �
T ( ) ( ),2 3 4 7 04 1 � � � � T ( ) ( ), ,3 6 4 7 33 4 1 � � � �
J 2 5 6( , ) T ( )1 2 � T ( ) ( ),2 4 5 6 31 2 � � � � T ( ) ( ), ,3 7 5 6 63 1 2 � � � � TT3 4 1 2 0 0 3 9 14, , , � � � � �
� � � � �( )0 5 6 1 T ( ) ( ),2 3 5 6 23 2 � � � � T ( ) ( ), ,3 6 5 6 54 3 2 � � � � TT3 1 4 2 0 0 6 9 15, , , � � � � �
T ( ) ( ),2 3 5 6 24 2 � � � � T ( ) ( ), ,3 6 5 6 53 4 2 � � � �
J 3 3 7( , ) T ( )1 3 � T ( ) ( ),2 4 3 7 01 3 � � � �
� � � � �( )0 3 7 4 T ( ) ( ),2 5 3 7 12 3 � � � �
T ( ) ( ),2 3 3 7 14 3 � � � � �
J 4 3 4( , ) T ( )1 4 � T ( ) ( ),2 4 3 4 31 4 � � � � T ( ) ( ), ,3 7 3 4 63 1 4 � � � �
� � � � �( )0 3 4 1 T ( ) ( ),2 5 3 4 42 4 � � � � T ( ) ( ), ,3 8 3 4 73 2 4 � � � �
T ( ) ( ),2 3 3 4 23 4 � � � �
Òàáëèöà 3. Ïðèìåðû ðàáîòû àëãîðèòìà
Ø à ã 2. Ñòðîèì âñå ïóòè ðàíãà 2. Íà òåêóùåì ðàíãå äëÿ êàæäîé ðàáîòû
âûáèðàåì ïóòè ñ ìèíèìàëüíîé âåëè÷èíîé òåêóùåãî çàïàçäûâàíèÿ. Åñëè
èõ íåñêîëüêî, òî âûáèðàåì òîò ïóòü, êîòîðûé ÿâëÿåòñÿ äîìèíèðóþùèì
(ñòðîãî äîìèíèðóþùèì), ò.å. âêëþ÷àåò îïòèìàëüíóþ ïîñëåäîâàòåëüíîñòü
ðàáîò íà äàííîì ðàíãå.
Ø à ã 3. Ñòðîèì âñå ïóòè ðàíãà 3 è ïîñëåäóþùèõ ðàíãîâ äî òåõ ïîð,
ïîêà íå äîñòèãíåì ðàíãà n. Ðàññ÷èòûâàåì ñóììàðíîå âðåìÿ çàïàçäûâàíèÿ
ðàáîò äëÿ ÷àñòíîé ïîñëåäîâàòåëüíîñòè � � j j jn1 2, ,..., è ñóììàðíîå ÷èñëî
Ìåòîä ìèíèìèçàöèè ñóììàðíîãî çàïàçäûâàíèÿ ðàáîò íà îäèíî÷íîì óñòðîéñòâå
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 2 67
Âåðøèíà Ðàíã 1 Ðàíã 2 Ðàíã 3 Ðàíã 4 TT
J1 4 7( , ) T ( ) ( )1 0 4 7 31 � � � � � T ( ) ,2 31 2 � T ( ) , ,3 51 2 3 � T ( ) , , ,4 111 2 3 4 � TT1 2 3 4 19, , , �
T ( ) , ,3 81 2 4 � T ( ) , , ,4 81 2 4 3 � TT1 2 4 3 19, , , �
T ( ) ,2 01 3 � T ( ) , ,3 61 3 2 � T ( ) , , ,4 111 3 2 4 � TT1 3 2 4 17, , , �
T ( ) , ,3 61 3 4 � T ( ) , , ,4 91 3 4 2 � TT1 3 4 2 15, , , �
T ( ) ,2 31 4 � T ( ) , ,3 61 4 2 � T ( ) , , ,4 81 4 2 3 � TT1 4 2 3 17, , , �
T ( ) , ,3 31 4 3 � T ( ) , , ,4 91 4 3 2 � TT1 4 3 2 15, , , �
J2 5 6( , ) T ( ) ( )1 0 5 6 12 � � � � � T ( ) ,2 22 1 � T ( ) , ,3 52 1 3 � T ( ) , , ,4 112 1 3 4 � TT2 1 3 4 18, , , �
T ( ) , ,3 82 1 4 � T ( ) , , ,4 82 1 4 3 � TT2 1 4 3 18, , , �
T ( ) ,2 12 3 � T ( ) , ,3 52 3 1 � T ( ) , , ,4 112 3 1 4 � TT2 3 1 4 17, , , �
T ( ) , ,3 72 3 4 � T ( ) , , ,4 82 3 4 1 � TT2 3 4 1 16, , , �
T ( ) ,2 42 4 � T ( ) , ,3 52 4 1 � T ( ) , , ,4 82 4 1 3 � TT2 4 1 3 17, , , �
T ( ) , ,3 42 4 3 � T ( ) , , ,4 82 4 3 1 � TT2 4 3 1 16, , , �
J3 3 7( , ) T ( ) ( )1 0 3 7 43 � � � � � T ( ) ,2 03 1 � T ( ) , ,3 63 1 2 � T ( ) , , ,4 113 1 2 4 � TT3 1 2 4 17, , , �
T ( ) , ,3 63 1 4 � T ( ) , , ,4 93 1 4 2 � TT3 1 4 2 15, , , �
T ( ) ,2 23 2 � T ( ) , ,3 53 2 1 � T ( ) , , ,4 113 2 1 4 � TT3 2 1 4 18, , , �
T ( ) , ,3 73 2 4 � T ( ) , , ,4 83 2 4 1 � TT3 2 4 1 17, , , �
T ( ) ,2 23 4 � T ( ) , ,3 33 4 1 � T ( ) , , ,4 93 4 1 2 � TT3 4 1 2 14, , , �
T ( ) , ,3 53 4 2 � T ( ) , , ,4 83 4 2 1 � TT3 4 2 1 15, , , �
J4 3 4( , ) T ( ) ( )1 0 3 4 14 � � � � � T ( ) ,2 04 1 � T ( ) , ,3 64 1 2 � T ( ) , , ,4 84 1 2 3 � TT4 1 2 3 14, , , �
T ( ) , ,3 34 1 3 � T ( ) , , ,4 94 1 3 2 � TT4 1 3 2 12, , , �
T ( ) ,2 24 2 � T ( ) , ,3 54 2 1 � T ( ) , , ,4 84 2 1 3 � TT4 2 1 3 15, , , �
T ( ) , ,3 43 1 2 � T ( ) , , ,4 84 2 3 1 � TT4 2 3 1 14, , , �
T ( ) ,2 14 3 � � T ( ) , ,3 34 3 1 � T ( ) , , ,4 94 3 1 2 � TT4 3 1 2 12, , , �
T ( ) , ,3 53 2 1 � T ( ) , , ,4 84 3 2 1 � TT4 3 2 1 13, , , �
Òàáëèöà 4. Ïðèìåð ðàáîòû àëãîðèòìà â ñëó÷àå ïîëíîãî ïåðåáîðà
ëîêàëüíî-îïòèìàëüíûõ ðàñïèñàíèé, ò.å. ðàáîò, ïîñòðîåííûõ àëãîðèòìîì
íà êàæäîì ðàíãå ïî îïðåäåëåííîìó ïðàâèëó äîìèíèðîâàíèÿ. Ïîëó÷åííàÿ
ïîñëåäîâàòåëüíîñòü ðàáîò�� ÿâëÿåòñÿ ñòðîãî îïòèìàëüíîé è äîìèíèðóþùåé,
åñëè äëÿ ëþáûõ ÷àñòíûõ ïîñëåäîâàòåëüíîñòåé �� è � 2 íà ðàçëè÷íûõ ðàíãàõ
Ñ.Â. Ìèíóõèí, Ä.Ñ. Ëåíüêî
68 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 2
Ïðàâèëî Íàçâàíèå Îïèñàíèå ïðàâèëà Ôîðìóëà îïðåäåëåíèÿ ïðèîðèòåòà
WEDD Weighted Earli-
est Due Date
Âçâåøåííûé íàè-
áîëåå ðàííèé äè-
ðåêòèâíûé ñðîê
max
w
d
j
j
�
�
�
�
�
�
WMDD Weighted Mod-
ified Due Date
Âçâåøåííûé ìîäè-
ôèöèðîâàííûé äè-
ðåêòèâíûé ñðîê
min
max ( , )p d t
w
j j
j
��
�
�
�
�
�
WSPT Weighted Shor-
test Processing
Time
Âçâåøåííîå íàè-
ìåíüøåå ïðîöåññîð-
íîå âðåìÿ
min
p
w
j
j
�
�
�
�
�
�
èëè max
w
p
j
j
�
�
�
�
�
�
WPD Weighted Pro-
cessing Time
Due Date
Îòíîøåíèå âçâå-
øåííîãî âðåìåíè
âûïîëíåíèÿ ê äè-
ðåêòèâíîìó ñðîêó
max
w
p d
j
j j
�
�
�
�
�
�
WMS Weighted Mini-
mum Slack
Âçâåøåííûé ìèíè-
ìàëüíûé ðåçåðâ min
max ( , )d p t
w
i i
j
� ��
�
�
�
�
�
0
CPRT
WT
Combined Prio-
rity Rule for
Total Weighted
Tardiness
Êîìáèíèðîâàííîå
ïðèîðèòåòíîå ïðà-
âèëî äëÿ ñóììàðíî-
ãî çàïàçäûâàíèÿ
max ( )
{ }
{ }
,
J A
J A
j l
j
l
c t
�
�
�
�
�
�
�
�
�
ATC Apparent Tardi-
ness Cost
Î÷åâèäíàÿ ñòîè-
ìîñòü çàïàçäûâàíèÿ
max
exp
max( , )
,
{ }J A
j
j
j
j j
j
w
p
d t p
k p
�
�
�
�
�
�
� � ��
�
�
�
�
�
�
�
�
�
0
k p A p
J A
l
j
� �
�
�2 1, /| |
{ }
X-RM X-dispatch
ATC
Ìîäèôèöèðîâàííîå
ATC
max
max( , )
~
{ }J A
j
j
j
B r t
p�
�
��
�
�
�
�
�
�
�
�
�
�
�
� 1
0
,
B �{ . , }16 2 , ~ /| |p A p
J A
l
l
�
�
�1
èëè ~ min
{ }
p p
J A
l
l
�
�
COVERT Weighted Cost
Over Time
Âçâåøåííàÿ còîè-
ìîñòü çàïàçäûâàíèÿ
çà îïðåäåëåííîå
âðåìÿ
max max ,
max( , )
{ }J A
j
j
j j
jj
w
p
d t p
k p�
�
� ��
�
�
�
�
�
�
�
�
�
�
�0 1
0
�
Òàáëèöà 5. Ïðàâèëà äîìèíèðîâàíèÿ ïðè ñóììàðíîì âçâåøåííîì çàïàçäûâàíèè
Ìåòîä ìèíèìèçàöèè ñóììàðíîãî çàïàçäûâàíèÿ ðàáîò íà îäèíî÷íîì óñòðîéñòâå
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 2 69
Â
åð
-
ø
è
í
à
Ð
àí
ã
1
Ð
àí
ã
2
Ð
àí
ã
3
Ð
àí
ã
4
Ñ
è
ñï
î
ëü
çî
âà
í
è
åì
ï
ð
à
âè
ëà
W
M
D
D
J
1
4
7
2
(
,
,
)
W
T
(
)1
1
�
((
)
)*
0
4
7
2
6
�
�
�
�
W
T
(
)
((
)
)*
,
2
5
4
7
2
4
2
1
�
�
�
�
W
T
(
)
((
)
)*
,
,
3
8
4
7
2
1
0
3
2
1
�
�
�
�
T
W
T
4
3
2
1
0
0
5
4
8
2
3
6
,
,
,
�
�
�
!
�
!
�
W
T
(
)
((
)
)
*
,
2
3
4
7
2
0
3
1
�
�
�
�
W
T
(
)
((
)
)
*
,
,
3
6
4
7
2
6
4
3
1
�
�
�
�
W
T
(
)
((
)
)*
,
2
3
4
7
2
0
4
1
�
�
�
�
W
T
(
)
((
)
)*
,
,
3
6
4
7
2
6
3
4
1
�
�
�
�
J
2
5
6
4
(
,
,
)
W
T
(
)1
2
�
((
)
)*
0
5
6
4
4
�
�
�
�
W
T
(
)
((
)
)*
,
2
4
5
6
4
1
2
1
2
�
�
�
�
W
T
(
)
((
)
)*
,
,
3
7
5
6
4
2
4
3
1
2
�
�
�
�
T
W
T
4
3
1
2
0
0
3
2
9
4
4
2
,
,
,
�
�
�
!
�
!
�
W
T
(
)
((
)
)
*
,
2
3
5
6
2
8
3
2
�
�
�
�
W
T
(
)
((
)
)
*
,
,
3
6
5
6
4
2
0
4
3
2
�
�
�
�
T
W
T
3
1
4
2
0
0
3
5
9
4
5
1
,
,
,
�
�
�
!
�
!
�
W
T
(
)
((
)
)*
,
2
3
5
6
4
8
4
2
�
�
�
�
W
T
(
)
((
)
)*
,
,
3
6
5
6
4
2
0
3
4
2
�
�
�
�
J
3
3
7
5
(
,
,
)
W
T
(
)1
3
�
((
)
)*
0
3
7
5
2
0
�
�
�
�
W
T
(
)
((
)
)*
,
2
4
3
7
5
0
1
3
�
�
�
�
W
T
(
)
((
)
)*
,
2
5
3
7
5
5
2
3
�
�
�
�
W
T
(
)
((
)
)
*
,
2
3
3
7
5
5
4
3
�
�
�
�
�
J
4
3
4
3
(
,
,
)
W
T
(
)1
4
�
((
)
)*
0
3
4
3
3
�
�
�
�
W
T
(
)
((
)
)*
,
2
4
3
4
3
9
1
4
�
�
�
�
W
T
(
)
((
)
)
*
,
,
3
7
3
4
3
1
8
3
1
4
�
�
�
�
W
T
(
)
((
)
)*
,
2
5
3
4
3
1
2
2
4
�
�
�
�
W
T
(
)
((
)
)*
,
,
3
8
3
7
5
2
0
4
2
3
�
�
�
�
W
T
(
)
((
)
)*
,
2
3
3
4
3
6
3
4
�
�
�
�
Á
åç
ï
ð
à
âè
ëà
ä
î
ì
è
í
è
ð
î
âà
í
è
ÿ
J
1
4
7
2
(
,
,
)
W
T
(
)1
1
�
((
)
)*
0
4
7
2
6
�
�
�
�
W
T
(
)
((
)
)*
,
2
5
4
7
2
4
2
1
�
�
�
�
W
T
(
)
((
)
)*
,
,
3
8
4
7
2
1
0
4
2
1
�
�
�
�
T
W
T
4
3
2
1
0
6
2
0
8
2
4
2
,
,
,
�
�
�
�
!
�
W
T
(
)
((
)
)*
,
2
3
4
7
2
0
3
1
�
�
�
�
W
T
(
)
((
)
)*
,
,
3
6
4
7
2
6
4
3
1
�
�
�
�
W
T
(
)
((
)
)
*
,
2
3
4
7
2
0
4
1
�
�
�
�
W
T
(
)
((
)
)
*
,
,
3
6
4
7
2
6
3
4
1
�
�
�
�
J
2
5
6
4
(
,
,
)
W
T
(
)1
2
�
((
)
)*
0
5
6
4
4
�
�
�
�
W
T
(
)
((
)
)*
,
2
4
5
6
4
1
2
1
2
�
�
�
�
W
T
(
)
((
)
)*
,
,
3
7
5
6
4
2
4
4
1
2
�
�
�
�
W
T
(
)
((
)
)*
,
2
3
5
6
4
8
3
2
�
�
�
�
W
T
(
)
((
)
)*
,
,
3
6
5
6
4
2
0
4
3
2
�
�
�
�
T
W
T
3
4
1
2
0
6
6
9
4
4
8
,
,
,
�
�
�
�
!
�
W
T
(
)
((
)
)
*
,
2
3
5
6
4
8
4
2
�
�
�
�
W
T
(
)
((
)
)
*
,
,
3
6
5
6
4
2
0
3
4
2
�
�
�
�
T
W
T
4
1
3
2
0
0
1
5
9
4
5
1
,
,
,
�
�
�
�
!
�
Ò
à
á
ëè
ö
à
6
.
Ï
ð
è
ì
åð
û
ð
à
á
î
ò
û
à
ë
ã
î
ð
è
ò
ì
à
â
ñë
ó
÷
à
å
â
çâ
åø
åí
í
î
ã
î
çà
ï
à
çä
û
â
à
í
è
ÿ
âûïîëíÿþòñÿ óñëîâèÿ: TT TT( ) ( )� �1 2
è k1 > k2 — äëÿ íåâçâåøåííîãî çàïàçäû-
âàíèÿ;TWT TWT( ) ( )� �1 2
è k kw w
1 2" —
äëÿ âçâåøåííîãî çàïàçäûâàíèÿ.
Ðåçóëüòàòû ýêñïåðèìåíòàëüíîãî
èññëåäîâàíèÿ àëãîðèòìà ñ èñïîëü-
çîâàíèåì ïðàâèë äîìèíèðîâàíèÿ.
Äëÿ èññëåäîâàíèÿ áàçîâîãî àëãîðèòìà
[21] ñ èñïîëüçîâàíèåì ïðàâèë äîìè-
íèðîâàíèÿ ðàçðàáîòàí ïðîãðàììíûé
ïðîäóêò, ñ ïîìîùüþ êîòîðîãî ðàññ÷è-
òàíû ïîëó÷åííûå â ðåçóëüòàòå ýêñïå-
ðèìåíòîâ çàâèñèìîñòè âðåìåíè âûïîë-
íåíèÿ (ðàáîòû àëãîðèòìà) è ñóììàð-
íîãî çàïàçäûâàíèÿ àëãîðèòìà äëÿ íå-
âçâåøåííîãî è âçâåøåííîãî çàïàçäû-
âàíèÿ (ðèñ. 3—5) íà îñíîâå ìåòîäèêè,
ïðåäëîæåííîé â [23] è àëãîðèòìà ãå-
íåðàöèè òåñòîâèõ ïîñëåäîâàòåëüíîñ-
òåé, ïðèâåäåííîãî â áèáëèîòåêå OR-Li-
brary [31]. Ïðè ýòîì èñïîëüçîâàíû
ñëåäóþùèå íàñòðîéêè ïàðàìåòðîâ:
÷èñëî ýêçåìïëÿðîâ — 75; äèàïàçîí
äèðåêòèâíûõ ñðîêîâ RDD = (0,2; 0,4;
0,6; 0,8; 1,0); ôàêòîð çàïàçäûâàíèÿ
TF = (0,2; 0,4; 0,6; 0,8; 1,0); ÷èñëî ðà-
áîò — 160; äëèòåëüíîñòè ðàáîò ñãåíå-
ðèðîâàíû ïî ðàâíîìåðíîìó çàêîíó â
èíòåðâàëå [1, 10].
Ðåçóëüòàòû ðàñ÷åòîâ, ïðèâåäåííûå
íà ðèñ. 3, ïîäòâåðæäàþò ïîëó÷åííóþ â
[21] îöåíêó âðåìåííîé ñëîæíîñòè èñ-
ñëåäóåìîãî àëãîðèòìà. Ðåçóëüòàòû,
ïðåäñòàâëåííûå íà ðèñ. 4, ñâèäå-
òåëüñòâóþò î òîì, ÷òî ïðè èñïîëüçî-
âàíèè äîìèíèðóþùåãî ïðàâèëà ñóì-
ìàðíîå âðåìÿ çàïàçäûâàíèÿ óìåíü-
øàåòñÿ, è ïðè ýòîì ëó÷øèì ðàñïè-
ñàíèåì ÿâëÿåòñÿ òî, êîòîðîå ïîëó÷åíî ñ
èñïîëüçîâàíèåì ïðàâèëà EDD.
Ñ.Â. Ìèíóõèí, Ä.Ñ. Ëåíüêî
70 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 2
Â
åð
-
ø
è
í
à
Ð
àí
ã
1
Ð
àí
ã
2
Ð
àí
ã
3
Ð
àí
ã
4
J
3
3
7
5
(
,
,
)
W
T
(
)1
3
�
((
)
)*
0
3
7
5
2
0
�
�
�
�
W
T
(
)
((
)
)*
,
2
4
3
7
5
0
1
3
�
�
�
�
W
T
(
)
((
)
)
*
,
,
3
7
3
7
5
1
5
4
1
3
�
�
�
�
W
T
(
)
((
)
)*
,
2
5
3
7
5
5
2
3
�
�
�
�
W
T
(
)
((
)
)*
,
,
3
8
3
7
5
2
0
4
2
3
�
�
�
�
W
T
(
)
((
)
)
*
,
2
3
3
7
5
5
4
3
�
�
�
�
�
J
4
3
4
3
(
,
,
)
W
T
(
)1
4
�
((
)
)*
0
3
4
3
3
�
�
�
�
W
T
(
)
((
)
)*
,
2
4
3
4
3
9
1
4
�
�
�
�
W
T
(
)
((
)
)*
,
2
5
3
4
3
1
2
2
4
�
�
�
�
W
T
(
)
((
)
)
*
,
2
3
3
4
3
6
3
4
�
�
�
�
Ï
ð
î
ä
î
ëæ
åí
è
å
ò
à
á
ë.
6
Ìåòðèêè îöåíèâàíèÿ ðåçóëüòàòîâ ðàáîòû àëãîðèòìà ïðè èñïîëü-
çîâàíèè ïðàâèëà äîìèíèðîâàíèÿ. Äëÿ îöåíêè óëó÷øåíèÿ ðåçóëüòàòîâ
ðàáîòû áàçîâîãî àëãîðèòìà ïðè èñïîëüçîâàíèè ïðàâèëà äîìèíèðîâàíèÿ
ïðåäëàãàþòñÿ ñëåäóþùèå ìåòðèêè:
îòíîøåíèå ÷èñëà âåðøèí ïîñòðîåííîãî êðàò÷àéøåãî ãàìèëüòîíîâà
ïóòè, ïîëó÷åííîãî ñ èñïîëüçîâàíèåì ïðàâèëà äîìèíèðîâàíèÿ, ê îáùåìó
Ìåòîä ìèíèìèçàöèè ñóììàðíîãî çàïàçäûâàíèÿ ðàáîò íà îäèíî÷íîì óñòðîéñòâå
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 2 71
800
600
400
200
50 100 150 200 50 100 150 200
à á
1,0
0,8
0,6
0,4
0,2
Â
ð
åì
ÿ
â
û
ï
î
ë
í
åí
è
ÿ
,
Â
ð
åì
ÿ
â
û
ï
î
ë
í
åí
è
ÿ
,
50 100 150 200
×èñëî ðàáîò
50 100 150 200
â ã
0
0
0
3
6
ì
ñ
(1
0
)
ì
ñ
(1
0
)
Ðèñ. 3. Çàâèñèìîñòü âðåìåíè âûïîëíåíèÿ îò ÷èñëà ðàáîò äëÿ áàçîâîãî àëãîðèòìà ñ èñ-
ïîëüçîâàíèåì ìåòîäà îïòèìèçàöèè: à — EDD; á — MDD; â — WEDD; ã — WMDD; à, á —
íåâçâåøåííîå çàïàçäûâàíèå; â, ã — âçâåøåííîå çàïàçäûâàíèå; # — âðåìÿ âûïîëíåíèÿ;
— àïïðîêñèìèðóþùèé ïîëèíîì Ò (n)
T n n n( ) , ,� � �0 174 2 8363 2
� �762 511 13628 97, ,n
T n n n( ) , ,� � �0 222 10 1613 2
� �62 778 945 52, ,n
T n n n( ) , ,� � �0 066 34 7683 2
� �270 639 41683 84, ,n
T n n n( ) , ,� � �0 238 7 0193 2
� �145 013 1695 93, ,n
30
25
20
15
10
5
Ñ
ó
ì
ì
àð
í
î
å
â
ð
åì
ÿ
çà
ï
àç
ä
û
â
àí
è
ÿ
,
ó.
å.
(1
0
)
20 40 60 80 100 120 140 160
×èñëî ðàáîò
0
3
Ðèñ. 4. Çàâèñèìîñòü ñóììàðíîãî âðåìåíè çàïàçäûâàíèÿ îò ÷èñëà ðàáîò ïðè èñïîëü-
çîâàíèè áàçîâîãî àëãîðèòìà ñ ðàçëè÷íûìè ïðàâèëàìè äîìèíèðîâàíèÿ: # — îïòèìèçàöèÿ
ïî íàïðàâëåíèþ; �— EDD; MDD; �— SPT
÷èñëó âåðøèí â ãðàôå — ïëîòíîñòü v n
dr
GP
� , ãäå vdr — ìíîæåñòâî âåðøèí
ãðàôà, ïîëó÷åííûõ íà îñíîâå îïðåäåëåííîãî ïðàâèëà äîìèíèðîâàíèÿ;
îòíîñèòåëüíîå óìåíüøåíèå ñóììàðíîãî çàïàçäûâàíèÿ ( ) /TT TT TTdr� ,
ãäå TTdr è TT — ñóììàðíîå çàïàçäûâàíèå ñ èñïîëüçîâàíèåì ïðàâèëà äîìè-
íèðîâàíèÿ è áåç åãî èñïîëüçîâàíèÿ.
Äëÿ ýêñïåðèìåíòàëüíîãî èññëåäîâàíèÿ ðàáîòû áàçîâîãî àëãîðèòìà ñ
èñïîëüçîâàíèåì ïðàâèë äîìèíèðîâàíèÿ ïðîâåäåíû âû÷èñëèòåëüíûå ýêñ-
ïåðèìåíòû ñ èñõîäíûìè äàííûìè î êîëè÷åñòâå ïðàêòè÷åñêè ïðèìåíÿå-
ìûõ ðàáîò. Äëÿ ýòîãî ñãåíåðèðîâàíû ïàêåòû èç 75 çàäàíèé ïî 20 —160
ðàáîò â êàæäîì è ðàññ÷èòàíû îòíîñèòåëüíîå óìåíüøåíèå ñóììàðíîãî âðåìå-
íè çàïàçäûâàíèÿ è ÷èñëî ïîëó÷àåìûõ ëîêàëüíî-îïòèìàëüíûõ ðåøåíèé
(ñì. ðèñ. 5).
Ñ.Â. Ìèíóõèí, Ä.Ñ. Ëåíüêî
72 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 2
52
50
48
$%
×
è
ñë
î
ë
î
ê
àë
ü
í
û
õ
ì
è
í
è
ì
ó
ì
î
â
,
%
20 60 100 140
×èñëî ðàáîò
à á
40
20
0
20
40
�
�
Î
òí
î
ñè
òå
ë
ü
í
î
å
ó
ì
åí
ü
ø
åí
è
å,
%
20 60 100 140
Ðèñ. 5. Çàâèñèìîñòü îòíîñèòåëüíîãî óìåíüøåíèÿ ñóììàðíîãî âðåìåíè çàïàçäûâàíèÿ (à) è
÷èñëà ëîêàëüíî-îïòèìàëüíûõ ðåøåíèé (á) îò ÷èñëà ðàáîò ïðè èñïîëüçîâàíèè ðàçëè÷íûõ
ìåòîäîâ îïòèìèçàöèè: �— EDD; — MDD; �— SPT
1,2
0,8
0,4
0
50 100 150
×èñëî ðàáîò
0 50 100 150
à á
Â
ð
åì
ÿ
â
û
ï
î
ë
í
åí
è
ÿ
,
ì
ñ
(1
0
)
6
Ðèñ. 6. Çàâèñèìîñòü âðåìåíè âûïîëíåíèÿ îò ÷èñëà ðàáîò äëÿ àëãîðèòìà îïòèìèçàöèè ïî
íàïðàâëåíèþ áåç èñïîëüçîâàíèÿ ïðàâèë äîìèíèðîâàíèÿ (à) è ñ èñïîëüçîâàíèåì ïðàâèë
EDD (á) ïðè ìÿãêèõ äèðåêòèâíûõ ñðîêàõ: # — âðåìÿ âûïîëíåíèÿ; Ò (n)
T n n n( ) , ,� � �0 150 37 2583 2
� �3444 982 60080 22, ,n
T n n n( ) , ,� � �0 183 36 7693 2
� �3165 193 5020111, ,n
Êàê ñëåäóåò èç ðèñ. 5, à, îòíîñèòåëüíîå óìåíüøåíèå ñóììàðíîãî çà-
ïàçäûâàíèÿ ïðè èñïîëüçîâàíèè ïðàâèë äîñòèãàåò 30 %, è ëó÷øèå ðàñ-
ïèñàíèÿ ïîëó÷àþòñÿ ïðè èñïîëüçîâàíèè ïðàâèë EDD è MDD. Ðåçóëüòàòû,
ïðèâåäåííûå íà ðèñ. 5, á, ñâèäåòåëüñòâóþò î òîì, ÷òî ÷èñëî ëîêàëüíî-
îïòèìàëüíûõ ðåøåíèé, ïîëó÷àåìûõ ñ èñïîëüçîâàíèåì ïðàâèë, äîñòèãàåò
50 %, è ëó÷øèì ïðè ýòîì ÿâëÿåòñÿ ðàñïèñàíèå, ïîëó÷àåìîå ñ èñïîëüçîâà-
íèåì ïðàâèëà EDD.
Ìåòîä ìèíèìèçàöèè ñóììàðíîãî çàïàçäûâàíèÿ ðàáîò íà îäèíî÷íîì óñòðîéñòâå
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 2 73
Ðèñ. 8. Çàâèñèìîñòü âðåìåíè âûïîëíåíèÿ îò ÷èñëà ðàáîò ïðè èñïîëüçîâàíèè àëãîðèòìà
îïòèìèçàöèè ïî íàïðàâëåíèþ áåç èñïîëüçîâàíèÿ ïðàâèë äîìèíèðîâàíèÿ (à) è ñ èñïîëü-
çîâàíèåì ïðàâèë COVERT (á) äëÿ ìÿãêèõ äèðåêòèâíûõ ñðîêîâ: # — âðåìÿ âûïîëíåíèÿ;
— Ò (n)
Ðèñ. 7. Çàâèñèìîñòü ñóììàðíîãî âðåìåíè
çàïàçäûâàíèÿ îò ÷èñëà ðàáîò ïðè ðàçëè÷-
íûõ äèðåêòèâíûõ ñðîêàõ: à — ìÿãêèõ; á —
ñðåäíèõ; â — æåñòêèõ; # — îïòèìèçàöèÿ ïî
íàïðàâëåíèþ; MDD; � — EDD; � —
SPT
T n n n( ) , ,� � �0 245 17 7933 2
� �2373 635 43593 94, ,n
T n n n( ) , ,� � �0 321 0 0093 2
� �1183 638 25223 89, ,n
Èññëåäîâàíèå âëèÿíèÿ äèðåêòèâíûõ ñðîêîâ ðàáîò íà âðåìÿ âûïîë-
íåíèÿ àëãîðèòìà ñ èñïîëüçîâàíèåì ïðàâèëà äîìèíèðîâàíèÿ. Ïðè ðå-
øåíèè òåîðåòè÷åñêèõ è ïðàêòè÷åñêèõ çàäà÷, ñâÿçàííûõ ñ ïëàíèðîâàíèåì
ðàáîò â ðàñïðåäåëåííûõ âû÷èñëèòåëüíûõ ñèñòåìàõ, âàæíûì ÿâëÿåòñÿ îïðå-
äåëåíèå íàèáîëåå òî÷íîãî âðåìåíè èõ âûïîëíåíèÿ. Åñëè â èñïîëüçóåìûõ
ìîäåëÿõ ðàáîò ó÷èòûâàåòñÿ äèðåêòèâíûé ñðîê, òî íåîáõîäèìî ó÷èòûâàòü è
åãî âåëè÷èíû, òàê êàê äëÿ ðàáîòû ïëàíèðîâùèêîâ òðåáóåòñÿ èíôîðìàöèÿ î
Ñ.Â. Ìèíóõèí, Ä.Ñ. Ëåíüêî
74 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 2
Äèàïàçîí
äëèòåëüíîñ-
òè ðàáîò, ó.å.
TF RDD
Ñóììàðíîå âðåìÿ
çàïàçäûâàíèÿ, ó.å.
Îòíîñèòåëüíîå
óëó÷øåíèå, %
Áåç ïðàâèëà EDD MDD SPT EDD MDD SPT
1—10 0,2 1,0 7199,733 0 0 7107,827 1,28
0,6 0,6 20336,48 10810,27 10578,36 20108,91 46,84 47,98 1,12
1,0 0,2 51923,33 51143,64 51111,84 52157,99 1,50 1,56 –0,45
10—100 0,2 1,0 71390,69 0 0 75364,17 –5,57
0,6 0,6 225281,8 123691,9 121989,5 228997,5 45,09 45,85 –1,65
1,0 0,2 576678,3 572597,8 572070,1 581796,4 0,71 0,80 –0,89
100—1000 0,2 1,0 727745,4 0 0 766290 –5,30
0,6 0,6 2318171 1272431 1238497 2294737 45,11 46,57 1,01
1,0 0,2 5748017 5709203 5701751 5801825 0,68 0,80 –0,94
Òàáëèöà 7. Îòíîñèòåëüíîå óìåíüøåíèå ñóììàðíîãî çàïàçäûâàíèÿ
äëÿ ðàçëè÷íûõ äëèòåëüíîñòåé ðàáîò è äèðåêòèâíûõ ñðîêîâ ïðè èñïîëüçîâàíèè
ïðàâèë äîìèíèðîâàíèÿ
Äèàïàçîí
äëèòåëüíîñòè
ðàáîò, ó.å.
TF RDD
Ñóììàðíîå âðåìÿ çàïàçäûâàíèÿ, ó.å.
Áåç ïðàâèëà WEDD WMDD WSPT WPD COVERT
1—10 0,2 1,0 33709,05 5126,867 0 20239,2 5286,64 4508,347
0,6 0,6 109812,9 48933,89 41866,95 81906,45 55057,16 59868,28
1,0 0,2 341932,8 326996,4 326294 332829,3 327690,1 328879,4
10—100 0,2 1,0 378100,6 56600,53 0 194523,3 58576,03 41506,89
0,6 0,6 1226679 560760,4 479471,2 924313,1 636130,9 716528,1
1,0 0,2 3776079 3616856 3620074 3691123 3638510 3638459
100—1000 0,2 1,0 3849057 545015,9 0 1954127 615005 403736,6
0,6 0,6 12310788 5640129 4877216 9440556 6388686 7019181
1,0 0,2 37838717 36395216 36348787 37038532 36619082 36594292
Òàáëèöà 8. Îòíîñèòåëüíîå óìåíüøåíèå ñóììàðíîãî âçâåøåííîãî çàïàçäûâàíèÿ ïðè
âðåìåíè âûïîëíåíèÿ è ñðîêàõ çàâåðøåíèÿ ðàáîò [32]. Ýòè âåëè÷èíû îöåíè-
âàþòñÿ ñ ïîìîùüþ ïðåäïîëàãàåìîãî (îæèäàåìîãî) âðåìåíè, ò.å. ïðåäâàðè-
òåëüíî ðàññ÷èòûâàþòñÿ ïîëüçîâàòåëÿìè íà îñíîâàíèè õðîíîëîãè÷åñêèõ äàí-
íûõ îá óæå âûïîëíåííûõ ðàáîòàõ.
 ðàáîòàõ [33—35] äëÿ îïðåäåëåíèÿ òèïîâ äèðåêòèâíûõ ñðîêîâ èñ-
ïîëüçóþòñÿ òèïû, îïðåäåëÿåìûå êàê æåñòêèé, ñðåäíèé è ñëàáûé. Â äàííîì
èññëåäîâàíèè æåñòêîñòü äèðåêòèâíîãî ñðîêà îïðåäåëèì êàê åãî îòíî-
øåíèå ê äëèòåëüíîñòè ðàáîòû: ÷åì ýòà âåëè÷èíà ìåíüøå, òåì áîëåå æåñò-
êèì ÿâëÿåòñÿ äèðåêòèâíûé ñðîê. Ó÷èòûâàÿ, ÷òî â ãåíåðàòîðå òåñòîâûõ
ïîñëåäîâàòåëüíîñòåé OR-Library [31] äèàïàçîí çàäàíèÿ äèðåêòèâíûõ ñðî-
êîâ ðåãóëèðóåòñÿ ïàðàìåòðîì RDD, äëÿ èññëåäîâàíèÿ âëèÿíèÿ æåñòêîñòè
äèðåêòèâíîãî ñðîêà íà ðàáîòó àëãîðèòìà ñ ïðàâèëîì äîìèíèðîâàíèÿ èñ-
ïîëüçóåì ñëåäóþùåå îïðåäåëåíèå.
Îïðåäåëåíèå 7. Äèðåêòèâíûå ñðîêè òåì æåñò÷å, ÷åì áîëüøåå çíà-
÷åíèå èìååò ïàðàìåòð TF è ÷åì ìåíüøåå — ïàðàìåòð RDD.
Çàäàíèÿìè ñ æåñòêèìè äèðåêòèâíûìè ñðîêàìè áóäåì ñ÷èòàòü òàêèå,
äëÿ êîòîðûõ TF = 1,0, RDD = 0,2, ñî ñðåäíèìè, — äëÿ êîòîðûõ TF = 0,6,
RDD = 0,6 è ñ ìÿãêèìè, — äëÿ êîòîðûõ TF = 0,2, RDD = 1,0.
Äëÿ îöåíèâàíèÿ âëèÿíèÿ ðàññìîòðåííûõ òèïîâ äèðåêòèâíûõ ñðîêîâ
íà ðàáîòó àëãîðèòìà â ñëó÷àå íåâçâåøåííîãî çàïàçäûâàíèÿ ïðîâåäåíû
ðàñ÷åòû ñóììàðíîãî çàïàçäûâàíèÿ äëÿ äëèòåëüíîñòåé ðàáîò, ðàñïðåäåëåí-
íûõ ïî ðàâíîìåðíîìó çàêîíó â èíòåðâàëå [1, 10]. Ðåçóëüòàòû ýòèõ ðàñ÷å-
òîâ ïîêàçàëè, ÷òî âðåìÿ ðàáîòû àëãîðèòìà ñîîòâåòñòâóåò ïîëó÷åííîé â
ðàáîòå [21] îöåíêå âðåìåííîé ñëîæíîñòè (ðèñ. 6).
Ìåòîä ìèíèìèçàöèè ñóììàðíîãî çàïàçäûâàíèÿ ðàáîò íà îäèíî÷íîì óñòðîéñòâå
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 2 75
Îòíîñèòåëüíîå óìåíüøåíèå âðåìåíè çàïàçäûâàíèÿ, %
ATC WMS WEDD WMDD WSPT WPD COVERT ATC WMS
0 0 84,79 39,96 84,32 86,63 100,00
43137,45 58378,11 55,44 61,87 25,41 49,86 45,48 60,72 46,84
325869,3 338015,1 4,37 4,57 2,66 4,17 3,82 4,70 1,15
0 0 85,03 48,55 84,51 89,02 100,00
498042,4 683777,9 54,29 60,91 24,65 48,14 41,59 59,40 44,26
3607753 3752082 4,22 4,13 2,25 3,64 3,64 4,46 0,64
0 0 85,84 49,23 84,02 89,51 100,00
5020131 6765935 54,19 60,38 23,31 48,10 42,98 59,22 45,04
36291279 37698080 3,81 3,94 2,11 3,22 3,29 4,09 0,37
èñïîëüçîâàíèè ðàçëè÷íûõ ïðàâèë äîìèíèðîâàíèÿ
Ãðàôèêè çàâèñèìîñòè âðåìåíè ñóììàðíîãî çàïàçäûâàíèÿ îò ÷èñëà
ðàáîò ïðè èõ äëèòåëüíîñòÿõ, ðàâíîìåðíî ðàñïðåäåëåííûõ â èíòåðâàëå [1,
10], ïðè ðàçëè÷íîé æåñòêîñòè äèðåêòèâíûõ ñðîêîâ ïðèâåäåíû íà ðèñ. 7. Èç
ïðåäñòàâëåííûõ ãðàôèêîâ âèäíî, ÷òî ñ óâåëè÷åíèåì æåñòêîñòè äèðåêòèâ-
íûõ ñðîêîâ ñóììàðíîå çàïàçäûâàíèå ðàáîò óâåëè÷èâàåòñÿ. Ïðè ýòîì íàèáî-
ëåå çíà÷èòåëüíîå óìåíüøåíèå ñóììàðíîãî çàïàçäûâàíèÿ îáåñïå÷èâàåòñÿ àë-
ãîðèòìîì, â êîòîðîì èñïîëüçóþòñÿ ïðàâèëà äîìèíèðîâàíèÿ EDD è MDD äëÿ
ìÿãêèõ è ñðåäíèõ äèðåêòèâíûõ ñðîêîâ (òàáë. 7).
Ðåçóëüòàòû ðàñ÷åòîâ ñóììàðíîãî âçâåøåííîãî çàïàçäûâàíèÿ â äèàïàçî-
íå äëèòåëüíîñòåé ðàáîò, ðàñïðåäåëåííûõ ïî ðàâíîìåðíîìó çàêîíó â èíòåð-
âàëå [1, 10], äëÿ ðàçíûõ òèïîâ äèðåêòèâíûõ ñðîêîâ ïîêàçàëè, ÷òî âðåìÿ
ðàáîòû àëãîðèòìà òàêæå ñîîòâåòñòâóåò ïîëó÷åííîé â ðàáîòå [21] îöåíêå
âðåìåííîé ñëîæíîñòè. Íà ðèñ. 8 ïðèâåäåíû ãðàôèêè çàâèñèìîñòè âðåìåíè
ðàáîòû àëãîðèòìà ñ èñïîëüçîâàíèåì ïðàâèëà äîìèíèðîâàíèÿ è áåç íåãî äëÿ
ìÿãêèõ äèðåêòèâíûõ ñðîêîâ îò ÷èñëà ðàáîò.
Ðåçóëüòàòû ïðîâåäåííûõ ýêñïåðèìåíòîâ è îòíîñèòåëüíîå óìåíüøå-
íèå ñóììàðíîãî âçâåøåííîãî çàïàçäûâàíèÿ ïðè ðàçëè÷íûõ äëèòåëüíîñòÿõ
ðàáîò è âåñîâ, ðàâíîìåðíî ðàñïðåäåëåííûõ â èíòåðâàëå [1, 10], äëÿ áàçî-
âîãî àëãîðèòìà ñ èñïîëüçîâàíèåì ðàçëè÷íûõ ïðàâèë äîìèíèðîâàíèÿ ïðè-
âåäåíû â òàáë. 8.
Òàêèì îáðàçîì, êàê ñëåäóåò èç òàáë. 8, â ñëó÷àå âçâåøåííîãî çàïàç-
äûâíèÿ ëó÷øèå ðàñïèñàíèÿ âûïîëíåíèÿ ðàáîò ïîëó÷åíû ïðè èñïîëüçî-
âàíèè ïðàâèë äîìèíèðîâàíèÿ WMDD, ATC è WMS, êîòîðûå ïîçâîëÿþò
óìåíüøèòü ñóììàðíîå çàïàçäûâàíèå äëÿ ìÿãêèõ è ñðåäíèõ äèðåêòèâíûõ
ñðîêîâ.
Âûâîäû
Ïðèìåíåíèå ïðàâèë äîìèíèðîâàíèÿ ïîçâîëÿåò íà êàæäîì øàãå ðàáîòû àëãî-
ðèòìà âûáèðàòü ëó÷øóþ èç òåêóùèõ ïîñëåäîâàòåëüíîñòåé ðàáîò.
Âêëþ÷åíèå ïðàâèë äîìèíèðîâàíèÿ â áàçîâûé àëãîðèòì íåçíà÷èòåëü-
íî óâåëè÷èâàåò âðåìÿ åãî ðàáîòû.
Èñïîëüçîâàíèå ïðàâèëà äîìèíèðîâàíèÿ äëÿ ðàññìîòðåííîãî àëãîðèò-
ìà ìèíèìèçàöèè ñóììàðíîãî âðåìåíè çàïàçäûâàíèÿ ïîçâîëÿåò ïîëó÷èòü
ëîêàëüíî-îïòèìàëüíûå ðåøåíèÿ è óìåíüøèòü âðåìÿ çàïàçäûâàíèÿ äëÿ
ðàáîò ñî ñðåäíèìè è ìÿãêèìè äèðåêòèâíûìè ñðîêàìè.
Ñîâðåìåííûå ñèñòåìû ïëàíèðîâàíèÿ âûïîëíåíèÿ çàäàíèé èìåþò âîç-
ìîæíîñòü ñîðòèðîâêè çàäàíèé ñ ðàçëè÷íûìè ïðèîðèòåòàìè. Ýòî òàêèå
ïëàíèðîâùèêè ïðîìåæóòî÷íîãî ñëîÿ Ãðèä-ñèñòåì, êàê ARC NorduGrid, è
ëîêàëüíûå ïëàíèðîâùèêè, íàïðèìåð MAUI, â êîòîðûõ âîçìîæíî èñïîëü-
çîâàíèå ïðåäëîæåííîãî àëãîðèòìà, èìåþùåãî ìàëóþ âðåìåííóþ ñëîæ-
Ñ.Â. Ìèíóõèí, Ä.Ñ. Ëåíüêî
76 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 2
íîñòü, äëÿ óëó÷øåíèÿ ëîêàëüíûõ ðàñïèñàíèé âûïîëíåíèÿ çàäàíèé ñ ïðî-
èçâîëüíûìè äèðåêòèâíûìè ñðîêàìè â óñëîâèÿõ âðåìåííûõ èëè áþäæåò-
íûõ îãðàíè÷åíèé.
The paper deals with the algorithms of minimizing the total lag of works on a single device on the
basis of determining the shortest Hamilton path in the arbitrary graph using the rank approach and
the dominance rules. The performance metrics of applying the dominance rules based on the eval-
uation of locally optimal solutions, obtained on different ranks and the values of relative reduc-
tion of total lag in relation to the basic algorithm are proposed. The results of computational ex-
periments for the weighted and unweighted cases for the works with different duration and the
types of due dates defined in the research are given. The conditions, under which, the proposed
algorithms allow improving the schedule of works are defined and the most effective dominance
rules are determined.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ye Nong, Gel Esma S., Li Xueping, Farley Toni, Lai Ying-Cheng Web Server QoS Models:
Applying Scheduling Rules from Production Planning // Computers & Operations Research. —
2005. — ¹ 32. — Ð. 1147—1164.
2. Zafril Rizal M Azmi, Kamalrulnizam Abu Bakar, Abdul Hanan Abdullah, Mohd Shahir
Shamsir, Wan Nurulsafawati Wan Manan Performance Comparison of Priority Rule Sched-
uling Algorithms Using Different Inter Arrival Time Jobs in Grid Environment // Intern. J. of
Grid and Distributed Computing. — 2011. — Vol. 4, No. 3. — Ð. 61—70.
3. Singh H., Dr. Kumar S. Dispatcher Based Dynamic Load Balancing on Web Server System //
Ibid. — 2011. — Vol. 4, No. 3. — P. 89—105
4. Zafril Rizal M Azmi, Kamalrulnizam Abu Bakar , Mohd Shahir Shamsir, Wan Nurulsafawati
Wan Manan, Abdul Hanan Abdullah Scheduling Grid Jobs Using Priority Rule Algorithms
and Gap Filling Techniques // Intern. J. of Advanced Science and Technology. — 2011. —
Vol. 37. — P. 61—76.
5. Klusacek D., Rudova H. Comparison of Multi-criteria Scheduling Techniques. S. Gorlatch,
P. Fragopoulou and T. Priol, Editors. —Springer US, 2008. — P. 173—184.
6. Klusacek D., Rudova H. Improving QoS in Computational Grids through Schedule-based
Approach // In Scheduling and Planning Applications Workshop at the Eighteenth Interna-
tional Conference on Automated Planning and Scheduling (ICAPS 2008). Sydney, Austra-
lia. — 2008. [Ýëåêòðîííûé ðåñóðñ]. — Ðåæèì äîñòóïà: decsai.ugr.es>~lcv/SPARK/08/
Papers/paper04.pdf.
7. Ëèñòðîâîé Ñ.Â., Ìèíóõèí Ñ.Â. Ìîäåëü è ïîäõîä ê ïëàíèðîâàíèþ ðàñïðåäåëåíèÿ
ðåñóðñîâ â ãåòåðîãåííûõ ÃÐÈÄ-ñèñòåìàõ // Ïðîáëåìû óïðàâëåíèÿ è èíôîðìàòèêè.
Ìåæäóíàðîäíûé íàó÷íî-òåõíè÷åñêèé æóðíàë. — 2012. — ¹ 5. — Ñ. 120—133.
8. Ëèñòðîâîé Ñ.Â., Ìèíóõèí Ñ.Â. Ìåòîä ðåøåíèÿ çàäà÷ î ìèíèìàëüíîì âåðøèííîì
ïîêðûòèè â ïðîèçâîëüíîì ãðàôå è çàäà÷è î íàèìåíüøåì ïîêðûòèè // Ýëåêòðîí. ìî-
äåëèðîâàíèå. — 2012. — 34, ¹1. — Ñ. 29—43.
9. Koulamas C. The Total Tardiness Problem: Review and Extensions // Operations Research. —
1994. — Vol. 42. — P. 1025—1041.
10. Koulamas C. The Single-machine Total Tardiness Scheduling Problem: Review and Exten-
sions // European J. of Operational Research. — 2010. — Vol. 202, No. 1. — P. 1—7.
11. Sena T., Suleka J.M., Dileepan Parthasarati Static Scheduling Research to Minimize
Weighted and Unweighted Tardiness: A State-of-the-art Survey //Intern. J. Production Eco-
nomics. — 2003. — Vol. 83, No. 1. — P. 1—12.
Ìåòîä ìèíèìèçàöèè ñóììàðíîãî çàïàçäûâàíèÿ ðàáîò íà îäèíî÷íîì óñòðîéñòâå
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 2 77
12. Du J., Leung J.Y.-T. Minimizing Total Tardiness on One Machine is NP-hard //Mathematics
of Operations Research. — 1990. — ¹ 15. — P. 483—495.
13. Lawler E.L. A «Pseudo Polynomial» Algorithm for Sequencing Jobs to Minimize Total Tar-
diness // Annals of Discrete Mathematics. — 1977. — No1. — P. 331—342.
14. Baker K.R., Shrage L.E. Finding an Optimal Sequence by Dynamic Programming an
Extension to Precedence-related Tasks // Operations Research Letters. — 1978. — No 26. —
P. 111 — 120.
15. Lawler E.L. A Fully Polynomial Approximation Scheme for the Total Tardiness Problem //
Ibid. — 1982. — No 1. — P. 207—208.
16. Potts C.N., Van Wassenhove L.N. Dynamic Programming and Decomposition Approaches
for the Single Machine Total Tardiness Problem // European J. of Operational. — 1987. —
No 32. — P. 405—414.
17. Kovalyov M.Y. Improving the Complexities of Approximation Algorithms for Optimization
problems // Operations Research Letters.— 1995.—Vol. 17, March.—P. 85—87.
18. Koulamas C. A Faster Fully Polynomial Approximation Scheme for the Single Machine
Total Tardiness Problem // European J. of Operational Research.— 2009.— No 193.—P. 637—
638.
19. Ïàâëîâ À.À., Ìèñþðà Å.Á. Íîâûé ïîäõîä ê ðåøåíèþ çàäà÷è «Ìèíèìèçàöèÿ ñóììàð-
íîãî âçâåøåííîãî îïîçäàíèÿ ïðè âûïîëíåíèè íåçàâèñèìûõ çàäàíèé ñ äèðåêòèâíûìè
ñðîêàìè îäíèì ïðèáîðîì» // Ñèñòåìíûå èññëåäîâàíèÿ è èíôîðìàöèîííûå òåõíîëî-
ãèè. — 2002. — ¹ 2. — Ñ. 7—32.
20. Ïàâëîâ Î.À., Ìèñþðà Å.Á., Øåâ÷åíêî Ê.Þ. Ïîáóäîâà ÏÄÑ-àëãîðèòìó ðîçâ’ÿçàííÿ
çàäà÷³ ì³í³ì³çàö³¿ ñóìàðíîãî çâàæåíîãî çàï³çíåííÿ âèêîíàííÿ ðîá³ò íà îäíîìó ïðèëàä³ //
³ñí. ÍÒÓÓ «Êϲ». ²íôîðìàòèêà, óïðàâë³ííÿ òà îá÷èñëþâàëüíà òåõí³êà: Çá. íàóê.
ïð. — Êè¿â: Âåê+, 2012. — ¹ 56. — Ñ. 58—70.
21. ̳íóõ³í Ñ.Â. Ìåòîä ì³í³ì³çàö³¿ ÷àñó âèêîíàííÿ çàâäàíü ç äèðåêòèâíèìè ñòðîêàìè íà
íåêëàñòåðèçîâàíîìó ðåñóðñ³ îá÷èñëþâàëüíî¿ ñèñòåìè // ²íôîðìàö³éíî-êåðóþ÷³ ñèñòå-
ìè íà çàë³çíè÷íîìó òðàíñïîðò³. — 2009. — ¹ 3. — Ñ. 47 — 53.
22. Minukhin S. Efficient Method for Single Machine Total Tardiness Problem // IV Intern.
Conf. «Problems of Cybernetics and Informatics» (PCI’2012), September 12—14, 2012.
[Ýëåêòðîííûé ðåñóðñ].— Påæèì äîñòóïà: www.pci2012.science.az/1/23.pdf.
23. ̳íóõ³í Ñ.Â., ˺íüêî Ä.Ñ. Äîñë³äæåííÿ ìåòîä³â ì³í³ì³çàö³¿ ñóìàðíîãî ÷àñó çàï³çíþ-
âàííÿ ðîá³ò ç äèðåêòèâíèìè ñòðîêàìè íà îäèíî÷íîìó îá÷èñëþâàëüíîìó ðåñóðñ³ // Ïðîá-
ëåìè ³ ïåðñïåêòèâè ðîçâèòêó ²Ò-³íäóñòð³¿. Ñèñòåìè îáðîáêè ³íôîðìàö³¿. — 2013. —
Âèï. ¹ 3 (110). Ò. 2. — Ñ. 30—35.
24. Øåâ÷åíêî Ê.Þ. Àëãîðèòì ã³ëîê òà ìåæ äëÿ ñòàòèñòè÷íèõ äîñë³äæåíü íîâîãî ÏÄÑ-
àëãîðèòìó ðîçâ’ÿçàííÿ çàäà÷³ ì³í³ì³çàö³¿ ñóìàðíîãî çâàæåíîãî çàï³çíåííÿ âèêîíàííÿ
ðîá³ò íà îäíîìó ïðèëàä³ // ³ñí. ÍÒÓÓ «Êϲ». ²íôîðìàòèêà, óïðàâë³ííÿ òà îá÷èñëþ-
âàëüíà òåõí³êà: Çá. íàóê. ïð. — Êè¿â: Âåê+, — 2012. — ¹ 55. — Ñ. 56—69.
25. Chu Ñ. Efficient Heuristics to Minimize Total Flow Time with Release Dates // Operations
Research Letters. — 1992. — ¹12. — P. 321—330.
26. Jouglet A., Savourey D.D., Carlier J., Baptiste P. Dominance-Based Heuristics for One-Ma-
chine Total Cost Problems // European J. of Operational Research. — 2008. — 184 (3). —
P. 879— 899.
27. Jouglet A., Savourey D. Dominance Rules for the Parallel Machine Total Weighted Tardi-
ness Scheduling Problem with Release Dates//Computers & Operations research. — 2011. —
Vol. 38, Issue 9. — P. 1259—1266.
28. Jackson J. R. Scheduling a Production Line to Minimize Maximum Tardiness. Minimizing
Total Tardiness for One Machine Research, Report 43, Management Science Research Pro-
ject, UCLA, 1955. [Ýëåêòðîííûé ðåñóðñ]. — Ðåæèì äîñòóïà: http://citeseerx.ist.psu.edu/
showciting?cid=38200.
Ñ.Â. Ìèíóõèí, Ä.Ñ. Ëåíüêî
78 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 2
29. Lai Tsung-Chyan, Kuo Yuh-Kwo Minimizing Total Tardiness for Single Machine Sequencing //
J. of the Operations Research Society of Japan.— 1996. — Vol. 39, ¹ 3. — Ð. 316—321.
30. Scheduling Single Machine Scheduling [Ýëåêòðîííûé ðåñóðñ].` — Ðåæèì äîñòóïà:
www.or.uni-bonn.de/lectures/sched10_2.pdf.
31. OR-Library [Ýëåêòðîííûé ðåñóðñ]. — Ðåæèì äîñòóïà: http://people.brunel.ac.uk/~
mastjjb/jeb/orlib/wtinfo.html.
32. Zotkin D., Keleher P.J. Job-Length Estimation and Performance in Backlling Schedulers //
In Proc. 8th High Performance Distributed Computing Conf. IEEE, 1999. [Ýëåêòðîííûé
ðåñóðñ]. — Ðåæèì äîñòóïà: http://www.umiacs.umd.edu/~dz/pbpslist/hpdc1999.pdf.
33. Mohamadreza Kaviani, Majid Aminnayeri, Seyed Nima Rafienejad, Fariborz Jolai. An Ap-
propriate Pattern to Solving a Parallel Machine Scheduling by a Combination of Meta-heu-
ristic and Data Mining // J. of American Science. — 2012. — ¹ 8 (1). — P. 160—167.
34. Chandra P., Li S., Stan M. Jobs and Tool Sequencing in an Automated Manufacturing Envi-
ronment // Intern. J. of Production Research. — 1993. — Vol. 31, Issue 1. — P. 2911—
2925.
35. Sekhar C.V. S., Devi M.P. Improvement of Performance in a Maintenance Job Shop // Proc.
of the 11th WSEAS Intern. Conf. on Applied Mathematics. Dallas, Texas, USA, March
22—24, 2007. — P. 29—34.
Ïîñòóïèëà 19.11.13;
ïîñëå äîðàáîòêè 17.12.13
ÌÈÍÓÕÈÍ Ñåðãåé Âëàäèìèðîâè÷, êàíä. òåõí. íàóê, ïðîôåññîð êàôåäðû èíôîðìàöèîííûõ
ñèñòåì Õàðüêîâñêîãî íàöèîíàëüíîãî ýêîíîìè÷åñêîãî óíèâåðñèòåòà.  1976 ã. îêîí÷èë Õàðü-
êîâñêèé èí-ò ðàäèîýëåêòðîíèêè. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — îïòèìèçàöèÿ ôóíêöèî-
íèðîâàíèÿ ðàñïðåäåëåííûõ âû÷èñëèòåëüíûõ ñèñòåì, ðàñïðåäåëåííûå âû÷èñëåíèÿ, îáëà÷íûå
âû÷èñëåíèÿ.
ËÅÍÜÊÎ Äìèòðèé Ñåðãååâè÷.  2013 ã. îêîí÷èë Õàðüêîâñêèé íàöèîíàëüíûé ýêîíîìè÷åñêèé
óíèâåðñèòåò. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — ìåòîäû è àëãîðèòìû ïîñòðîåíèÿ ðàñïè-
ñàíèé.
Ìåòîä ìèíèìèçàöèè ñóììàðíîãî çàïàçäûâàíèÿ ðàáîò íà îäèíî÷íîì óñòðîéñòâå
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 2 79
|
| id | nasplib_isofts_kiev_ua-123456789-100993 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0204-3572 |
| language | Russian |
| last_indexed | 2025-12-07T18:06:08Z |
| publishDate | 2014 |
| publisher | Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| record_format | dspace |
| spelling | Минухин, С.В. Ленько, Д.С. 2016-05-28T18:10:08Z 2016-05-28T18:10:08Z 2014 Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования / С.В. Минухин, Д.С. Ленько // Электронное моделирование. — 2014 — Т. 36, № 2. — С. 57-79. — Бібліогр.: 35 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/100993 621.398 Рассмотрен метод минимизации суммарного запаздывания работ на одиночном устройстве на основе определения кратчайшего гамильтонового пути в произвольном полносвязном графе с использованием рангового подхода и правил доминирования. Предложены метрики оценивания улучшения результатов работы алгоритма при использовании правил доминирования—относительного уменьшения суммарного запаздывания и числа получаемых локально-оптимальных решений. Приведены результаты вычислительных экспериментов для взвешенного и невзвешенного случаев запаздывания работ с произвольными директивными сроками. Найдены условия, при которых используемый алгоритм позволяет улучшить расписания работ и определить наиболее эффективные правила доминирования. Розглянуто метод мінімізації сумарного запізнювання робіт на одиночному пристрої на основі визначення найкоротшого гамільтонового шляху в довільному повнозв’язному графі з використанням рангового підходу і правил домінування. Запропоновано метрики оцінювання поліпшення результатів роботи алгоритму при використанні правил домінування — відносного зменшення сумарного запізнювання і кількості одержуваних локально-оптимальних рішень. Наведено результати обчислювальних експериментів для зваженого і незваженого запізнювання робіт з довільними директивними термінами. Визначено умови, при яких досліджуваний алгоритм дозволяє покращити розклад робіт, і знайдено найбільш ефективні правила домінування. The paper deals with the algorithms of minimizing the total lag of works on a single device on the basis of determining the shortest Hamilton path in the arbitrary graph using the rank approach and the dominance rules. The performance metrics of applying the dominance rules based on the evaluation of locally optimal solutions, obtained on different ranks and the values of relative reduction of total lag in relation to the basic algorithm are proposed. The results of computational experiments for the weighted and unweighted cases for the works with different duration and the types of due dates defined in the research are given. The conditions, under which, the proposed algorithms allow improving the schedule of works are defined and the most effective dominance rules are determined. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Вычислительные процессы и системы Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования Article published earlier |
| spellingShingle | Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования Минухин, С.В. Ленько, Д.С. Вычислительные процессы и системы |
| title | Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования |
| title_full | Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования |
| title_fullStr | Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования |
| title_full_unstemmed | Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования |
| title_short | Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования |
| title_sort | метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования |
| topic | Вычислительные процессы и системы |
| topic_facet | Вычислительные процессы и системы |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/100993 |
| work_keys_str_mv | AT minuhinsv metodminimizaciisummarnogozapazdyvaniârabotnaodinočnomustroistvenaosnoverangovogopodhodaipravildominirovaniâ AT lenʹkods metodminimizaciisummarnogozapazdyvaniârabotnaodinočnomustroistvenaosnoverangovogopodhodaipravildominirovaniâ |