• 5G
• bi-dimensional assignment problem
• mixed-integer linear programming formulation
• scheduling

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.