Title

A note on posterior tight worst-case bounds for longest processing time schedules

Document Type

Article

Publication Date

3-14-2019

Publication Title

4OR

Volume

17

First Page

97

Last Page

107

Keywords

LPT algorithm, Multiprocessor scheduling, Parallel machines, Worst case analysis

Abstract

© 2018, Springer-Verlag GmbH Germany, part of Springer Nature. This note proposes and analyzes a posterior tight worst-case bound for the longest processing time (LPT) heuristic for scheduling independent jobs on identical parallel machines with the objective of minimizing the makespan. It makes natural remarks on the well-known posterior worst-case bounds, and shows that the proposed bound can complement the well-known posterior bounds to synergistically achieve a better posterior worst-case bound for the LPT heuristic. Moreover, it gives some insight on LPT asymptotical optimality.

This document is currently not available here.

Share

COinS