Linear programming models for load balancing

DOI10.1016/0305-0548(91)90042-PMaRDI QIDQ810365zbMATH OpenFDO

Authors Manlio Gaudioso, Pasquale Legato

Publication date 1991

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0305-0548(91)90042-P

zbMATH Keywords

exact algorithmload balancingpartitioning problem

Mathematics Subject Classification ID

Computational methods for problems pertaining to operations research and mathematical programming (90-08) Deterministic scheduling theory in operations research (90B35) Linear programming (90C05) Abstract computational complexity for mathematical programming problems (90C60)

Review text

The problem of optimally sharing a given workload among a number of machines under a presently known load level is formulated both as a linear program and as a partitioning problem. An interpretation of the problem in terms of scheduling theory is described, and an exact algorithm running in O(n log n) time is presented.

Recommendations

• \(O(n)\) algorithms for load balancing in distributed computing systems
• Scheduling to Minimize Maximum Workload
• Exact dynamic load balancing of MIMD architectures with linear programming algorithms
• Optimal Load Balancing in a Multiple Processor System with Many Job Classes
• Lexicographically Minimum and Maximum Load Linear Programming Problems

Cites work

• Formulation and Solution of Nonlinear Integer Production Planning Problems for Flexible Manufacturing Systems
• scientific article; zbMATH DE number 3873052 (Why is no real title available?)
• scientific article; zbMATH DE number 3550182 (Why is no real title available?)
• Scheduling with deadlines and loss functions

Cited in

(9)

• \(O(n)\) algorithms for load balancing in distributed computing systems
• Measures of balance in combinatorial optimization
• The load balancing problem
• Lexicographically Minimum and Maximum Load Linear Programming Problems
• Scheduling to Minimize Maximum Workload
• One-dimensional partitioning for heterogeneous systems: theory and practice
• Analysis and modelling of a production line in a corrugated box factory
• scientific article; zbMATH DE number 2078926 (Why is no real title available?)
• Principles of Distributed Systems

This page was built for publication: Linear programming models for load balancing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q810365)