Optimal online algorithms on two hierarchical machines with tightly-grouped processing times. (English) Zbl 1320.90039
Summary: This paper considers an online hierarchical scheduling problem on two parallel identical machines. The objective is to minimize the makspan. It is assumed that all jobs have bounded processing times in between \(p\) and \(rp\), where \(p>0\) and \(r\geq 1\). We first improve a previous result by giving an optimal online algorithm for the non-preemptive version. For the preemptive version, we present an optimal preemptive algorithm without introducing idle time for all \(r\geq 1\). If the algorithm is allowed to use idle time, we show that the semi-online information that jobs are tightly-grouped cannot help improve the bound of the pure online problem.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
References:
| [1] | Bar-Noy A, Freund A, Naor J (2001) On-line load balancing in a hierarchical server topology. SIAM Journal on Computing. 31:527-549 · Zbl 0994.68069 · doi:10.1137/S0097539798346135 |
| [2] | Chassid O, Epstein L (2008) The hierarchical model for load balancing on two machines. Journal of Combinatorial Optimization. 15(4):305-314 · Zbl 1145.90379 · doi:10.1007/s10878-007-9078-0 |
| [3] | Crescenzi P, Gambosi G, Penna P (2004) On-line algorithms for the channel assignment problem in cellular networks. Discrete Applied Mathematics. 137:237-266 · Zbl 1047.90007 · doi:10.1016/S0166-218X(03)00341-X |
| [4] | Dósa G, Epstein L (2008) Preemptive scheduling on a small number of hierarchical machines. Information and Computation. 206(5):602-619 · Zbl 1148.68332 · doi:10.1016/j.ic.2007.11.004 |
| [5] | He Y, Zhang G (1999) Semi on-line scheduling on two identical machines. Computing. 62:179-187 · Zbl 0940.90032 · doi:10.1007/s006070050020 |
| [6] | Jiang Y (2008) Online scheduling on parallel machines with two GoS levels. Journal of Combinatorial Optimization. 16:28-38 · Zbl 1176.90221 · doi:10.1007/s10878-007-9095-z |
| [7] | Jiang Y, He Y, Tang C (2006) Optimal online algorithms for scheduling on two identical machines under a grade of service. Journal of Zhejiang University Science. 7A:309-314 · Zbl 1108.90314 · doi:10.1631/jzus.2006.A0309 |
| [8] | Liu M, Chu C, Xu Y, Zheng F (2011) Semi-online scheduling on 2 machines under a grade of service provision with bounded processing times. Journal of Combinatorial Optimization. 21:138-149 · Zbl 1209.90179 · doi:10.1007/s10878-009-9231-z |
| [9] | Park J, Chang S, Lee K (2006) Online and semi-online scheduling of two machines under a grade of service provision. Operations Research Letters. 34:692-696 · Zbl 1112.90036 · doi:10.1016/j.orl.2005.11.004 |
| [10] | Tan Z, Zhang A (2010) A note on hierarchical scheduling on two uniform machines. Journal of Combinatorial Optimization. 20:85-95 · Zbl 1198.90210 · doi:10.1007/s10878-008-9195-4 |
| [11] | Tan Z, Zhang A (2011) Online hierarchical scheduling: An approach using mathematical programming. Theoretical Computer Science. 412:246-256 · Zbl 1207.90058 · doi:10.1016/j.tcs.2009.08.014 |
| [12] | Wu Y, Ji M, Yang Q (2012) Optimal semi-online scheduling algorithms on two parallel identical machines under a grade of service provision. International Journal of Production Economics. 135:367-371 · doi:10.1016/j.ijpe.2011.07.021 |
| [13] | Zhang A, Jiang Y, Tan Z (2009) Online parallel machines scheduling with two hierarchies. Theoretical Computer Science. 410:3597-3605 · Zbl 1171.68006 · doi:10.1016/j.tcs.2009.04.007 |
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.
