Article ID: | iaor2005959 |
Country: | Netherlands |
Volume: | 44 |
Issue: | 2 |
Start Page Number: | 132 |
End Page Number: | 141 |
Publication Date: | Jul 2004 |
Journal: | Networks |
Authors: | Arbib Claudio, Smriglio Stefano, Servilio Mara |
Keywords: | scheduling |
This article investigates a two-user competitive scheduling problem. The problem arises in a Universal Mobile Telecommunications 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 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.