Minimizing mean absolute deviation of job completion times from the mean completion time

Gur Mosheiov

Naval Research Logistics (NRL), 2000, vol. 47, issue 8, 657-668

Abstract: In many scheduling environments it is recommended to control the balance of the performance of individual jobs, e.g., the variability of the job completion or waiting times. In service systems, for example, it may be important to provide customers with an identical or similar service quality, as measured by their time in system or waiting time. Several measures of variation have been studied in scheduling literature in this context; our paper considers the measure of Mean Absolute Deviation of job completion times from the Mean Completion time (MADMC). Recently, Aneja et al. (1998) proved that minimizing MADMC on a single‐machine is NP‐hard. We introduce a simple heuristic and an easily obtained lower bound on the optimal MADMC value. We prove that the worst case optimality gap of the heuristic is bounded by the constant 2, and that this bound is tight. Better worst case bounds can be achieved in special cases. Both the heuristic and the lower bound are shown to be asymptotically accurate under very general conditions. Both the heuristic and lower bound are extended to parallel identical machines. In our extensive numerical study we show that the heuristic produces, both in the single‐machine and in the multi‐machine case, extremely close‐to‐optimal schedules. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 657–668, 2000

Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/1520-6750(200012)47:83.0.CO;2-1

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:47:y:2000:i:8:p:657-668

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 ().