Skip to Main content Skip to Navigation
Journal articles

Scheduling in a single-server with state-dependent service rates

Abstract : We consider single-server scheduling to minimize holding costs where the capacity, or rate of service, depends on the number of jobs in the system, and job sizes become known upon arrival. In general, this is a hard problem, and counter-intuitive behavior can occur. For example, even with linear holding costs the optimal policy may be something other than SRPT or LRPT, it may idle, and it may depend on the arrival rate. We first establish an equivalence between our problem of deciding which jobs to serve when completed jobs immediately leave, and a problem in which we have the option to hold on to completed jobs and can choose when to release them, and in which we always serve jobs according to SRPT. We thus reduce the problem to determining the release times of completed jobs. For the clearing, or transient system, where all jobs are present at time 0, we give a complete characterization of the optimal policy and show that it is fully determined by the cost-to-capacity ratio. With arrivals, the problem is much more complicated, and we can obtain only partial results. We show that if the cost-to-capacity ratio is linear, then all non-idling policies yield the same average cost. We further characterize the optimal policy in some special cases. For example, we show that as long as capacity is increasing in the number of jobs, LRPT stochastically minimizes the mean busy period.
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download
Contributor : Balakrishna Prabhu Connect in order to contact the contributor
Submitted on : Wednesday, May 2, 2018 - 12:01:15 PM
Last modification on : Monday, July 4, 2022 - 9:08:30 AM
Long-term archiving on: : Tuesday, September 25, 2018 - 7:15:00 PM


Files produced by the author(s)



Urtzi Ayesta, Balakrishna Prabhu, Rhonda Righter. Scheduling in a single-server with state-dependent service rates. Probability in the Engineering and Informational Sciences, Cambridge University Press (CUP), 2020, 34 (4), pp.507 - 521. ⟨10.1017/S0269964819000160⟩. ⟨hal-01783136⟩



Record views


Files downloads