Online and Semi–Online Scheduling on Two Hierarchical Machines with a Common Due Date to Maximize the Total Early Work

Man Xiao; Xiaoqiao Liu; Weidong Li; Xin Chen; Malgorzata Sterna; Jacek Blazewicz

doi:10.61822/amcs-2024-0018

.blurhash-client-img { display: none !important; }

Online and Semi–Online Scheduling on Two Hierarchical Machines with a Common Due Date to Maximize the Total Early Work

International Journal of Applied Mathematics and Computer Science

Volume 34 (2024): Issue 2 (June 2024)

By: Man Xiao, Xiaoqiao Liu, Weidong Li, Xin Chen, Malgorzata Sterna and Jacek Blazewicz

Open Access

|Jun 2024

Abstract

In this study, we investigate several online and semi-online scheduling problems related to two hierarchical machines with a common due date to maximize the total early work. For the pure online case, we design an optimal online algorithm with a competitive ratio of . Additionally, for the cases when the largest processing time is known, we give optimal algorithms with a competitive ratio of 6/5 if the largest job is a lower-hierarchy one, and of − 1 if the largest job is a higher-hierarchy one.

References

Akaria, I. and Epstein, L. (2022). Online scheduling with migration on two hierarchical machines, Journal of Combinatorial Optimization 44(5): 3535–3548.
Search in Google Scholar Back to article
Bar-Noy, A., Freund, A. and Naor, J. (2001). On-line load balancing in a hierarchical server topology, SIAM Journal on Computing 31(2): 527–549.
Search in Google Scholar Back to article
Chen, X., Kovalev, S., Liu, Y., Sterna, M., Chalamon, I. and Błażewicz, J. (2021). Semi-online scheduling on two identical machines with a common due date to maximize total early work, Discrete Applied Mathematics 290: 71–78.
Search in Google Scholar Back to article
Chen, X., Liang, Y., Sterna, M., Wang, W. and Błażewicz, J. (2020a). Fully polynomial time approximation scheme to maximize early work on parallel machines with common due date, European Journal of Operational Research 284(1): 67–74.
Search in Google Scholar Back to article
Chen, X., Shen, X., Kovalyov, M.Y., Sterna, M. and Błażewicz, J. (2022). Alternative algorithms for identical machines scheduling to maximize total early work with a common due date, Computers & Industrial Engineering 171: 108386.
Search in Google Scholar Back to article
Chen, X., Sterna, M., Han, X. and Błażewicz, J. (2016). Scheduling on parallel identical machines with late work criterion: Offline and online cases, Journal of Scheduling 19: 729–736.
Search in Google Scholar Back to article
Chen, X., Wang, W., Xie, P., Zhang, X., Sterna, M. and Błażewicz, J. (2020b). Exact and heuristic algorithms for scheduling on two identical machines with early work maximization, Computers & Industrial Engineering 144: 106449.
Search in Google Scholar Back to article
Gordon, V., Proth, J.M. and Chu, C. (2002). A survey of the state-of-the-art of common due date assignment and scheduling research, European Journal of Operational Research 139(1): 1–25.
Search in Google Scholar Back to article
Graham, R., Lawler, E., Lenstra, J. and Rinnooy Kan, A. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics 5: 287–326.
Search in Google Scholar Back to article
Györgyi, P. and Kis, T. (2020). A common approximation framework for early work, late work, and resource leveling problems, European Journal of Operational Research 286(1): 129–137.
Search in Google Scholar Back to article
Janiak, A., Kwiatkowski, T. and Lichtenstein, M. (2013). Scheduling problems with a common due window assignment: A survey, International Journal of Applied Mathematics and Computer Science 23(1): 231–241, DOI: 10.2478/amcs-2013-0018.
Search in Google Scholar Back to article
Jiang, Y. (2008). Online scheduling on parallel machines with two GoS levels, Journal of Combinatorial Optimization 16(1): 28–38.
Search in Google Scholar Back to article
Jiang, Y., Guan, L., Zhang, K., Liu, C., Cheng, T. and Ji, M. (2021). A note on scheduling on two identical machines with early work maximization, Computers & Industrial Engineering 153: 107091.
Search in Google Scholar Back to article
Jiang, Y., He, Y. and Tang, C. (2006). Optimal online algorithms for scheduling on two identical machines under a grade of service, Journal of Zhejiang University: Science A 7(3): 309–314.
Search in Google Scholar Back to article
Li, W. (2024). Improved approximation schemes for early work scheduling on identical parallel machines with common due date, Journal of the Operations Research Society of China 12: 341–350, DOI: 10.1007/s40305-022-00402-y.
Search in Google Scholar Back to article
Liu, X., Wang, W., Chen, X., Sterna, M. and Blazewicz, J. (2023). Exact approaches to late work scheduling on unrelated machines, International Journal of Applied Mathematics and Computer Science 33(2): 285–295, DOI: 10.34768/amcs-2023-0021.
Search in Google Scholar Back to article
Luo, T. and Xu, Y. (2015). Semi-online hierarchical load balancing problem with bounded processing times, Theoretical Computer Science 607: 75–82.
Search in Google Scholar Back to article
Park, J., Chang, S. and Lee, K. (2006). Online and semi-online scheduling of two machines under a grade of service provision, Operations Research Letters 34(6): 692–696.
Search in Google Scholar Back to article
Sterna, M. (2011). A survey of scheduling problems with late work criteria, Omega 39(2): 120–129.
Search in Google Scholar Back to article
Sterna, M. (2021). Late and early work scheduling: A survey, Omega 104: 102453.
Search in Google Scholar Back to article
Sterna, M. and Czerniachowska, K. (2017). Polynomial time approximation scheme for two parallel machines scheduling with a common due date to maximize early work, Journal of Optimization Theory and Applications 174: 927–944.
Search in Google Scholar Back to article
Wang, W., Chen, X., Musial, J. and Blazewicz, J. (2020). Two meta-heuristic algorithms for scheduling on unrelated machines with the late work criterion, International Journal of Applied Mathematics and Computer Science 30(3): 573–584, DOI: 10.34768/amcs-2020-0042.
Search in Google Scholar Back to article
Xiao, M., Liu, X. and Li, W. (2021). Semi-online early work maximization problem on two hierarchical machines with partial information of processing time, in W. Wu and H. Du (Eds), Algorithmic Applications in Management, Lecture Notes in Computer Science, Vol. 13153, Springer, Cham, pp. 146–156.
Search in Google Scholar Back to article
Xiao, M., Liu, X. and Li, W. (2023). Semi-online early work maximization problems on two hierarchical uniform machines with partial information of processing time, Journal of Combinatorial Optimization 46(3): 21.
Search in Google Scholar Back to article

Articles in this issue

DOI: https://doi.org/10.61822/amcs-2024-0018 | Journal eISSN: 2083-8492 | Journal ISSN: 1641-876X

Journal RSS Feed

Language: English

Page range: 253 - 261

Submitted on: Oct 20, 2023

Accepted on: Feb 2, 2024

Published on: Jun 25, 2024

Published by: University of Zielona Góra

In partnership with: Paradigm Publishing Services

Publication frequency: 4 issues per year

Keywords:

online and semi-online,

early work,

hierarchical scheduling,

competitive ratio

Related subjects:

Mathematics,

Applied mathematics

© 2024 Man Xiao, Xiaoqiao Liu, Weidong Li, Xin Chen, Malgorzata Sterna, Jacek Blazewicz, published by University of Zielona Góra
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Volume 34 (2024): Issue 2 (June 2024)