ЗАДАЧА СКЛАДАННЯ РОЗКЛАДУ ВИКОНАННЯ РОБІТ З УРАХУВАННЯМ ЇХНІХ ЧАСОВИХ ВІКОН

Автор(и)

  • О. Г. Жданова Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського»
  • В. В. Коваленко Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського»

DOI:

https://doi.org/10.31649/1997-9266-2023-167-2-97-101

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

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

Анотація

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

Біографії авторів

О. Г. Жданова, Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського»

канд. техн. наук, доцент, доцент кафедри інформаційних систем та технологій

В. В. Коваленко, Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського»

студент факультету інформатики та обчислювальної техніки

Посилання

СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ

M. L. Pinedo, Planning and Scheduling in Manufacturing and Services, Second Edition. New York, USA: Springer Science+Business Media, 2009, pp. 209-215.

B. B. Brandenburg, and M. Gül, “Global Scheduling Not Required: Simple, Near-Optimal Multiprocessor Real-Time Scheduling with Semi-Partitioned Reservations,” in 2016 IEEE Real-Time Systems Symposium (RTSS), Porto, Portugal, 2016, pp. 99-110. https://doi.org/10.1109/RTSS.2016.019 .

L. Bo, and S. Bin, “Slack-based advance reservation for grid jobs,” in 2010 3rd International Conference on Advanced Computer Theory and Engineering (ICACTE), Chengdu, China, 2010, pp. V3418-V3421. https://doi.org/10.1109/ICACTE.2010.5579599 .

C. Hu, J. Huai, and T. Wo, “Flexible resource reservation using slack time for service grid,” in 12th International Conference on Parallel and Distributed Systems (ICPADS'06), Minneapolis, MN, USA, 2006, pp. 327-324. https://doi.org/10.1109/ICPADS.2006.49 .

B. Li, Y. Li, M. He, H. Wu, and J. Yang, “Scheduling of a Relaxed Backfill Strategy with Multiple Reservations,” in 2010 International Conference on Parallel and Distributed Computing, Applications and Technologies, Wuhan, China, 2010, pp. 311-316. https://doi.org/10.1109/PDCAT.2010.24 .

N. P. Rodrigo, W. B. Daundasekera, and A. I. Perera, “One-Dimensional Bin-Packing Problems with Branch and Bound Algorithm,” in International Journal of Discrete Mathematics, vol. 3, no. 2, pp. 36-40, 2018. New York, USA.

K. Fleszar, and K. S. Hindi, “New heuristics for one-dimensional bin-packing,” Computers & Operations Research, vol. 29, no. 7, pp. 821-839, 2002, Uxbridge, United Kingdom. https://doi.org/10.1016/S0305-0548(00)00082-4 .

A. C. F. Alvim, C. C. Ribeiro, F. Glover, and D. J. Aloise, “A Hybrid Improvement Heuristic for the One-Dimensional Bin Packing Problem,” Journal of Heuristics, vol. 10, no. 2, pp. 205-229, 2004. https://doi.org/10.1023/B:HEUR.0000026267.44673.ed

E. G. Coffman Jr., M. R. Garey, and D. S. Johnson, “Bin packing with divisible item sizes,” Journal of Complexity, vol. 3, no. 4, pp. 406-428, 1987. https://doi.org/10.1016/0885-064X(87)90009-4 .

J. O. Berkey, and P. Y. Wang, “Two-Dimensional Finite Bin-Packing Algorithms,” Journal of the Operational Research Society, vol. 38, no. 5, pp. 423-429, 1987. https://doi.org/10.1057/jors.1987.70 .

A. Lodi, S. Martello, and D. Vigo, “Recent advances on two-dimensional bin packing problems,” Discrete Applied Mathematics, vol. 123, pp. 379-396, 2002. https://doi.org/10.1016/S0166-218X(01)00347-X .

J.-K. Kim, H. Lee-Kwang, and S. W. Yoo, “Fuzzy bin packing problem,” Fuzzy Sets and Systems, vol. 120, no. 3, pp. 429-434, 2001. https://doi.org/10.1016/s0165-0114(99)00073-1 .

N. Bansal, J. Correa, C. Kenyon, and M. Sviridenko, “Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes,” Mathematics of Operations Research, vol. 31, no. 1, pp. 31-49, 2006. https://doi.org/10.1287/moor.1050.0168 .

##submission.downloads##

Переглядів анотації: 93

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

2023-05-04

Як цитувати

[1]
О. Г. Жданова і В. В. Коваленко, «ЗАДАЧА СКЛАДАННЯ РОЗКЛАДУ ВИКОНАННЯ РОБІТ З УРАХУВАННЯМ ЇХНІХ ЧАСОВИХ ВІКОН», Вісник ВПІ, вип. 2, с. 97–101, Трав. 2023.

Номер

Розділ

Інформаційні технології та комп'ютерна техніка

Метрики

Завантаження

Дані завантаження ще не доступні.