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

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.