On the optimality of the LP-based algorithm for online scheduling with GoS eligibility constraints. (English) Zbl 1408.90144
Summary: We consider the online scheduling problem on \(m\) identical machines subject to the Grade of Service (GoS) eligibility constraints. The goal is to minimize the makespan. For fractional jobs that can be arbitrarily split between machines and can be processed in parallel, we provide an optimal online algorithm based on the solution of linear programming.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 68W27 | Online algorithms; streaming algorithms |
| 90C05 | Linear programming |
References:
| [1] | Azar, Y.; Naor, A.; Rom, R., The competitiveness of on-line assignments, J. Algorithms, 18, 221-237, (1995) · Zbl 0818.68026 |
| [2] | Bar-Noy, A.; Freund, A.; Naor, J., On-line load balancing in a hierarchical server topology, SIAM J. Comput., 31, 527-549, (2001) · Zbl 0994.68069 |
| [3] | Chassid, O.; Epstein, L., The hierarchical model for load balancing on two machines, J. Comb. Optim., 15, 4, 305-314, (2008) · Zbl 1145.90379 |
| [4] | Chen, X.; Xu, Z.; Dósa, G.; Han, X.; Jiang, H., Semi-online hierarchical scheduling problems with buffer or rearrangements, Inform. Process. Lett., 113, 127-131, (2013) · Zbl 1259.68255 |
| [5] | Dósa, G.; Epstein, L., Preemptive scheduling on a small number of hierarchical machines, Inform. Comput., 206, 602-619, (2008) · Zbl 1148.68332 |
| [6] | Ebenlendr, T.; Jawor, W.; Sgall, J., Preemptive online scheduling: optimal algorithms for all speeds, Algorithmica, 53, 4, 504-522, (2009) · Zbl 1166.90007 |
| [7] | Ebenlendr, T.; Sgall, J., Semi-online preemptive scheduling: one algorithm for all variants, Theory Comput. Syst., 48, 3, 577-613, (2011) · Zbl 1217.68249 |
| [8] | Hou, L.; Kang, L., Online and semi-online hierarchical scheduling for load balancing on uniform machines, Theoret. Comput. Sci., 412, 1092-1098, (2011) · Zbl 1208.90064 |
| [9] | Hou, L.; Kang, L., Online scheduling on uniform machines with two hierarchies, J. Comb. Optim., 24, 593-612, (2012) · Zbl 1261.90017 |
| [10] | Hwang, H.; Chang, S.; Hong, Y., A posterior competitiveness for List scheduling algorithm on machines with eligibility constraints, Asia-Pac. J. Oper. Res., 21, 117-125, (2004) · Zbl 1056.90067 |
| [11] | Hwang, H.; Chang, S.; Lee, K., Parallel machine scheduling under a grade of service provition, Comput. Oper. Res., 31, 2055-2061, (2004) · Zbl 1074.68529 |
| [12] | Jiang, Y., Online scheduling on parallel machines with two GoS levels, J. Comb. Optim., 16, 28-38, (2008) · Zbl 1176.90221 |
| [13] | 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) · Zbl 1108.90314 |
| [14] | Lee, K.; Hwang, H.; Lim, K., Semi-online scheduling with GoS eligibility constraints, Int. J. Prod. Econ., 153, 204-214, (2014) |
| [15] | Lee, K.; Leung, J. Y.-T.; Pinedo, M., Makespan minimization in online scheduling with machine eligibility, Ann. Oper. Res., 204, 189-222, (2013) · Zbl 1272.90015 |
| [16] | Leung, J. Y.-T.; Li, C., Scheduling with processing set restrictions: A survey, Int. J. Prod. Econ., 116, 251-262, (2008) |
| [17] | Lim, K.; Lee, K.; Chang, S., Improved bounds for online scheduling with eligibility constraints, Theoret. Comput. Sci., 412, 5211-5224, (2011) · Zbl 1233.90164 |
| [18] | Lu, X.; Liu, Z., Semi-online scheduling problems on two uniform machines under a grade of service provision, Theoret. Comput. Sci., 489-490, 58-66, (2013) · Zbl 1294.90026 |
| [19] | Luo, T.; Xu, Y., Optimal algorithm for semi-online scheduling on two machines under GoS levels, Optim. Lett., (2014) |
| [20] | 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) · Zbl 1112.90036 |
| [21] | Tan, Z.; Zhang, A., A note on hierarchical scheduling on two uniform machines, J. Comb. Optim., 20, 85-95, (2010) · Zbl 1198.90210 |
| [22] | Tan, Z.; Zhang, A., Online hierarchical scheduling: an approach using mathematical programming, Theoret. Comput. Sci., 412, 246-256, (2011) · Zbl 1207.90058 |
| [23] | Tan, Z.; Zhang, A., Online and semi-online scheduling, (Pardalos, P. M.; etal., Handbook of Combinatorial Optimization, (2013), Springer New York), 2191-2252 |
| [24] | Wu, Y.; Cheng, T. C.E.; Ji, M., Optimal algorithms for semi-online machine covering on two hierarchical machines, Theoret. Comput. Sci., 531, 37-46, (2014) · Zbl 1359.90046 |
| [25] | Zhang, A.; Jiang, Y.; Fan, L.; Hu, J., Optimal online algorithms on two hierarchical machines with tightly-grouped processing times, J. Comb. Optim., 29, 4, 781-795, (2015) · Zbl 1320.90039 |
| [26] | Zhang, A.; Jiang, Y.; Tan, Z., Optimal algorithms for online hierarchical scheduling on parallel machines, technical report, (2008), Zhejiang University |
| [27] | Zhang, A.; Jiang, Y.; Tan, Z., Online parallel machines scheduling with two hierarchies, Theoret. Comput. Sci., 410, 3597-3605, (2009) · Zbl 1171.68006 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
