A Direct Proof of the 4/3 Bound of LPT Scheduling Rule

DOI

10.2991/fmsmt-17.2017.102How to use a DOI?

Keywords

Scheduling, Parallel Machines, Longest Processing Time First, Worst-case Analysis.

Abstract

The problem of scheduling independent jobs on identical parallel machines for minimizing makespan has been intensely studied in the literature. One of the most popular constructive algorithms for this problem is the LPT (Longest Processing Time First) rule whose approximation ratio has been proved by contradiction. A direct proof of its approximation ratio is presented, which can be regarded as an acquisition of knowledge by deductive means.

Copyright

© 2017, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Xin Xiao
PY  - 2017/04
DA  - 2017/04
TI  - A Direct Proof of the 4/3 Bound of LPT Scheduling Rule
BT  - Proceedings of the 2017 5th International Conference on Frontiers of Manufacturing Science and Measuring Technology (FMSMT 2017)
PB  - Atlantis Press
SP  - 486
EP  - 489
SN  - 2352-5401
UR  - https://doi.org/10.2991/fmsmt-17.2017.102
DO  - 10.2991/fmsmt-17.2017.102
ID  - Xiao2017/04
ER  -