Home > Research > Publications & Outputs > Auction based models for ticket allocation prob...

Research

Associated organisational units

Links

Text available via DOI:

Keywords

View graph of relations

Auction based models for ticket allocation problem in IT service delivery industry

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review

Published

Standard

Auction based models for ticket allocation problem in IT service delivery industry. / Deshpande, P.M.; Garg, D.; Suri, Neeraj.
2008 IEEE International Conference on Services Computing. IEEE, 2008. p. 111-118.

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review

Harvard

Deshpande, PM, Garg, D & Suri, N 2008, Auction based models for ticket allocation problem in IT service delivery industry. in 2008 IEEE International Conference on Services Computing. IEEE, pp. 111-118. https://doi.org/10.1109/SCC.2008.83

APA

Deshpande, P. M., Garg, D., & Suri, N. (2008). Auction based models for ticket allocation problem in IT service delivery industry. In 2008 IEEE International Conference on Services Computing (pp. 111-118). IEEE. https://doi.org/10.1109/SCC.2008.83

Vancouver

Deshpande PM, Garg D, Suri N. Auction based models for ticket allocation problem in IT service delivery industry. In 2008 IEEE International Conference on Services Computing. IEEE. 2008. p. 111-118 doi: 10.1109/SCC.2008.83

Author

Deshpande, P.M. ; Garg, D. ; Suri, Neeraj. / Auction based models for ticket allocation problem in IT service delivery industry. 2008 IEEE International Conference on Services Computing. IEEE, 2008. pp. 111-118

Bibtex

@inproceedings{b5d082d7fc8e46dab241b72c4ef5e247,
title = "Auction based models for ticket allocation problem in IT service delivery industry",
abstract = "In this paper, we study the service request (ticket) allocation problem which arises in every IT service delivery organization. We refer to this problem as Ticket Allocation Problem (TAP). We first show that TAP is an instance of the online scheduling problem on unrelated machines, which is known to be a hard problem. Next, we describe a baseline model, namely push model, that deals with the TAP. The push model is an industry wide standard and can be used with any known online scheduling algorithm for unrelated machines. To elaborate this further, we discuss a well known Generalized List Scheduling algorithm which can be used by the push model. We prove a bound for this algorithm's competitive ratio which beats all the known bounds. We show that push model suffers from an inherent inefficiency due to scheduler having incomplete and imprecise information regarding agents' proficiency. Finally, we show that if the scheduling algorithm used by the push model can be converted into a truthful auction mechanism then all the inefficiencies of the push model can be overcome. We refer to the resulting model as the pull model. To illustrate the idea, we map the Generalized List Scheduling algorithm into a truthful auction mechanism. Through simulation experiments, we show that the auction based pull model results in higher efficiency than the push model. {\textcopyright} 2008 IEEE.",
keywords = "Algorithms, Boolean functions, Commerce, Information technology, Mechanisms, Scheduling, Allocation problems, Services computing, Unrelated machines, Scheduling algorithms",
author = "P.M. Deshpande and D. Garg and Neeraj Suri",
year = "2008",
month = jul,
day = "7",
doi = "10.1109/SCC.2008.83",
language = "English",
isbn = "9780769532837",
pages = "111--118",
booktitle = "2008 IEEE International Conference on Services Computing",
publisher = "IEEE",

}

RIS

TY - GEN

T1 - Auction based models for ticket allocation problem in IT service delivery industry

AU - Deshpande, P.M.

AU - Garg, D.

AU - Suri, Neeraj

PY - 2008/7/7

Y1 - 2008/7/7

N2 - In this paper, we study the service request (ticket) allocation problem which arises in every IT service delivery organization. We refer to this problem as Ticket Allocation Problem (TAP). We first show that TAP is an instance of the online scheduling problem on unrelated machines, which is known to be a hard problem. Next, we describe a baseline model, namely push model, that deals with the TAP. The push model is an industry wide standard and can be used with any known online scheduling algorithm for unrelated machines. To elaborate this further, we discuss a well known Generalized List Scheduling algorithm which can be used by the push model. We prove a bound for this algorithm's competitive ratio which beats all the known bounds. We show that push model suffers from an inherent inefficiency due to scheduler having incomplete and imprecise information regarding agents' proficiency. Finally, we show that if the scheduling algorithm used by the push model can be converted into a truthful auction mechanism then all the inefficiencies of the push model can be overcome. We refer to the resulting model as the pull model. To illustrate the idea, we map the Generalized List Scheduling algorithm into a truthful auction mechanism. Through simulation experiments, we show that the auction based pull model results in higher efficiency than the push model. © 2008 IEEE.

AB - In this paper, we study the service request (ticket) allocation problem which arises in every IT service delivery organization. We refer to this problem as Ticket Allocation Problem (TAP). We first show that TAP is an instance of the online scheduling problem on unrelated machines, which is known to be a hard problem. Next, we describe a baseline model, namely push model, that deals with the TAP. The push model is an industry wide standard and can be used with any known online scheduling algorithm for unrelated machines. To elaborate this further, we discuss a well known Generalized List Scheduling algorithm which can be used by the push model. We prove a bound for this algorithm's competitive ratio which beats all the known bounds. We show that push model suffers from an inherent inefficiency due to scheduler having incomplete and imprecise information regarding agents' proficiency. Finally, we show that if the scheduling algorithm used by the push model can be converted into a truthful auction mechanism then all the inefficiencies of the push model can be overcome. We refer to the resulting model as the pull model. To illustrate the idea, we map the Generalized List Scheduling algorithm into a truthful auction mechanism. Through simulation experiments, we show that the auction based pull model results in higher efficiency than the push model. © 2008 IEEE.

KW - Algorithms

KW - Boolean functions

KW - Commerce

KW - Information technology

KW - Mechanisms

KW - Scheduling

KW - Allocation problems

KW - Services computing

KW - Unrelated machines

KW - Scheduling algorithms

U2 - 10.1109/SCC.2008.83

DO - 10.1109/SCC.2008.83

M3 - Conference contribution/Paper

SN - 9780769532837

SP - 111

EP - 118

BT - 2008 IEEE International Conference on Services Computing

PB - IEEE

ER -