Abstract
This paper is concerned with the fractional version of online hierarchical scheduling problem on uniform machines. In the problem, the jobs and machines have several different hierarchies and each job can be arbitrarily split between the machines with hierarchies not above the hierarchy of the job. The objective is to minimize the makespan. The authors present an optimal algorithm for the problem with three hierarchies.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Graham R L, Lawler E L, Lenstra J K, et al, Optimization and approximation in deterministic sequencing and scheduling: A survey, Ann. Discrete Math., 1979, 5: 287–326.
Bar-Noy A, Freund A, and Naor J, Online load balancing in a hierarchical server topology, SIAM J. Comput., 2001, 31: 527–549.
Hwang H, Chang S, and Lee K, Parallel machine scheduling under a grade of service provision, Comput. Oper. Res., 2004, 31: 2055–2061.
Tan Z Y and Zhang A, Online hierarchical scheduling: An approach using mathematical programming, Theor. Comput. Sci., 2011, 412: 246–256.
Jiang Y W, Online scheduling on parallel machines with two GoS levels, J. Comb. Optim., 2008, 16: 28–38.
Zhang A, Jiang Y W, and Tan Z Y, Online parallel machines scheduling with two hierarchies, Theor. Comput. Sci., 2009, 410: 3597–3605.
Azar Y, Naor J, and Rom R, The competitiveness of on-line assignments, J. Algorithms, 1995, 18: 221–237.
Chassid O and Epstein L, The hierarchical model for load balancing on two machines. J. Comb. Optim., 2008, 15: 305–314.
Tan Z Y and Zhang A, A note on hierarchical scheduling on two uniform machines, J. Comb. Optim., 2010, 20: 85–95.
Hou L Y and Kang L Y, Online and semi-online hierarchical scheduling for load balancing on uniform machines, Theor. Comput. Sci., 2011, 412: 1092–1098.
Hou L Y and Kang L Y, Online scheduling on uniform machines with two hierarchies, J. Comb. Optim., 2012, 24: 593–612.
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was supported by National Natural Science Foundation of China under Grant No. 11171106.
This paper was recommended for publication by Editor WANG Shouyang.
Rights and permissions
About this article
Cite this article
Lu, X., Liu, Z. An optimal online algorithm for fractional scheduling on uniform machines with three hierarchies. J Syst Sci Complex 29, 1650–1657 (2016). https://doi.org/10.1007/s11424-016-5001-z
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11424-016-5001-z