OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Dynamic fluid-based scheduling in a multi-class abandonment queue

Larranaga, Maialen and Ayesta, Urtzi and Verloop, Maaike Dynamic fluid-based scheduling in a multi-class abandonment queue. (2013) Performance Evaluation, 70 (10). 841-858. ISSN 0166-5316

(Document in English)

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

Official URL: http://dx.doi.org/10.1016/j.peva.2013.08.009


We investigate how to share a common resource among multiple classes of customers in the presence of abandonments. We consider two different models: (1) customers can abandon both while waiting in the queue and while being served, (2) only customers that are in the queue can abandon. Given the complexity of the stochastic optimization problem we propose a fluid model as a deterministic approximation. For the overload case we directly obtain that the c˜µ/θ rule is optimal. For the underload case we use Pontryagin’s Maximum Principle to obtain the optimal solution for two classes of customers; there exists a switching curve that splits the two-dimensional state-space into two regions such that when the number of customers in both classes is sufficiently small the optimal policy follows the c˜µ-rule and when the number of customers is sufficiently large the optimal policy follows the c˜µ/θ-rule. The same structure is observed in the optimal policy of the stochastic model for an arbitrary number of classes. Based on this we develop a heuristic and by numerical experiments we evaluate its performance and compare it to several index policies. We observe that the suboptimality gap of our solution is small.

Item Type:Article
Additional Information:Thanks to Elsevier editor. The definitive version is available at http://www.sciencedirect.com The original PDF of the article can be found at Performance Evaluation website : http://www.sciencedirect.com/science/journal/01665316
HAL Id:hal-01130331
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 > Euskal Herriko Unibertsitatea - EHU (SPAIN)
Laboratory name:
Deposited On:11 Mar 2015 15:12

Repository Staff Only: item control page