This article investigates a two-user competitive scheduling problem. The problem arises in a Universal Mobile Telecommunication System (UMTS) developed within the European IST project FUTURE: given two mobile terminals, one wants to maximize the on-time data packets transmitted to one user, while guaranteeing a certain amount of on-time data packets to the other. We show that the problem is NP-hard, despite peculiar properties of data and solutions. We propose a fast Lagrangian heuristic able to cope with a severe real-time requirement, and compare it to a greedy-like heuristic on a set of practical instances.
A Competitive Scheduling Problem and its Relevance to UMTS Channel Assignment
ARBIB, CLAUDIO;SMRIGLIO, STEFANO
2004
Abstract
This article investigates a two-user competitive scheduling problem. The problem arises in a Universal Mobile Telecommunication System (UMTS) developed within the European IST project FUTURE: given two mobile terminals, one wants to maximize the on-time data packets transmitted to one user, while guaranteeing a certain amount of on-time data packets to the other. We show that the problem is NP-hard, despite peculiar properties of data and solutions. We propose a fast Lagrangian heuristic able to cope with a severe real-time requirement, and compare it to a greedy-like heuristic on a set of practical instances.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
