Article ID: | iaor1999186 |
Country: | United States |
Volume: | 45 |
Issue: | 3 |
Start Page Number: | 297 |
End Page Number: | 311 |
Publication Date: | Apr 1998 |
Journal: | Naval Research Logistics |
Authors: | Aneja Y.P., Kabadi S.N., Nagar A. |
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.