Online hierarchical scheduling on two machines with known total size of low-hierarchy jobs

References

• A. Bar-Noy, A. Freund, and J. Naor, On-line load balancing in a hierarchical server topology, SIAM J. Comput. 31(2) (2001), pp. 527–549. doi: 10.1137/S0097539798346135
   Web of Science ®Google Scholar
• X. Chen, Z. Xu, G. Dósa, X. Han, and H. Jiang, Semi-online hierarchical scheduling problems with buffer or rearrangements, Inform. Process. Lett. 113(4) (2013), pp. 127–131. doi: 10.1016/j.ipl.2012.12.007
   Web of Science ®Google Scholar
• G. Dósa and Y. He, Semi-online algorithms for parallel machine scheduling problems, Computing 72(3) (2004), pp. 355–363.
   Web of Science ®Google Scholar
• L. Epstein, Bin stretching revisited, Acta Inform. 39(2) (2003), pp. 97–117. doi: 10.1007/s00236-002-0102-7
   Web of Science ®Google Scholar
• R.L. Graham, Bounds for certain multiprocessing anomalies, Bell System Tech. J. 45(9) (1966), pp. 1563–1581. doi: 10.1002/j.1538-7305.1966.tb01709.x
   Google Scholar
• H.C. Hwang, S.Y. Chang, and K. Lee, Parallel machine scheduling under a grade of service provision, Comput. Oper. Res. 31(12) (2004), pp. 2055–2061. doi: 10.1016/S0305-0548(03)00164-3
   Web of Science ®Google Scholar
• M. Ji and T. Cheng, An FPTAS for parallel-machine scheduling under a grade of service provision to minimize makespan, Inform. Process. Lett. 108(4) (2008), pp. 171–174. doi: 10.1016/j.ipl.2008.04.021
   Web of Science ®Google Scholar
• Y. Jiang, Online scheduling on parallel machines with two GoS levels, J. Comb. Optim. 16(1) (2008), pp. 28–38. doi: 10.1007/s10878-007-9095-z
   Web of Science ®Google Scholar
• Y. Jiang, Y. He, and C. Tang, Optimal online algorithms for scheduling on two identical machines under a grade of service, J. Zhejiang Univ. Sci. A 7(3) (2006), pp. 309–314. doi: 10.1631/jzus.2006.A0309
   Google Scholar
• H. Kellerer, V. Kotov, M.G. Speranza, and Zs. Tuza, Semi on-line algorithms for the partition problem, Oper. Res. Lett. 21(5) (1997), pp. 235–242. doi: 10.1016/S0167-6377(98)00005-4
   Web of Science ®Google Scholar
• K. Lee and K. Lim, Semi-online scheduling problems on a small number of machines, J. Sched. 16(5) (2013), pp. 461–477. doi: 10.1007/s10951-013-0329-x
   Web of Science ®Google Scholar
• K. Lee, J.Y.-T. Leung, and M.L. Pinedo, Makespan minimization in online scheduling with machine eligibility, Ann. Oper. Res. 204(1) (2013), pp. 1–34.
   Web of Science ®Google Scholar
• K. Lee, H. Hwang, and K. Lim, Semi-online scheduling with GoS eligibility constraints, Int. J. Production Econ. (2014). doi:10.1016/j.ijpe.2014.03.001.
   Web of Science ®Google Scholar
• K. Lim, K. Lee, and S.Y. Chang, Improved bounds for online scheduling with eligibility constraints, Theor. Comput. Sci. 412(39) (2011), pp. 5211–5224. doi: 10.1016/j.tcs.2011.05.029
   Web of Science ®Google Scholar
• X. Min, J. Liu, and Y. Wang, Optimal semi-online algorithms for scheduling problems with reassignment on two identical machines, Inform. Process. Lett. 111(9) (2011), pp. 423–428. doi: 10.1016/j.ipl.2011.01.002
   Web of Science ®Google Scholar
• J. Park, S.Y. Chang, and K. Lee, Online and semi-online scheduling of two machines under a grade of service provision, Oper. Res. Lett. 34(6) (2006), pp. 692–696. doi: 10.1016/j.orl.2005.11.004
   Web of Science ®Google Scholar
• H. Sun and Y. Huang, Semi-online Multiprocessor Scheduling with Nonsimultaneous Machine Available Times, 2010 Third International Conference on Information and Computing (ICIC), Wuxi, China, Vol. 3, pp. 115–118. IEEE, 2010. doi: 10.1109/ICIC.2010.213
   Google Scholar
• Z. Tan and Y. He, On-line and semi on-line scheduling on parallel machines with non-simultaneous machines available times, J. System Sci. Math. Sci. 22(4) (2000), pp. 414–421.
   Google Scholar
• Z. Tan and Y. He, Semi-on-line problems on two identical machines with combined partial information, Oper. Res. Lett. 30(6) (2002), pp. 408–414. doi: 10.1016/S0167-6377(02)00164-5
   Web of Science ®Google Scholar
• Z. Tan and A. Zhang, A note on hierarchical scheduling on two uniform machines, J. Comb. Optim. 20(1) (2010), pp. 85–95. doi: 10.1007/s10878-008-9195-4
   Web of Science ®Google Scholar
• G.J. Woeginger, A comment on parallel-machine scheduling under a grade of service provision to minimize makespan, Inform. Process. Lett. 109(7) (2009), pp. 341–342. doi: 10.1016/j.ipl.2008.11.008
   Web of Science ®Google Scholar
• Y. Wu and Q. Yang, Optimal Semi-online Scheduling Algorithms on Two Parallel Identical Machines under a Grade of Service Provision, 6th International Conference on Algorithmic Aspects in Information and Management, Weihai, China, July 19–21, pp. 261–270, 2010.
   Google Scholar
• Y. Wu, M. Ji, and Q. Yang, Optimal semi-online scheduling algorithms on two parallel identical machines under a grade of service provision, Int. J. Production Econ. 135(1) (2012), pp. 367–371. doi: 10.1016/j.ijpe.2011.07.021
   Web of Science ®Google Scholar
• G. Zhang, A simple semi on-line algorithm for P2//Cmax with a buffer, Inform. Process. Lett. 61 (1997), pp. 145–148. doi: 10.1016/S0020-0190(97)00006-9
   Web of Science ®Google Scholar
• G. Zhang and D. Ye, A note on on-line scheduling with partial information, Comput. Math. Appl. 44(3) (2002), pp. 539–543. doi: 10.1016/S0898-1221(02)00168-2
   Web of Science ®Google Scholar