Мінімізація сумарного зваженого моменту випередження виконання завдань на одному приладі
We consider the problem of building a feasible schedule for the execution of tasks with various due dates on a single machine. The optimality criteria are double fold: the first is the latest time of the machine start, the second is minimization of the total weighted earliness of tasks in a feasible...
Saved in:
| Date: | 2023 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України
2023
|
| Subjects: | |
| Online Access: | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/305 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Physico-mathematical modeling and informational technologies |
| Download file: |  |
Institution
Physico-mathematical modeling and informational technologies| _version_ | 1867479677060251648 |
|---|---|
| author | Pavlov, Alexander Khalus, Elena Medvediev, Mykhailo |
| author_facet | Pavlov, Alexander Khalus, Elena Medvediev, Mykhailo |
| author_institution_txt_mv | [
{
"author": "Alexander Pavlov",
"institution": "д. т. н., професор, Національний технічний університет України «КПІ ім. Ігоря Сікорського», пр. Перемоги, 37, 03056, Київ"
},
{
"author": "Elena Khalus",
"institution": "старший викладач, Національний технічний університет України «КПІ ім. Ігоря Сікорського», пр. Перемоги, 37, 03056, Київ"
},
{
"author": "Mykhailo Medvediev",
"institution": "студент, Національний технічний університет України «КПІ ім. Ігоря Сікорського», пр. Перемоги, 37, 03056, Київ"
}
] |
| author_sort | Pavlov, Alexander |
| baseUrl_str | http://www.fmmit.lviv.ua/index.php/fmmit/oai |
| collection | OJS |
| datestamp_date | 2025-02-21T17:31:10Z |
| description | We consider the problem of building a feasible schedule for the execution of tasks with various due dates on a single machine. The optimality criteria are double fold: the first is the latest time of the machine start, the second is minimization of the total weighted earliness of tasks in a feasible schedule where the criteria are given in a lexicographic order. That is, the starting time of the machine is as late as possible, and when this condition is fulfilled, the minimum possible value of the total weighted earliness of tasks is reached on a feasible schedule. The authors showed that this problem is qualitatively harder than the above formulated problem with equal positive weights. This paper proposes an exact method based on building of feasible solution trees. Fundamentally new are the formulated restrictions on the set of vertices of each level and the theoretically substantiated efficient rules for cutting branches. The rules are implemented in a statistically significant way already at the first levels of the feasible solution tree. The practical value of the proposed method is illustrated by the possibility of its application in a multi-level model of innovative project management at the last level of its hierarchy. |
| first_indexed | 2026-06-09T01:10:04Z |
| format | Article |
| fulltext |
57
doi.org/10.15407/fmmit2023.37.057
Мінімізація сумарного зваженого моменту випередження
виконання завдань на одному приладі
Олександр Павлов1, Олена Халус2, Михайло Медведєв3
1 д. т. н., професор, Національний технічний університет України «КПІ ім. Ігоря Сікорського», пр. Перемоги,
37, 03056, Київ, e-mail: pavlov.fiot@gmail.com
2 старший викладач, Національний технічний університет України «КПІ ім. Ігоря Сікорського», пр. Перемоги,
37, 03056, Київ, e-mail: selena.ua@gmail.com
3 студент, Національний технічний університет України «КПІ ім. Ігоря Сікорського», пр. Перемоги, 37, 03056,
Київ, e-mail: misha.medvedev2001@gmail.com
Розглядається задача побудови допустимого розкладу виконання завдань з різними дирек-
тивними строками на одному приладі, оптимального за критеріями: перший – максималь-
но пізній момент запуску приладу, другий – мінімізація сумарного зваженого моменту ви-
передження виконання завдань допустимого розкладу. Критерії задані в лексикографічно-
му порядку, тобто момент запуску приладу максимально пізній, і при виконанні цієї умови
на допустимому розкладі досягається мінімально можливе значення сумарного зваженого
моменту випередження виконання завдань. Автори показали, що ця задача є якісно більш
складною, ніж сформульована вище задача з рівними додатними вагами. В цій роботі про-
понується точний метод, що ґрунтується на побудові дерев допустимих розв’язків. Прин-
ципово новими є сформульовані обмеження на множину вершин кожного рівня та теоре-
тично обґрунтовані ефективні правила відсікання гілок, що статистично значимо почи-
нають реалізовуватися на перших рівнях дерева допустимих розв’язків. Практичне значен-
ня запропонованого методу ілюструється можливістю його застосування в багаторівне-
вій моделі управління інноваційними проектами на останньому рівні її ієрархії.
Ключові слова: календарне планування; оптимізація; допустимий
розклад; багаторівнева модель управління
Вступ. Апарат математичного моделювання систем управління об’єктами з
дискретними технологічними процесами включає в себе одноетапні задачі кален-
дарного планування, як (а) максимально агреговані моделі об’єкта управління;
(б) складові частини багаторівневих математичних моделей [1–9]. В цій роботі
розглядається узагальнення наступної одноетапної задачі: при максимально мож-
ливому моменті запуску приладу знайти допустимий розв’язок (кожне завдання
не порушує свій директивний строк), якому відповідає мінімальне значення
величини сумарного випередження виконання завдань. Ефективний розв’язок
цієї задачі наведено в [8]. Узагальнення полягає в використанні довільних
додатних експертних ваг в критерії: мінімізації сумарного зваженого
випередження виконання завдань в допустимому розкладі. Показано, що таке
узагальнення не дозволяє використати основну ідею, покладену в основі ефек-
УДК 519.854
mailto:pavlov.fiot@gmail.com
mailto:selena.ua@gmail.com
mailto:misha.medvedev2001@gmail.com
Олександр Павлов, Олена Халус, Михайло Медведєв
Мінімізація сумарного зваженого моменту випередження виконання завдань …
58
тивного алгоритму розв’язання для випадку рівних ваг [8]. Якісна характерис-
тика запропонованого методу наведена в анотації. Структура математичної мо-
делі [9] багаторівневої системи управління інноваційними проектами гарантує
ефективне використання точного методу на останньому рівні ієрархії цієї моделі.
1. Формальна постановка та аналіз властивостей задачі
Є n завдань njj ,1, . Для кожного завдання задані 0jl
– час виконання,
0jd – директивний строк виконання, nj ,1 . Завдання виконуються без пере-
ривань на одному приладі. Треба знайти допустимий розклад (кожне завдання не
порушує свій директивний строк), який задовольняє двом критеріям оптималь-
ності, що реалізуються в наступному порядку: прилад починає роботу в макси-
мально пізній момент часу
maxr , і при виконанні цієї умови на допустимому розк-
ладі досягається
jj
n
j
j Cd
1
min , (1)
де jC – момент завершення виконання j-го завдання, 0 j
– довільні експертні
ваги.
Для 1 j теоретично та експериментально обґрунтована ідея [8] побудо-
ви оптимального (субоптимального) розкладу, яка полягає в тому, що завдання,
починаючі з кінця розкладу, розташовуються (при умові непорушення їх директи-
вних строків) за незростанням величин часу їх виконання njl j ,1, . При довіль-
них значеннях ваг njj ,1,0 , це припущення є невірним. Дійсно, нехай
1212 , CCll ; (2)
1122 lClC . (3)
З нерівності (2) випливає, що
1221 lClC (4)
і, незалежно від того, виконується нерівність (3) чи ні в допустимому розкладі,
коли перше і друге завдання можуть стояти поруч в будь-якому порядку, перше
завдання повинно стояти перед другим. Нехай
1212 , CCll . (5)
В цьому випадку порядок першого і другого завдання залежить від знаку
нерівності
21 lC 12 lC . (6)
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 37, 57-61
59
2. Точний метод розв’язання одноетапної задачі календарного планування
за двома критеріями, заданими в лексикографічному порядку
2.1. Знаходження
maxr
– максимально пізнього моменту запуску приладу.
Ефективний точний поліноміальний алгоритм знаходження
maxr
наведено в [8].
2.2. Точний метод знаходження допустимого розкладу з мінімальним сумар-
ним випередженням виконання завдань при
maxr
– максимально пізньому
моменту запуску приладу. Нехай nni kij
n
,1, – це множина завдань, кожна з
яких може бути останньою в допустимому розкладі, тобто
nn
n
j
jj kidlr
ni
,1,
1
max
,
де
ni
jd – директивний строк виконання завдання
ni
j .
Кожне завдання
ni
j є коренем
nk дерев допустимих розкладів. Множина
гілок кожного дерева допустимих розкладів для достатньо великої кількості за-
вдань може бути ефективно побудована в силу того, що:
а) кількість гілок кожного дерева суттєво менше кількості всіх перестав-
лень індексів 1,,1 n , тому що для довільної гілки
11
,,,,, iiii jjjj
mnn
кожне
завдання, що стоїть на m-тому місці, повинно задовольняти умові
mipni
j
mn
p
j
n
j
j dllr
1
01
max ; (7)
б) існує два ефективних правила відсікання гілок. Перше правило: гілка
1,,,,
1
mjjj
mmn iii , (8)
є кінцевою на дереві допустимих розкладів, якщо завдання
mm ii jj ,
1
можуть стоя-
ти поруч в будь-якому порядку, і їх розташування в (8) не задовольняє необхід-
ним умовам оптимальності (умови (2)–(6)).
Друге правило відсікання гілок: нехай 1,1, mtjt
– це множина за-
вдань, що задається виразом
mntjnjj
ti
,,,1, \ . (9)
Якщо для множини завдань (9) та моменту запуску приладу maxr
розклад, в якому
завдання, починаючи з першої позиції, розташовані в порядку, що відповідає не
зменшенню величин їх директивних строків, є недопустимим, то на множині
завдань (9) та maxr
допустимого розкладу не існує, і гілка (8) є кінцевою.
Якісний аналіз та вже проведені експерименти показують, що коли момент
запуску приладу є maxr , обмеження на кількість робіт на n–m+1-тому рівні дерева
Олександр Павлов, Олена Халус, Михайло Медведєв
Мінімізація сумарного зваженого моменту випередження виконання завдань …
60
допустимих розкладів (7) та обидва правила відсікання гілок приводять к суттє-
вому скороченню кількості гілок, починаючи з перших рівнів. Оптимальний роз-
клад – це гілка довжини n з множини всіх, побудованих за всіма
nk деревами
допустимих розкладів гілок довжини n, для якої виконується умова (1).
Висновки. Таким чином, в роботі:
1. Розглянута задача побудови оптимального за критерієм мінімізації су-
марного зваженого моменту випередження виконання завдань на одному приладі
при максимально пізньому моменту його запуску.
2. Приведено точний метод її розв’язання, що полягає в побудові дерев до-
пустимих розв’язків.
3. Запропонована алгоритмічна схема побудови дерев допустимих роз-
кладів та ефективні правила відсікання гілок при умові, що величина моменту
запуску приладу є максимальною.
4. Показана можливість практичного застосування запропонованого мето-
ду в багаторівневих моделях управління інноваційними проектами.
Література
[1] Wang, Z.Y., Lu, C. (2021). An integrated job shop scheduling and assembly sequence planning
approach for discrete manufacturing. Journal of Manufacturing Systems, 61, 27-44. doi:
10.1016/j.jmsy.2021.08.003
[2] Li, X., Gao, L. (2020). Introduction for Integrated Process Planning and Scheduling. In: Effective
Methods for Integrated Process Planning and Scheduling. Engineering Applications of
Computational Methods, vol 2. Springer, Berlin, Heidelberg. doi: 10.1007/978-3-662-55305-3_1
[3] Tuo, L., Dai, L., Chen, X. (2014). Scheduling of Discrete Manufacturing Process for Energy
Saving. In: Applied Mechanics and Materials (Vols. 556–562, pp. 4248–4254). Trans Tech
Publications, Ltd. doi: 10.4028/www.scientific.net/amm.556-562.4248
[4] Kulcsár, G., & Kulcsárné, F.M. (2009). Solving multi-objective production scheduling problems
using a new approach. Production Systems and Information Engineering, A Publication of the
University of Miskolc, 5, 81–94.
[5] Pavlov, A.A. (2021). Long-Term Operational Planning of a Small-Series Production Under Uncer-
tainty (Theory and Practice). In: Hu, Z., Petoukhov, S., Dychka, I., He, M. (eds) Advances in Com-
puter Science for Engineering and Education III. ICCSEEA 2020. Advances in Intelligent Systems
and Computing, vol 1247, pp. 167-180. Springer, Cham. doi: 10.1007/978-3-030-55506-1_15
[6] Pavlov, A.A., Khalus, E.A., Borysenko, I.V. (2019). Planning Automation in Discrete Systems
with a Given Structure of Technological Processes. In: Hu, Z., Petoukhov, S., Dychka, I., He, M.
(eds) Advances in Computer Science for Engineering and Education. ICCSEEA 2018. Advances
in Intelligent Systems and Computing, vol 754, pp. 177-185. Springer, Cham. doi: 10.1007/978-3-
319-91008-6_18
[7] Pavlov, A.A., Misura, E.B., Melnikov, O.V., Mukha, I.P. (2019). NP-Hard Scheduling Problems
in Planning Process Automation in Discrete Systems of Certain Classes. In: Hu, Z., Petoukhov, S.,
Dychka, I., He, M. (eds) Advances in Computer Science for Engineering and Education.
ICCSEEA 2018. Advances in Intelligent Systems and Computing, vol 754, pp. 429-436. Springer,
Cham. doi: 10.1007/978-3-319-91008-6_43
[8] Zgurovsky, M.Z., Pavlov, A.A. (2019). Optimal Scheduling for Two Criteria for a Single Machine
with Arbitrary Due Dates of Tasks. In: Combinatorial Optimization Problems in Planning and
Decision Making. Studies in Systems, Decision and Control, vol 173, pp. 17-38. Springer, Cham.
doi: 10.1007/978-3-319-98977-8_2
[9] Zgurovsky, M.Z., Pavlov, A.A. (2019). Algorithms and Software of the Four-Level Model of
Planning and Decision Making. In: Combinatorial Optimization Problems in Planning and
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 37, 57-61
61
Decision Making. Studies in Systems, Decision and Control, vol 173, pp. 407-518. Springer,
Cham. doi: 10.1007/978-3-319-98977-8_9
Minimization of the total weighted earliness of tasks on a single machine
Alexander Pavlov, Elena Khalus, Mykhailo Medvediev
We consider the problem of building a feasible schedule for the execution of tasks with various
due dates on a single machine. The optimality criteria are double fold: the first is the latest time of
the machine start, the second is minimization of the total weighted earliness of tasks in a feasible
schedule where the criteria are given in a lexicographic order. That is, the starting time of the ma-
chine is as late as possible, and when this condition is fulfilled, the minimum possible value of the
total weighted earliness of tasks is reached on a feasible schedule. The authors showed that this
problem is qualitatively harder than the above formulated problem with equal positive weights.
This paper proposes an exact method based on building of feasible solution trees. Fundamentally
new are the formulated restrictions on the set of vertices of each level and the theoretically sub-
stantiated efficient rules for cutting branches. The rules are implemented in a statistically signifi-
cant way already at the first levels of the feasible solution tree. The practical value of the pro-
posed method is illustrated by the possibility of its application in a multi-level model of innovative
project management at the last level of its hierarchy.
Отримано 22.03. 23
|
| id | oai:ojs2.www.fmmit.lviv.ua:article-305 |
| institution | Physico-mathematical modeling and informational technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-06-09T01:10:04Z |
| publishDate | 2023 |
| publisher | Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України |
| record_format | ojs |
| resource_txt_mv | wwwfmmitlvivua/73/8b4ec2918669470131db26e142873173.pdf |
| spelling | oai:ojs2.www.fmmit.lviv.ua:article-3052025-02-21T17:31:10Z Minimization of the total weighted earliness of tasks on a single machine Мінімізація сумарного зваженого моменту випередження виконання завдань на одному приладі Pavlov, Alexander Khalus, Elena Medvediev, Mykhailo календарне планування; оптимізація; допустимий розклад; багаторівнева модель управління We consider the problem of building a feasible schedule for the execution of tasks with various due dates on a single machine. The optimality criteria are double fold: the first is the latest time of the machine start, the second is minimization of the total weighted earliness of tasks in a feasible schedule where the criteria are given in a lexicographic order. That is, the starting time of the machine is as late as possible, and when this condition is fulfilled, the minimum possible value of the total weighted earliness of tasks is reached on a feasible schedule. The authors showed that this problem is qualitatively harder than the above formulated problem with equal positive weights. This paper proposes an exact method based on building of feasible solution trees. Fundamentally new are the formulated restrictions on the set of vertices of each level and the theoretically substantiated efficient rules for cutting branches. The rules are implemented in a statistically significant way already at the first levels of the feasible solution tree. The practical value of the proposed method is illustrated by the possibility of its application in a multi-level model of innovative project management at the last level of its hierarchy. Розглядається задача побудови допустимого розкладу виконання завдань з різними директивними строками на одному приладі, оптимального за критеріями: перший – максимально пізній момент запуску приладу, другий – мінімізація сумарного зваженого моменту випередження виконання завдань допустимого розкладу. Критерії задані в лексикографічному порядку, тобто момент запуску приладу максимально пізній, і при виконанні цієї умови на допустимому розкладі досягається мінімально можливе значення сумарного зваженого моменту випередження виконання завдань. Автори показали, що ця задача є якісно більш складною, ніж сформульована вище задача з рівними додатними вагами. В цій роботі пропонується точний метод, що ґрунтується на побудові дерев допустимих розв’язків. Принципово новими є сформульовані обмеження на множину вершин кожного рівня та теоретично обґрунтовані ефективні правила відсікання гілок, що статистично значимо починають реалізовуватися на перших рівнях дерева допустимих розв’язків. Практичне значення запропонованого методу ілюструється можливістю його застосування в багаторівневій моделі управління інноваційними проектами на останньому рівні її ієрархії. Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України 2023-06-27 Article Article application/pdf https://www.fmmit.lviv.ua/index.php/fmmit/article/view/305 PHYSICO-MATHEMATICAL MODELLING AND INFORMATIONAL TECHNOLOGIES; No. 37 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 57-61 ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; № 37 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 57-61 2617-5258 1816-1545 10.15407/fmmit2023.37 uk https://www.fmmit.lviv.ua/index.php/fmmit/article/view/305/273 Авторське право (c) 2023 Олександр Павлов, Олена Халус, Михайло Медведєв (Автор) |
| spellingShingle | календарне планування оптимізація допустимий розклад багаторівнева модель управління Pavlov, Alexander Khalus, Elena Medvediev, Mykhailo Мінімізація сумарного зваженого моменту випередження виконання завдань на одному приладі |
| title | Мінімізація сумарного зваженого моменту випередження виконання завдань на одному приладі |
| title_alt | Minimization of the total weighted earliness of tasks on a single machine |
| title_full | Мінімізація сумарного зваженого моменту випередження виконання завдань на одному приладі |
| title_fullStr | Мінімізація сумарного зваженого моменту випередження виконання завдань на одному приладі |
| title_full_unstemmed | Мінімізація сумарного зваженого моменту випередження виконання завдань на одному приладі |
| title_short | Мінімізація сумарного зваженого моменту випередження виконання завдань на одному приладі |
| title_sort | мінімізація сумарного зваженого моменту випередження виконання завдань на одному приладі |
| topic | календарне планування оптимізація допустимий розклад багаторівнева модель управління |
| topic_facet | календарне планування оптимізація допустимий розклад багаторівнева модель управління |
| url | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/305 |
| work_keys_str_mv | AT pavlovalexander minimizationofthetotalweightedearlinessoftasksonasinglemachine AT khaluselena minimizationofthetotalweightedearlinessoftasksonasinglemachine AT medvedievmykhailo minimizationofthetotalweightedearlinessoftasksonasinglemachine AT pavlovalexander mínímízacíâsumarnogozvaženogomomentuviperedžennâvikonannâzavdanʹnaodnomupriladí AT khaluselena mínímízacíâsumarnogozvaženogomomentuviperedžennâvikonannâzavdanʹnaodnomupriladí AT medvedievmykhailo mínímízacíâsumarnogozvaženogomomentuviperedžennâvikonannâzavdanʹnaodnomupriladí |