✦ LIBER ✦

Minimizing weighted mean absolute deviation of flow times in single machine systems

✍ Scribed by Y. P. Aneja; S. N. Kabadi; A. Nagar

Publisher: John Wiley and Sons
Year: 1998
Tongue: English
Weight: 94 KB
Volume: 45
Category: Article
ISSN: 0894-069X
DOI: 10.1002/(sici)1520-6750(199804)45:3<297::aid-nav4>3.0.co;2-2

No coin nor oath required. For personal study only.

✦ Synopsis

We discuss the problem of scheduling several jobs on a single machine with the objective of minimizing the weighted mean absolute deviation of flow times around the weighted mean flow time. We first show that the optimal schedule is W-shaped. For the unweighted case, we show that all optimal schedules are V-shaped. This characterization enables us to show that the problem is NP-hard. We then provide a pseudopolynomial algorithm for the unweighted problem. Finally, we consider three heuristic algorithms for the unweighted problem and report computational experience with these algorithms. ᭧ 1998