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

Y. P. Aneja, S. N. Kabadi and A. Nagar

Naval Research Logistics (NRL), 1998, vol. 45, issue 3, 297-311

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. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 297–311, 1998

Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1002/(SICI)1520-6750(199804)45:33.0.CO;2-2

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:45:y:1998:i:3:p:297-311

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().