Problem of Scheduling Jobs Considering Time Windows
DOI:
https://doi.org/10.31649/1997-9266-2023-167-2-97-101Keywords:
scheduling, parallel machines, release date, due date, heuristic algorithmAbstract
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.
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 .
Downloads
-
PDF (Українська)
Downloads: 154
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
