The exact LPT-bound for maximizing the minimum completion time

doi:10.1016/0167-6377(92)90004-M

Operations Research Letters

Volume 11, Issue 5, June 1992, Pages 281-287

https://doi.org/10.1016/0167-6377(92)90004-M Get rights and content

Abstract

We consider the problem of assigning a set of jobs to a system of m identical processors in order to maximize the earliest processor completion time. It was known that the LPT-heuristic gives an approximation of worst case ratio at most $34$ . In this note we show that the exact worst case ratio of LPT is (3m − 1)/(4m − 2).

References (3)

E.G. Coffman et al.
A performance guarantee for the greedy set-partitioning algorithm
Acta Inform.
(1984)

There are more references available in the full text version of this article.

Cited by (78)

Load balancing for multi-beam additive manufacturing systems
2023, Additive Manufacturing
As powder bed fusion (PBF) additive manufacturing (AM) becomes a more mature field, system configurations are gradually moving away from the classic single heat source, layer-by-layer system configurations towards unconventional system configurations that offer higher throughput. Higher throughput systems allow PBF systems to be considered for a larger variety of industrial applications. However, the inclusion of multiple heat sources, or beams, also increases the complexity of the control schemes needed. For multi-beam systems with overlapping fields of view, the distribution of workload, or load balancing, across these beams directly affects the total print time for a build. Additionally, the probability of any beam failing in a multi-beam system increases with the number of beams. While manual methods of load balancing and dealing with beam failures are reasonable for current generation multi-beam systems, as system configurations become more complex, manual methods will become prohibitively inefficient. This paper introduces two different ways to load balance multi-beam systems of various configuration types, regardless of their complexity, which are highly performant. A consequence of this performance is the enablement of on-the-fly load balancing in the event a beam fails, thus improving system robustness.
Reducing price of anarchy of selfish task allocation with more selfishness
2013, Theoretical Computer Science
In this paper we consider the task allocation problem from a new game theoretic perspective. We assume that tasks and machines are both controlled by selfish agents with two distinct objectives, which stands in contrast to the passive role of machines in the traditional model of selfish task allocation. To characterize the outcome of this new game where two classes of players interact, we introduce the concept of dual equilibrium. We prove that the price of anarchy with respect to dual equilibria is 1.4, which is considerably smaller than the counterpart 2 in the traditional model. Our study shows that activating more freedom and selfishness in a game may bring about a better global outcome.
Polynomial-time Combinatorial Algorithm for General Max–Min Fair Allocation
2024, Algorithmica
Optimization of Inter-group Criteria for Clustering with Minimum Size Constraints
2024, arXiv
Quantum mutual information redistribution in a pure tripartite state by a number partitioning algorithm
2023, Physical Review A
Quantum mutual information redistribution by Number Partitioning algorithm
2023, arXiv

View all citing articles on Scopus

^☆: This paper was supported by a grant from the Hungarian Academy of Sciences (OTKA Nr. 2037). Part of this research was done during the second and third authors' stay at József Attila University.

View full text

The exact LPT-bound for maximizing the minimum completion time☆

Abstract

A performance guarantee for the greedy set-partitioning algorithm

Acta Inform.