Information technologies and computer sciences

Problem of Scheduling Jobs Considering Time Windows

Authors

O. H. Zhdanova
National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute” ROR
V. V. Kovalenko
National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute” ROR
DOI https://doi.org/10.31649/1997-9266-2023-167-2-97-101

Keywords

scheduling parallel machines release date due date heuristic algorithm

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 bin-packing 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.

556 292

How to Cite

[1]
“Problem of Scheduling Jobs Considering Time Windows”, Вісник ВПІ, no. 2, pp. 97–101, May 2023, doi: 10.31649/1997-9266-2023-167-2-97-101.

Author Biographies

O. H. Zhdanova, National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”

Cand. Sc. (Eng.), Associate Professor of the Chair of Information Systems and Technologies

V. V. Kovalenko, National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”

Student of the Department of Informatics and Computer Engineering

 

References

СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ
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 .

Most read articles by the same author(s)