Online Scheduling with Unit Processing Times and Processing Set Restrictions

doi:10.1007/s40305-019-00256-x

Journal of the Operations Research Society of China ›› 2019, Vol. 7 ›› Issue (3): 475-484.doi: 10.1007/s40305-019-00256-x

所属专题： Management Science

收稿日期:2018-07-31 修回日期:2018-10-30 出版日期:2019-09-30 发布日期:2019-10-08
通讯作者: An Zhang, Yong Chen, Guang-Ting Chen, Long-Cheng Liu, Yi-Wei Jiang, Zhi-Yi Tan E-mail:anzhang@hdu.edu.cn;chenyong@hdu.edu.cn;gtchen@hdu.edu.cn;longchengliu@xmu.edu.cn;jywzju@163.com;tanzy@zju.edu.cn
基金资助:
Guang-Ting Chen was supported by the National Natural Science Foundation of China (No. 11571252). Long-Cheng Liu was supported by the China Scholarship Council Grants (No. 201706315073) and the Fundamental Research Funds for the Central Universities (No. 20720190068). Yi-Wei Jiang was supported by the National Natural Science Foundation of China (No. 11571013). Zhi-Yi Tan was supported by the National Natural Science Foundation of China (Nos. 11471286, 11671356) and the Natural Science Foundation of Zhejiang Province (No. LR12A01001). An Zhang was supported by the National Natural Science Foundation of China (No. 11771114).

Online Scheduling with Unit Processing Times and Processing Set Restrictions

Yong Chen¹, Guang-Ting Chen², Long-Cheng Liu^3,4, Yi-Wei Jiang⁵, Zhi-Yi Tan⁶, An Zhang¹

1 Department of Mathematics, Hangzhou Dianzi University, Hangzhou 310018, China;
2 School of Electronics and Information Engineering, Taizhou University, Taizhou 318000, Zhejiang, China;
3 School of Mathematical Sciences, Xiamen University, Xiamen 361005, China;
4 Department of Computing Science, University of Alberta, Edmonton, AB T6G 2R3, Canada

Received:2018-07-31 Revised:2018-10-30 Online:2019-09-30 Published:2019-10-08
Contact: An Zhang, Yong Chen, Guang-Ting Chen, Long-Cheng Liu, Yi-Wei Jiang, Zhi-Yi Tan E-mail:anzhang@hdu.edu.cn;chenyong@hdu.edu.cn;gtchen@hdu.edu.cn;longchengliu@xmu.edu.cn;jywzju@163.com;tanzy@zju.edu.cn

摘要/Abstract

Abstract: This paper investigates online scheduling problems with processing set restrictions. There is a sequence of jobs that are revealed one by one over list, where each job has unit processing time. A job can only be processed by a subset of the machines, namely the processing set of the job. The objective is to minimize the makespan. For m machines with two different processing sets, we propose an optimal algorithm with a competitive ratio of 3/2. For three machines with inclusive processing sets, an optimal algorithm with competitive ratio 5/3 is provided.

Key words: Online scheduling, Competitive ratio, Processing sets

中图分类号:

90B35

. [J]. Journal of the Operations Research Society of China, 2019, 7(3): 475-484.

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.

参考文献

[1] Leung, J.Y.-T., Li, C.L.:Scheduling with processing set restrictions:a survey. Int. J. Prod. Econ. 116, 251-262(2008)
[2] Lee, K., Leung, J.Y.-T., Pinedo, M.:Makespan minimization in online scheduling with machine eligibility. Ann. Oper. Res. 204, 189-222(2013)
[3] Tan, Z., Zhang, A.:Online and semi-online scheduling. In:Pardalos, P.M., et al. (eds.) Handbook of Combinatorial Optimization, 2nd edn, pp. 2191-2252. Springer, New York (2013)
[4] Leung, J.Y.-T., Li, C.L.:Scheduling with processing set restrictions:a literature update. Int. J. Prod. Econ. 175, 1-11(2016)
[5] Azar, Y., Naor, A., Rom, R.:The competitiveness of on-line assignments. J. Algorithms 18, 221-237(1995)
[6] Lim, K., Lee, K., Chang, S.:Improved bounds for online scheduling with eligibility constraints. Theor. Comput. Sci. 412, 5211-5224(2011)
[7] Bar-Noy, A., Freund, A., Naor, J.:On-line load balancing in a hierarchical server topology. SIAM J. Comput. 31, 527-549(2001)
[8] 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, 692-696(2006)
[9] Jiang, Y., He, Y., Tang, C.:Optimal online algorithms for scheduling on two identical machines under a grade of service. J. Zhejiang Univ. Sci. 7A, 309-314(2006)
[10] Tan, Z., Zhang, A.:Online hierarchical scheduling:an approach using mathematical programming. Theor. Comput. Sci. 412, 246-256(2011)
[11] Karhi, S., Shabtay, D.:Online scheduling of two job types on a set of multipurpose machines. Int. J. Prod. Econ. 150, 155-162(2014)
[12] Zhang, A., Jiang, Y., Tan, Z.:Online parallel machines scheduling with two hierarchies. Theor. Comput. Sci. 410, 3597-3605(2009)
[13] Kravchenko, S.A., Werner, F.:Parallel machine problems with equal processing times:a survey. J. Sched. 14, 435-444(2011)
[14] Shabtay, D., Karhi, S.:Online scheduling of two job types on a set of multipurpose machines with unit processing times. Comput. Oper. Res. 39, 405-412(2012)

Online Scheduling with Unit Processing Times and Processing Set Restrictions

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics

本文评价