Home > Research > Publications & Outputs > A nearly-optimal index rule for scheduling of u...

Electronic data

  • infocom-abandonment-v7_cameraready

    Rights statement: ©2011 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE." "This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

    Accepted author manuscript, 310 KB, PDF document

Links

Text available via DOI:

View graph of relations

A nearly-optimal index rule for scheduling of users with abandonment

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSNConference contribution/Paperpeer-review

Published
Close
Publication date04/2011
Host publicationINFOCOM, 2011 Proceedings IEEE
PublisherIEEE
Pages2849-2857
Number of pages9
ISBN (Print)9781424499199
<mark>Original language</mark>English
EventIEEE INFOCOM 2011 - IEEE Conference on Computer Communications - Shanghai, China, United Kingdom
Duration: 10/04/201115/04/2011

Conference

ConferenceIEEE INFOCOM 2011 - IEEE Conference on Computer Communications
Country/TerritoryUnited Kingdom
Period10/04/1115/04/11

Conference

ConferenceIEEE INFOCOM 2011 - IEEE Conference on Computer Communications
Country/TerritoryUnited Kingdom
Period10/04/1115/04/11

Abstract

We analyze a comprehensive model for multi-class job scheduling accounting for user abandonment, with the objective of minimizing the total discounted or time-average sum of linear holding costs and abandonment penalties. We assume geometric service times and Bernoulli abandonment probabilities. We solve analytically the case in which there are 1 or 2 users in the system to obtain an optimal index rule. For the case with more users we use recent advances from the restless bandits literature to obtain a new simple index rule, denoted by AJN, which we propose to use also in the system with arrivals. In the problem without abandonment, the proposed rule recovers the cμ-rule which is well-known to be optimal both without and with arrivals. Under certain conditions, our rule is equivalent to the cμ/θ-rule, which was recently proposed and shown to be asymptotically optimal in a multi-server system with overload conditions. We present results of an extensive computational study that suggest that our rule is almost always superior or equivalent to other rules proposed in the literature, and is often optimal.

Bibliographic note

©2011 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE." "This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.