Competitive strategies for an online generalized assignment problem with a service consecution constraint

Feifeng Zheng, Yongxi Cheng, Yinfeng Xu and Ming Liu

European Journal of Operational Research, 2013, vol. 229, issue 1, 59-66

Abstract: This work studies a variant of the online generalized assignment problem, where there are m⩾2 heterogeneous servers to process n requests which arrive one by one over time. Each request must either be assigned to one of the servers or be rejected upon its arrival, before knowing any information of future requests. There is a corresponding weight (or revenue) for assigning each request to a server, and the objective is to maximize the total weights obtained from all the requests. We study the above problem with a service consecution constraint, such that at any time each server is only allowed to process up to d consecutive requests.

Keywords: Assignment; Online strategy; Service consecution constraint; Competitive ratio; Lower bound (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221713001227
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:229:y:2013:i:1:p:59-66

DOI: 10.1016/j.ejor.2013.02.004

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().