OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

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

Ayesta, Urtzi and Prabhu, Balakrishna and Righter, Rhonda Scheduling in a single-server queue with state-dependent service rates. (2019) Probability in the Engineering and Informational Sciences. ISSN 0269-9648

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: https://doi.org/10.1017/S0269964819000160


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.

Item Type:Article
Audience (journal):International peer-reviewed journal
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Other partners > IKERBASQUE (SPAIN)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > University of California - UC Berkeley (USA)
Other partners > University of the Basque Country - UPV/EHU (SPAIN)
Laboratory name:
Deposited On:30 Jun 2020 07:40

Repository Staff Only: item control page