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

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

0.00 Avg rating0 Votes
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: , ,
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.