Online and semi-online scheduling on two hierarchical machines with a common due date to maximize the total early work

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

International Journal of Applied Mathematics and Computer Science, Tome 34 (2024) no. 2, pp. 253-261.

Résumé

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 √2. 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 √5 − 1 if the largest job is a higher-hierarchy one.

Détail

Keywords: online scheduling, semi online scheduling, early work, hierarchical scheduling, competitive ratio

Bibliographie

[1] Akaria, I. and Epstein, L. (2022). Online scheduling with migration on two hierarchical machines, Journal of Combinatorial Optimization 44(5): 3535-3548.

[2] 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.

[3] 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.

[4] 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.

[5] 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.

[6] 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.

[7] 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.

[8] 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.

[9] 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.

[10] 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.

[11] 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.

[12] Jiang, Y. (2008). Online scheduling on parallel machines with two GoS levels, Journal of Combinatorial Optimization 16(1): 28-38.

[13] 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.

[14] 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.

[15] 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.

[16] 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.

[17] Luo, T. and Xu, Y. (2015). Semi-online hierarchical load balancing problem with bounded processing times, Theoretical Computer Science 607: 75-82.

[18] 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.

[19] Sterna, M. (2011). A survey of scheduling problems with late work criteria, Omega 39(2): 120-129.

[20] Sterna, M. (2021). Late and early work scheduling: A survey, Omega 104: 102453.

[21] 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.

[22] 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.

[23] 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.

[24] 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.