Bi-dimensional assignment problems for 5G antenna scheduling

C

L

M

T

ESI DI

L

AUREA

M

AGISTRALE

Bi-dimensional assignment problem

for 5G antennas scheduling

5 Marzo 2021

C

ANDIDATO

Giulia Ansuini

R

ELATORE

Prof. Antonio Frangioni

C

ONTRORELATRICE

Prof.ssa Maria Grazia Scutellà

Contents

1 Periodic Scheduling: State of the Art 4

1.1 Problem definition . . . 4

1.2 Literature about Periodic Scheduling problem . . . 5

1.2.1 Exact algorithm for single resource’s case . . . 8

1.2.2 Heuristic for Periodic Scheduling problem . . . 10

1.2.3 New approach: Temporal Bin Packing problem . . . 10

1.3 Relationships with our model . . . 17

2 Definition of models 20 2.1 Conflict-Based model . . . 21 2.1.1 CB-Fixed-Forced . . . 22 2.1.2 CB-Moveable-Forced . . . 24 2.1.3 CB-Fixed-Optional . . . 25 2.1.4 CB-Moveable-Optional . . . 26 2.2 Matrix-Based Model . . . 27 2.2.1 MB-Fixed-Forced . . . 28 2.2.2 MB-Moveable-Forced . . . 29 2.2.3 MB-Fixed-Optional . . . 29 2.2.4 MB-Moveable-Optional . . . 30

2.2.5 Another formulation for MB-F-* . . . 30

3 Implementation of models 32 3.1 Implementation . . . 32

3.1.1 Construction of Conflict-Based Model . . . 32

3.1.2 Construction of Matrix-Based Model . . . 33

3.2 Data generation . . . 38

4 Analysis of the results 39 4.1 Choice of parameters . . . 39

4.2 Sequential approach . . . 41

4.3 Comparison of Conflict-Based and Matrix-Based Models . . . 44

Introduction

This Thesis studies a bi-dimensional assignment problem arising from 5G an-tenna scheduling. The resources are airframes, that are vectors of Resource Blocks (RBs) periodically allocated to the tasks at each slot of time, Transmis-sion Time Interval (TTI), by the base station. Each RB can be assigned to only one task 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 an 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. At first the problem looks like a generalization of Periodic Scheduling Problem and Bin Packing Problem together, hence we start by reviewing the specific literature.

First of all, the thesis starts from 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 process-ing. Thanks to the variety of applications there are many of interpretations and analyses of the PSP which may be useful for our problem; we focused on the PSP used in the context of processor and operations, since its formulation is the most adaptable to our case of airframe and tasks. For this kind of issue we analyzed an exact algorithm for PSP with single resource and a heuristic where instead of periodic constraint it is used a new request called proportion-ate progress. But these approaches do not consider the space dimension of our problem, all the periodic operations have a duration in time and no size in space. Hence we moved our focus to the other way to look at our problem, it can be seen as a Bin Packing Problem with a new dimension, the time. This problem is introduced recently as Temporal Bin Packing Problem, its objects have a time windows in which they must be scheduled and a size that con-sumes the capacity of the bin. The difference from our case is that our tasks have periods, not durations, and our airframes are made from ordered RBs,

indeed also the position of the tasks in the airframe is relevant.

In conclusion 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 collisions between the tasks are identified, and we propose two different ways to manage these: Conflict-Based and Matrix-Based. For the first model we describe the

position of tasks with two sets of binary variables one for each dimension: x_i,t

that represents if task i is assigned to the airframe t and yi,hthat indicates if

the first RB assigned to i is in position h in the airframe. The first section of the formulation is made from assignment constraints, the second one is composed from conflict constraints: thanks to the definition of new variables and new sets of indices that describe the collision between tasks in time and space we manage the conflicts in both the dimensions. The second model uses only a set

of binary variables with three indices xi,h,t, in this way one variable describes

both space and time allocation of a task. Also in this model in the first part there are assignment constraints and in the second one the conflict constraints, in this model we do not create new variables but only a new set of indices to describe and prohibit collisions in time and space.

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. For some of these formulations we introduced new constraints and variables, for example we need new inequalities to manage the conflicts between new moveable tasks and fixed old ones.

The formulation of all these variants 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. In particular in the first attempt the old tasks are fixed and all the new ones must be placed, if this request is unfeasible, we allow more degrees of freedom to the tasks. The second model consider the old tasks moveable in order to place all the new tasks, also this request can be unfeasible. Instead the last two formulations have always a solution, since we can schedule only a subset of new tasks, while the old ones are fixed or moveable.

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. For the Conflict-Based

model we chose to create variables and constraints separately and add to the model with the functions CPXaddrows and CPXaddcols, while for the Matrix-Based model we copied the entire model in the structure of CPLEX with the function CPXcopylp. Both ways have positive and negative aspects, for example the Matrix-Based model has optimized code, but it supports the constructions of model with limited size; the Conflict-Based model has difficult constraints to optimize, but it generates smaller models so it can solve bigger instances.

Finally, the models are tested on several instances corresponding to a re-alistic 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. In the last chapter there is the analysis of this results and the discussion on parameters and best approach.

Chapter 1

Periodic Scheduling: State of the

Art

1.1

Problem definition

Our problem can be labelled as scheduling problem, indeed we have tasks to which resources are to be allocated. The resources are airframes, that are vectors consist of Resource Blocks (RBs) enumerate from 1 to M . They are allocated periodically to a subset of tasks at each slot of time by the base sta-tion. The time unit is called Transmission Time Interval and depends on the

technology used, it can range from 62, 4µs to 1 ms. The RBs can be assigned

to only one task in each TTI and they have to verify some constraints. Let

N = {1, . . . , n} be the set of periodic tasks, each i ∈ N is an ordered pair

(πi, wi) where πi is the task period and wi is the required number of RBs.

When the RBs are allocated to a task in a TTI we say that the task is aired. The RBs assigned to a task must be contiguous blocks of the airframe vector and at each TTI that the task is aired the designated RBs must be always the same. The aim of this problem is to find a schedule for a given task’s set N, i.e. an allocation of RBs to its tasks in a hyperperiod H. This latter is defined as the

least common multiple of all the tasks periods, H = lcmi∈N(πi), and it is the

minimum number of TTI after which the schedule is repeated. A schedule S is

uniquely defined by n ordered pairs(h_i, t_i), one for each task i ∈ N, where:

• hi ∈ {1, . . . , M − wi + 1} represents the position of the first RBs of the

contiguous w_i blocks{hi, . . . , M− wi+ 1} that task i needs;

• t_i ∈ {0, . . . , πi− 1} represents the first TTI at which the task i is aired the

first time.

When these parameters are fixed, all the allocations of a task in the hyperpe-riod are decided, indeed the same RBs are scheduled for the same task in the following TTIs: t_i, ti+ πi, ti+ 2πi, . . . , ti+  H πi − 1 ‹ πi.

A schedule S is feasible for a set N of tasks, if all the tasks have assigned the required RBs under the above constraints. A set of tasks N is said to be schedu-lable if there exist a feasible schedule S for it. The presented problem looks like a generalization of Periodic Scheduling problem and Bin Packing problem together, indeed there are constrains both in time and space dimension. We can consider each airframe as a bin of size M and each task as a item with size

w_i. In this representation the H bins, one for each TTI in the hyperperiod, are

partitioned by each item i∈ N into _πH_i subsets of sizeπ_i:

{0, . . . , πi− 1} , {πi, . . . , 2πi− 1} , . . . , § H πi − 1 ‹ πi, . . . , H− 1 ª . In time dimension the tasks must be scheduled periodically, but differently from the Periodic Scheduling problem they have all the same duration equal to 1 TTI. In correspondence of the assignment of a task to a bin in a subset of its partition, there are multiple assignments of the same item to other bins, one in each subset that depend on its period. The allocations of the bins of the subsets are not independent due to of periodicity’s request. In space dimension the tasks have a size and they have to fit in bins of capacity M , while verifying the contiguity constraint. In each periodic assignment of the same task the position of the RBs is important, so testing capacity for each bin is not enough to guarantee feasibility of the schedule. Hence the model must be handled contemporary both the conflicts in time and in space of the assignments. To solve our problem in the next sections there are presented some results on related topics.

1.2

Literature about Periodic Scheduling problem

Periodic Scheduling problem, PSP for short, is one of the most studied argu-ment in Operative Research, because it arises in many different areas as air-craft crew scheduling, preventive maintenance scheduling, public transport planning, process control and real-time processing. This problem deals with periodic assignment of a set of jobs to a finite set of resources under some con-straints and this configuration can describe several real circumstances. Thanks

to the variety of applications there are a lot of interpretations and analysis of the problem, a large portion of the literature has recently grown up around the public transport and airline crew scheduling. For these implementations the input data about jobs and resources are modelled on graphs and they are

devel-oped from the Periodic Event Scheduling problem introduced in[6] by Serafini

and Ukovich. On the other side the PSP is used in the context of processors and

operations and it was introduced for the first time in[4], this branch of studies

is more useful for our purpose than the other, indeed our problem has not a structure that can be easily modelled with a graph, hence we will focus on this second class of problems. The most general definition of PSP is the following:

let {x1, . . . , xn} be a set of operations, each xi is characterized by a period πi

and a duration d_i, the operation x_i must to be performed by a resource each

πi slots of time and the process takes di time, di ≤ πi.

PSP can be classified in • single resource • multiple resources

and this is fundamental for the complexity of the problem, when the planning deals with a single resource there are several optimal algorithms, but none of them can be extended to a multiple resources, indeed, as Liu pointed out in [4], have multiple resources free for use add a surprising amount of difficult instead of a single resource.

Another classification is between • preemptive

• nonpreemptive

periodic scheduling, if the preemption is allowed the process of a job can be interrupted to give priority to another job more important and, after the end of the second job, the first can be completed. In the nonpreemptive scheduling problem a schedule S is uniquely defined by the starting time of any operation {s1, . . . , sn}, where si is the starting time of xi with 0≤ si ≤ πi ∀i ∈ {1, . . . , n},

and consequently s_i + d_i− 1 is the ending time, all the executions run on the

same processor without interruption. When we are planning periodic opera-tions, we obtain a periodic scheduling: a schedule S is called periodic with

period H if for all instants t ∈ Z and for any operation xi is true that xi is

exe-cuted at time t if and only if x_i is executed at time t+ H. To make it possible

must be worth thatπi|H ∀i, hence the minimum period is H = lcm(π1, . . . ,πn).

Usually the aim is to minimize the number of processors used for the schedule of all the operations.

• constrained case • unconstrained case

if it is required to use the same processor for all the implementations of one job this is called the constrained case, instead if all the executions of an operation can be run in any processors is the unconstrained case.

Constrained Periodic Scheduling is aN P problem and we can prove this

for the decisional formulation of CPS: given a set of operations, each of them with period and duration, and an integer k we check if exists a constrained nonpreemptive schedule of all the operations with at most k processors. For the proof of complexity we restrict the problem CSP to the instances that have

all the operations with the same periodπi = p [3].

Theorem 1.1. CPS isN P -complete in the strong sense.

Proof. We can obtain the thesis with a proof by reduction to Bin Packing

prob-lem, BPP for short, which is N P -complete in the strong sense. For BPP we

consider a set of items A= {a₁, . . . , a_n}, each of them with size si, i∈ {1, . . . , n}, an integer B that represents the capacity of all bins and an integer k. In the decisional formulation the aim is to check if A can be partitioned in disjoint subsets A₁, . . . , A_k such thatP

i:ai∈Ajsi ≤ B ∀ j ∈ {1, . . . , K}. To transform this

instance of BPP in an instance of CSP we define for each item ai an operation

x_i with duration d_i = s_i and π_i = B. We can observe that a subset of periodic

operations can be run in the same processor if and only if the corresponding

items can be collocated in a bin. Hence the items {a1, . . . , an} can be packed

in k bins if and only if the operations {x1, . . . , xn} can be performed with k

processors.

CPS is part of the hard problems, hence it is known that there is no efficient

optimization algorithm. To solve this problem in[3] approximation algorithms

are introduced. In the case of identical periods it has already been proven that the CSP can be transform in a BPP, hence the several approximation algorithms for the BPP can be apply to the CSP. Instead for the case with arbitrary periods

this is not applicable and in[3] a new algorithm is presented. The main idea is

that if one or more operations are assigned to one processor, then the idle time of the processor can be represented by one or more periodic intervals. So the problem of assign periodic operations to processors becomes the problem of assign periodic operations to periodic intervals and the iterative algorithm try all the schedule of operations to intervals and it chooses the best, namely the one with minimum idle time. This problem can be considered as a maximum weight matching problem on a bipartite graph that can be solved in an efficient way.

1.2.1

Exact algorithm for single resource’s case

Moving on the exact algorithms there are some ideas that can be helpful for our

problem, even if not directly. In[5] it is introduced an exact algorithm for the

multiple periodic activities scheduling to one facility. In the solution proposed the most important step is the partition into simpler and smaller sub-problem that are independent between them. The input data are n periodic activities in

a set N , where each activity i has periodπ_i and work content w_i and it must

be processed in a facility. The total period in which all the jobs are planned is

H = lcm_i(π_i) and the value to be decided is t_i, namely the first execution of

activity i. The aim in this optimization problem is to minimize the peak load

L. Observe that all the jobs have duration equal to 1, while they have a work

content that is not in time but in load. The work load at every moment is Wj

and it is equal to the sum of the work content w_i of the activities scheduled in

the instant j ∈ {1, . . . , H}. Any work has to be scheduled in the facility that has

a finite capacity M and in this case is M = maxj{Wj}, i.e. the maximum load

in the period H. To model the problem in a ILP formulation binary variables are introduced

x_{i, j}=

¨

1 if activity i is scheduled at time j

0 otherwise (1.1)

and the model is the following:

ILP : min L (1.2) s.t. πi X j=1 x_{i, j}= 1 i_{∈ N} (1.3) n X i=1 w_ix_{i, j≤ L} j_{∈ {1, . . . , H}} (1.4) x_{i, j}= x_{i, j+π} i i∈ N , j ∈ {1, . . . , H − πi} (1.5) x_i, j∈ {0, 1} i∈ N , j ∈ {1, . . . , H} (1.6)

Constraints (1.3) assign to each activity a slot of time of the facility in which can be processed, the following (1.4) force the sum of work content of activity scheduled at time j to be less or equal of L, that is the peak load minimized in the objective function, the constraints (1.5) impose periodicity of the activities. The latest are integrality constraints.

The sub-problems are given by the partition of the activities in subsets

N₁, . . . , N_r, each N_k has a related set P_k of the periods of its activities and a

value `_k = lcm_i∈Pkπ_k. The main result for the partition of the problem is the

Proposition 1.2. If`<sub>k</sub>and`_j are relatively prime for every k, j∈ {1, . . . , r}, then

when all the activities in N are scheduled the minimum peak load is

L∗=

r X

k=1

L∗_k.

Proof. Assume that we have a fixed schedule for the k-th sub-problem and

its minimum peak load takes place in the instant tk ∈ {1, . . . , `k}. Due to the

periodicity of the tasks in every instant x such that x ≡ tk(mod `k) there is the

minimum peak load of this sub-problem. This is true for all k∈ {1, ..., r} and

the values`k are pairwise coprime, hence for the Chinese Remainder Theorem

there is a solution x for the system      x ≡ t1 (mod `1) .. . x <sub>≡ tk</sub>(mod `_k) . (1.7)

So in the instant x takes place the minimum peak load of all the sub-problems and we can conclude that the global minimum peak load is the arithmetic sum of the minimum peak load of the sub-problems.

Hence to minimize L, it is enough minimizing each Lk separately. This

allows us to have r independent sub-problems:

ILPk: min Lk (1.8) s.t. πi X j=1 x_{i, j}= 1 i∈ Nk (1.9) X i∈Nk w_ix_i, j≤ Lk j∈ {1, . . . , H} (1.10) x_i, j= xi, j+πi i∈ Nk, j∈ {1, . . . , H − πi} (1.11) x_{i, j∈ {0, 1}} i_{∈ Nk}, j∈ {1, . . . , H} (1.12)

The problem is the same of the original one, but being smaller it is possible to optimize bigger instance. Obviously the complexity depends on the input data

and the size of the subsets can be very different, but in the example in[5] we

can see how powerful is the result: the variables decrease from 1200 to less than 12 and the constrains from 1298 to less than 8.

1.2.2

Heuristic for Periodic Scheduling problem

Because PSP is a hard problem, until P = N P , we have already said that

exact algorithms with polynomial time do not exist, but in [1] it is presented

a scheduling generation algorithm with polynomial time. To this purpose the authors defined a new request called proportionate progress, instead of peri-odic constraint it is used a stricter one: fairness. Since each P-fair schedule is also periodic, the polynomial-time scheduling generation algorithm, that pro-duces a P-fair schedule for each feasible instance, also solves PSP, despite not

optimally. In [1] the problem addressed is the scheduling of n periodic tasks

x_i to m identical copies of a resource, each task has period π_i and duration d_i

and one resource can process a task at a time, it is also introduced the weight

of a job, a new value which is defined wi =

di

πi. This last is used to describe

the new property: a schedule holds a proportionate progress if and only if each task has scheduled resources in proportion of his weight, namely at

ev-ery time t ∈ N each task xi is scheduled eitherdwi · te or bwi · tc times. This

request arises naturally in several real circumstances, for example in the crew scheduling for airlines: the weight can represent the number of working days in a week, in this way the P-fair schedule produces a planning in which every flight crew schedule works in a constant rate; another application can be the real-time communication network in which with a P-fair schedule the queue is not too long. The main idea of the P-fair scheduling algorithm is to assign at

each time t ≥ 0 a dynamic priority to each task and the m highest priorities

are scheduled. The priority is calculated in order to hold the proportionate progress property.

1.2.3

New approach: Temporal Bin Packing problem

Recently it is introduced in[2] a different way to model and solve the

schedul-ing of tasks with time windows constraints to production plant with a capacity, it is called Temporal Bin Packing problem, TBPP for short. The TBPP is a gener-alization of the Bin Packing problem to which is added a temporal dimensional,

indeed there is a set N = {1, . . . , n} of items with different sizes w_i, i∈ N , that

have to be packed in bins J = {1, . . . , m} all with the same capacity M like in

BPP. Moreover each item i∈ N has a starting si and ending titime, these define

a time windows in which the item consumes the capacity of the bin which it is assigned, while out of the time window the weight of the item is not consid-ered in the calculation of the occupied capacity. Hence the packing of items

into bins is computed over a discretized time horizon {1, . . . , T } and the bins

are renewable resources that are available at any time unit in the period. Also in this generalization each item must be assigned to exactly one bin. It is clear

that also the TBPP is anN P -hard problem, indeed if all the starting times are equal to the same value and all the ending times to another value, the TBPP is

transformed in a BPP, which is known to beN P -hard.

Formulations

In[2] two models are presented which one has polynomial size and the other

exponential. For the first Integer Linear Programming formulation two sets of variables are introduced

x_i, j=

¨

1 if item i is packed in bin j

0 otherwise i∈ N , j ∈ J, (1.13)

y_j=

¨

1 if bin j is active

0 otherwise j∈ J. (1.14)

The following is the compact formulation for the TBPP, it is based on the math-ematical model proposed by Kantorovich:

ILPc: minX j∈J y_j (1.15) s.t. X j∈J x_{i, j}= 1 i∈ N (1.16) X i∈St w_ix_{i, j}≤ M yj t∈ T, j ∈ J (1.17) x_{i, j}∈ {0, 1} I ∈ N , j ∈ J (1.18) y_i∈ {0, 1} j∈ J (1.19)

The aim of the ILPc _{model is to minimize the number of active bins, while the}

constraints (1.16) force each item to be packed in one bin, like a classical BPP. Instead the constraints (1.17) impose that the capacity of each bin is respected, but in a particular way. This check is not carried out at any time, but only when there may be a weight change and this may be at the starting time of items.

For this purpose special sets of items are defined for all i∈ N

S_i= {l ∈ N | s_l ≤ si ≤ tl}, (1.20)

that contains the items for which the instant si is included in their time

win-dows. Since all the items in S_i can be packed at the same time, a capacity

con-strained must be imposed in this instant time, but the number of constraints

at time s_i is dominated by the one at time s_k. So it is introduced a new set of indices not dominated

¯

T = {t ∈ N | S_t 6⊆ Sk ∀k ∈ N }, (1.21)

that for ease we rewrite T = {1, . . . , | ¯T|}. The lasts (1.18) and (1.19) are

integrality constrains.

The second formulation is based on the Gilmore and Gomory reformulation of the Cutting-Stock problem and it is characterized by an exponential number of variables. It is introduced the set of the feasible patterns, which are subsets of items that can be packed in a bin

P = ( P ⊆ N : X i∈St∩P w_i ≤ M, t ∈ T ) . (1.22)

For each of this pattern is defined a binary variable as follow

ξP = ¨

1 if pattern P is selected

0 otherwise P∈ P . (1.23)

The ILP formulation for the TBPP with exponential size is the following

ILPe_{: min}X P∈P ξP (1.24) s.t. X p∈P :i∈P ξP = 1 i∈ N (1.25) ξP ∈ {0, 1} P∈ P (1.26)

The objective function to minimize is the number of patterns used under the constraints (1.25) which impose that each item is contained in exactly one active pattern. The lasts (1.26) are integrality constraints.

Lower and upper bounds

The most interesting result of the article for our purpose is the particular use of Branch and Price method for the resolution of the problem: there are several lower bounds and upper bounds that are combined in an effective way with Branch and Price based on Column Generation.

The first bound introduced is

LB₀= max

t∈T z(ILP

where ILPc_{(t) is the formulation ILP}c_{which models only the items in S}

t. At least

LB₀ bins must be active to solve TBPP. Another lower bound is the continuous

relaxation of ILPc_{, which we indicate with LP}c_,

LB₁= dz(LPc)e. (1.28)

To improve this value the authors use two lifting techniques for preprocessing instances that increase the weight of items, while it guarantees that the lifted

instance has the same optimal value of the original one. The LB1 calculated

on the instances obtained from the two different techniques are indicated as

LB₂I and LB₂I I.

Moving on the exponential size formulation it is defined the continuous

relax-ation of ILPe_{and it is}

LB₃= dz(LPe)e. (1.29)

It is proven that this last lower bound is better than the continuous relaxation of the compact formulation

z(LPc) ≤ z(LPe). (1.30)

To find some useful upper bound there are introduced two heuristics. The first is the classical Greedy algorithm First-Fit heuristic that is known for the BPP and it is easily adaptable to TBPP. This heuristic analysis one item at each step, first it opens only one bin and at each step it looks for the first open bin that can holds the current item, if this bin exists the item is placed here, otherwise a new bin is open. For the TBPP is added the check if the chosen bin can contain the item during all its time window. The value calculated with this Greedy

algorithm is indicated with U B1.

The second heuristic introduced is the Rolling Horizon heuristic which solves

ILPc_{for a subset of the time-step constraints: it is chosen∆ ∈ {1, . . . , |T|} and}

_{|T |}

∆ is the time window. In ILPck∆, where k ∈ 1, . . . , |T |∆ , there are only

the constraints about the instants in Tk = [(k + 1)∆, k∆] and the variables

correspond to the items N_k = ∪_j∈T

kSj, namely the items for which the instant

j falls in their time windows. At k-th step the algorithm looks for a feasible

solution of ILPc_k∆, if the solution exists the items are placed in the bins and

variables analysed are fixed. If at each step a feasible solution is found the

global solution is the second upper bound, U B2.

Branch and Price scheme

The Branch and Price consists in two main elements: Column Generation to

Master Problem (RMP), that is LPe _{reduced to a subset of variables B ⊂ P ,} this subset is initialized with the columns correspond to the best solution found with the Greedy algorithm. The RMP is the following

(P) min ¨ X P∈B ξP : X P∈B:i∈P ξP = 1, i ∈ N, ξP ≥ 0, P ∈ B « (1.31) and it is solved thanks its dual

(D) max ¨ X i∈N πi : X i∈P πi ≤ 1, P ∈ B, πi ≥ 0, i ∈ N « (1.32)

where πi is the dual variable correspond to the i-th constraint of the primal.

We can observe that the authors formulate the dual considering in the first block of constraints in (P) the greater or equal instead of the equal, indeed the dual variables must be non-negative. With this change the solution of the variant can be transformed in a solution of the original problem, indeed if an item is in more than one bin it is sufficient to remove the copies of the item in all the bins except in one. First of all it is resolved optimally the dual Restricted

Master Problem (D), letπ∗_{the optimal solution and then it looks for a violated}

constraint in P \ B, namely if

∃ P∗∈ P \ B : X

i∈P∗

π∗

i > 1. (1.33) To find this violated pattern it is defined a new problem called Pricing Problem, that has a new set of variables

z_i=

¨

1 if item i is selected in pattern P∗

0 otherwise i∈ N . (1.34)

The Pricing Problem is the following

max ( X i∈N π∗ izi : X i∈St w_iz_{i ≤ M, t ∈ T, zi∈ {0, 1}, i ∈ N} ) (1.35) it has the form of a Temporal Knapsack Problem. It is noted that in this

for-mulationπ∗_i are fixed and they do not have the role of variables. Let z(π∗) the

optimal solution of this separation problem, if z(π∗_{) > 1 a violated pattern P}∗

exists and it is

hence this pattern is added to the subsetB of variables of primal RMP and it is solved again, this process takes place until a violated pattern is not found.

When this happens, namely z(π∗_{) ≤ 1, the LP}e_{is solved optimally.}

The other main element for the Branch and Price is the branching scheme

for ILPe, it should hold two properties:

• a complete scheme, the integrality has to be imposed in each case; • it does not require modifications to the master problem, in order to use

the same algorithm to solve the RMP in all the iterations.

The authors present two different schemes, the first one is characterized by

standard branching rule: a fractional variableξ∗_P is selected and two children

nodes are created in which are imposed ξ∗_P = 1 e ξ∗_P = 0 respectively, this

enforcement is immediate to achieve in the sub-problem of the children node and it respects the two property required. The second scheme is based on a different branching rule: for each pair of items it is imposed that they are

packed together or in different bins; in particular it is selected a pair of r, s∈ N

if they are fractionally packedP_{P∈ ˆP :r,s∈P}ξ∗_P = γ, with γ fractional. In this case

is more complicated impose the rule, to pack together the items it is sufficient

to create a super item i with starting time s_i = min{s_r, s_s}, ending time ti =

max{tr, ts} and weight depending on time

w_i,t=    w_r if r∈ St and s /∈ St w_s if r /∈ St and s∈ St w_r+ w_s if r∈ St and s∈ St t∈ [si, ti]. (1.37)

Instead to pack the items in different bins, conflicts constraints must be added

in the Pricing Problem as z_r+ z_s ≤ 1. In this case the branching scheme is

complete and it is proved in[2], while the second property is not verified.

For the Branch and Price it is presented also a heuristic to span a section of the decision tree, it is called H-Diving heuristic. The starting point is the

solution of LPe _{with the Column Generation that provides the lower bound}

LB₃ and the root node, from this node begins the exploration of the tree by

the Branch and Price with standard branching rule and the token-based rule, which limits the number of right branches. The aim of the heuristic is to find a solution in a short time and chose the left branch helps in this way, indeed

fixing a fractional variableξ_P equal to 1 reduces the problem size and forces the

algorithm to find a feasible solution. It is allowed to the algorithm to perform all the left branches, but only K right branches. This heuristic provides a new upper bound in short time.

Algorithm for TBPP

The overall algorithm proposed in [2] is a particular combination of the

pre-sented bounds and the Branch and Price, it is called B&P+. The outline of this

algorithm is the following

Phase1 : • compute LB= max{LB0, LB1, LB2I, LB I I 2 }; • compute U B= min{UB₁, U B₂}; • if LB= UB than STOP; Phase2 :

• compute LB3, i.e. the LPewith Column Generation;

• update LB;

• if LB= UB than STOP;

Phase3 :

• run H-Diving heuristic; • update U B;

• if LB= UB than STOP;

Phase4 :

• run Branch and Price with the second branching rule; • update LB and U B;

• if LB= UB than STOP.

It is noted that all the bounds introduced above are used to search optimal solutions without the process of the Branch and Price. The Phase 2 is the most time consuming indeed it employs the Column Generation to solve the continuous relaxation of the exponential size model.

1.3

Relationships with our model

Our problem can be classified as a multiple resources nonpreemptive con-strained periodic scheduling problem. We have M Resource Blocks each of which can process one task per times, we assume that all the resources are identical, the operations can be assigned to all the resources and their dura-tion does not depend on this choice. If in our problem we consider the Resource Blocks of the airframe vectors as processors, it is related to a constrained non-preemptive scheduling problem, indeed the request of the same RBs for all the assignment of one task is close to the constrained case. Hence also our problem is a hard once. To solve optimization problem important tools, in particular for hard ones, are heuristics and relaxations to bound the optimal solutions and to test the quality of feasible ones.

The problem addressed is not decomposable in independent sub-problems like exact algorithm presented in Section 1.2.1, this decomposition could be used for a particular relaxation of the original problem, but the proof does not seem extendable to our configuration. The formulation 1.2 can only describe the assignment of jobs to one facility in periodic way, but it cannot manage the request of our problem about the selection of RBs in the airframe: they have to be contiguous and always the same for all the processing of a task. The jobs of our problem can be considered as the activities introduced in that problem, indeed also our tasks have a period and a weight that uses the capacity of the

resource. In [5] there is only one facility that can represents our airframes,

one at each instant, since they are all the same we can consider only one in different instants. In the ILP model addressed the capacity of the facility is the value to minimize, instead in our problem is a fixed quantity equal to M RBs. There are several differences between the two problems and to achieve this formulation we must consider a relaxation for elimination of constraint of our problem. The requests to be eliminated are the ones that describe the conflicts in space and time of the tasks, so the remaining constraints represent the assignment of tasks to airframes and the periodicity. The check that the weight of all the tasks assigned to one airframe does not exceed the threshold

M is not directly, we must add another constraint L≤ M to bound the variable

of the peak load.

According with the notation at the beginning of this chapter we have N =

{1, . . . , n} periodic tasks, each of which is characterized by an ordered pair

(πi, wi) where πi is the task period and wi is the required number of RBs, that

we can consider as the weight. The airframes are labelled {1, . . . , H}, one at

use the model presented in[5] we define a set of binary variables

x_{i, j}=

¨

1 if task i is scheduled at time j

0 otherwise i∈ N , j ∈ {1, . . . , H} (1.38)

and the model is the following

min L (1.39) πi X j=1 x_i, j= 1 i∈ N (1.40) n X i=1 w_ix_i, j≤ L j∈ {1, . . . , H} (1.41) x_{i, j}= x_{i, j+π} i i∈ N , j ∈ {1, . . . , H − πi} (1.42) L≤ M (1.43) x_{i, j}∈ {0, 1} i∈ N , j ∈ {1, . . . , H} (1.44)

It looks like a Bin Packing problem with the constraint of periodicity, indeed there are the assignment constraints (1.40), the capacity constraints (1.41), in which L is bounded with the new constraint (1.43), and the integrality con-straints (1.44) that are peculiar of BPP, while (1.5) impose the periodicity of tasks. With the intention of not relaxing even the capacity constraints of the re-sources we lose the independence of the sub-problem, indeed the sub-problems in 1.2.1 have the aim to find the minimum peak load without bound so they can schedule an item in any instant ignoring if the other sub-problems are taking up the capacity of the resources in the same instant.

Another useful process is the new approach of TBPP presented in Sec-tion 1.2.1, but there are several differences between TBPP and our problem. To formulate our issue as a TBPP we have to eliminate some constraints, in particular also in this case we cannot request specific position of RBs in the airframe for each task. Each activity in TBPP has weight and duration, while our task has weight and period, hence also the periodicity constraints must be relaxed. The duration of tasks that we want to schedule is equal to 1, so the temporal dimension of TBPP is missing. Moreover the resources in TBPP are a set of bins with a finite capacity and the number of bins is the value to min-imize, while we have a number fixed of resources, namely an airframe with

M RBs. The bins in this problem are considered all in each instant, unlike our

problem that has one resource, whereby airframe, at each instant of time. If we model our problem as the compact formulation we achieve a standard BPP,

indeed it is introduced also in this case the binary variables

x_{i, j}=

¨

1 if task i is scheduled at time j

0 otherwise i∈ N , j ∈ J (1.45)

and the constraints that model the relaxation of our problem are X j∈J x_{i, j}= 1 i_{∈ N} (1.46) X i∈N w_ix_{i, j}≤ M j∈ J (1.47) x_{i, j∈ {0, 1}} i_{∈ N , j ∈ J} (1.48)

that look like BPP. For the formulation with exponential number of variables there is introduced the set of patterns

P = ¨ P ⊆ N : X i∈P w_i≤ M « (1.49) and the related binary variables

ξP = ¨

1 if pattern P is selected

0 otherwise P∈ P . (1.50)

The constraints that must be verified is the following as in ILPe

X

P∈P :i∈P

ξP= 1 i∈ N (1.51)

ξP ∈ {0, 1} P ∈ P (1.52)

Both models cannot describe the complex structure of our problem, in partic-ular the position of the tasks in the airframe and the related conflicts. Hence all the models above can formulate only a relaxation that has the form of BPP. From the 1.2.3 the particular application of Branch and Price can be more use-ful than the formulation, indeed we can follow the development of lower and upper bound from continuous relaxation of both models.

Chapter 2

Definition of models

As we have seen in section 1.3, in literature there are no models which de-scribe the complexity of our problem, hence in this chapter we present two new formulations. Let us assume that we have a set F of old tasks already in place and a set N of new tasks that we want to insert in the airframes. There are different strategies to manage this problem: we can consider the old tasks fixed in their previous 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 of N . These choices lead us to four different versions of our models.

Two models have been developed: first one is Conflict-Based and second Matrix-Based. In both models, as described in section 1.1, at each time unite TTI we have to assign a subset of tasks to one airframe that is a vector made

of M RBs. Each task i ∈ A, where A = N ∪ F, has a period πi and a required

number of RBs w_i, which must be sequentially and in the same position in

all periodic repetitions. To define a feasible schedule the time horizon is H =

lcmi∈Aπi, i.e. the least common multiple of all task’s periods. Each RB can be

assigned to only one task, hence the challenge is to handle both overlaps in

time and space. Two tasks i, j∈ A aired in TTI t, t0respectively collide in time

if and only if ni, nj ∈ N exist such that

t+ n_iπ_i= t0+ n_jπ_j,

namely they are in the same airframe in their repetitions niand njrespectively.

This is a Diophantine equation in which n_i, n_j are the integer unknowns

n_iπ_i− njπj = t0− t this equation has a solution if and only if

t0− t ≡ 0 (mod gcd(πi,πj)). (2.1)

The latter congruence is the condition to be tested for time collisions. Instead for the space conflict it is sufficient to check the intersection of RBs assigned:

let h, h0 _{the positions in the airframe of the first block assigned to i and j}

re-spectively, there is a collision if and only if

[h, h + wi− 1] ∩



h0, h0+ wj− 1 6= ;. (2.2)

For the feasibility of the problem two tasks can collide only in one dimension, if the collision is in space and in time there is an overlap and two items are assigned to the same RBs, this is forbidden.

To differentiate the models, we will use the following abbreviations: for example, CB-F-F, CB stands for Conflict-Based and it can be also MB, Matrix-Based; the first letter describes the old tasks, F for fixed or M for moveable; the second one is for the new tasks, F for forced or O for optional.

2.1

Conflict-Based model

The first model we present is the natural adaptation of assignment problem to deal with the collisions in time and space. In this model to manage the overlap of tasks, two sets are defined:

T(i, t, j) = t0∈ {0, . . . , πj− 1} | t0− t ≡ 0 (mod gcd(πi,πj)

(2.3)

that for i, j∈ A, t ∈ {0, . . . , πi−1} contains all the instants t0for which j comes

in conflict with i aired in TTI t;

H(i, h, j) =h0∈ {1, . . . , M − wj+ 1} | [h, h + wi− 1] ∩ 

h0, h0+ w_j− 1 6= ; (2.4)

that for i, j∈ A, h ∈ {1, . . . , M − wi+ 1} includes all the positions h0 for which

j intersects with i in position h.

To describe the first formulation, we define four sets of binary variables: the first two represent the position of tasks in time and space

x_i,t=

¨

1 if task i is assigned to TTI t

0 otherwise i∈ A, t ∈ {0, . . . , πi− 1}, (2.5)

y_i,h=

¨

1 if task i has first RB in h

0 otherwise i∈ A, h ∈ {1, . . . , M − wi+ 1}, (2.6)

the latest two are used to handle the collisions

c t_{i, j}=

¨

1 if tasks i and j are in conflict in time

ch_{i, j}=

¨

1 if tasks i and j are in conflict in space

0 otherwise i, j∈ A. (2.8)

2.1.1

CB-Fixed-Forced

First of all our aim is to search a feasible schedule of new tasks, while the old ones are fixed. To manage the conflict with fixed tasks we define two new sets

for each pair i ∈ N and f ∈ F

C T(i, f ) =t∈ {0, . . . , πi− 1} | t − tf ≡ 0 (mod gcd(πi,πf)) (2.9) C H(i, f ) =h∈ {1, . . . , M − wi+ 1} | [h, h + wi− 1] ∩ [hf, hf + wf − 1] 6= ; (2.10) which contains respectively the instants and the positions in the airframe of i that would lead to a conflict with the fixed task f . The model is the following

(CB-F-F) min 0 (2.11) s.t. πi−1 X t=0 x_i,t = 1 i∈ N (2.12) M−wi+1 X h=1 y_i,h= 1 i∈ N (2.13) c t_{i, j}≥ xi,t+ X t0_{∈T (i,t, j)} x_j,t0− 1 i, j∈ N , t ∈ {0, . . . , πi− 1} (2.14) ch_i, j≥ yi,h+ X h0_{∈H(i,h, j)} y_j,h0− 1 i, j∈ N , h ∈ {1, . . . , M − w_i+ 1} (2.15) c t_{i, j}+ ch_{i, j}≤ 1 i, j∈ N (2.16) X t∈C T (i, f ) x_i,t+ X h∈C H(i, f ) y_i,h≤ 1 i∈ N , f ∈ F (2.17) x_i,t ∈ {0, 1} i∈ N , t ∈ {0, . . . , πi− 1} (2.18) y_i,h∈ {0, 1} i∈ N , h ∈ {1, . . . , M − wi+ 1} (2.19) c t_{i, j∈ {0, 1}} i, j∈ N (2.20) ch_i, j∈ {0, 1} i, j∈ N (2.21)

The constraints in (2.12) require to all the new tasks to have a position in time,

1}. In the same way (2.13) impose to all the new tasks to have assigned a

position of its first RB in{1, . . . , M −wi+1}. These constraints are assignment’s

ones, while the following inequalities manage the collisions between them. Constraints in (2.14) check the feasibility of position in time dimension for

each pair of tasks i, j ∈ N and if there is a collision cti, j takes value 1, indeed

the right-hand side is at most equal to 1 only when the two tasks are in conflict:

variable x_i,t and the summation over T(i, t, j) are both equal to one, this lead

us to have c ti, j ≥ 1. If i is not located in t or j is not placed in a TTI of

T(i, t, j) the inequality became ct_{i, j}≥ 0 or cti, j≥ −1, which are always verify.

We can observe that the summation is over all possible locations of j in time that cause a collision with i in t. The constraints (2.15) are the same of the

previous but in space dimension: ch_{i, j} is forced to be 1 if and only if i and j

collide in space. With (2.16) the collisions both in space and in time of each pair of tasks i, j are prohibited. Up to now we have a schedule of new tasks without collisions between them. The constraint (2.17) requires that there are no conflicts even between new and old tasks: the first sum is equal to 1 if i is assigned to a TTI that causes a conflict with f , similarly the second sum has the value 1 if i is placed in an RB that makes it intersect with f ; the addition of this sums is forced to be less than 1 so it is not allowed the location of i for which it collides with f . The remaining constraints make variables binary. The objective function is constantly 0, because this is a feasibility problem, so we want only a feasible solution.

Conflict constraints

We also tried a different formulation for the constraints (2.17) that must

con-trol there are no conflicts between new and fixed tasks. For each task i ∈ N ,

TTI t ∈ {0, . . . , πi − 1} and position h ∈ {1, . . . , M − wi + 1} we define the

following sets

T F(i, t) = {f ∈ F | t − t_f ≡ 0 mod (gcd(πi,πf))}

that contains all the fixed tasks f with which i would conflict in time if it is assigned at TTI t and

H F(i, h) = {f ∈ F | [h, h + w_i− 1] ∪ [hf, hf + wf − 1] 6= ;}

that similar contains all the fixed tasks f with which i would conflict in space if it is placed at height h. To have a correct scheduling of new task i we must

prohibit the positions (h, t) when these cause collisions both in time and in

space with a certain f , i.e. if

The new constrains are

x_i,t+ y_i,h≤ 1 i∈ N , t, h s.t.C(i, t, h) 6= ;. (2.22)

For the implementation we do not use these constraints but the previous ones (2.17), because they have a continuous relaxation worse than the first ones. The proof is the following. Each continuous solution that verifies (2.17) verifies

also the (2.22), indeed for each i ∈ N and f ∈ F of (2.17) exists C(i, h, t) 6= ;

which contains that f , hence the corresponding constraint in (2.22) is neces-sarily verified, because it has only one variable of the sums of each constraint of (2.17) that globally must be less than 1. On the other hand a solution that verifies (2.22) do not necessarily verifies (2.17), indeed there may be variables which validate the constraint (2.22) individually, but their sum can be greater than 1.

2.1.2

CB-Moveable-Forced

To place all the new tasks let us assume in this version that the old tasks are moveable and the aim is to locate all the new tasks, minimizing the relocation

of old tasks. Let(h_i, t_i), i ∈ F, the positions of these latter, to check these ones

we define another set of binary variables

z_i=

¨

1 if task i is relocated

The model is the following (CB-M-F) minX i∈F z_i (2.24) s.t. πi−1 X t=0 x_i,t= 1 i∈ A (2.25) M−wi+1 X h=1 y_i,h= 1 i_{∈ A} (2.26) c t_{i, j}≥ xi,t+ X t0_{∈T (i,t, j)} x_j,t0− 1 i, j∈ A, t ∈ {0, . . . , πi− 1} (2.27) ch_{i, j}≥ yi,h+ X h0_{∈H(i,h, j)} y_j,h0− 1 i, j∈ A, h ∈ {1, . . . , M − wi+ 1} (2.28) c t_{i, j}+ ch_{i, j}≤ 1 i, j∈ A (2.29) z_i ≥ 1 − xi,ti/2 − yi,hi/2 i∈ F (2.30) x_i,t∈ {0, 1} i∈ A, t ∈ {0, . . . , πi− 1} (2.31) y_i,h∈ {0, 1} i∈ A, h ∈ {1, . . . , M − wi+ 1} (2.32) c t_{i, j}∈ {0, 1} i, j∈ A (2.33) ch_{i, j}∈ {0, 1} i, j∈ A (2.34) z_{i ∈ {0, 1}} i_{∈ F} (2.35)

The constraints (2.25)-(2.29), similar to the previous model, provide a sched-ule of all the tasks without collisions between them. The new constraints (2.30)

check if the old tasks in F are relocated: if xi,ti = 1 and yi,hi = 1 the old task

i is in the same position so z_i ≥ 0 and minimizing it takes value 0, while if i

is moved in space, time or both directions, at most z_i ≥ 12 so it’s forced to be

1. The latest constraints impose to the variables to be binary. The objective

function is the sum of variables z_i and it is equal to the number of old moved

tasks which we want to minimize.

2.1.3

CB-Fixed-Optional

A lot of instances may be unfeasible for the previous models, so a different approach can be the following: to maximize the new tasks located while the old ones are fixed. In this case there is always a solution, because we can also place no new items. The formulation of this model is led by a little modification

of CB-F-F and it is the following (CB-F-O) max X i∈N πi−1 X t=0 x_i,t (2.36) πi−1 X t=0 x_{i,t ≤ 1} i_{∈ N} (2.37) M−wi+1 X h=1 y_i,h≤ 1 i∈ N (2.38) πi−1 X t=0 x_i,t− M−wi+1 X h=1 y_i,h= 0 i_{∈ N} (2.39) (2.14), (2.15), (2.16), (2.17), (2.18), (2.19), (2.20), (2.21)

The constraints (2.37) and (2.38) impose at most a position in space and in time of new tasks, hence they are optional. The constraints (2.39) check that if a new task has a location in space or time, it must have a position also in the other dimension. The remaining constraints are the same of CB-F-F, they are used to manage the conflicts between new tasks and to check if the placed ones are in conflict with the fixed tasks. The last constraints make the variables binary. The objective function indicates the number of new tasks placed which we want to maximize.

2.1.4

CB-Moveable-Optional

Also in this approach to position more tasks we can allow the old ones to move: to maximize the new tasks located, minimizing the old ones moved. The

for-mulation of this model is led by a little modification of CB-M-F (CB-M-O) max X i∈N πi−1 X t=0 x_i,t− 1 |F| + 1 X i∈F z_i (2.40) s.t. πi−1 X t=0 x_i,t = 1 i_{∈ F} (2.41) M−wi+1 X h=1 y_i,h= 1 i∈ F (2.42) (2.37), (2.38), (2.39), (2.27), (2.28), (2.29), (2.30), (2.31), (2.32), (2.33), (2.34), (2.35)

The constraints (2.41) and (2.42) impose to the old tasks to have a position in time and in space, while (2.37)-(2.39) as in CB-F-O impose to the new items to have at most a position. The remaining constraints are the same of CB-M-F, they are used to manage the conflicts between tasks and to check if the old tasks are moved. The objective function has a different formulation than the previous ones: the first summation indicates the number of new located tasks, that is maximized, and the second summation gives the number of old tasks moved, that being subtracted from the value of the objective function the model will minimize. This last sum is multiplied by a factor less than 1 in order to prefer the placement of a new task over not moving an old one.

2.2

Matrix-Based Model

The second type of model has a different construction, it is Matrix-Based and it is formulated with only one set of binary variables

x_i,h,t =

¨

1 if i is placed in RB h and TTI t

0 otherwise (2.43)

i∈ A, h ∈ {1, . . . , M − wi+ 1}, t ∈ {0, . . . , πi− 1}. To avoid conflicts it is defined this set

C(h, t) = { (i, h0, t0) i ∈ A, h0∈ {1, . . . , M − wi+ 1}, t0∈ {0, . . . , πi− 1} | (2.44)

if i is in(h0, t0), i has assigned also the RB (h, t) } (2.45)

for each h ∈ {1, . . . , M} and t ∈ {0, . . . , H − 1}. Also for this Matrix-Based

2.2.1

MB-Fixed-Forced

The first variant is the feasibility problem in which old tasks are fixed and we search a feasible schedule of all the new tasks. For this formulation the variables corresponding to positions that cause conflicts with fixed tasks must be placed equal to 0, hence we can eliminate these ones and define only the variables



x_i,h,t | (i, h, t) ∈ V where

V = {(i, h, t) i ∈ N, h ∈ {1, . . . , M − w_i+ 1}, t ∈ {0, . . . , π_i− 1} |

if i∈ N is placed in (h, t) does not create conflicts with any tasks in F}.

(2.46) Moreover not all blocks shall be checked if they belong to more than one new task, but only the ones free from the old tasks, i.e. the positions in the set

L= {(h, t) h ∈ {1, . . . , M}, t ∈ {0, . . . , H − 1} |

(h, t) is not assigned to any fixed tasks}. (2.47)

The model is the following

(MB-F-F) min 0 (2.48) s.t. X (i,h,t)∈V x_i,h,t = 1 i∈ N (2.49) X (i,h0,t0_{)∈C(h,t)∩V} x_i,h0,t0≤ 1 (h, t) ∈ L (2.50) x_i,h,t∈ {0, 1} (i, h, t) ∈ V (2.51)

The constraints (2.49) impose that all the new tasks must be placed indeed it is

defined for all i∈ N in order to have an infeasible solution if a feasible position

does not exist. If we built the constraints only for i ∈ N such that there exist

h∈ {1, . . . , M − wi+1} and t ∈ {0, . . . , πi− 1} for which (i, h, t) ∈ V , we would

have that if a constraint is not create, the model has not the obligation to place the corresponding task. The constraints (2.50) check that the RBs free from old tasks are assigned to at most one new task. We can observe that the sum

is above the position(i, h0, t0) ∈ C(h, t) intersected with V , the indices of the

created variables. The lasts make the variables binary. The objective function is constantly zero, because this is a feasibility problem.

2.2.2

MB-Moveable-Forced

In this version to facilitate the positioning of all the new tasks, we consider the old tasks moveable: we want to position all the new ones while minimize the number of old tasks relocated, in order to do this we need a new parameter

αi,h,t =

¨

1 if h6= hi or t 6= ti

0 otherwise i∈ F, h ∈ {1, . . . , M−wi+1}, t ∈ {0, . . . , πi−1}

this is equal to 1 if task i ∈ F is moved in time, in space or in both dimensions.

The model is the following

(MB-M-F) min X i∈F M−wi+1 X h=1 πi−1 X t=0 αi,h,txi,h,t (2.52) s.t. M−wi+1 X h=1 πi−1 X t=0 x_i,h,t = 1 i∈ A (2.53) X (i,h0_,t0_)∈C(h,t) x_i,h0,t0≤ 1 h∈ {1, . . . , M}, t ∈ {0, . . . , H − 1} (2.54) x_{i,h,t∈ {0, 1} i ∈ A, h ∈ {1, . . . , M − wi}+ 1}, t ∈ {0, . . . , π_{i− 1}} (2.55)

The constraints (2.53) impose that each task i∈ A has a position in the airframe

and in its first period. The constraints (2.54) check the collisions: each RB (h, t), where h ∈ {1, . . . , M} and t ∈ {0, . . . , H −1}, can be assigned to only one task, to do this for each position we sum x_i,h0,t0such that(i, h0, t0) ∈ C(h, t), that

contains all the tasks that in a certain position occupy also(h, t) and we force

this sum to be less than 1. The objective function minimizes the number of old tasks moved, indeed if task in F remains in the old position the corresponding variable in objective function is multiply by 0, instead in all the other positions the variable is multiply by 1.

2.2.3

MB-Fixed-Optional

To always have a solution, let us assume the new tasks optional, while the old ones are fixed. Also in this case we do not define all the variables and constraints, indeed we use the sets V and L defined in (2.46) and (2.47). The

model is the following (MB-F-O) max X (i,h,t)∈V x_i,h,t (2.56) s.t. X (i,h,t)∈V x_i,h,t ≤ 1 i∈ N (2.57) (2.50), (2.51)

The constraints (2.57) check that new tasks have at most a position assigned, we can observe that the summation is only of the variables created, hence the ones in V . The latest constraints are for the collisions and the type of variables. The objective function maximizes the number of new tasks scheduled.

2.2.4

MB-Moveable-Optional

In this version the aim is to maximize the number of new tasks inserted, mini-mizing the old tasks relocated. The model becomes

(MB-M-O) max X i∈N M−wi+1 X h=1 πi−1 X t=0 x_i,h,t− 1 |F| + 1 X i∈F M−wi+1 X h=1 πi−1 X t=0 αi,h,txi,h,t (2.58) s.t. M−wi+1 X h=1 πi−1 X t=0 x_i,h,t = 1 i_{∈ F (2.59)} M−wi+1 X h=1 πi−1 X t=0 x_i,h,t ≤ 1 i∈ N (2.60) (2.53), (2.54)

The constraints (2.59) impose that the old tasks must be placed, while with (2.60) all the new tasks can have at most a position. The remaining constraints manage the collisions and impose to the variables to be binary. In the objective function the first sum is equal to the number of new tasks placed and the second one to the number of old tasks moved. As in CB-M-O the second ones are multiply by a factor less than 1, so as to favour the placement of a new task, instead of keeping fixed an old one.

2.2.5

Another formulation for MB-F-*

Thanks to the sets V and L, defined in (2.46) and (2.47), the models MB-F-F and MB-F-O have a reduction of the number of variables and constraints compared

to MB-M-F and MB-M-O, but their construction creates delays. Another way to formulate these models with all the variables and constraints are the following.

(MB-F-F-2) min 0 (2.61) s.t. M−wi+1 X h=1 πi−1 X t=0 x_i,h,t = 1 i∈ N (2.62) X (i,h0,t0_)∈C(h,t) x_i,h0,t0 ≤ 1 − `(h, t) h∈ {1, . . . , M}, t ∈ {0, . . . , H − 1} (2.63) x_i,h,t ∈ {0, 1} i ∈ N , h ∈ {1, . . . , M − wi+ 1}, t ∈ {0, . . . , πi− 1} (2.64)

The constraints (2.62) impose to all the new tasks to have a position in space and time. To check the collisions of all the tasks we need to define a new parameter

`(h, t) =

¨

1 if(h, t) is assigned to a fixed task

0 otherwise (2.65)

h∈ {1, . . . , M}, t ∈ {0, . . . , H − 1}.

Thanks to this parameter when the block in position(h, t) is already occupied

by a fixed task, the right-hand side of (2.63) becomes equal to zero, hence all the variables is the left-hand side must be zero and positions of new tasks which also occupy the block in question are prohibited.

Also for MB-F-O we need to define the new parameter (2.65), the formula-tion is the following

(MB-F-O-2) max X i∈N M−wi+1 X h=1 πi−1 X t=0 x_i,h,t (2.66) s.t. M−wi+1 X h=1 πi−1 X t=0 x_i,h,t≤ 1 i∈ N (2.67) (2.63), (2.64)

The first constraints (2.67) impose that the new tasks have at most a position in space and time, they are optionals. The collisions between new and old tasks are managed by the (2.63) as in the previous model. The last constraints make the variables binary.

Chapter 3

Implementation of models

The two models in their variants described in the previous chapter are im-plemented and solved with CPLEX, in particular we use the CPLEX Callable

Library for C++ language. The code needs three input data: the number

rel-ative to the chosen variant, information of new tasks we want scheduling and if their exist, the information and positions of old tasks already placed in the airframes. The output of our code is the output of the selected solver, in this case is the MIP Solver available in CPLEX.

3.1

Implementation

The code consists in three parts: reading of data input, construction of model and resolution. We organized the input data in text file and after reading in in-teger and simple arrays. After the merge of new and old tasks, we construct the model. In CPLEX to define a problem to solve there exists a function

CPXcre-ateprobthat creates an active problem objects. The idea is that we copy the data and the structure of our model in this problem object, indicating constraints, variables and objective function. To do this, there are various routines and for our two models we used two different ways. When the problem is created the last step is the same for both models: we call the MIP Solver CPXmipopt with our problem as argument. Let’s see the two ways chosen for construction of models.

3.1.1

Construction of Conflict-Based Model

For this model we chose to add rows and columns separately to the empty problem object already created. First of all we create empty rows with the function CPXaddrows, for which we specify only the sense of constraints and