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

Анотація

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