# Scheduling Plans of Tasks
Internship report. Supervisors: Amal El Fallah Seghrouchni, Safia-Kedad
Sidhoum

Davide Andrea Guastella

###### Abstract

We present a heuristic algorithm for solving the problem of scheduling plans
of tasks. The plans are ordered vectors of tasks, and tasks are basic
operations carried out by resources. Plans are tied by temporal, precedence
and resource constraints that makes the scheduling problem hard to solve in
polynomial time.

The proposed heuristic, that has a polynomial worst-case time complexity,
searches for a feasible schedule that maximize the number of plans scheduled,
along a fixed time window, with respect to temporal, precedence and resource
constraints.

##  I Introduction

Scheduling is a decision-making process that is used on a regular basis in
many manufacturing and services industries [1]. It deals with the allocation
of resources to tasks over given time periods and its goal is to optimize one
or more objectives.

From a theoretical point of view, a scheduling problem is a constrained
combinatorial optimization problem where a set of task must be ordered in such
a way that all these are arranged, according to one or more constraints, to
constitute a schedule that minimize or maximize a given objective function.

One of the most popular scheduling problem is the resource-constrained project
scheduling problem (RCPSP) [2]: the objective of resource-constrained
scheduling consists in developing a schedule such that a set of tasks is
completed as early as possible considering both the precedence relationships
and the restricted availabilities of resources.

The scheduling problem we are facing can be thought as a particular case of
the RCPSP problem: in our case we are facing the problem of scheduling plans
of tasks subject to both precedence, resource and temporal constraints. Also,
rather than scheduling tasks as in the RCPSP, our problem aims at selecting a
maximum number of plans.

##  II Case studies

Nowadays, airborne platforms such as Remote Piloted Air Vehicles (RPAS) are
employed in different scenario including conflicts, surveillance and rescue
[3]. In these scenario, airborne platforms operate in highly dynamic
environments with a low predictability. In this context, onboard instruments
(i.e. sensors) allow the platform, hence the mission manager, to collect
knowledge from the field. Sensors carried by RPAS are now able to perform a
large panel of functions such as image acquisition, spectrum analysis, and
object tracking [4]. All these sensors play a major role in operation and
their optimization has become essential.

Because of the criticality of the context and the mission’s objectives, it is
important to develop a method that orchestrates the operations conducted by
the sensors, such that the mission is accomplished correctly and by satisfying
all the constraints. Moreover, due to both critical contexts and dynamic
environment, it is important to orchestrate the operations of the sensors
within a relatively short time.

As further case study, consider the in-flight airplane safety [5]. In this
context there is a need for detecting and resolving data errors which could
come from faulty sensor measurements, inaccurate data processing, or poor
information transmission, that can lead to catastrophic accidents as in the
case of the Air France 447’s accident. Our scheduling technique can be
employed as a fault recovery technique: for example, once the fault has been
detected by the on-board sensors, a system scheduler could discards the
remaining flight plans, and schedules a set of emergency plans into the
current flight schedule. These emergency plans are strictly time constrained,
and their orchestration necessarily needs to lead to a schedule which can
guarantee the safety of passengers.

##  III Definitions

######  Definition 1 (Plan of Tasks).

A plan of tasks $\Pi_{k}$ is a partial ordering of tasks $J^{k}_{i}$ to
address a specific goal. Each plan $\Pi_{k}$ is characterized by a priority
value $\alpha_{k}$. The structure of the plan is depicted by an activity-on-
node (AON) network where the nodes and the arcs represent the tasks and the
precedence relations respectively [6]. The precedence relations are described
by the notation $\prec$. For example, given two plans $\Pi_{k}$ and $\Pi_{j}$,
$\Pi_{k}\prec\Pi_{j}$ indicates that the plan $\Pi_{k}$ must be scheduled
before $\Pi_{j}$.

A plan is defined by the following notation:

$\Pi_{k}=(J^{k}_{1},...,J^{k}_{n_{k}})$

where $k$ is an arbitrary index for the plan, $n_{k}$ is the number of tasks
in the plan $\Pi_{k}$ and $J^{k}_{i}$, with $0\leq i\leq n_{k}$ is the $i$-th
task of the plan $\Pi_{k}$. The set of tasks is topologically sorted (see 3).

A plan $\Pi_{k}$ could not be scheduled if at least one task
$J^{k}_{i}\in\Pi_{k}$ could not be scheduled due to unsatisfied constraints.

A plan $\Pi_{k}$ is characterized by a set of resources
$\mathcal{R}^{k}\subseteq\mathcal{R}$.

######  Definition 2.

A graph $G=(V,E)$ consists of a set of vertices $V$, and a set of edges
$E\subseteq V\times V$. In a directed graph the edges are directed from one
vertex to another. A directed acyclic graph (or DAG) is a directed graph with
no directed cycles: a directed cycle is a path that starts from any vertex $u$
and ends in $u$.

######  Definition 3 (Topological Sort).

A topological sort of a directed acyclic graph (DAG) $G=(V,E)$ is a linear
ordering of all its vertices such that if the graph $G$ contains an edge
$(u,v)$ then $u$ appears before $v$ in the ordering [7, 8]. If the graph
contains a cycle, then no linear ordering is possible.

For example, in Figure 1 a directed acyclic graph is showed, for which a
topological sorting can be found, since it has no cycles. Figure 2 shows a
possible topological sorting for the graph in Figure 1, where the different
colors depict the different frontiers in the corresponding DFS graph.

######  Definition 4 (Frontier).

A frontier $f$ for a graph $G=(V,E)$ is a set of nodes $f\subseteq V$ such
that the maximum distance between each node $u\in f$ and the root node in the
corresponding DFS graph is the same.

Figure 1: A Directed Acyclic Graph. Figure 2: A possible topological sorting
for the DAG in Figure 1.

######  Definition 5 (Task).

A task $J^{k}_{i}$ is an atomic operation that a subset of resources must
execute. Each task $J^{k}_{i}$ belongs uniquely to one plan $\Pi_{k}$. Tasks
are characterized by the following elements:

  * •

a processing time $p^{k}_{i}\in\mathbb{N}_{0}$, $p^{k}_{i}\geq 1$;

  * •

a release date $r^{k}_{i}\in\mathbb{N}$;

  * •

a due date $d^{k}_{i}\in\mathbb{N}_{0}$;

  * •

a time lag $\delta^{k}_{ij}\in\mathbb{N}$, if $J^{k}_{i}\prec J^{k}_{j}$;

  * •

a set of resources $\mathcal{R}^{k}_{i}=\\{\rho_{1},...,\rho_{n}\\}$,
$\mathcal{R}^{k}_{i}\subseteq\mathcal{R}^{k}$, which the task $J^{k}_{i}$ is
assigned to.

The tasks within a plan can be dependent by a precedence graph that provides
the precedence constraints between the tasks. As for the plans, the precedence
relations between tasks are described by the notation $\prec$. For example,
given two tasks $J_{1}^{k}$ and $J_{2}^{k}$ belonging to the same plan
$\Pi_{k}$, $J_{1}^{k}\prec J_{2}^{k}$ indicates that the task $J_{1}^{k}$
precedes the execution of the task $J_{2}^{k}$.

######  Definition 6 (Time lag).

A time lag $\delta^{k}_{ij}$ is a fixed amount of time which separates the
finishing and starting times of a pair of tasks $J^{k}_{i}$ and $J^{k}_{j}$
respectively. By default, it is $0$.

In this paper, we assume that there is no preemption in the task execution.
Therefore, the execution of the tasks can not be interrupted once started.
Moreover, we assume that each task could consume more than one resource during
its execution.

######  Definition 7 (Resource).

A resource $\rho$ is any hardware or software tool that tasks can use to
handle information. A resource $\rho$ has a limited availability value
$B_{\rho}$. Resources are typically distinct in renewable and nonrenewable
[6]: renewable resources have a fixed value of availability in each time
period, while nonrenewable resources have a fixed value of availability along
the entire project’s time horizon. In the addressed scheduling problem, we
deal with renewable resources with a fixed availability value of
$B_{\rho}=1,~{}\forall\rho\in\mathcal{R}$, in each time period. In particular,
resources with a fixed availability value of $B_{\rho}=1$ are also called
unary or disjunctive resources.

######  Definition 8 (Resource availability).

The availability $B_{\rho}\in\mathbb{N}_{0}$ of a resource $\rho$ represents
the maximum value of availability of the resource $\rho$ in each time period.

The abstract amount of usage of the resource $\rho$ by the task $J^{k}_{i}$,
in each time period, is represented by $b^{k}_{i\rho}=\\{0,1\\}$.

In this work we are concerned with solving the problem of scheduling plans of
tasks by using a heuristic that maximizes the number of plans scheduled in a
fixed time window, taking into account precedence, time, and resource
constraints.

##  IV Problem statement

###  IV-A Constraints

####  IV-A1 Temporal constraints

When a plan $\Pi_{k}$ is scheduled, for each task $J^{k}_{i}\in\Pi_{k}$ both
the starting time $s^{k}_{i}$ and the completion time
$C^{k}_{i}=s^{k}_{i}+p^{k}_{i}$ must be inside the temporal window
$[W_{s},W_{e}]$ and also inside the temporal window $[r^{k}_{i},d^{k}_{i}]$,
where

$(r^{k}_{i}\geq W_{s})\wedge(d^{k}_{i}\leq W_{e}),~{}\forall
J^{k}_{i}\in\Pi_{k}.$

The value of $s^{k}_{i}$ for a task $J^{k}_{i}\in Pi_{k}$ is calculated as the
maximum value between $W_{s}$, the release date $r^{k}_{i}$ of the task
$J^{k}_{i}$ augmented by the time lag $\delta^{k}_{ij}$, and the maximum
completion time $C^{k}_{j}$ for each predecessor $J^{k}_{j}\in\Pi_{k}$.
Formally,

$\begin{split}s^{k}_{i}=max(W_{s},r^{k}_{i},~{}max_{j\in
pred^{k}_{i}}(C^{k}_{j}+\delta^{k}_{ij})),\end{split}$ (1)

where $pred^{k}_{i}$ is the set of predecessors of the task $J^{k}_{i}$.

Given a set $\mathcal{P}$ of plans, the plan $\Pi_{k}\in\mathcal{P}$ satisfies
the temporal constraints if

$\exists s^{k}_{i}~{}\forall J^{k}_{i}\in\Pi_{k}:(s^{k}_{i}\geq
r^{k}_{i})\wedge(s^{k}_{i}+p^{k}_{i}\leq d^{k}_{i}).$

####  IV-A2 Precedence constraints

In order to maintain the precedence constraints between plans, a set
$\mathcal{P}$ of plans to be scheduled is topologically ordered, since the
precedence between plans can be represented as an acyclic directed graph
(DAG), as showed in Figure 1. In our context, a graph $G$ is a tuple $(V,E)$
where $V$ is a set of vertices and $v_{k}\in V$ represents a plan
$\Pi_{k}\in\mathcal{P}$, and an arc $(u,v)$ represents a precedence constraint
between the plans that are represented by nodes $u$ and $v$ respectively.

####  IV-A3 Resource constraints

The scheduling problem we address assumes that each task $J^{k}_{i}\in\Pi_{k}$
which has a feasible starting time $s^{k}_{i}$, can be executed by a subset
$\mathcal{R}^{k}_{i}\subseteq\mathcal{R}^{k}$ of resources if in the time
period $[s^{k}_{i},C^{k}_{i}]$ the utilization of each resource
$\rho\in\mathcal{R}^{k}_{i}$ does not exceed its availability $B_{\rho}$.

###  IV-B Classification and mathematical formulation

A typical formal way to describe the scheduling problems is by using the
three-field classification $[\alpha,\beta,\gamma]$ introduced by Graham et al.
[9], where

  * •

$\alpha$ specifies the machine environment,

  * •

$\beta$ specifies the characteristics of the activities,

  * •

$\gamma$ and describes the objective function(s).

An extension of the Graham’s classification has been proposed in order to
provide a more accurate way to formally describe the scheduling problems [10].
According to the extended notation, the plans of tasks scheduling problem can
be stated as

$PS1,1,1~{}|~{}prec_{\Pi};~{}prec_{J};~{}[W_{s},W_{e}];~{}[r^{k}_{i},d^{k}_{i}];~{}\delta^{k}_{ij}~{}|~{}\max_{k}\sum_{k}\alpha_{k}x_{k}$

where $PSm,1,1\in\alpha$ indicates a resource environment for a project
scheduling problem with $m$ resources, a maximum availability of $1$ unit per
time for each resource, and a resource utilization, by each task, of at most
$1$ unit per time period.
$prec_{\Pi};~{}prec_{J};~{}[W_{s},W_{e}];~{}[r^{k}_{i},d^{k}_{i}];~{}\delta^{k}_{ij}\in\beta$
depicts the characteristics of both plans and tasks: $prec_{\Pi}$ indicates a
precedence constraints between plans; $prec_{J}$ indicates a precedence
constraints between tasks; $[W_{s},W_{e}]$ and $[r^{k}_{i},d^{k}_{i}]$
indicates, for each task $J^{k}_{i}\in\Pi_{k}$, the time constraints discussed
in IV-A1; $\delta^{k}_{ij}$ indicates that each task $J^{k}_{i}$ can have a
time lag between its starting time $s^{k}_{i}$ and the completion time
$C^{k}_{j}$ of its predecessor.

The mathematical formulations for the RCPSP can be conveniently employed to
model the objective function with respect to the temporal, precedence and
resource constraints [11]. The proposed formulation is based on time
discretization for describing the usage of the resources and the processing of
the tasks over time. In our context the time horizon, divided into unitary
time periods, is a fixed time window $[W_{s},W_{e}]$, where the maximum number
of plans has to be scheduled. Given a plan $\Pi_{k}\in\mathcal{P}$ and a task
$J^{k}_{i}\in\Pi_{k}$, and a time instant $t\in[r^{k}_{i},d^{k}_{i}]$, let
$y^{k}_{it}$ be a boolean variable that indicates whether the task $J^{k}_{i}$
starts exactly at time $t$. Also, let $x_{k}$ be a boolean variable that
indicates whether a plan $\Pi_{k}\in\mathcal{P}$ is executed. Thus, a plan
$\Pi_{k}\in\mathcal{P}$ is executed if

$\sum_{i=1}^{n_{k}}\sum_{t=r^{k}_{i}}^{d^{k}_{i}}y^{k}_{it}=n_{k}~{}\Rightarrow~{}x_{k}=1,$

where $n_{k}$ is the number of tasks in $\Pi_{k}$. If a task $J^{k}_{i}$ has a
feasible starting time $s^{k}_{i}$ equals to $t$, then $y^{k}_{it}=1$ for a
time instant $t\in[r^{k}_{i},d^{k}_{i}]$. Thus, if the sum

$\sum_{i=1}^{n_{k}}\sum_{t=r^{k}_{i}}^{d^{k}_{i}}y^{k}_{it}$

is equal to $n_{k}$, then $\Pi_{k}$ is executed. Therefore, the variable
$x_{k}$ is equal to $1$. By using this notation, the objective function to
maximize can be formulated as:

$\displaystyle\max_{k}\sum_{k=1}^{K}\alpha_{k}x_{k}$

such that,

$\displaystyle\sum_{i=1}^{n_{k}}\sum_{t=r^{k}_{i}}^{d^{k}_{i}}y^{k}_{it}=n_{k}\Rightarrow
x_{k}=1$ $\displaystyle\forall\Pi_{k}\in\mathcal{P}$ (2)
$\displaystyle(t+\delta^{k}_{ij}\geq r^{k}_{i})~{}\wedge$
$\displaystyle(t+\delta^{k}_{ij}+p^{k}_{i}\leq d^{k}_{i})\Rightarrow
y^{k}_{it}=1$ $\displaystyle\forall t\in[W_{s},W_{e}],$ $\displaystyle\forall
J^{k}_{i}\in\Pi_{k}$ (3)
$\displaystyle\sum_{t}t\cdot(y^{k}_{it}-y^{k}_{jt})\geq
p^{k}_{i}+\delta^{k}_{ij}$ $\displaystyle\textnormal{if }J^{k}_{i}\prec
J^{k}_{j},$ $\displaystyle\forall J^{k}_{i},J^{k}_{j}\in\Pi_{k},i\neq j$ (4)
$\displaystyle\sum_{i=1}^{n_{k}}b^{k}_{i\rho}\cdot\sum_{\tau=t}^{t+p^{k}_{i}}y_{i\tau}^{k}\leq
B_{k}$ $\displaystyle\forall\rho\in\mathcal{R},~{}\forall t\in[W_{s},W_{e}]$
(5)

Constraint (2) imposes that for each plan $\Pi_{k}\in\mathcal{P}$ all the
tasks $J^{k}_{i}\in\Pi_{k}$ have a starting time assigned. Constraint (3)
imposes that each task $J^{k}_{i}$ has a starting time and a completion time
within the time window $[r^{k}_{i},d^{k}_{i}]$. Constraints (4) and (5) impose
respectively the precedence and resource constraints.

##  V Proposed method

In this section is discussed a greedy heuristic for the problem of scheduling
plans of tasks.

######  Definition 9 (Schedule).

A schedule $S$ is a vector $(s^{k}_{i})$, $i=1,...,n_{k},~{}k=1,...,K$ such
that $s^{k}_{i}\in S$ is a starting time for the task $J^{k}_{i}$. A schedule
represents a solution for the scheduling problem if it satisfies the
scheduling constraints.

Given a temporal window $W=[W_{s},W_{e}]$, the goal of the proposed heuristic
is to create a feasible schedule that contains the maximum number of plans of
tasks, inside the temporal window $[W_{s},W_{e}]$, regarding their weight,
such that each scheduled plan $\Pi_{k}$ satisfies the precedence, temporal and
resource constraints discussed in IV. The set $\mathcal{P}$ of plans given as
input to the algorithm is preventively sorted in order to maintain their
precedence relations, and also to evaluate, at each iteration of the
algorithm, the plan with the highest priority value. The feasibility of the
plans is evaluated in a schedule $S_{w}$ until no plans remains to schedule,
or there is no plan that can be scheduled due to a violation of the
constraints.

Each plan $\Pi_{k}\in\mathcal{P}$ could have precedence relations between its
tasks. The topological sorting of the tasks ensures that the execution of the
tasks is done with respect to the their precedence relations. Example 1 shows
an example of feasible schedule where a precedence relation occurs between the
tasks of a plan.

######  Example 1.

Figure 3 shows a Gantt diagram for a feasible schedule for a set of plans
$\mathcal{P}=\\{\Pi_{1},\Pi_{2}\\}$, which parameters are listed in Table I. A
precedence constraint occurs between the tasks $J^{2}_{1}$ and $J^{2}_{2}$,
both belonging to the plan $\Pi_{2}$.

| $r^{k}_{i}$ | $d^{k}_{i}$ | $p^{k}_{i}$ | $\delta^{k}_{ij}$ | $\mathcal{R}^{k}_{i}$ | $J^{k}_{i}\prec J^{k}_{j}$
---|---|---|---|---|---|---
$J^{1}_{1}$ | $2$ | $7$ | $3$ | $0$ | $\\{1\\}$ |
$J^{2}_{1}$ | $3$ | $8$ | $2$ | $0$ | $\\{2\\}$ | $J^{2}_{1}\prec J^{2}_{2}$
$J^{2}_{2}$ | $4$ | $9$ | $2$ | $0$ | $\\{1\\}$ |
TABLE I: The parameters of the tasks of the plans $\Pi_{1}$ and $\Pi_{2}$ in
the Example 1. Figure 3: A feasible schedule for the set $\mathcal{P}$ of two
plans. A precedence constraint occurs between $J^{2}_{1}$ and $J^{2}_{2}$.

The task $J^{2}_{2}$ has been scheduled after the end of the execution of the
task $J^{2}_{1}$, since there is a precedence constraint between $J^{2}_{1}$
and $J^{2}_{2}$. For this reason, the task $J^{2}_{2}$ has not been scheduled
at $5$.

For a given DAG, more than one topological sort could exist. Under this
assumption, different topological sorting for a plans’ precedence graph could
lead to different schedules. For this reason, the plans belonging to the same
frontier are sorted by their priority value, since for these plans the order
in which they are scheduled is irrelevant according to the precedence
constraints. Moreover, different plans may have the same priority value: in
this case, the plans must be sorted according to a different criterion
described in the following.

Given a feasible schedule $S_{w}$ and a subset
$\mathcal{P}_{\alpha_{k}}\subseteq\mathcal{P}$ of plans having the same
priority value $\alpha_{k}$, in order to maximize the resource utilization for
each tasks $J^{k}_{i}\in\Pi_{k}\in\mathcal{P}_{\alpha_{k}}$ we calculate an
idle time between each task $J^{k}_{i}\in\Pi_{k}$ and its predecessor, in the
same resource.

######  Definition 10 (Idle time).

Let $S$ be a feasible schedule containing two plans $\Pi_{k}$, $\Pi_{p}$,
$p\neq k$. Let $J^{k}_{i}\in\Pi_{k}$ and $J^{p}_{j}\in\Pi_{p}$ be two tasks
scheduled on the same resource $\rho\in\mathcal{R}$, where
$s^{k}_{i}>C^{p}_{j}$. If there is at least one plan $\Pi_{q}$ schedulable in
$S$ such that $\exists J^{q}_{l}\in\Pi_{q}$ executed by the same resource
$\rho\in\mathcal{R}$ such that

$(C^{p}_{j}\leq s^{q}_{l}<s^{k}_{i})\wedge(C^{p}_{j}<C^{q}_{l}\leq
s^{k}_{i}),$

the time window $[C^{p}_{j},s^{k}_{i}]$ is said to be an idle time.

In Figure 4 is showed an idle time between two tasks.

Figure 4: The time window $[C^{p}_{j},s^{k}_{i}]$ is an idle time because
$J^{q}_{l}\in\Pi_{q}$ can be scheduled in this interval.

Let $S$ be a feasible schedule, and $\mathcal{P}_{\alpha_{k}}$ a set of plans
having each one priority $\alpha_{k}$. The plans of $\mathcal{P}_{\alpha_{k}}$
are scheduled in order to minimize the presence of idle times. This is done by
choosing iteratively the plans who minimize the following quantity:

$\sum_{i}s^{k}_{i}-C_{\Gamma^{k}_{i}(\rho_{i})},~{}\forall
J^{k}_{i}\in\Pi_{k}\in\mathcal{P}_{\alpha_{k}}$

where $C_{\Gamma^{k}_{i}(\rho_{i})}$ is the completion time of the task
$\Gamma^{k}_{i}(\rho_{i})$, that is, the predecessor of task $J^{k}_{i}$ in
the same resource $\rho_{i}$ executing the task $J^{k}_{i}$.

Example 2 shows how the idle time is used by the proposed heuristic to
determine the order according to which two plans have to be scheduled.

######  Example 2.

Let $\mathcal{P}=\\{\Pi_{1},\Pi_{2},\Pi_{3},\Pi_{4}\\}$ be a set of plans to
schedule, which information are listed in Table II, and let $S_{w}$ be a
feasible schedule where $\Pi_{1}$ and $\Pi_{2}$ have been scheduled (Figure
5(a)). Let $\mathcal{P}_{l}=\\{\Pi_{3},\Pi_{4}\\}$ be a set of two plans such
that $\Pi_{3}$ and $\Pi_{4}$ have priority values $\alpha_{3}=l$ and
$\alpha_{4}=l$ respectively. As showed in Figure 5(b)-5(c), both plans
$\Pi_{3}$ and $\Pi_{4}$ generate two feasible schedules.

| $r^{k}_{i}$ | $d^{k}_{i}$ | $p^{k}_{i}$ | $\delta^{k}_{ij}$ | $\mathcal{R}^{k}_{i}$ | $J^{k}_{i}\prec J^{k}_{j}$
---|---|---|---|---|---|---
$J^{1}_{1}$ | $2$ | $7$ | $3$ | $0$ | $\\{1\\}$ |
$J^{2}_{1}$ | $2$ | $6$ | $2$ | $0$ | $\\{2\\}$ |
$J^{2}_{2}$ | $4$ | $10$ | $3$ | $0$ | $\\{1\\}$ |
$J^{3}_{1}$ | $4$ | $7$ | $2$ | $0$ | $\\{3\\}$ |
$J^{4}_{1}$ | $3$ | $6$ | $1$ | $0$ | $\\{4\\}$ | $J^{4}_{1}\prec J^{4}_{2}$
$J^{4}_{2}$ | $2$ | $7$ | $3$ | $0$ | $\\{2\\}$ |
TABLE II: The parameters of the tasks of a set $\mathcal{P}$ of $4$ plans.

The difference between the starting time $s^{3}_{1}$ and its predecessor (in
this case $W_{s}$ since there is no predecessor of $J^{3}_{1}$) is equal to 2.
Within $\mathcal{P}_{l}$, the plan $\Pi_{4}$ has a task $J^{4}_{1}$ that can
be scheduled at $s^{4}_{1}=3<s^{3}_{1}$, where all the constraints are
satisfied, and both $J^{4}_{1}$ and $J^{3}_{1}$ demand the same resource.
Moreover, scheduling the plan $\Pi_{4}$ before $\Pi_{3}$ leads to a schedule
where no idle times are generated. Therefore, plan $\Pi_{4}$ is scheduled
before plan $\Pi_{3}$.

(a)

(b)

(c)

Figure 5: Scheduling plans with the same priority value into a schedule with
two plans schedule (Figure 5(a)). Scheduling plan $\Pi_{3}$ before plan
$\Pi_{4}$ (Figure 5(b)) leads to a schedule with an idle time of 2, since in
the interval $[2,4]$ the task $J^{4}_{1}$ of the feasible plan $\Pi_{4}$ can
be scheduled. Scheduling plan $\Pi_{4}$ before $\Pi_{3}$ (Figure 5(c)) leads
to a schedule with an idle time of 0. Therefore, $\Pi_{3}$ is scheduled before
$\Pi_{4}$.

The scheduling algorithm operates in a similar way as the serial scheduling
scheme proposed in [11]. In our context, we assume that each resource has a
maximum availability of 1 in each time period. In this case, each resource can
execute one task at a time. The idea of the proposed heuristic is to schedule
all the plans as soon as possible by respecting the resource, precedence and
temporal constraints. The insertion of the plans into a schedule is done by
handling an event list $\mathcal{EL}$. An event is a $4$-tuple
$(t(e),\mathcal{S}(e),\mathcal{C}(e),(b_{\rho}(e))_{\rho\in\mathcal{R}})$:

  * •

$t(e)$ denotes the time instant of the event;

  * •

$\mathcal{S}(e)$ is the set of tasks starting exactly at time $t(e)$;

  * •

$\mathcal{C}(e)$ is the set of tasks completing exactly at time $t(e)$;

  * •

$b_{\rho}(e)$ represents the usage of resource $\rho$ during interval
$[t(e),t(next_{e})[$, where $next_{e}$ is the first event following $e$ in
$\mathcal{EL}$.

When a feasible task $J^{k}_{i}$ is scheduled and inserted into
$\mathcal{S}(e)$ for a an event $e\in\mathcal{EL}$, the usage of the resource
$b_{\rho}(e)$ is set to $1$. The resource constraints for the scheduling
problem we address assumes that no task can be scheduled at $t(e)$ if
$b_{\rho}(e)=1$.

###  V-A Description of the heuristic

The proposed heuristic (Algorithm 1) ($BuildSchedule$) takes in input a set
$\mathcal{P}$ of plans and a set $\mathcal{R}$ of resources, and it gives as
output a feasible schedule $S_{l}$, that is, a vector of starting times
$s^{k}_{i}$ for each scheduled task $J^{k}_{i}\in\Pi_{k}$ such that the
constraints discussed in the previous section are met.

At the beginning, the algorithm initializes the used data structures. At line
1 and 2 respectively, two set $\mathcal{P}_{s}$ and $\mathcal{P}_{f}$ are
initialized: they will be used to store respectively the successfully
scheduled plans and the discarded (unscheduled) plans. Then, two empty
schedules $S_{l}$ and $S_{w}$ are initialized. They will contain respectively
the last feasible schedule found and the current working schedule. The working
schedule is a schedule used for testing the feasibility of the plans during
the search. Finally, an event list $\mathcal{EL}$ is initialized at line 5.
The first step of the algorithm is to sort the set $\mathcal{P}$ of plans
according to both precedence relations and priority values (line 6). This is
done by Algorithm 2, that returns a sorted list $\mathcal{P}_{u}$ of plans.
Then, a loop over $\mathcal{P}_{u}$ starts until there is a plan left to
schedule (line 7). At line 8, the highest priority plan $\Pi_{k}$ is taken
from the sorted set $\mathcal{P}_{u}$ of plans. Then, at line 10 the algorithm
checks if there exists more than one plan in $\mathcal{P}_{u}$ with the same
priority value $\alpha_{k}$ of $\Pi_{k}$. If the value of $\alpha_{k}$ is
unique among the values of priority of the plans in $\mathcal{P}_{u}$, the
algorithm tries to schedule the plan (line 11), otherwise a set
$\mathcal{P}_{\alpha_{k}}\subset\mathcal{P}$ of plans is calculated,
containing all the plans that have priority value $\alpha_{k}$. All the plans
in $\mathcal{P}_{\alpha_{k}}$ are then scheduled by Algorithm 5. Thus, the
plans successfully scheduled are added into $\mathcal{P}_{s}$ (line 20), and
the plans not scheduled are removed from the working schedule (line 22).
Finally, the last feasible schedule $S_{l}$ is updated (line 24).

Algorithm 1 takes at most $O(K^{3}n^{3})$ time, where $K=|\mathcal{P}|$ is the
number of plans to schedule.

All the data structures used for storing plans, $\mathcal{P}$,
$\mathcal{P}_{u}$, $\mathcal{P}_{s}$ and $\mathcal{P}_{f}$, are implemented as
self-balancing binary search trees to ensure insertion, removal and get
operations in logarithmic time [7]. At line 5 the event list $\mathcal{EL}$ is
initialized. As the data structures used for storing plans, the event list is
implemented as self-balancing binary search tree. At line 6 the plans are
sorted by the Algorithm 2.

The while loop 7-26 iterates until the set of plans $\mathcal{P}_{u}$ is not
empty. In the worst case, if the plans belongs all to the same frontier, the
inner loop takes at most $O(K^{3}n^{3})$ time.

The $Get$ operations at line 8 takes logarithmic time with respect to the
number of elements in $\mathcal{P}_{u}$.

At line 9 the algorithm get the number of plans in $\mathcal{P}_{u}$ that have
priority value $\alpha_{k}$. We use an auxiliary data structure to store this
information and get the value in $O(1)$.

The $Add$ and $Remove$ operations at line 13 and 15 respectively require both
$O(\log K)$ time. Getting the plans with priority $\alpha_{k}$ (line 18)
requires constant time, since a hash map is used to store the plans with the
same priority value: the key of a record is a value of priority $\alpha_{k}$,
and the value is a list of plans having each one $\alpha_{k}$ as priority
value.

The $Add$ operation at line 20 requires $O(K\log K)$ time. The $Remove$
operations at line 21 and 22 require both $O(K\log K)$ time.

Algorithm 1 BuildSchedule

0: A set of plans $\mathcal{P}$

0: A feasible schedule $S_{l}$, a set $\mathcal{P}_{s}$ of scheduled plans, a
set $\mathcal{P}_{f}$ of unscheduled plans

1: $\mathcal{P}_{s}\leftarrow\\{\\}$ {Scheduled plans}

2: $\mathcal{P}_{f}\leftarrow\\{\\}$ {Discarded plans}

3: $S_{l}\leftarrow\left(\right)$ {Feasible schedule}

4: $S_{w}\leftarrow\left(\right)$ {Working schedule}

5: $\mathcal{EL}\leftarrow\\{\\}$

6: $\mathcal{P}_{u}\leftarrow$ SortPlans($\mathcal{P}$)

7: while $\mathcal{P}_{u}\neq\emptyset$ do

8: $\Pi_{k}\leftarrow$ Get($\mathcal{P}_{u}$)

9: $\mathcal{N}_{\alpha_{k}}\leftarrow$ number of plans in $\mathcal{P}_{u}$
with priority $\alpha_{k}$

10: if $\mathcal{N}_{\alpha_{k}}=1$ then

11: $success\leftarrow$ SchedulePlan($\Pi_{k}$, $S_{w}$, $\mathcal{EL}$)

12: if $success$ then

13: Add($\Pi_{k}$, $\mathcal{P}_{s}$)

14: else

15: Remove($\Pi_{k}$, $S_{w}$)

16: end if

17: else

18: $\mathcal{P}_{\alpha_{k}}\leftarrow$ plans of $\mathcal{P}$ with priority
$\alpha_{k}$

19: $\mathcal{U}\leftarrow$ SchedulePlanSet($\mathcal{P}_{\alpha_{k}}$,
$S_{w}$, $\mathcal{EL}$)

20: Add($\mathcal{P}_{\alpha_{k}}\setminus\mathcal{U}$, $\mathcal{P}_{s}$)

21: Remove($\mathcal{P}_{\alpha_{k}}$, $\mathcal{P}_{u}$)

22: Remove($\mathcal{U}$, $S_{w}$)

23: end if

24: $S_{l}\leftarrow S_{w}$

25: $\mathcal{P}_{f}=\mathcal{P}\setminus\mathcal{P}_{s}$

26: end while

Algorithm 2 ($SortPlans$) sort a set $\mathcal{P}$ of plans in decreasing
order of priority so that the precedence constraints between plans are also
respected. At line 1 a topological sort algorithm is executed for the plan
set. A set of couples $(\Pi_{i},F_{i})$ is returned, where $\Pi_{i}$ is the
$i$-th plan in the topological sorting, and $F_{i}$ is the subset of plans of
the frontier $f_{i}$ which the plan $\Pi_{i}$ belongs to. Then, let $F$ be the
set of subsets $F_{i}$ of plans for each frontier $f_{i}$ (line 2), a loop
over each set $F_{i}$ is done (line 4-7), where each $F_{i}$ is sorted
according to the priority value the plans in the frontier $f_{i}$ (line 5),
and then added to the set $\mathcal{P}_{u}$ of sorted plans (line 6).

Algorithm 2 takes at most $O(K\log K+n_{k})$, where $K=|\mathcal{P}|$ is the
number of the plans to be sorted. At line 1, the set of plans is topologically
sorted. The topological sort requires at most $O(K+n_{k})$ where $n_{k}$ is
the number of predecessors in the precedence’s graph of the plan $\Pi_{k}$.

At line 2 the set of frontiers discovered by the topological sort is
assembled: this set is implemented as an hash table where the key of a record
is a priority value $\alpha_{k}$, and the value is a list of plans having each
one $\alpha_{k}$ as priority value.

The loop 4-7 iterates over each frontier in the precedence’s graph, and sort
the plans belonging to that frontier according to their priority value. At
line 5, plans belonging to a specific frontier $f$ are sorted by using the
timsort algorithm [12]. The for loop requires at most $O(K\log K)$ time if all
the plans belong to the same frontier.

Algorithm 2 SortPlans

0: A set of plans $\mathcal{P}$

0: A sorted set of plans $\mathcal{P}_{u}$

1: $\mathcal{P}_{t}\leftarrow TopologicalSort(\mathcal{P})$

2: compute $F_{i}$ for $i=1,...,f$

3: $\mathcal{P}_{u}=\emptyset$

4: for $i=1,...,f$ do

5: sort $F_{i}$ according to $\alpha$

6: $Add(F_{i},\mathcal{P}_{u})$

7: end for

8: return $\mathcal{P}_{u}$

Algorithm 3 ($SchedulePlan$) schedules a single plan $\Pi_{k}$ into a schedule
$S_{w}$ using an event list $\mathcal{EL}$. It iterates over all the tasks
$J^{k}_{i}\in\Pi_{k}$ and for each task, the precedence constraints are
checked, and then the task is scheduled into the schedule $S_{w}$. If at least
one task could not be scheduled, the algorithm immediately breaks the loop,
and false is returned, since the plan could not be scheduled such that all the
constraints are satisfied.

Algorithm 3 takes $O(n^{3})$ time, where
$n=\sum_{k}n_{k},\forall\Pi_{k}\in\mathcal{P}$ is the total number of tasks
already scheduled in $S_{w}$. Inside the loop the Algorithm 4 is executed
$O(n_{k})$ time.

Algorithm 3 SchedulePlan

0: A plan $\Pi_{k}$, a schedule $S_{w}$, an event list $\mathcal{EL}$

0: $true$ if $\Pi_{k}$ has been scheduled in $S_{w}$, $false$ otherwise.

1: for all task $J^{k}_{i}\in\Pi_{k}$ do

2: success $\leftarrow$ scheduleTask($J^{k}_{i}$, $S_{w}$, $\mathcal{EL}$)

3: if not success then

4: mark $\Pi_{k}$ as unschedulable

5: return $false$

6: end if

7: end for

8: return $true$

Algorithm 4 ($ScheduleTask$) do the actual task insertion into a schedule. It
starts by calculating the earliest possible starting time given by (1) if we
do not consider the resource availability. At line 2 the algorithm searches
for an event $e$ in $\mathcal{EL}$ such that $t(e)=s^{k}_{i}$. If such event
does not exist, a new event $e$ is created at $t(e)=s^{k}_{i}$. At line 4, the
algorithm starts a loop to search for the earliest feasible start and end
events $e$ and $f$ for the task $J^{k}_{i}$. The loop iterates until $f$ is
not the last event or the remaining duration $\mu$, initially set to
$p^{k}_{i}$, it is not null. If the condition of the while loop is satisfied,
$g$ is assigned the event following $f$ (line 5), and the algorithm proceeds
by checking the resource availability and the constraints test for $J^{k}_{i}$
in $t(e)$ (line 6). If both the tests succeed, $\mu$ is decreased by
$t(g)-t(f)$ and $g$ is assigned to $f$. If the tests fail, then $e$ is not a
valid insertion position, and then $e$ is set to $g$ while $\mu$ is reset to
$p^{k}_{i}$. After the loop, a final check for the constraints is done (line
13). If the final check fails, then all the tasks of the plan $\Pi_{k}$ are
removed from each event $e$ in the event list $\mathcal{EL}$ (line 14), the
plan $\Pi_{k}$ is marked as unschedulable (line 15) and $false$ is returned.

Once the constraints are verified for $e$ at line 13, the algorithm proceed
with the insertion of the task $J^{k}_{i}$ into the working schedule (line
18), and into the event $e$ (line 19). Then, at line 21, the event $e$ is
added into the event list $\mathcal{EL}$ if it is not already in. The steps
(23-31) update the event list. The last step consists in updating the
resources usage by the scheduled tasks (line 32).

Algorithm 4 has a time complexity of $O(n^{2})$, where $n=\sum_{k}n_{k}$.
Searching for a feasible starting time $s^{k}_{i}$ (line 1) requires at most
$O(n-1)$ time if task $J^{k}_{i}$ has $n-1$ predecessors. Searching for the
event $e$ such that $t(e)=s^{k}_{i}$ (line 2) requires at most
$O(\log|\mathcal{EL}|)$ since a balanced tree data structure is used for the
event list.

In the worst case, for a set $\mathcal{P}$ of plans with cardinality
$|\mathcal{P}|=K$, the maximum number of events in $\mathcal{EL}$ is $2n$ if
we suppose that all the tasks are scheduled consecutively with a minimal lag
between each task, that is

$|\mathcal{S}(e)|=1\wedge|\mathcal{C}(e)|=0~{}\vee$
$|\mathcal{S}(e)|=0\wedge|\mathcal{C}(e)|=1,~{}\forall e\in\mathcal{EL}.$

The while loop (lines 4-12) iterates over the event list $\mathcal{EL}$. Since
there are less than $2n$ events, the while loop takes $O(n)$ time.

Searching for the event following $f$ in $\mathcal{EL}$ (line 5) takes at most
$O(\log|\mathcal{EL}|)$ time. Checking if the temporal constraints are
satisfied at $t(e)$ (line 6) takes $O(1)$ time. The remaining operations
inside the loop require constant time.

Removing all the tasks $J^{k}_{i}\in\Pi_{k}$ from each event
$e\in\mathcal{EL}$ (line 14) takes $O(n_{k}\log|\mathcal{EL}|)$.

Adding the task $J^{k}_{i}$ to the schedule $S_{w}$ (line 18) requires at most
$O(\log n)$ since an efficient balanced tree data structure is used for the
schedules. Adding the task $J^{k}_{i}$ to the set $\mathcal{S}_{e}$ (line 19)
requires constant time.

Adding the event $e$ to the event list $\mathcal{EL}$ (line 21) requires
$O(\log|\mathcal{EL}|)$ time.

The event list update takes $O(\log|\mathcal{EL}|)$ if the event $g$ has to be
inserted in $\mathcal{EL}$ (lines 26,29), otherwise the insertion of
$J^{k}_{i}$ into $\mathcal{C}(f)$ (line 24) requires $O(1)$ time.

Algorithm 4 ScheduleTask

0: A task $J^{k}_{i}$, a schedule $S_{w}$, an event list $\mathcal{EL}$

0: $true$ if $J^{k}_{i}$ has been scheduled in $S_{w}$, $false$ otherwise.

1: $s^{k}_{i}=max(W_{s},r^{k}_{i},~{}max_{j\in
pred^{k}_{i}}(C^{k}_{j}+\delta^{k}_{ij}))$

2: $e\leftarrow$ GetEvent($s^{k}_{i}$, $\mathcal{EL}$)

3: $\mu\leftarrow p^{k}_{i};f\leftarrow e$

4: while ($f$ is not the last event of $\mathcal{EL})\wedge(\mu>0)$ do

5: $g\leftarrow next_{f}$

6: if
$(b_{\rho}(f)=0,~{}\forall\rho\in\mathcal{R}^{k}_{i})\wedge$$($CheckConstraints$(t(e),J^{k}_{i}))$
then

7: $\mu\leftarrow max(0,\mu-t(g)+t(f))$

8: $f\leftarrow g$

9: else

10: $\mu\leftarrow p^{k}_{i}$; $e\leftarrow g$; $f\leftarrow g$

11: end if

12: end while

13: if not CheckConstraints$(t(e),J^{k}_{i})$ then

14: remove all tasks $J^{k}_{i}\in\Pi_{k}$ from $e$, $\forall
e\in\mathcal{EL}$

15: mark $\Pi_{k}$ as unschedulable

16: return false

17: end if

18: Add($J^{k}_{i}$, $S_{w}$)

19: Add($J^{k}_{i}$, $\mathcal{S}$($e$))

20: if $e\notin\mathcal{EL}$ then

21: $\mathcal{EL}\leftarrow\mathcal{EL}\cup e$

22: end if

23: if $t(e)+p^{k}_{i}=t(f)$ then

24: Add($J^{k}_{i}$, $\mathcal{C}$($f$))

25: else if $t(e)+p^{k}_{i}>t(f)$ then

26: insert
$g=(t(e)+p^{k}_{i},\emptyset,\\{t\\},(b_{\rho}(f))_{\forall\rho\in\mathcal{R}^{k}_{i}})$
in $\mathcal{EL}$

27: $f\leftarrow g$

28: else

29: insert
$g=(t(e)+p^{k}_{i},\emptyset,\\{t\\},(b_{\rho}(pred_{f}))_{\forall\rho\in\mathcal{R}^{k}_{i}})$
in $\mathcal{EL}$

30: $f\leftarrow g$

31: end if

32: $b_{\rho}(g)=1~{}\forall\rho\in\mathcal{R}^{k}_{i},~{}\forall g$ between
$e$ and $pred_{f}$ in $\mathcal{EL}$

33: return true

Algorithm 5 ($SchedulePlanSet$) schedules a set $\mathcal{P}_{\alpha_{k}}$ of
plans such that each plan $\Pi_{k}\in\mathcal{P}_{\alpha_{k}}$ has a priority
value $\alpha_{k}$. The idea of the algorithm is to find, at each iteration,
the plan who minimizes the sum of the size of the idle time windows generated
by its tasks. The algorithm starts by creating a copy $V$ of the plan set
$\mathcal{P}_{\alpha_{k}}$ (line 1). The while loop (lines 3-25) iterates
until there is no plan left in $V$ to schedule. At each iteration, two
variables $minIdleTime$ and $bestPlan$ are used to keep the next candidate
plan to schedule. The loop at (6-19) iterates over the plans in $V$ and
searches for the candidate plan to schedule. Each plan $\Pi_{k}$ is scheduled
into a temporary schedule $S_{temp}$ (line 9). At each iteration, the
algorithm chooses the plan $\Pi_{k}\in\mathcal{P}_{\alpha_{k}}$ that minimizes
the sum of the time differences between $t(e)$ and $t(pred_{e})$ (line 11),
for each event $e$ such that $J^{k}_{i}\in\mathcal{S}(e)$, $\forall
J^{k}_{i}\in\Pi_{k}$.

Algorithm 5 takes at most $O(K^{2}n^{3})$ time. The main loop (lines 3-25) is
repeated until there is some plan left to schedule, and it is repeated at most
$O(K)$ time. The inner loop (lines 6-19) schedule each plan
$\Pi_{k}\in\mathcal{P}_{\alpha_{k}}$ and keeps the plan which minimize the
idle times between each task and its predecessor. The inner loop takes
$O(Kn^{3})$ time.

Algorithm 5 SchedulePlanSet

0: A set $\mathcal{P}_{\alpha_{k}}\subset\mathcal{P}$ of plans, a schedule
$S_{w}$, an event list $\mathcal{EL}$

0: A set $\mathcal{U}$ of unscheduled plans

1: $V\leftarrow\mathcal{P}_{\alpha_{k}}$

2: $\mathcal{U}\leftarrow\emptyset$

3: while $V\neq\emptyset$ do

4: $minIdleTime\leftarrow+\infty$

5: $bestPlan\leftarrow\emptyset$

6: for all $\Pi_{k}\in\mathcal{P}_{\alpha_{k}}$ do

7: $S_{temp}\leftarrow S_{w}$

8: $\mathcal{EL}_{temp}\leftarrow\mathcal{EL}$

9: $success\leftarrow schedulePlan(\Pi_{k},S_{temp},\mathcal{EL}_{temp})$

10: if $success$ then

11: $it=\sum_{i}(t(e)-t(pred_{e})),\forall J^{k}_{i}\in\mathcal{S}(e)$

12: if $it\leq minIdleTime$ then

13: $minIdleTime\leftarrow it$

14: $bestPlan\leftarrow\Pi_{k}$

15: end if

16: else

17: $Remove(\Pi_{k},V)$

18: end if

19: end for

20: $success\leftarrow schedulePlan(bestPlan,S_{w},\mathcal{EL})$

21: if not $success$ then

22: $Add(bestPlan,\mathcal{U})$

23: end if

24: $Remove(bestPlan,V)$

25: end while

26: return $\mathcal{U}$

Algorithm 6 ($CheckConstraints$) checks if a starting time $t(e)$ satisfies
the temporal constraints, discussed in IV-A1, for a task $J^{k}_{i}$. If the
temporal constraints are satisfied, the algorithm returns true.

Algorithm 6 requires constant time.

Algorithm 6 CheckConstraints

0: A task $J^{k}_{i}$, a starting time $t(e)$ for $J^{k}_{i}$

0: $true$ if $J^{k}_{i}$ satisfies the temporal constraints, $false$
otherwise.

1: if
$\left(t(e)\in[r^{k}_{i},d^{k}_{i}]\right)\wedge\left(t(e)\in[W_{s},W_{e}]\right)\wedge\left(t(e)+p^{k}_{i}\in[W_{s},W_{e}]\right)$
then

2: return true

3: end if

4: return false

In Table III are resumed the functions employed by the proposed method,
together with a short description and their time complexity.

Function name and description |  Time complexity
---|---
$BuildSchedule(\mathcal{P})$ |
Entry point algorithm. It is responsible |
for assembling a feasible schedule for a set $\mathcal{P}$ of plans. |  $O(K^{3}n^{3})$
$SchedulePlan(\Pi_{k},S_{w},\mathcal{EL})$ |
Schedule the plan $\Pi_{k}$ into the schedule $S_{w}$. |  $O(n^{3})$
$SchedulePlanSet(\mathcal{P}_{\alpha_{k}},S_{w},\mathcal{EL})$ |
Schedule a set of plans $\mathcal{P}_{\alpha_{k}}$ that have the same priority value into the schedule $S_{w}$. |  $O(K^{2}n^{3})$
$ScheduleTask(J^{k}_{i},S_{w},\mathcal{EL})$ |
Schedule the task $J^{k}_{i}$ into the schedule $S_{w}$. |  $O(n^{2})$
$SortPlans(\mathcal{P})$ |
Sort a set of plans $\mathcal{P}$ according to their precedence relations by using $TopologicalSort$ algorithm. Then, the plans that belong to the same frontier in the topological sorting are sorted by their priority value. |  $O(K\log K+n_{k})$
$TopologicalSort(\mathcal{P})$ |
Sort a set of plans $\mathcal{P}$ according to their precedence relations by using a topological sorting algorithm. It returns a sorted copy of the plan set given as input. |  $O(K+n_{k})$
$GetEvent(s^{k}_{i},\mathcal{EL})$ |
Get the event $e\in\mathcal{EL}$ such that $t(e)=s^{k}_{i}$. If such event does not exists, a new event $e$ is created at $t(e)=s^{k}_{i}$. |  $O(\log|\mathcal{EL}|)$
$Get(\mathcal{P})$ Get the highest priority plan from $\mathcal{P}$. |  $O(\log K)$
TABLE III: Descriptions of the functions used by the scheduling algorithm.

######  Example 3.

In this example we show how different plans are scheduled according to the
proposed heuristic. We start from a feasible schedule containing two plans
$\Pi_{1}$ and $\Pi_{2}$, and we try to schedule in order the plans $\Pi_{3}$,
$\Pi_{4}$ and $\Pi_{5}$. In Table IV are listed the parameters of the plans of
tasks $\mathcal{P}=\\{\Pi_{1},\Pi_{2},\Pi_{3},\Pi_{4},\Pi_{5}\\}$.

| $r^{k}_{i}$ | $d^{k}_{i}$ | $p^{k}_{i}$ | $\delta^{k}_{ij}$ | $\mathcal{R}^{k}_{i}$ | $J^{k}_{i}\prec J^{k}_{j}$
---|---|---|---|---|---|---
$J^{1}_{1}$ | $1$ | $7$ | $4$ | $0$ | $\\{1\\}$ | $J^{1}_{1}\prec J^{1}_{2}$
$J^{1}_{2}$ | $5$ | $8$ | $2$ | $1$ | $\\{3\\}$ |
$J^{2}_{1}$ | $4$ | $7$ | $2$ | $0$ | $\\{2\\}$ | $J^{2}_{1}\prec J^{2}_{2}$
$J^{2}_{2}$ | $5$ | $9$ | $3$ | $0$ | $\\{1\\}$ |
$J^{3}_{1}$ | $1$ | $8$ | $3$ | $0$ | $\\{3\\}$ |
$J^{4}_{1}$ | $2$ | $7$ | $2$ | $0$ | $\\{2\\}$ | $J^{4}_{1}\prec J^{4}_{2}$
$J^{4}_{2}$ | $3$ | $7$ | $1$ | $2$ | $\\{3\\}$ |
$J^{5}_{1}$ | $5$ | $10$ | $3$ | $0$ | $\\{2\\}$ | $J^{5}_{1}\prec J^{5}_{2}$
$J^{5}_{2}$ | $5$ | $11$ | $1$ | $0$ | $\\{1,3\\}$ |
TABLE IV: The parameters of the tasks of the plans in Example 3.

Let $\Pi_{3}$ be the next plan to be scheduled, which has only one task
$J^{3}_{1}$. The earliest starting time $s^{3}_{1}$ is set to the release time
$r^{3}_{1}=1$. The event $e_{1}\in\mathcal{EL}$ has a time instant
$t(e)=r^{3}_{1}=1$, thus $e_{1}$ is the first event in which $J^{3}_{1}$ can
be scheduled. The resource constraints in $e_{1}$ are satisfied for
$J^{3}_{1}$, so it can be scheduled at $t(e_{1})=2$. The resource usages
$b_{3}(e_{1})$ and $b_{3}(e_{2})$ are finally updated.

Table V shows the resulting Gantt diagram and the event list $\mathcal{EL}$
after the insertion of the plan $\Pi_{3}$.

$e$ | $t(e)$ | $\mathcal{S}(e)$ | $\mathcal{C}(e)$ | $b_{1}(e)$ | $b_{2}(e)$ | $b_{3}(e)$
---|---|---|---|---|---|---
$e1$ | $2$ | $\\{J^{1}_{1},\bm{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}J^{3}_{1}}}\\}$ | $\emptyset$ | $1$ | $0$ | $1$
$e2$ | $4$ | $\\{J^{2}_{1}\\}$ | $\emptyset$ | $1$ | $1$ | $1$
$e3$ | $5$ | $\emptyset$ | $\\{\bm{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}J^{3}_{1}}}\\}$ | $1$ | $1$ | $0$
$e4$ | $6$ | $\\{J^{2}_{2}\\}$ | $\\{J^{2}_{1},J^{1}_{1}\\}$ | $1$ | $0$ | $0$
$e5$ | $7$ | $\\{J^{1}_{2}\\}$ | $\emptyset$ | $1$ | $0$ | $1$
$e6$ | $9$ | $\emptyset$ | $\\{J^{1}_{2},J^{2}_{2}\\}$ | $0$ | $0$ | $0$

TABLE V: Insertion of the plan $\Pi_{3}$ into a feasible schedule.

Following, plan $\Pi_{4}$ is the next plan to be scheduled. The earliest
starting time $s^{4}_{1}$ for $J^{4}_{1}$ is $s^{4}_{1}=t(e_{1})=W_{s}$. At
$e_{1}$ the temporal and resource constraints for $J^{4}_{1}$ are satisfied,
so it is scheduled at $s^{4}_{1}=t(e_{1})=2$, and then the resource usages
$b_{2}(e_{1})$ is updated. Following, an insertion point is searched for the
task $J^{4}_{2}$. The earliest starting time for $J^{4}_{2}$ is
$s^{4}_{2}=t(e_{4})=6$, since there is a time lag between $J^{4}_{2}$ and its
predecessor $J^{4}_{1}$. The event $e_{4}$ is a good insertion point for the
task $J^{4}_{2}$, since here the precedence, resource and temporal constraints
are met. $J^{4}_{2}$ is finally scheduled at $s^{4}_{2}=t(e_{4})=6$. The
resource usage $b_{3}(e_{4})$ is updated. Since a feasible insertion point has
been found for both $J^{4}_{1}$ and $J^{4}_{2}$, the plan $\Pi_{4}$ is
scheduled correctly and the schedule generated is considered as feasible
schedule.

Table VI shows the resulting Gantt diagram and the event list $\mathcal{EL}$
after the insertion of the plan $\Pi_{4}$.

$e$ | $t(e)$ | $\mathcal{S}(e)$ | $\mathcal{C}(e)$ | $b_{1}(e)$ | $b_{2}(e)$ | $b_{3}(e)$
---|---|---|---|---|---|---
$e1$ | $2$ | $\\{J^{1}_{1},J^{3}_{1},\bm{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}J^{4}_{1}}}\\}$ | $\emptyset$ | $1$ | $1$ | $1$
$e2$ | $4$ | $\\{J^{2}_{1}\\}$ | $\\{\bm{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}J^{4}_{1}}}\\}$ | $1$ | $1$ | $1$
$e3$ | $5$ | $\emptyset$ | $\\{J^{3}_{1}\\}$ | $1$ | $1$ | $0$
$e4$ | $6$ | $\\{\bm{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}J^{4}_{2}}},J^{2}_{2}\\}$ | $\\{J^{2}_{1},J^{1}_{1}\\}$ | $1$ | $0$ | $1$
$e5$ | $7$ | $\\{J^{1}_{2}\\}$ | $\\{\bm{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}J^{4}_{2}}}\\}$ | $1$ | $0$ | $1$
$e6$ | $9$ | $\emptyset$ | $\\{J^{1}_{2},J^{2}_{2}\\}$ | $0$ | $0$ | $0$

TABLE VI: Insertion of the plan $\Pi_{4}$ into a feasible schedule.

Finally, plan $\Pi_{5}$ is the last plan to be scheduled. The earliest
starting time for $J^{5}_{1}$ is $s^{5}_{1}=5$. At $t(e_{3})=5$ the temporal
and resource constraints for $J^{5}_{1}$ are not satisfied ($b_{2}(e_{3})=1$).
The next event $e_{4}$ is a good insertion point for the task $J^{5}_{1}$,
since here the resource constraint and also the temporal constraints are met.
The task $J^{5}_{1}$ is finally scheduled at $s^{5}_{1}=t(e_{4})$. Following,
an insertion point is searched for the task $J^{5}_{2}$, which consumes both
the resources $1$ and $3$. The earliest starting time for $J^{5}_{2}$ is
$s^{5}_{2}=5$. The resources constraints are not satisfied in the events
$e_{3}$, $e_{4}$ and $e_{5}$. The event $e_{6}$ is the first feasible
insertion point for the task $J^{5}_{2}$, since at $t(e_{6})$ the precedence
and temporal constraints are met. Also, in $e_{6}$ both resources $1$ and $3$
are available ($b_{1}(e_{6})=0$ and $b_{3}(e_{6})=0$). The task $J^{5}_{2}$ is
finally scheduled at $s^{5}_{2}=t(e_{6})$, and the usages of resources $1$ and
$3$, respectively $b_{1}(e_{6})$ and $b_{3}(e_{6})$, are updated. Since a
feasible insertion point has been found for both $J^{5}_{1}$ and $J^{5}_{2}$,
the plan $\Pi_{5}$ is scheduled correctly and the schedule generated is
considered as feasible schedule.

Table VII shows the resulting Gantt diagram and the event list $\mathcal{EL}$
after the insertion of the plan $\Pi_{5}$.

$e$ | $t(e)$ | $\mathcal{S}(e)$ | $\mathcal{C}(e)$ | $b_{1}(e)$ | $b_{2}(e)$ | $b_{3}(e)$
---|---|---|---|---|---|---
$e1$ | $2$ | $\\{J^{1}_{1},J^{3}_{1},J^{4}_{1}\\}$ | $\emptyset$ | $1$ | $1$ | $1$
$e2$ | $4$ | $\\{J^{2}_{1}\\}$ | $\\{J^{4}_{1}\\}$ | $1$ | $1$ | $1$
$e3$ | $5$ | $\emptyset$ | $\\{J^{3}_{1}\\}$ | $1$ | $1$ | $0$
$e4$ | $6$ | $\\{J^{4}_{2},J^{2}_{2},\bm{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}J^{5}_{1}}}\\}$ | $\\{J^{2}_{1},J^{1}_{1}\\}$ | $1$ | $1$ | $1$
$e5$ | $7$ | $\\{J^{1}_{2}\\}$ | $\\{J^{4}_{2}\\}$ | $1$ | $1$ | $1$
$e6$ | $9$ | $\\{\bm{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}J^{5}_{2}}}\\}$ | $\\{J^{1}_{2},J^{2}_{2},\bm{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}J^{5}_{1}}}\\}$ | $1$ | $0$ | $1$
$e7$ | $10$ | $\emptyset$ | $\\{\bm{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}J^{5}_{2}}}\\}$ | $0$ | $0$ | $0$

TABLE VII: Insertion of the plan $\Pi_{5}$ into a feasible schedule.

##  VI Computational results

In this section we present the computational results for the proposed
heuristic. All the experiments were run on an entry-level machine (Intel
i5-4210U, 6GB RAM, Linux OS). The algorithms were entirely written in Java
(version $8$).

We run different experiments of our algorithm by using a benchmark that
depicts a realist scenario of a mission carried out by a Remote Piloted Air
Vehicle (RPAS), which set of plans, listed in Table VIII, has to be scheduled.
The validity of the mission is constrained between $0$ and $180$ seconds.
Therefore, the time window $[W_{s},W_{e}]$ is fixed to $[0,180]$.

$\Pi_{k}$ | $n_{k}$ | $\alpha_{k}$ | $\mathcal{R}^{k}$ | $[r^{k},d^{k}]$ | $p^{k}_{1}$ | $p^{k}_{2}$ | $p^{k}_{3}$ | $p^{k}_{4}$ | $\delta^{k}_{ij}$ | $\Pi_{k}\prec\Pi_{j}$ | $J^{k}_{i}\prec J^{k}_{j}$
---|---|---|---|---|---|---|---|---|---|---|---
$\Pi_{1}$ | $2$ | $3$ | $\\{1,2\\}$ | $[0,180]$ | $3$ | $3$ |  |  |  |  | $J^{1}_{1}\prec J^{1}_{2}$
$\Pi_{2}$ | $2$ | $3$ | $\\{3,4\\}$ | $[0,180]$ | $4$ | $4$ |  |  |  |  |
$\Pi_{3}$ | $1$ | $3$ | $\\{5\\}$ | $[0,180]$ | $3$ |  |  |  |  |  |
$\Pi_{4}$ | $1$ | $3$ | $\\{6\\}$ | $[0,180]$ | $3$ |  |  |  |  |  |
$\Pi_{5}$ | $1$ | $3$ | $\\{7\\}$ | $[0,180]$ | $1$ |  |  |  |  |  |
$\Pi_{6}$ | $1$ | $3$ | $\\{8\\}$ | $[0,180]$ | $1$ |  |  |  |  |  |
$\Pi_{7}$ | $4$ | $1$ | $\\{5,9,10,11\\}$ | $[80,160]$ | $20$ | $20$ | $20$ | $20$ |  |  | $J^{7}_{3}\prec J^{7}_{4}$
$\Pi_{8}$ | $4$ | $1$ | $\\{5,9,10,11\\}$ | $[40,120]$ | $20$ | $20$ | $20$ | $20$ |  |  | $J^{8}_{3}\prec J^{8}_{4}$
$\Pi_{9}$ | $4$ | $1$ | $\\{5,9,10,11\\}$ | $[40,120]$ | $20$ | $20$ | $20$ | $20$ |  |  | $J^{9}_{3}\prec J^{9}_{4}$
$\Pi_{10}$ | $3$ | $5$ | $\\{1,2,10\\}$ | $[50,80]$ | $5$ | $5$ | $5$ |  |  |  | $J^{10}_{1}\prec J^{10}_{2}$
$\Pi_{11}$ | $4$ | $5$ | $\\{5,9,10,11\\}$ | $[80,120]$ | $20$ | $20$ | $20$ | $20$ |  | $\Pi_{10}\prec\Pi_{11}$ | $J^{11}_{3}\prec J^{11}_{4}$
$\Pi_{12}$ | $4$ | $1$ | $\\{5,9,10,11\\}$ | $[0,80]$ | $20$ | $20$ | $20$ | $20$ |  |  | $J^{12}_{3}\prec J^{12}_{4}$
$\Pi_{13}$ | $3$ | $5$ | $\\{1,2,10\\}$ | $[0,40]$ | $5$ | $5$ | $5$ |  |  |  | $J^{13}_{1}\prec J^{13}_{2}$
$\Pi_{14}$ | $4$ | $5$ | $\\{5,9,10,11\\}$ | $[40,80]$ | $20$ | $20$ | $20$ | $20$ |  | $\Pi_{13}\prec\Pi_{14}$ | $J^{14}_{3}\prec J^{14}_{4}$
$\Pi_{15}$ | $3$ | $6$ | $\\{1,2,10\\}$ | $[0,20]$ | $5$ | $5$ | $5$ |  |  |  | $J^{15}_{1}\prec J^{15}_{2}$
$\Pi_{16}$ | $4$ | $6$ | $\\{5,9,10,11\\}$ | $[20,80]$ | $20$ | $20$ | $20$ | $20$ |  | $\Pi_{15}\prec\Pi_{16}$ | $J^{16}_{3}\prec J^{16}_{4}$
$\Pi_{17}$ | $2$ | $8$ | $\\{3,4\\}$ | $[60,120]$ | $2$ | $2$ |  |  |  |  | $J^{17}_{1}\prec J^{17}_{2}$
$\Pi_{18}$ | $2$ | $8$ | $\\{3,4\\}$ | $[60,120]$ | $2$ | $2$ |  |  |  |  | $J^{18}_{1}\prec J^{18}_{2}$
$\Pi_{19}$ | $2$ | $8$ | $\\{3,4\\}$ | $[60,120]$ | $2$ | $2$ |  |  |  |  | $J^{19}_{1}\prec J^{19}_{2}$
$\Pi_{20}$ | $3$ | $6$ | $\\{1,2,10\\}$ | $[0,20]$ | $5$ | $5$ | $5$ |  |  |  | $J^{20}_{1}\prec J^{20}_{2}$
$\Pi_{21}$ | $4$ | $6$ | $\\{6,9,10,11\\}$ | $[20,60]$ | $20$ | $20$ | $20$ | $20$ |  | $\Pi_{20}\prec\Pi_{21}$ | $J^{21}_{3}\prec J^{21}_{4}$
$\Pi_{22}$ | $2$ | $6$ | $\\{14,10\\}$ | $[30,70]$ | $2$ | $2$ |  |  |  |  |
$\Pi_{23}$ | $4$ | $1$ | $\\{6,9,10,11\\}$ | $[40,90]$ | $20$ | $20$ | $20$ | $20$ |  |  | $J^{23}_{3}\prec J^{23}_{4}$
$\Pi_{24}$ | $4$ | $1$ | $\\{6,9,10,11\\}$ | $[80,150]$ | $20$ | $20$ | $20$ | $20$ |  |  | $J^{24}_{3}\prec J^{24}_{4}$
$\Pi_{25}$ | $4$ | $1$ | $\\{6,9,10,11\\}$ | $[80,130]$ | $20$ | $20$ | $20$ | $20$ |  |  | $J^{25}_{3}\prec J^{25}_{4}$
$\Pi_{26}$ | $4$ | $1$ | $\\{6,9,10,11\\}$ | $[130,160]$ | $20$ | $20$ | $20$ | $20$ |  |  | $J^{26}_{3}\prec J^{26}_{4}$
$\Pi_{27}$ | $2$ | $4$ | $\\{14,10\\}$ | $[0,180]$ | $2$ | $2$ |  |  |  |  |
$\Pi_{28}$ | $3$ | $6$ | $\\{1,2,10\\}$ | $[80,120]$ | $5$ | $5$ | $5$ |  |  |  | $J^{28}_{1}\prec J^{28}_{2}$
$\Pi_{29}$ | $2$ | $6$ | $\\{3,4\\}$ | $[120,140]$ | $2$ | $2$ |  |  |  | $\Pi_{28}\prec\Pi_{29}$ | $J^{29}_{1}\prec J^{29}_{2}$
$\Pi_{30}$ | $2$ | $6$ | $\\{14,10\\}$ | $[120,140]$ | $2$ | $2$ |  |  |  |  |
$\Pi_{31}$ | $4$ | $1$ | $\\{6,9,10,11\\}$ | $[150,190]$ | $20$ | $20$ | $20$ | $20$ |  |  | $J^{31}_{3}\prec J^{31}_{4}$
$\Pi_{32}$ | $2$ | $4$ | $\\{3,4\\}$ | $[120,140]$ | $2$ | $2$ |  |  |  |  | $J^{32}_{1}\prec J^{32}_{2}$
TABLE VIII: The benchmark used for evaluating the performance of the proposed
method.

We first evaluated the proposed heuristic on the benchmark listed in Table
VIII. Then, we evaluated the performance of the proposed heuristic on
different benchmarks obtained by modifying the set of plans listed in Table
VIII. These modified benchmarks are opportunely set up in such a way that the
constraints are more or less relaxed. Thus, we studied eight different
scenarios, which results are listed in Table IX. Following are listed the
differences between each scenario:

  * •

Scenario 1: set of plans listed in Table VIII;

  * •

Scenario 2: in this scenario all the plans have the same temporal window
$[r^{k},d^{k}]$ fixed to $[0,180]$, and the plans are all tied by precedence
relations, so that $\forall i,j,j>i,\Pi_{i}\prec\Pi_{j}$;

  * •

Scenario 3: in this scenario we modified the release time of each plan in such
way to have the maximum number of events;

  * •

Scenario 4: in this scenario we duplicated all the plans with priority $6$ and
$8$;

  * •

Scenario 5: in this scenario we duplicated all the plans with priority $1$ and
$3$;

  * •

Scenario 6: in this scenario we used the same benchmark as the scenario 1, but
we used a time window $[W_{s},W_{e}]$ fixed to $[0,90]$;

  * •

Scenario 7: in this scenario we used the same benchmark as the scenario 1, but
we used a time window $[W_{s},W_{e}]$ fixed to $[0,270]$;

  * •

Scenario 8: in this scenario we used the same benchmark as the scenario 1, but
each plan has a duplicate.

Table IX presents the execution times for each scenario. Each execution time
is calculated as the mean of the execution times of ten runs of the algorithm
on the same benchmark.

| $K=|\mathcal{P}|$ | $Kn_{k}$ | $|\mathcal{P}_{s}|$ | $|\mathcal{P}_{s}|n_{k}$ | Time (in ms)
---|---|---|---|---|---
Scenario 1 | $32$ | $91$ | $24$ | $56$ | $\sim 183$
Scenario 2 | $32$ | $91$ | $24$ | $67$ | $\sim 183$
Scenario 3 | $32$ | $91$ | $24$ | $64$ | $\sim 219$
Scenario 4 | $42$ | $118$ | $30$ | $68$ | $\sim 316$
Scenario 5 | $47$ | $135$ | $29$ | $64$ | $\sim 345$
Scenario 6 | $32$ | $91$ | $16$ | $35$ | $\sim 197$
Scenario 7 | $32$ | $91$ | $24$ | $60$ | $\sim 228$
Scenario 8 | $64$ | $182$ | $37$ | $81$ | $\sim 538$
TABLE IX: Execution times of the eight scenarios.

The obtained computational results of the algorithm gave us a first proof of
concept concerning the complexity of the scheduling problem we address.
Moreover, the results are yet satisfactory in the context of scheduling plans
for RPAS. As the problem of scheduling plans of tasks is difficult due to its
tight constraints, we conclude that the quality of the schedules provided by
the proposed heuristic is good with respect to the complexity of the evaluated
benchmarks.

##  VII Future works

###  VII-A Variable resource availability

The proposed heuristic considers only resources with a fixed availability of
$B_{\rho}=1,~{}\forall\rho\in\mathcal{R}$. A generalization of the algorithm
could take into account resources with variable availability values, so that
one resource could be used by different tasks at the same time. Augmenting the
resource availability could also lead to better schedules in terms of number
of plans scheduled into a fixed time window, as showed in Example 4.

######  Example 4.

Let $\mathcal{P}=\\{\Pi_{1},\Pi_{2}\\}$ be a set of two plans $\Pi_{1}$ and
$\Pi_{2}$ which have each one task, respectively $J^{1}_{1}$ ($r^{1}_{1}=1$,
$d^{1}_{1}=6$, $p^{1}_{1}=3$) and $J^{2}_{1}$ ($r^{2}_{1}=4$, $d^{2}_{1}=10$,
$p^{2}_{1}=4$). In Figure 6 are showed two possible schedules for the task
$J^{2}_{1}$. If the resource $1$ has a maximum availability $B_{1}=1$ (Figure
6(a)), the earliest starting time for the task $J^{2}_{1}$ would be $6$,
because otherwise the usage of resource would exceed its availability.
Instead, if the availability of the resource is $2$ (Figure 6(b)), the
earliest starting time would be set to $4$ (that is, the release time of the
task), and so the use of the resource is maximized. Also, in the schedule
showed in Figure 6(b) the time interval $[5,8]$ can be employed for scheduling
other tasks, whereas this is not possible in the schedule in Figure 6(a).

(a)

(b)

Figure 6: Scheduling of task $J^{2}_{1}$, which has a release time of $4$,
into a resource with availability $B_{1}=1$ (6(a)) and a resource with
availability $B_{1}=2$ (6(b)).

###  VII-B $p^{k}_{i}$ as function of time

The value of the processing time $p^{k}_{i}$ for a task $J^{k}_{i}$ could be
modeled as a function of time $p^{k}_{i}(t)$ in such a way that the processing
time of a task $J^{k}_{i}$ can vary according to the time instant in which it
is scheduled. To motivate this extension, we present in Example 5 a case study
of a RPAS that has to accomplish some in-flight operation.

######  Example 5.

Let us consider a RPAS that has to accomplish a mission where it has to follow
a straight trajectory and collect data from an object $R$ located in the
terrain during a fixed time range, as depicted in Figure 7. During the the
time range in which the RPAS is within the object’s range it has to send
information to the object $R$ in the terrain. The operation of sending
information could require more time when the RPAS is far from the object, but
less time when it is near the object. Thus, the processing time function
related to the operation of sending information could be modeled as an inverse
Gaussian function, as showed in Figure 8, where $d_{max}$ and $d_{min}$ are
respectively the maximum and the minimum distance between the RPAS and the
object $R$.

Figure 7: An example of RPAS that has to communicate informations to an object
$R$. The processing time of the tasks communicating with $R$ could vary
according to the distance between the object $R$ and the RPAS with respect to
the time instant $t$. Figure 8: An inverse Gaussian used to model the
processing time $p(t)$ of the the operation of sending information to a fixed
object for the RPAS in Figure 7.

###  VII-C Alternative schedules

The proposed heuristic works in an incremental fashion, adding plans in order
to a working schedule $S_{w}$ and keeping a set $\mathcal{P}_{s}$ of
successfully scheduled plans, as well as a set $\mathcal{P}_{f}$ of
unscheduled plans. The incremental process of construction of a feasible
schedule can be represented as an directed acyclic graph, as shown in the
example graph in Figure 9. According to this representation, each vertex
represents a feasible schedule, while a directed arc $(i,j)$, which has label
$\Pi_{k}$, represents the insertion of the plan $\Pi_{k}$ into the schedule
$S_{i}$, that leads to a new feasible schedule $S_{j}$.

Figure 9: The graph representation of a feasible schedule with four plans (in
blue), and two possible alternative schedule (yellow and green).

The incremental manner of constructing the schedules has the advantage of
being able to return a feasible schedule at each iteration of the algorithm.

Since the proposed method builds only a graph with no branches (no alternative
schedule paths), a possible extension could consider different metrics to
build alternative paths in the graph of solutions. For example, as the
proposed heuristic returns a set $\mathcal{P}_{f}$ of plans unscheduled due to
constraints violations, one possible extension could increase the priority
values of the unscheduled plans in $\mathcal{P}_{f}$ while lowering those of a
subset of feasible plans in $\mathcal{P}_{s}$. In this manner, alternative
paths in the solution graph could be found. Also, these alternative paths
could maximize further the objective function, thus allowing the heuristic
method to escape from the local optima.

##  VIII Conclusions

This article presented a heuristic algorithm for the problem of scheduling
plans of tasks. The algorithm may be employed in realistic scenarios where the
classical scheduling technique can not be used due to the considered
constraints.

## References

  * [1] M. L. Pinedo, Scheduling.  Springer US, 2012.  DOI: 10.1007/978-1-4614-2361-4.
  * [2] R. Klein, Scheduling of Resource-Constrained Projects, vol. 10 of Operations Research/Computer Science Interfaces Series.  Boston, MA: Springer US, 2000.  DOI: 10.1007/978-1-4615-4629-0.
  * [3] L. Grivault, A. E. Fallah-Seghrouchni, and R. Girard-Claudon, “Agent-Based Architecture for Multi-sensors System Deployed on Airborne Platform,” pp. 86–89, IEEE, Sept. 2016.
  * [4] S. Kemkemian and M. Nouvel-Fiani, “Toward common radar & EW multifunction active arrays,” pp. 777–784, IEEE, Oct. 2010.
  * [5] S. Imai, E. Blasch, A. Galli, W. Zhu, F. Lee, and C. A. Varela, “Airplane flight safety using error-tolerant data stream processing,” IEEE Aerospace and Electronic Systems Magazine, vol. 32, pp. 4–17, Apr. 2017.
  * [6] C. Schwindt and J. Zimmermann, eds., Handbook on Project Management and Scheduling Vol.1.  Cham: Springer International Publishing, 2015.  DOI: 10.1007/978-3-319-05443-8.
  * [7] T. H. Cormen, C. Stein, R. L. Rivest, and C. E. Leiserson, Introduction to Algorithms.  McGraw-Hill Higher Education, 2nd ed., 2001.
  * [8] A. B. Kahn, “Topological sorting of large networks,” Communications of the ACM, vol. 5, pp. 558–562, Nov. 1962.
  * [9] R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. R. Kan, “Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey,” Annals of Discrete Mathematics, vol. 5, pp. 287–326, Jan. 1979\.
  * [10] P. Brucker, A. Drexl, R. Möhring, K. Neumann, and E. Pesch, “Resource-constrained project scheduling: Notation, classification, models, and methods,” European Journal of Operational Research, vol. 112, pp. 3–41, Jan. 1999.
  * [11] C. Artigues, S. Demassey, and E. Neron, Resource-Constrained Project Scheduling: Models, Algorithms, Extensions and Applications.  ISTE, 2007.
  * [12] T. Peters, “Timsort.” http://bugs.python.org/file4451/timsort.txt, 2002\.