ПДС-алгоритми для двоетапної задачі календарного планування в детермінованій постановці та в умовах невизначеності

Автор(и)

  • О. Павлов КПІ ім. Ігоря Сікорського, Україна
  • О. Халус КПІ ім. Ігоря Сікорського, Україна
  • О. Місюра КПІ ім. Ігоря Сікорського, Україна
  • О. Мельников КПІ ім. Ігоря Сікорського, Україна
  • М. Медведєв КПІ ім. Ігоря Сікорського, Україна

DOI:

https://doi.org/10.20535/1560-8956.42.2023.279170

Ключові слова:

двоетапна задача календарного планування, ПДС-алгоритм, NP- складні нові задачі, емпірична матриця парних порівнянь, невизначеність

Анотація

Розглядається двоетапна задача календарного планування, в якій на першому етапі розв’язується задача сумарного запізнення моментів завершення роботи ідентичних незалежних пристроїв відносно спільного директивного строку. Цей оптимальний розв’язок водночас повинен задовольняти наступній умові: різниця між найпізнішим та найбільш раннім строками завершення роботи пристроїв є мінімальною в порівнянні з іншими оптимальними розв’язками. На другому етапі кожен пристрій в момент звільнення починає виконувати послідовно незалежно від інших пристроїв нову
множину завдань, кожне з яких має свій директивний строк, за критерієм мінімізації сумарного зваженого запізнення виконання кожного завдання відносно його директивного строку. В даній постановці оптимальним розв’язком сформульованої задачі є той, у якого є оптимальний розв’язок першого етапу, а розв’язок другого етапу є умовно оптимальним (оптимальним відносно отриманих моментів звільнення пристроїв після виконання завдань першого етапу). На розв’язок першого етапу може бути накладена додаткова умова: моменти запуску пристроїв на другому етапі повинні задовольняти наперед заданому лексикографічному порядку. Зрозуміло, що в наведеній постановці кожен пристрій є багатофункціональним. Сформульована вище задача в умовах невизначеності означає, що вектори вагових коефіцієнтів критеріїв для кожного пристрою на другому етапі задані неоднозначно. Неоднозначність може бути пов’язана з тим, що вагові коефіцієнти задаються не одним, а декількома експертами, чи в силу того, що другий етап може бути реалізований в майбутньому, і тому вектор вагових коефіцієнтів вважається випадковим дискретним із заданим розподілом, чи його неоднозначність задається відповідною функцією належності. Автори запропонували ПДС-алгоритми розв’язання цієї задачі в детермінованій постановці та в умовах невизначеності. Тобто, кожен алгоритм містить наближений поліноміальний підалгоритм побудови оптимального розкладу, для якого сформульовані достатні ознаки його оптимальності.

Бібл. 9

Посилання

Li X., Gao L. Introduction for Integrated Process Planning and Scheduling. Engineering Applications of Computational Methods. 2020. Vol. 2. P. 1–15. DOI: 10.1007/978-3-662-55305-3_1.

NP-Hard Scheduling Problems in Planning Process Automation in Discrete Systems of Certain Classes / Pavlov A.A. et al. Advances in Intelligent Systems and Computing : The First International Conference on Computer Science, Engineering and Education Applications ICCSEEA 2018, Kyiv, 18-20 Jan. 2018. Cham: Springer, 2019.P. 429–436. DOI: 10.1007/978-3-319-91008-6_43.

Pavlov A.A., Khalus E.A., Borysenko I.V. Planning Automation in Discrete Systems with a Given Structure of Technological Processes. Advances in Intelligent Systems and Computing : The First International Conference on Computer Science, Engineering and Education Applications ICCSEEA 2018, Kyiv, 18-20 Jan. 2018. Cham: Springer, 2019, P. 177–185. DOI: 10.1007/978-3-319-91008-6_18.

Ceschia S., Di Gaspero L., Schaerf A. Solving discrete lot-sizing and scheduling by simulated annealing and mixed integer programming. Computers & Industrial Engineering. 2017. Vol. 114. P. 235-243. DOI: 10.1016/j.cie.2017.10.017.

Zgurovsky M.Z., Pavlov A.A. The Total Weighted Tardiness of Tasks Minimization on a Single Machine. In: Combinatorial Optimization Problems in Planning and Decision Making: Theory and Applications. 1st ed. Studies in Systems, Decision and Control, vol. 173, P. 107–217. – Springer, Cham, 2019. DOI: 10.1007/978-3-319-98977-8_4.

Zgurovsky M.Z., Pavlov A.A. The Total Tardiness of Tasks Minimization on Identical Parallel Machines with Arbitrary Fixed Times of Their Start and a Common Due Date. In: Combinatorial Optimization Problems in Planning and Decision Making: Theory and Applications. 1st ed. Studies in Systems, Decision and Control, vol. 173, P. 265–290. – Springer, Cham, 2019. DOI: 10.1007/978-3-319-98977-8_6.

Pavlov A.A. Optimization for one class of combinatorial problems under uncertainty. Adaptive Systems of Automatic Control, Vol. 1 (34), 2019, С. 81–89. DOI: 10.20535/1560-8956.1.2019.178233.

Павлов О.А., Жданова О.Г., Сперкач М.О. Задача составления допустимого расписания с максимально поздним моментом запуска выполнения идентичными параллельными приборами работ с общим директивным сроком. Вісник НТУУ "КПІ". Серія "Інформатика, управління та обчислювальна техніка". 2014. Вип. 61. C. 93-102. URL: https://ela.kpi.ua/handle/123456789/16721 (дата звернення: 10.03.2023).

Zgurovsky M.Z., Pavlov A.A. The Four-Level Model of Planning and Decision Making. In: Combinatorial Optimization Problems in Planning and Decision Making: Theory and Applications. 1st ed. Studies in Systems, Decision and Control, vol. 173, P. 265–290. – Springer, Cham, 2019. DOI: 10.1007/978-3-319-98977-8_8.

##submission.downloads##

Опубліковано

2023-05-01