In this paper, we investigate online scheduling problems on two parallel identical machines under a grade of service provision with makespan as the objective function. The jobs arrive over time and each job can be scheduled only when it has already been arrived. We consider three different versions: (i) the two machines cannot be idle at the same time until all arrived jobs have been processed; (ii) further to the first problem, jobs are processed on a first-come, first-serviced basis; (iii) each job must be assigned to one of the two machines as soon as it arrives. Respectively for three online scheduling problems, optimal online algorithms are proposed with competitive ratio ($\sqrt{5}$ + 1)/2, ($\sqrt{5}$ + 1)/2 and 5/3.
Shuang Cai, Ke Liu
. Online Scheduling on Two Parallel Identical Machines Under a Grade of Service Provision[J]. Journal of the Operations Research Society of China, 2022
, 10(4)
: 689
-702
.
DOI: 10.1007/s40305-020-00325-6
[1] Mizgier, K.J., Wagner, S.M., Juettner, M.P.: Disentangling diversification in supply chain networks. Int. J. Prod. Econ. 162, 115–124(2015)
[2] Lee, K., Leung, J.Y.T., Pinedo, M.L.: Makespan minimization in online scheduling with machine eligibility. Ann. Oper. Res. 204(1), 189–222(2013)
[3] Graham, R.L., Lawler, E.L., Lenstra, J.K., et al.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5, 287–326(1979)
[4] Park, J., Chang, S.Y., Lee, K.: Online and semi-online scheduling of two machines under a grade of service provision. Oper. Res. Lett. 34(6), 692–696(2006)
[5] Jiang, Y., He, Y., Tang, C.: Optimal online algorithms for scheduling on two identical machines under a grade of service. J. Zhejiang Univ. Sci. A 7(3), 309–314(2006)
[6] Wu,Y.,Ji,M.,Yang,Q.:Optimal semi-online scheduling algorithms on two parallel identical machines under a grade of service provision. Int. J. Prod. Econ. 135(1), 367–371(2012)
[7] Zhang, A., Jiang, Y., Tan, Z.: Online parallel machines scheduling with two hierarchies. Theor. Comput. Sci. 410(38–40), 3597–3605(2009)
[8] Tan, Z., Zhang, A.: A note on hierarchical scheduling on two uniform machines. J. Comb. Optim. 20(1), 85–95(2010)
[9] Jiang, Y.: Online scheduling on parallel machines with two GoS levels. J. Comb. Optim. 16(1), 28–38(2008)
[10] Liu,M.,Xu,Y.,Chu,C.,etal.:Online scheduling on two uniform machines to minimize the makespan. Theor. Comput. Sci. 410(21–23), 2099–2109(2009)
[11] Mandelbaum, M., Shabtay, D.: Scheduling unit length jobs on parallel machines with lookahead information. J. Sched. 14(4), 335–350(2011)
[12] Lu, X., Liu, Z.: Semi-online scheduling problems on two uniform machines under a grade of service provision. Theor. Comput. Sci. 489, 58–66(2013)
[13] Chen, B., Vestjens, A.P.A.: Scheduling on identical machines: how good is LPT in an on-line setting? Oper. Res. Lett. 21(4), 165–169(1997)
[14] Noga, J., Seiden, S.S.: An optimal online algorithm for scheduling two machines with release times. Theor. Comput. Sci. 268(1), 133–143(2001)
[15] Hong, K.S., Leung, J.Y.T.: On-line scheduling of real-time tasks. In: Real-Time Systems Symposium. Proceedings, pp. 244–250. IEEE (1988)
[16] Lee, K., Leung, J.Y.T., Pinedo, M.L.: Scheduling jobs with equal processing times subject to machine eligibility constraints. J. Sched. 14(1), 27–38(2011)
[17] Xu, J., Liu, Z.H.: An optimal online algorithm for scheduling on two parallel machines with GoS eligibility constraints. J. Oper. Res. Soc. China 4(3), 371–377(2016)
[18] Li, S., Zhang, Y.: On-line scheduling on parallel machines to minimize the makespan. J. Syst. Sci. Complex. 29(2), 472–477(2016)
[19] Yuan, J.J., Ren, L.L., Tian, J., et al.: Online scheduling on two uniform unbounded parallel-batch machines to minimize makespan. J. Oper. Res. Soc. China 7(2), 303–319(2019)
[20] Cai, S., Liu, K.: Heuristics for online scheduling on identical parallel machines with two GoS levels. J. Syst. Sci. Complex. 32(4), 1180–1193(2019)
