Online Scheduling on Two Parallel Identical Machines Under a Grade of Service Provision

doi:10.1007/s40305-020-00325-6

Journal of the Operations Research Society of China ›› 2022, Vol. 10 ›› Issue (4): 689-702.doi: 10.1007/s40305-020-00325-6

Previous Articles Next Articles

Online Scheduling on Two Parallel Identical Machines Under a Grade of Service Provision

Shuang Cai¹, Ke Liu^2,3

1 Data Department, Beijing Kingsoft Cloud Network Technology Co., Ltd., Beijing 100086, China;
2 Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China;
3 University of Chinese Academy of Sciences, Beijing 100190, China

Received:2019-02-01 Revised:2019-08-23 Online:2022-12-30 Published:2022-11-09
Contact: Shuang Cai,Ke Liu E-mail:caishuang@kingsoft.com;kliu@amss.ac.cn
Supported by:
This research was supported by the National Natural Science Foundation of China (Nos. 11271356, and 71390334).

Abstract

Abstract: 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.

Key words: Online scheduling, Parallel machines, A grade of service provision, GoS

CLC Number:

90B06
68M20

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.

TrendMD

References

[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)

Online Scheduling on Two Parallel Identical Machines Under a Grade of Service Provision

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 4

Recommended Articles

Metrics

Comments

[1]	Hai-Ling Liu, Xi-Wen Lu. Online Scheduling on a Parallel Batch Machine with Delivery Times and Limited Restarts [J]. Journal of the Operations Research Society of China, 2022, 10(1): 113-131.
[2]	Yong Chen, Guang-Ting Chen, Long-Cheng Liu, Yi-Wei Jiang, Zhi-Yi Tan, An Zhang. Online Scheduling with Unit Processing Times and Processing Set Restrictions [J]. Journal of the Operations Research Society of China, 2019, 7(3): 475-484.
[3]	Jin-Jiang Yuan, Li-Li Ren, Ji Tian, Ru-Yan Fu. Online Scheduling on Two Uniform Unbounded Parallel-Batch Machines to Minimize Makespan [J]. Journal of the Operations Research Society of China, 2019, 7(2): 303-319.
[4]	Ji Tian · Ruyan Fu · Jinjiang Yuan. Online Over Time Scheduling on Parallel-Batch Machines: A Survey [J]. Journal of the Operations Research Society of China, 2014, 2(4): 445-.