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

Special Issue: Management Science

Previous Articles Next Articles

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

CLC Number:

90B35

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.

TrendMD

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 3

Recommended Articles

Metrics

Comments

[1]	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.
[2]	Wen-Hua Li, Xing Chai. Online Scheduling on Bounded Batch Machines to Minimize the MaximumWeighted Completion Time [J]. Journal of the Operations Research Society of China, 2018, 6(3): 455-466.
[3]	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-.