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.
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
.
DOI: 10.1007/s40305-019-00256-x
[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)
