Work-conserving disciplines are asymptotic optimal in completion time minimization
Authors:
- 3 June 2022
- journal article
- research article
- Published by Taylor & Francis in IISE Transactions
- Vol. 55 (6) , 616-628
Abstract
In this paper, we prove that in a stable multi-server system, where different machines are allowed to have different speeds, all work-conserving disciplines are asymptotic optimal for minimizing total completion time, if job size and interarrival time distributions have finite moments. As a byproduct of our analysis, we obtain tight upper bound on the competitive ratios of work-conserving disciplines on minimizing the metric of flow time.Keywords
Funding Information
- IITP
This publication has 19 references indexed in Scilit:
- Probabilistic asymptotic analysis of stochastic online scheduling problemsIIE Transactions, 2007
- On the Asymptotic Optimality of a Simple On-Line Algorithm for the Stochastic Single-Machine Weighted Completion Time Problem and Its ExtensionsOperations Research, 2006
- SRPT Scheduling for Web Servers2001
- Approximation Techniques for Average Completion Time SchedulingSIAM Journal on Computing, 2001
- Minimizing average completion time in the presence of release datesMathematical Programming, 1998
- Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation AlgorithmsMathematics of Operations Research, 1997
- Scheduling Parallel Machines On-LineSIAM Journal on Computing, 1995
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey1979
- Bounds on Multiprocessing Timing AnomaliesSIAM Journal on Applied Mathematics, 1969
- Various optimizers for single‐stage productionNaval Research Logistics Quarterly, 1956