ETD

Archivio digitale delle tesi discusse presso l'Università di Pisa

Tesi etd-02162021-145424


Tipo di tesi
Tesi di laurea magistrale
Autore
ANSUINI, GIULIA
URN
etd-02162021-145424
Titolo
Bi-dimensional assignment problems for 5G antenna scheduling
Dipartimento
MATEMATICA
Corso di studi
MATEMATICA
Relatori
relatore Prof. Frangioni, Antonio
Parole chiave
  • bi-dimensional assignment problem
  • scheduling
  • 5G
  • mixed-integer linear programming formulation
Data inizio appello
05/03/2021
Consultabilità
Completa
Riassunto
This Thesis studies a bi-dimensional assignment problem arising from 5G antenna scheduling. The resources are airframes, that are vectors of Resource Blocks (RBs) periodically allocated to the tasks at each slot of time (TTI) by the base station. Each RB can be assigned to only one tasks in each TTI. Each task has a period and a required number of RBs, that must be contiguous blocks of the airframe vector and always be the same at each TTI that the task is aired. The aim of the problem is to find a RB schedule for a given set of new tasks to be inserted considering a set of old tasks already in place. This is a bi-dimensional assignment problem in that the RBs must be allocated both in time and in space without generating collisions. The Thesis start by reviewing the literature in Periodic Scheduling Problem (PSP), one of the most studied topics in Operative Research since it arises in many different areas such as aircraft crew scheduling, preventive maintenance scheduling, public transport planning, process control, and real-time processing. Thanks to the variety of applications there are many of interpretations and analyses of the PSP which may be useful for our problem; however, all the variants in the literature are, at best, relaxations of our own, since none considers at the same time the space conflicts (due to the position of the tasks in the airframe) and the time conflicts (due to tasks being periodical). Hence we introduce several new different Mixed-Integer Linear Programming (MILP) formulations of the problem. The main issue of these formulations is the way in which the collision between the tasks are identified, and we propose two different ways to manage this: Conflict-Based and Matrix-Based. For each of these we introduce four formulations of increasing size and complexity depending on the fact that the old tasks are considered fixed in their current positions or moveable to facilitate the placement of new tasks, and that all the new ones must necessarily be inserted, or we are allowed to only insert a subset. This allows us to solve them in sequence, starting from the more “rigid” ones (with less degrees of freedom) and moving up if these have no solution, which is often quickly identified. All the variants of the model have been solved with the general-purpose, state-of-the-art, off-the-shelf MILP solver CPLEX. Since these models can be very-large-size, even constructing them can be costly; we discuss different ways of implementing them using the CPLEX Callable Library. Finally, the models are tested on several instances corresponding to a realistic 5G setting. Our results show that the sequential approach is indeed in general more efficient than the one where only the most general formulation is immediately solved, and that even large instances can often be solved quickly depending on the characteristics of the 5G scenario.
File