Задача складання розкладу виконання робіт з урахуванням їхніх часових вікон

Abstract

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

The article is devoted to the scheduling optimization problem in which the machines are parallel and identical, and jobs, apart from their processing times, also have time windows, i.e. time intervals within the limits of which the job can be performed, and outside of which the job cannot be performed. The job’s time window is determined by its release date, which is non-zero in general case, and its and due date. It is considered that all time windows belong to the interval between the minimum release date and the maximum due date, and that each job has one and only one time window. The optimization criteria are: maximization of the number of jobs that are performed, and maximization of the total duration time of jobs that are performed. The analysis of the similar problems, such as problems of processor’s computational load planning, and binpacking problems, was conducted. The examples of practical usage of the considered problem were provided. The heuristic algorithm for solving the problem was proposed, and it is comprised of consideration of the job in a certain order, and search of the machine and starting time for this job. Four variations of this heuristic algorithm that are based on heuristic rules of job consideration order depending on jobs’ parameters are proposed, such as processing time, time window width, slack (difference between time window width and processing time), and ratio of time window width to processing time. A series of experiments was conducted to evaluate which algorithm variation is effective for solving the problem for each of two suggested optimization criteria. In the process of experiments, it was determined that for the criteria of maximization of the number of jobs that are performed , the effective rule is based on time window width, and for the criteria of maximization of the total duration time of jobs that are performed, the effective rule is based on the duration of the job realization.