z-logo
Premium
Minimizing mean absolute deviation of job completion times from the mean completion time
Author(s) -
Mosheiov Gur
Publication year - 2000
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(200012)47:8<657::aid-nav4>3.0.co;2-1
Subject(s) - upper and lower bounds , absolute deviation , scheduling (production processes) , heuristic , mathematical optimization , computer science , bounded function , asymptotically optimal algorithm , mathematics , constant (computer programming) , context (archaeology) , statistics , mathematical analysis , paleontology , biology , programming language
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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here