Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Semi-online hierarchical scheduling for $$l_p$$ l p -norm load balancing with buffer or rearrangements

Semi-online hierarchical scheduling for $$l_p$$ l p -norm load balancing with buffer or... In this paper, we consider the semi-online hierarchical scheduling for load balancing on two identical machines. In the problem, the jobs are available online over list and the objective is to minimize the $$l_p$$ l p -norm of the two machines’ loads. Two semi-online versions are investigated: the buffer version and the rearrangement version. We design a unified optimal semi-online algorithm for both models. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png 4OR Springer Journals

Semi-online hierarchical scheduling for $$l_p$$ l p -norm load balancing with buffer or rearrangements

Qi, Xianglai; Yuan, Jinjiang
4OR , Volume 15 (3) – Nov 25, 2016
Download PDF
12 pages

Loading next page...
 
/lp/springer-journals/semi-online-hierarchical-scheduling-for-l-p-l-p-norm-load-balancing-SPGUUcMaR8
Publisher
Springer Journals
Copyright
Copyright © 2016 by Springer-Verlag Berlin Heidelberg
Subject
Business and Management; Operation Research/Decision Theory; Optimization; Industrial and Production Engineering
ISSN
1619-4500
eISSN
1614-2411
DOI
10.1007/s10288-016-0334-y
Publisher site
See Article on Publisher Site

Abstract

In this paper, we consider the semi-online hierarchical scheduling for load balancing on two identical machines. In the problem, the jobs are available online over list and the objective is to minimize the $$l_p$$ l p -norm of the two machines’ loads. Two semi-online versions are investigated: the buffer version and the rearrangement version. We design a unified optimal semi-online algorithm for both models.

Journal

4OR – Springer Journals

Published: Nov 25, 2016

References

  • Ancient and new algorithms for load balancing in the $$l_p$$ l p norm
    Avidor, A; Azar, Y; Sgall, J
  • Online load balancing in a hierarchical server topology
    Bar-Noy, A; Freund, A; Naor, J
  • Worst-case analysis of a placement algorithm related to storage allocation
    Chandra, AK; Wong, CK
  • Semi-online hierarchical scheduling problems with buffer or rearrangements
    Chen, X; Xu, ZZ; Dósa, G; Han, X; Jiang, H
  • Optimization and approximation in deterministic sequencing and scheduling: a survey
    Graham, RL; Lawler, EL; Lenstra, JK; Rinnooy Kan, AHG
  • Parallel machine scheduling under a grade of service provision
    Hwang, HC; Chang, SY; Lee, K
  • Optimal online algorithms for scheduling on two identical machines under a grade of service
    Jiang, YW; He, Y; Tang, CM
  • Semi on-line algorithms for the partition problem
    Kellerer, H; Kotov, V; Speranza, MG; Tuza, Z
  • Makespan minimization in online scheduling with machine eligibility
    Lee, K; Leung, JY-T; Pinedo, ML
  • Scheduling with processing set restrictions: a survey
    Leung, JY-T; Li, C-L
  • Semi-online scheduling on two machines under a grade of service provision with bounded processing times
    Liu, M; Chu, CB; Xu, YF; Zheng, FF
  • Semi-online scheduling with two GoS levels and unit processing time
    Luo, TB; Xu, YF; Luo, L; He, CZ
  • Online and semi-online scheduling of two machines under a grade of service provision
    Park, J; Chang, SY; Lee, K
  • Online hierarchical scheduling: an approach using mathematical programming
    Tan, ZY; Zhang, A
  • Optimal semi-online scheduling algorithms on two parallel identical machines under a grade of service provision
    Wu, Y; Ji, M; Yang, Q
  • Optimal online algorithms on two hierarchical machines with tightly-grouped processing times
    Zhang, A; Jiang, YW; Fan, LD; Hu, JL