Jérôme Fortin
email: fortin@irit.fr

Didier Dubois
email: dubois@irit.fr

Solving Fuzzy PERT Using Gradual Real Numbers

Keywords: Fuzzy PERT, Gradual Numbers, Floats

, that represents soft boundaries of a fuzzy interval. We show that algorithms in the interval-valued case can be adapted to fuzzy intervals considering them as crisp intervals of gradual numbers.

Introduction

Temporal Constraint Networks (TCN) represent relations between dates of events and also allow to express constraints on the possible durations of activities from intervals of values. TCN have been extended to take into account uncertainty of durations of some tasks in realistic applications by making a distinction between so-called contingent constraints and controllable ones [START_REF] Morris | Dynamic control of plans with temporal uncertainty[END_REF]. The resulting network becomes a decision-making problem under uncertainty. This paper reconsiders the most basic scheduling problem, that of minimizing the makespan of a partially ordered set of activities, in the context of incomplete knowledge. When the durations of tasks of a project scheduling problem are ill-known and modeled by intervals, the problem can be viewed as a special kind of TCN where all tasks are modeled by contingent constraints, and controllable constraints only describe precedence between tasks. Of course, the resulting network is always controllable if the graph of precedence constraints is acyclic. This paper answers the question of optimizing the total duration of such a network when constraints are set by fuzzy intervals.

One goal of project scheduling problem is to compute earliest starting dates, latest starting dates and floats of the different tasks, and to identify critical tasks. When tasks durations are precisely known, this problem is solved by the PERT/CPM Algorithm (Critical Path Method). When task durations are ill-known and lie in an interval, this problem is much more difficult. In recent paper [START_REF] Fortin | Interval analysis in scheduling[END_REF], we give polynomial algorithms to compute upper bound of floats in the interval-valued model. Here we prove that those algorithms can be adapted the fuzzy-valued problem. For this purpose, we will recall and use a recent notion introduced in fuzzy set theory, called gradual numbers [START_REF] Fortin | Gradual numbers and their application to fuzzy interval analysis[END_REF]. This notion makes it possible to define and use gradual bounds of fuzzy intervals and then apply already known interval analysis ideas to the fuzzy counterpart of interval problems.

The paper is organized as follows; Section 2 gives the background needed to construct our new algorithms: Subsection 2.1 recalls the basic PERT/CPM problem of project scheduling. Subsection 2.2 re-states the recent results of [START_REF] Fortin | Interval analysis in scheduling[END_REF] to solve the PERT/CPM problem when tasks are modeled by intervals. Then Subsection 2.3 gives general definition and intuitions of so-called gradual numbers. A subproblem is addressed in Section 3, that is the computation of earliest starting dates, latest starting dates and floats when durations of tasks are modeled by gradual numbers. And finally Section 4 gives algorithms to compute degrees of necessary criticality in polynomial time, and the least upper bound (LUB) of floats for each possibility degree λ ¢¡ 0£ 1¤ .

Preliminaries

Classical PERT Model

An activity network is classically defined as a set of activities (or tasks) with given duration times, related to each other by means of precedence constraints. When there are no resource constraints, it can be represented by a directed, connected and acyclic graph. Of major concern, is to minimize the ending time of the last task, also called the makespan of the network. For each task, three quantities have practical importance for the management of the activity network: The earliest starting time est i j of an activity ¡ i£ j¥ is the date before which the activity cannot be started without violation of a precedence constraint.

The latest starting time lst i j of an activity ¡ i£ j¥ is the date after which the activity cannot be started without delaying the end of the project. The float f i j of an activity ¡ i£ j¥ is the difference between the latest starting time lst i j and the earliest starting time est i j . An activity is critical if and only if its float is equal to zero. Under the assumption of minimal makespan, critical tasks must be started and completed at prescribed time-points.

A directed, connected and acyclic graph G ¦ ¨ § V£ A © , represents an activity net- work. We use the activity-on-arc convention. V is the set of nodes (events), V ¦ n, and A is the set of arcs (activities), A ¦ m. The set V ¦ 1£ 2£ £ n is labeled in such a way that i § j for each activity ¡ i£ j¥ A. Activity durations d i j (weights of the arcs) ¡ i£ j¥ A are well known. See Figure 1 for a simple example of project scheduling problem. Task durations are the values given on the arc of the graph. Two nodes 1 and n are distin- guished as the initial and final node, respectively. We also need some additional notations to speak about predecessor or successor of a task or a node, and subgraphs of G: Succ ¡ i¥ (resp. Pred ¡ i¥ ) refers to the set of nodes that immediately follow (resp.

precede) node i V .

SUCC ¡ i£ j¥ (resp. PRED ¡ i£ j¥ ) denotes the set of all arcs that come after (resp. before) ¡ i£ j¥ A, and SUCC ¡ j¥ (resp. PRED ¡ j¥ ) stands for the set of all nodes that come after (resp. before) j V .

G ¡ i£ j¥ is the subgraph of G composed of nodes succeeding i and preceding j. G ¡ d i j ¦ d¥ is the graph where duration of task ¡ i£ j¥ is replaced by d.

With these notations, we can give precise formulas defining earliest starting dates, latest starting dates and floats of tasks and events: The earliest starting date of an event k is the longest path from the beginning of the project, represented by node 1, and node k. We arbitrary fix the starting time of project to est 1 ¦ 0. Of course the earliest starting date of a task ¡ k£ l¥ is equal to the earliest starting date of event k. The following recursive formula give the key to compute earliest starting dates of events and tasks.

est k ¦ ¡ 0 if k ¦ 1 max j¢ Pred £ k¤ ¡ est j ¥ d jk ¥ otherwise est kl ¦ est k
The earliest ending time for the project is the earliest starting time of the last event n. In order to ensure a minimal duration of the project, the latest starting date of event n is equal to its earliest starting date (lst n ¦ est n ). The latest starting date of a task ¡ k£ l¥ is the time after which we can not start its execution without delaying the end of the project, so it is in fact the difference between the earliest ending date of the project and the longest path from node n and node l minus the duration of the task ¡ k£ l¥ . We can now define the latest starting date of events and tasks by the following formulas:

lst k ¦ ¡ est n if k ¦ n min l ¢ Succk ¡ lst l ¦ d kl ¥ otherwise lst kl ¦ lst l ¦ d kl
The float of a task ¡ k£ l¥ which represents the length of the time window for the beginning of the execution of the task is the difference between the latest starting date and the earliest starting date:

f kl ¦ lst kl ¦ est kl
The well known PERT/CPM algorithm computes the earliest starting dates, latest starting dates and float in linear time complexity (O ¡ m ¥ n¥ ). It executes a forward recur- sion from node 1 to node n to give the longest path from node 1 to each node of the graph. Then it runs a backward recursion to compute latest starting dates and so the floats.

The PERT algorithm give the following earliest starting dates, latest starting dates and floats of project of Figure 1:

est 12 ¦ 0, est 23 ¦ 2, est 13 ¦ 0, lst 12 ¦ 0, lst 23 ¦ 2, lst 13 ¦ 1, f 12 ¦ 0, f 23 ¦ 0, f 13 ¦ 1.

Interval-Valued PERT Model

In this section we recall recent results published in the CP2005 conference proceedings [START_REF] Fortin | Interval analysis in scheduling[END_REF]. Suppose the durations d i j of tasks ¡ i£ j¥ of the precedent model are not precisely known, but are known to lie in an interval range D i j ¦ ¨ § d© i j £ d i j ¤ . It means that the real exact duration of the task will be in D i j , but it can neither be known nor chosen in this interval. This problem was first formulated by Buckley [START_REF] Buckley | Fuzzy PERT[END_REF], and was completely solved very recently in [START_REF] Fortin | Interval analysis in scheduling[END_REF].

An instantiation of all task durations of the network is called a configuration, and a instantiation of all task durations for which task duration is set to the minimal value d© i j or maximal value d i j is called a extreme configuration. We note the set of possible configurations: ¦ ¢¡ £ i£ j¤ ¢ A D i j .

In this formulation, a task ¡ i£ j¥ can be possibly critical, if there exists a configuration for which ¡ i£ j¥ is critical in the usual sense. A task is not possibly critical if there exists no configuration for which ¡ i£ j¥ is critical in the usual sense. A task is necessarily critical if it is critical for each configuration. And a task is not necessarily critical is there exists at least one configuration for which the task is not critical in the usual sense. Finding possible and necessarily critical tasks is very important for a project manager. Other useful pieces of information are the possible earliest starting dates, possible latest starting date and possible floats, which become intervals:

EST kl ¦ § est © kl £ est kl ¤ ¦ est kl ¡ Ω¥ Ω LST kl ¦ § lst © kl £ lst kl ¤ ¦ lst kl ¡ Ω¥ Ω F kl ¦ § f © kl £ f kl ¤ ¦ f kl ¡ Ω¥ Ω
where est kl ¡ Ω¥ (resp. lst kl ¡ Ω¥ and f kl ¡ Ω¥ ) represents the earliest starting date of ¡ k£ l¥ (resp. latest starting date and float) in configuration Ω.

Asserting Necessarily Criticality

Asserting if a task is possibly critical is an NP-Hard problem [START_REF] Chanas | On the hardness of evaluating criticality of activities in planar network with duration intervals[END_REF], while asserting is a task is necessarily critical is polynomially solvable [START_REF] Fortin | Interval analysis in scheduling[END_REF]. As in the classical problem, criticality and floats are obviously connected:

Proposition 1 An activity ¡ k£ l¥ A is possibly (resp. necessarily) critical in G if and

only if f © kl ¦ 0 (resp. f kl ¦ 0).
In this paper we focus on asserting the necessarily criticality of a task, and on computing the upper bound of the float, when durations are modeled by fuzzy interval. The same approach can be applied for computing latest starting dates in polynomial time, or for asserting the possible criticality of a task and computing the lower bound of the float, but it can only be done with exponential time complexity. Because of the lack of space in conference proceedings, we choose to deal with necessarily criticality and upper bound of the float. A first algorithm that asserts the necessarily criticality of a task ¡ k£ l¥ in the interval case when predecessors of ¡ k£ l¥ are precisely known is based on the following propositions [START_REF] Fortin | Interval analysis in scheduling[END_REF]:

Proposition 2 An activity ¡ k£ l¥ A is necessarily critical in G if
¡ k£ l¥ is necessarily critical in G ¦ ¨ § ¡ k£ l¥ is necessarily critical in G ¡ d i j ¦ d © i j ¥ . If ¡ k£ l¥ is not critical in G ¡ 1£ i¥ , then: ¡ k£ l¥ is necessarily critical in G ¦ ¨ § ¡ k£ l¥ is necessarily critical in G ¡ d i j ¦ d i j ¥ .
Proposition 2 and 3 lead to an algorithm for asserting the necessary criticality of a given activity ¡ k£ l¥ in a network in which all activities that precede ¡ k£ l¥ have precise durations. The algorithm recursively assigns an exact duration to tasks succeeding ¡ k£ l¥ without changing the necessarily criticality of ¡ k£ l¥ .

The algorithm works as follows: At the initialization, we set all durations of tasks not succeeding ¡ k£ l¥ to their upper bound, and duration of ¡ k£ l¥ to its lower bound (according to Proposition 2). Then at the first iteration of the algorithm, we only consider the subnetwork G ¡ 1£ l¥ . In this network, all tasks durations are precisely fixed, so a classical PERT/CPM run decides the necessary criticality of ¡ k£ l¥ in G ¡ 1£ l¥ . Now, according to Proposition 2 we can set to a precise duration tasks immediately succeeding node l:

if ¡ k£ l¥ is necessary critical in G ¡ 1£ l¥ , duration of tasks ¡ l £ m¥ (m Succ ¡ l¥ ) are set
to their minimal duration, otherwise, they are set to their maximal duration. Then the second iteration considers the sub-network G ¡ 1£ l ¥ 1¥ . At this step all tasks durations are precisely set in this sub-network, we can check the criticality of ¡ k£ l¥ with the standard PERT/CPM algorithm, and so on. After the last iteration, all tasks durations are precisely instantiated and ¡ k£ l¥ is critical in this instantiation, if and only if task ¡ k£ l¥ is necessary critical in the original network G ¡ 1£ n¥ (where duration of tasks not preceding ¡ k£ l¥ are intervals).

The next proposition will lead to a polynomial algorithm which asserts the necessary criticality of a task ¡ k£ l¥ in the general case: Proposition 4 Let ¡ k£ l¥ A be a distinguished activity, and ¡ i£ j¥ be an activity such that ¡ i£ j¥ PRED ¡ k£ l¥ . If ¡ k£ l¥ is necessarily critical in G ¡ j£ n¥ , then:

¡ k£ l¥ is necessarily critical in G ¦ ¨ § ¡ k£ l¥ is necessarily critical in G ¡ d i j ¦ d © i j ¥ If ¡ k£ l¥ is not necessarily critical in G ¡ j £ n¥ , then: ¡ k£ l¥ is necessarily critical in G ¦ ¨ § ¡ k£ l¥ is necessarily critical in G ¡ d i j ¦ d i j ¥
With the help of the previous algorithm, Proposition 4 leads to an algorithm which recursively assigns an exact duration to tasks preceding ¡ k£ l¥ without changing the nec- essarily criticality of ¡ k£ l¥ . At the first iteration, we consider the sub-network G ¡ k£ n¥ . In this network all tasks preceding ¡ k£ l¥ have precise durations (because there is no task preceding ¡ k£ l¥ ). So we can invoke the previous algorithm to know if ¡ k£ l¥ is necessary critical in G ¡ k£ n¥ . Now, with the help of Proposition 4, we can precisely set the dura- tion of tasks just preceding node k. At the second iteration, we consider the sub-network G ¡ k ¦ 1£ n¥ , where all tasks preceding ¡ k£ l¥ are now precisely fixed, so we can call the previous algorithm (with original interval durations for tasks succeeding ¡ k£ l¥ ), and so on. At the end of this Algorithm, all durations of tasks preceding ¡ k£ l¥ are precisely set, and ¡ k£ l¥ is necessary critical in the original network if and only if it is necessary critical in the instantiated network. So finally, putting together Proposition 3 and 4 we can assert if a task ¡ k£ l¥ is necessarily critical in O ¡ mn¥ time complexity.

The two previous algorithms used conjointly instantiate all task duration in a network without changing the necessary criticality of a given task ¡ k£ l¥ . That means that ¡ k£ l¥ is necessarily critical if and only if its float is null in the so-built configuration. If ¡ k£ l¥ is necessary critical the LUB of the float have been computed and is f kl ¦ 0. But, if this float is not null in the constructed configuration, then the computed value of the float is not the correct LUB of float of ¡ k£ l¥ . We call this computed value the potential float of ¡ k£ l¥ .

Computing Least Upper Bound of Floats

The key idea to compute the least upper bound (LUB) on float f kl of activity ¡ k£ l¥ in G, is to increase the minimal duration d © kl until ¡ k£ l¥ becomes necessarily critical. Then it is proved that the LUB of float is equal to the overall increment of d © kl [START_REF] Fortin | Interval analysis in scheduling[END_REF]:

Proposition 5 Let f kl be the minimal nonnegative real number such that ¡ k£ l¥ is neces-

sarily critical in G ¡ d kl ¦ d © kl ¥ f kl ¥ . Then f kl ¦ f kl .
Let us explain how to find this increment. One can note that if a task ¡ k£ l¥ is necessarily critical in G, then there exists a path p from node 1 to node k such that for every node j p, ¡ k£ l¥ is necessarily critical in G ¡ j £ n¥ [START_REF] Fortin | Interval analysis in scheduling[END_REF]. So the minimal increment that can make ¡ k£ l¥ necessarily critical is given by next lemma:

Lemma 1 Let ∆ ¦ min j f kl ¡ j £ n¥ f kl ¡ j £ n¥ ¡ ¦ 0 where f kl ¡ j £ n¥ is the potential float of task ¡ k£ l¥ in G ¡ j £ n¥ , j PRED ¡ k¥ (i.e. f
kl ¡ j £ n¥ is the float in the configuration induced by the algorithm which asserts if ¡ k£ l¥ is necessary critical).

Then for all ε § ∆, activity ¡ k£ l¥ is not necessarily critical in G ¡ j £ n¥ , j PRED ¡ k¥ , with duration d kl ¦ d © kl ¥ ε (the configuration constructed for asserting the necessary criticality is the same). Moreover there exists j PRED ¡ k¥ such that ¡ k£ l¥ becomes necessarily critical in G ¡ j £ n¥ with duration d kl ¦ d© kl ¥ ∆ (the configuration constructed for asserting the necessary criticality is not the same).

The algorithm which computes the LUB of floats works as follow: For each node i preceding ¡ k£ l¥ it computes the potential float of ¡ k£ l¥ in G ¡ i£ n¥ with the algorithm which assert the necessary criticality of ¡ k£ l¥ . If the potential float of ¡ k£ l¥ in G ¡ 1£ n¥ is not 0, then the minimal potential float computed is added to the minimal duration d © kl of ¡ k£ l¥ , and the algorithm is run again from the beginning until ¡ k£ l¥ becomes necessary critical in G. The total added value to the minimal duration d © kl so far is then the LUB of the floats of ¡ k£ l¥ .

We are going to see that those algorithms can be easily adapted to the fuzzy-valued version of this problem, using the new notion of gradual numbers, thus providing in polynomial time the degree of necessarily criticality of a task.

Gradual Numbers

To solve the fuzzy interval valued model PERT, we will use in this paper the recent notion of gradual numbers [START_REF] Fortin | Gradual numbers and their application to fuzzy interval analysis[END_REF].

What is often called a fuzzy number [START_REF] Zadeh | Fuzzy sets[END_REF][START_REF] Dubois | Fuzzy interval analysis[END_REF] is the extension of an interval, not a real number. Hence, fuzzy interval is a better name for a fuzzy set of reals whose cuts are intervals. In a fuzzy interval, it is the interval that models incomplete knowledge (we know that some parameter lies between two bounds), not the fuzziness per se. Intervals model uncertainty in a Boolean way: a value in the interval is possible; a value outside is impossible. What fuzziness brings is to make the boundaries of the interval softer, thus making uncertainty gradual.

In order to model the essence of graduality without uncertainty, gradual numbers are defined as follow: Definition 1 (Gradual real number [START_REF] Fortin | Gradual numbers and their application to fuzzy interval analysis[END_REF]) A gradual real number (or gradual number for short) r is defined by an assignment function A r from ¡ 0£ 1¤ (the unit interval minus 0) to the reals. We note the set of all gradual real numbers.

A gradual number is a number parametrized by a value α which range in ¡ 0£ 1¤ . Intu- itively, an element α ¡ 0£ 1¤ is the degree of plausibility of a scenario, and A r ¡ α¥ is the value of some parameter in this scenario. Using the notion of gradual number, we can describe a fuzzy interval M by an ordered pair of specific gradual numbers ¡ m© £ m ¥ . m© is called the gradual lower bound of M and m the gradual upper bound. To ensure the well known shape of a fuzzy interval, several properties of m© and m must hold: the domains of A m¡ and A m¢ must be ¡ 0£ 1¤

A m¡ need to be increasing A m¢ need to be decreasing m© and m must be well ordered (A m¡ ¤£ A m¢ ). Such a pair of gradual numbers intuitively describe a fuzzy interval with membership function:

µ M ¡ x¥ ¦ ¥ ¦ ¦ § ¦ ¦ ¨sup λ A m¡ ¡ λ¥ £ x if x A m¡ ¡ ¡ 0£ 1¤ ¥ 1 if A m¡ ¡ 1¥ £ x £ A m¢ ¡ 1¥ sup λ A m¢ ¡ λ¥ © x if x A m¢ ¡ ¡ 0£ 1¤ ¥ 0 otherwise
An upper semi continuous membership function µ M ¡ ¥ , can be described by the pair of gradual reals ¡ m© £ m ¥ defined by

A m¡ : ¡ 0£ 1¤ ¦ λ ¦ A m¡ ¡ λ¥ ¦ in f x µ M ¡ x¥ © λ A m¢ : ¡ 0£ 1¤ ¦ λ ¦ A m¢ ¡ λ¥ ¦ sup x µ M ¡ x¥ © λ
To know more about general framework of gradual numbers, reader should refer to the following papers: [START_REF] Fortin | Gradual numbers and their application to fuzzy interval analysis[END_REF][START_REF] Dubois | A generalized vertex method for computing with fuzzy intervals[END_REF][START_REF] Dubois | Fuzzy elements in a fuzzy set[END_REF]. The sum of gradual numbers r and s is simply defined by summing their assignment

functions. It is r ¥ s such that α ¡ 0£ 1¤ , A r s ¡ α¥ ¦ A r ¡ α¥ ¥ A s ¡ α¥ . Most algebraic
properties of real numbers are preserved for gradual real numbers, contrary to the case of fuzzy intervals. For example, the set of the gradual real numbers with the addition operation forms a commutative group with identity 0 (A

0 ¡ λ¥ ¦ 0£ λ ¡ 0£ 1¤ ). Indeed
the gradual real number r has an inverse ¦ r under the addition: A © r ¡ α¥ ¦ ¦ A r ¡ α¥ , and r ¥ ¡ ¦ r¥ ¦ 0. Classical arithmetic operations are defined intuitively: If r and s are two gradual numbers,

addition: A r s ¡ α¥ ¦ A r ¡ α¥ ¥ A s ¡ α¥ . subtraction: A r © s ¡ α¥ ¦ A r ¡ α¥ ¦ A s ¡ α¥ . multiplication: A r s ¡ α¥ ¦ A r ¡ α¥ ¡ A s ¡ α¥ . division: A r s ¡ α¥ ¦ A r £ α¤ A s £ α¤ , if λ ¡ 0£ 1¤ , A s ¡ α¥ ¡ ¦ 0. maximum: max ¡ A r £ A s ¥ ¡ α¥ ¦ max ¡ A r ¡ α¥ £ A s ¡ α¥ ¥ . minimum: min ¡ A r £ A s ¥ ¡ α¥ ¦ min ¡ A r ¡ α¥ £ A s ¡ α¥ ¥ .
Note that contrary to real numbers, the maximum operation on gradual numbers is not selective: max ¡ A r £ A s ¥ ¡ ¦ A r or A s. There are sub-ranges of ¡ 0£ 1¤ where max ¡ A r £ A s ¥ ¦

A r and it is A s in the complementary range. If A r and A s are linear, these ranges are of the form ¡ 0£ θ¤ and § θ£ 1¤ for a threshold θ.

The Gradual-Valued Project Scheduling Problem

As in the previous section, an activity network is represented by a directed, connected and acyclic graph G ¦ ¨ § V£ A © . But now, activity durations di j ( ¡ i£ j¥ A) are defined by gradual numbers. It means that all durations depend on a parameter to be chosen (for instance indexing scenarios). This problem formulation is given to validate the PERT algorithm with gradual numbers which is used in next sections. However we can see this problem as an optimization problem on a family of scenarios: for a given λ, di j ¡ λ¥ is a precise duration, and so configuration (set of the durations) at degree λ is a particular scenario. This parametric approach can model dependencies between tasks durations, but only with one degree of freedom. Figure 2 provides gradual durations of tasks of the project of Figure 1. d13 ¡ λ¥ ¦ 2 λ means that the duration of task ¡ 1£ 3¥ is 2 in each considered scenario. We can note on this example that the duration of tasks ¡ 1£ 2¥ and ¡ 2£ 3¥ are correlated, and the more time the task ¡ 1£ 2¥ will require, the faster the task ¡ 2£ 3¥ will be executed.

Computing earliest starting date, latest starting date and float of this problem is very simple: we just need to run the standard PERT Algorithm, where ¥ , ¦ , max and min are the four operations on gradual numbers seen in the previous section. This is due to the fact that all algebraic properties needed to apply the PERT Algorithm are preserved by the gradual numbers, for example the fact that § £ max£ ¥ © is an idempotent semi-ring, validates the forward recursion of the PERT Algorithm. The backward recursion is possible since the addition operation as an inverse ( § £ ¥ © is a commutative group), so con- trary to the interval-valued problem, we do not run the risk of counting any uncertainty twice. For more detail, the reader should refer to [START_REF] Fortin | Gradual numbers and their application to fuzzy interval analysis[END_REF][START_REF] Gondran | Graphs and Algorithms[END_REF].

Algorithm 1 works as follow: Line 1 is the initialization to 0 of all the earliest starting dates of events (nodes of the graph). Part from line 2 to line 5 is the standard forward recursion which computes earliest starting dates. Line 6 is initialization of the latest starting dates. Lines 7 to 11 is the standard backward recursion which computes latest starting dates and float. The main difference between this algorithm and the usual PERT/CPM algorithm is in the form of the results, because max and min are not selective, a characteristic of a task may not correspond to a single configuration. For instance, a task may be critical for some values of λ ¡ 0£ 1¤ and not critical for other values.

We present on Figure 3 the results of the computation of the earliest starting date, latest starting date and float of task ¡ 2£ 3¥ . It means that for all scenario generated with λ © 1 3 , the task ¡ 2£ 3¥ is critical, but it is not for λ £ 1 3 . In practice, we must store this information describing a more complex situation than in the deterministic case.

Algorithm 1: GradualPERT

Input: A network G ¦ ¨ § V£ A © , activity duration is known as gradual numbers.

Output: Gradual earliest starting date ẽ st i j , gradual latest starting date l st i j and gradual float fi j of each task ¡ i£ j¥ of the network.

1 foreach i § 1 n¤ do ẽ st i 0; 2 for i l to n ¦ 1 do 3 foreach j Succ ¡ i¥ do 4 ẽ st i j ẽ st i ; 5 ẽ st j max ¡ ẽ st j £ ẽ st i ¥ di j ¥ ; 6 foreach i § 1 n¤ do l st i ẽ st n ; 7 for j n downto 2 do 8 foreach i Pred ¡ j¥ do 9 l st i j l st j ¦ di j ; 10 fi j ¦ l st i j ¦ ẽ st i j ; 11 l st i min ¡ l st i £ l st j ¦ di j ¥ ;

Fuzzy Interval Valued PERT

In this section, we suppose that durations of tasks of the project are given by fuzzy intervals. A simple model of a fuzzy task duration for a regular PERT user can be a triangular fuzzy interval whose core is the most plausible duration and whose support is the interval of all possible durations. We show that we can assert the necessarily criticality degree of a task in polynomial time complexity. Then we will give an algorithm to obtain the gradual upper bound of the float of a given task.

Asserting Necessarily Criticality

We have seen in Section 2.2 that we can precisely set the duration of all tasks of the network without changing the criticality of a given task ¡ k£ l¥ when task duration are modeled by crisp intervals. To assert the degree of necessary criticality of a task ¡ k£ l¥ in the fuzzy case, we can use the same type of algorithm, using gradual numbers instead of real numbers. But from Proposition 3 (resp. 4), to fix the precise gradual duration of a task ¡ i£ j¥ , we have to test if the task ¡ k£ l¥ is critical in the subnetwork G ¡ j £ n¥ (resp. G ¡ 1£ j¥ ). We have seen in the previous section that on a gradual PERT, tasks can be critical for some possibility degree and not critical for others (see example on Figure 3).

This means that the gradual duration assigned to task ¡ i£ j¥ may involve both upper and lower gradual bounds of the duration Di j ¦ § d© i j £ d i j ¤ .

Algorithm 2:

Input: A network G, activity ¡ k£ l¥ , fuzzy interval durations Duv ¦ § d© uv £ d uv ¤ , ¡ u£ v¥ A and for every task in PRED ¡ k£ l¥ the duration dkl is precisely given (but gradual).

Output: f

kl the "potential" maximal float of task ¡ k£ l¥ : f kl ¡ λ¥ ¦ 0 for all pos- sibility degree for which the task is necessarily critical, f kl ¡ λ¥ © 0 for all possibility degree for which the task is not necessarily critical, but in this case f kl ¡ λ¥ is not the exact float of ¡ k£ l¥ . 1 foreach ¡ u£ v¥ SUCC ¡ k£ l¥ do duv d uv ;

2 dkl d © kl ; 3 for i l to n ¦ 1 such that i SUCC ¡ l¥ ¢¡ l do 4 f kl Algorithm 1 with G ¡ 1£ i¥ ; 5 foreach λ ¢¡ 0£ 1¤ such that f kl ¡ λ¥ ¦ 0 do 6 foreach j Succ ¡ i¥ do di j ¡ λ¥ d © i j ¡ λ¥ ; 7 foreach λ ¢¡ 0£ 1¤ such that f kl ¡ λ¥ © 0 do 8 foreach j Succ ¡ i¥ do di j ¡ λ¥ d i j ¡ λ¥ ; 9 return f kl ;
Line 1 of Algorithm 2 initializes gradual durations of all tasks of the network not succeeding ¡ k£ l¥ to their maximal gradual bounds, according to Proposition 2. Lines 3£ 8 assign gradual values for the tasks succeeding ¡ k£ l¥ , depending on the criticality of ¡ k£ l¥ , with respect to Proposition 4. The creation of the gradual duration di j (Lines 5 and 8) may seem complex, but is very simple to implement in practice, for example, when durations are given by piecewise linear fuzzy intervals [START_REF] Kerre | Implementation of piecewise linear fuzzy quantities[END_REF]. Then gradual bounds of those interval can be simply modeled by the lists of their kinks. All computed gradual durations are also piecewise linear, since operations ¥ , ¦ , max and min preserve the piecewise linearity.

In this context, finding all λ ¡ 0£ 1¤ such that f kl ¡ λ¥ ¦ 0 remains to find the pairs of adjacent kinks whose abscissa is 0. Note that the result f kl of Algorithm 2 is not the correct maximal gradual float f kl of ¡ k£ l¥ : it is correct only if f kl ¡ λ¥ ¦ 0. So this Algorithm is useful to know the Necessary degree criticality of a task when its predecessors are precisely (but gradually) fixed, and will be invoked in the next algorithm. We can now compute the gradual upper bound of the floats of a task ¡ k£ l¥ . The idea is to make ¡ k£ l¥ necessarily critical for all λ by adding a gradual duration ∆ to d © kl . This is done by Algorithm 4. The first step of the algorithm computes f kl ¡ i£ n¥ , the "potential float" of ¡ k£ l¥ in the network G ¡ i£ n¥ (lines 1 and 2). In practice, only one iteration of Algorithm 3 is needed to obtain f kl ¡ i£ n¥ for all i Pred ¡ k¥ . The second step of the algorithm constructs a gradual duration ∆ to add to d© kl in order to make ¡ k£ l¥ necessarily critical in at least one more sub-network G ¡ i£ n¥ , for all possibility degree (lines 5 and 6).

In practice, constructing ∆ is easy, we just need to restrict all the f kl ¡ i£ n¥ on a domain for which f kl ¡ i£ n¥ ¡ λ¥ ¡ ¦ 0 and f kl ¡ 1£ n¥ ¡ λ¥ ¡ ¦ 0 , and take their minimum, as defined in Section 2.3. Algorithm 4 repeats this step until ¡ k£ l¥ becomes necessarily critical in G ¡ 1£ n¥ for all possibility degree. The total gradual increase of d © kl is then the gradual float f kl of ¡ k£ l¥ . By definition of the gradual numbers, the obtained f kl is such that f kl ¡ λ¥ is the exact LUB of floats of task ¡ k£ l¥ at possibility degree λ, and the degree of criticality is 1 ¦ inf λ fkl ¡ λ¥ ¦ 0 .

Remark: In the interval-valued problem, asserting possible criticality and computing lower bound of floats are NP-Hard problems [START_REF] Fortin | Interval analysis in scheduling[END_REF]. However efficient algorithms exist and can be adapted to the fuzzy interval case with the help of gradual numbers. One of these algorithms consists in running a PERT/CPM on configurations where all task durations are set to their lower bounds but on a path from node 1 to node n [START_REF] Dubois | Computational methods for determining the latest starting times and floats of tasks in interval-valued activity networks[END_REF]. The lower bound of the float of a task is then the minimal computed float over the configurations issued from all possible paths. This method is directly applicable to the fuzzy-valued problem, using gradual bounds of fuzzy intervals, instead of usual interval end-points.

Conclusion

In this paper, we generalize some recent results of [START_REF] Fortin | Interval analysis in scheduling[END_REF] for project scheduling problems under uncertainty, when task durations are modeled by fuzzy intervals. We give algorithms that assert the degree of necessarily criticality of a given task in polynomial time. And we construct an algorithm to compute the least upper bound of floats in polynomial time for each possibility degree λ ¡ 0£ 1¤ . Those algorithms are based on the very recent notion of gradual number, which provides a new way of looking at fuzzy intervals as classical intervals of gradual numbers. Thus allowing to apply interval analysis methods to fuzzy intervals directly.

Figure 1 .

 1 Figure 1. Simple project scheduling problem

Figure 2 .

 2 Figure 2. Gradual duration of tasks of the project of Figure 1

Figure 3 .

 3 Figure 3. Gradual earliest starting date, latest starting date and float

  Algorithm 3 computes the necessary criticality degree of a given task ¡ k£ l¥ when all task durations are fuzzy interval valued. It recursively assigns precise (but gradual) durations to tasks preceding node k, due to to Proposition 4. The result is a gradual "potential" maximal float f kl of task ¡ k£ l¥ , which means that ¡ k£ l¥ is necessarily critical at degree at least λ if and only if f kl ¡ λ¥ ¦ 0. But if f kl ¡ λ¥ © 0, then f kl ¡ λ¥ is not the correct maximal float of ¡ k£ l¥ at possibility degree λ. Computing the exact maximal float f kl ¡ λ¥ at possibility degree λ is the subject of the next paragraph. A network G, activity ¡ k£ l¥ , fuzzy interval durations Duv ¦ § d© uv £ d uv ¤ , ¡ u£ v¥ A. ¡ λ¥ is not the exact float of ¡ k£ l¥ . 1 for j k downto 2 such that i PRED ¡ k¥ ¢¡ k do

	Algorithm 3:
		Input: Output: f sibility degree for which the task is necessarily critical, f kl the "potential" maximal float of task ¡ k£ l¥ : f kl ¡ λ¥ ¦ 0 for all pos-kl ¡ λ¥ © 0 for all possibility degree for which the task is not necessarily critical, but in this case f
	2 3	f foreach λ ¢¡ 0£ 1¤ such that f kl Algorithm 2 with G ¡ j £ n¥ ; kl ¡ λ¥ ¦ 0 do
	3 f 4 while f kl 0; dkl kl ¡ 1£ n¥ ¡ d © kl ; ¦ 0 do 5 foreach λ ¢¡ 0; 1¤ do 6 ∆¡ λ¥ min f

kl 4 foreach i Pred ¡ j¥ do di j ¡ λ¥ d© i j ¡ λ¥ ; 5 foreach λ ¢¡ 0£ 1¤ such that f kl ¡ λ¥ © 0 do 6 foreach i Pred ¡ j¥ do di j ¡ λ¥ d i j ¡ λ¥ ; 7 return f kl ; Algorithm 4: Input: A network G, activity ¡ k£ l¥ , fuzzy interval durations Duv , ¡ u£ v¥ A. Output: The gradual least upper bound f kl of floats of ¡ k£ l¥ . 1 foreach i Pred ¡ k¥ do 2 f kl ¡ i£ n¥ f kl with Algorithm 3 in network G ¡ i£ n¥ ; kl ¡ j £ n¥ ¡ λ¥ j PRED ¡ k¥ £ f kl ¡ j £ n¥ ¡ λ¥ ¡ ¦ 0 ; 7 dkl dkl ¥ ∆; 8 foreach i Pred ¡ k¥ do 9 f kl ¡ i£ n¥ f kl with Algorithm 3 in network G ¡ i£ n¥ ; 10 return f kl 4.2. Computing Gradual Least Upper Bound of Floats


Marc Vincent
email: marc.vincent@thalesgroup.com

Amal El

Vincent Corruble

Narayan Bernardin

Rami Kassab

Frédéric Barbaresco

Amal El Fallah

Monte Carlo Tree Search for Multi-function Radar Task Scheduling

Keywords: Artificial Intelligence, Multi-function Radar, Combinatorial Optimization, Scheduling

published or not. The documents may come

L'archive ouverte

Introduction

Multi-function radars (MFR) are a class of radars that are able to concurrently perform a range of functions that would otherwise have to be carried out by several distinct radars. MFRs have been made possible by the development of phased-array antennas, which enhance the radar's flexibility by enabling greater control over waveforming and beamforming. An MFR's functions usually include search, tracking, and various combat-assistance roles such as missile guidance. Given that a radar runs under constraints of time, power, and processing, a key challenge of MFR design is radar resource management, which consists in allocating these resources between functions [START_REF] Moo | Adaptive Radar Resource Management[END_REF]. Resources must be allocated according to the radar's mission, which determines the priority level of each function.

Among these resources, time budget is the most critical, as the time spent performing a given task closely reflects its importance. Each function consists of one or more tasks, for example tracking a specific target; each task is carried out by performing a number of dwells characterized by requirements in desired execution time, duration, and power. Based on the current situation, the radar continuously generates dwell requests corresponding to its different functions.

The resulting list of requests is regularly transmitted to a scheduler, whose role is to decide which dwells should be executed and at what time. Efficient scheduling is crucial in overload situations, which happen when temporal constraints prevent from executing all dwells, forcing the scheduler to drop some of them according to their level of priority.

This scheduling problem is usually tackled with heuristics, yet such methods become increasingly suboptimal as the complexity of the situations radars face grows. These situations involve new threats, like drone swarms, which are likely to create overload, and hyper-maneuvering, high-velocity, and furtive targets, which might require more resources to track efficiently. Proposed alternatives make use of a range of methods, including expert systems, metaheuristics, and neural networks [START_REF] Jeauneau | Scheduling on a fixed multifunction radar antenna with hard time constraint[END_REF][START_REF] Moo | Adaptive Radar Resource Management[END_REF][START_REF] Winter | On scheduling a multifunction radar[END_REF][START_REF] Zheng | On scheduling a multifunction radar with duty cycle budget[END_REF].

In this work, we treat task scheduling as a sequential decision problem. In recent years, in the wake of significant progress in the field of combinatorial games, such as for Go [START_REF] Silver | Mastering the game of Go without human knowledge[END_REF], this kind of approach has been extended successfully to "single-player" combinatorial settings [START_REF] Laterre | Ranked Reward: Enabling Self-Play Reinforcement Learning for Combinatorial Optimization[END_REF]. We build upon the work of Gaafar et al. [START_REF] Gaafar | Reinforcement Learning for Cognitive Radar Task Scheduling[END_REF], who first proposed to apply this type of technique to radar task scheduling.

First, we present our main contribution, a formulation of the radar task scheduling problem as a Markov decision process that allows building schedules in a flexible way. Then, we exemplify the usefulness of our model with a heuristic and a variant of Monte Carlo Tree Search (MCTS) adapted to this formulation. Finally, we evaluate our algorithms and demonstrate the improvement in performance brought by our approach.

Framework

We formalize the problem of radar task scheduling similarly to Gaafar et al. [START_REF] Gaafar | Reinforcement Learning for Cognitive Radar Task Scheduling[END_REF]. As we mentioned above, our model of an MFR scheduler processes one fixed set of tasks1 at a time. An updated set of tasks is received at regular intervals. In the meantime, no tasks may be added to the set that is being processed. Each task in a set I = {1, ..., n} is characterized by its temporal constraints and its priority level. The temporal constraints of a task i are defined by its length L i , its start time T i s and drop time T i dr (respectively the earliest and latest date at which it can start executing), and its due time T i du , which is the desired execution time. In this work, for any given instance, these constraints are all held constant over the course of the scheduling process: we do not consider preemptive tasks (e.g. for dwell interleaving) or variable duration time. Our goal is to determine for each task i in I whether to schedule it (x i = 1, else 0), and if so at what execution time t i , or to drop it (y i = 1, else 0). Scheduled tasks must be entirely contained in a temporal frame [0, T max ]. In order to arbitrate between tasks in case of conflicts, each task is ascribed a drop cost C i dr and a delay cost C i de which reflect its priority level. The drop cost is incurred only when the corresponding task is dropped while the delay cost determines how much the difference between the actual and ideal execution times is penalized; this difference is an absolute value, unlike in [START_REF] Gaafar | Reinforcement Learning for Cognitive Radar Task Scheduling[END_REF] where due times were not distinct from start times. How to assign relevant values to these costs in an operational context is left to future work. We write instances of the problem as P = {(L i , T i s , T i dr , T i du , C i dr , C i de ) ∀i ∈ I ; T max }, and its (partial) solutions, or schedules, as s = {(x i , y i , t i ) ∀i ∈ I}. The objective is to minimize the sum of costs (or total cost) C P (s). We summarize the problem below, where ⊕ represents an exclusive or:

min C P (s) = i∈I x i t i -T i du C i de + y i C i dr s.t.            T i s ≤ t i ≤ T i dr ∀i ∈ I t i + L i ≤ T max ∀i ∈ I t i + L i ≤ t j ⊕ t j + L j ≤ t i if x i = x j = 1, ∀(i < j) ∈ I 2 t i ∈ R + ∀i ∈ I x i , y i ∈ {0, 1} with x i = 1 -y i , ∀i ∈ I (1)
This problem can be solved to optimality with mixed-integer programming (MIP). Unfortunately, since problem (1) is in NP 1 , the computation time for MIP grows exponentially with the number of tasks, making it prohibitive for radar applications. In order to give further insight into the structure of the problem, we offer its detailed formulation for MIP:

min C P (s) = i∈I l i de C i de + (1 -x i )C i dr s.t.                            T i s ≤ t i ≤ T i dr t i + L i ≤ T max l i de ≥ t i -T i du l i de ≥ T i du -t i        ∀i ∈ I t i + L i ≤ t j + M (n ij + o ij ) t j + L j ≤ t i + M (n ij + 1 -o ij ) ∀(i < j) ∈ I 2 n ij = 2 -x i -x j ∀(i < j) ∈ I 2 x i ∈ {0, 1}, t i , l i de ∈ R + ∀i ∈ I o ij ∈ {0, 1}, n ij ∈ R + ∀(i < j) ∈ I 2 (2)
where M is an arbitrarily large number such that M T max . Of interest in formulation ( 2) is the presence of binary variables o ij in addition to x i . The values of o ij determine the order in which the scheduled tasks are placed. This highlights the fact that problem (1) can be subdivided in three successive subproblems:

1. inclusion: determine which tasks to schedule; 2. ordering: determine the order in which these tasks should be scheduled; 3. time setting: determine the execution times of these ordered scheduled tasks.

Note that problem (1) can also be solved with heuristics like earliest start time first (EST) or earliest deadline first (EDF). These heuristics (and variations thereof) are common in radar resource management because they are fast and easy to implement. However they will often produce poor solutions, for two reasons: first, because they operate on the premise that the schedule must be built by adding tasks in chronological order; second, because they do not account for task priority.

By contrast, we aim to develop approximate algorithms for radar task scheduling that can approach optimal solutions while keeping reasonable computation times. Our first step is to model problem (1) as a Markov decision process (MDP). MDPs are the most common formalization of sequential decision problems. An MDP is defined by: a finite state space S, a finite action space A, a distribution over initial states µ : S → [0, 1], a transition function T : S × A × S → [0, 1], which gives the conditional probability T (s | s, a) of transition to the next state s given the previous state s and selected action a, and a reward function R : S × A × S → R that gives the reward associated with a transition. We can associate a strategy π : S × A → [0, 1] to an MDP, i.e. a probability distribution over which action to take in a given state. The objective is usually to maximize the value function, which is the expectation of the sum of rewards:

V π (s 0 ) = E at∼π,st∼T T t=0 γ t R(s t , a t , s t+1 ) where γ ∈ [0, 1]
is the discount factor and T the final step of an episode. Once we have defined a suitable MDP, we will need an algorithm that outputs a strategy for this MDP, which we call the decision algorithm. Following Gaafar et al. [START_REF] Gaafar | Reinforcement Learning for Cognitive Radar Task Scheduling[END_REF], we define a state as a partial schedule, where a number of tasks have been scheduled at certain execution times and a number of others dropped while respecting the constraints of (1). The only initial state s 0 for a given instance of the problem is the associated empty schedule, where no tasks are scheduled or dropped. We also define an action as the choice of one task to schedule in the set of available tasks A = {i ∈ I | x i = y i = 0}. Terminal states are states where no actions are available, that is, complete schedules, where all tasks are scheduled or dropped. We can define the reward as the cost difference between the two states involved in a transition, i.e. R(s, a, s ) = C P (s) -C P (s ). With γ = 1, the value function becomes V π (s 0 ) = E π [C P (s 0 ) -C P (s T )], which corresponds to our initial objective of finding a schedule s that minimizes C P (s). In practice, in our algorithms, we reason directly on costs.

The choice of the transition function is the most crucial aspect of this formalization. Transitions must deterministically decide what execution times to set and which tasks to drop when a new task is added to a partial schedule.

The simplest option, used in [START_REF] Gaafar | Reinforcement Learning for Cognitive Radar Task Scheduling[END_REF], is to add tasks chronologically: any newly added task i is assigned an execution time greater than that of all previously scheduled tasks, and tasks that cannot be placed after i are dropped. However, this restricts the range of viable strategies, since the decision algorithm has to solve both the inclusion and the ordering sub-problems at the same time, while the transition function only deals with the time setting sub-problem.

Instead, we propose a transition model that allows building schedules in a more flexible way. Our idea is to model the transition function such that it solves both the ordering and the time setting sub-problems at each step. That is, given a set S of scheduled tasks, the transition determines the order of tasks and their execution times by minimizing the total delay cost:

min i∈S l i de C i de s.t.                        T i s ≤ t i ≤ T i dr t i + L i ≤ T max l i de ≥ t i -T i du l i de ≥ T i du -t i        ∀i ∈ S t i + L i ≤ t j + M o ij t j + L j ≤ t i + M (1 -o ij ) ∀(i < j) ∈ S 2 t i , l i de ∈ R + ∀i ∈ S o ij ∈ {0, 1} ∀(i < j) ∈ S 2 (3)
Given a partial schedule s = {(x i , y i , t i ) ∀i ∈ I}, in order to schedule a new task j ∈ I, we solve sub-problem (3) for S = {i ∈ I | x i = 1} ∪ {j}. If there is no solution to the sub-problem, j has to be dropped. After a task is scheduled, all remaining tasks in A can be tested for dropping using this procedure.

Sub-problem (3) can also be treated with a MIP solver; however this requires finding the order and execution times of all tasks in S at every transition. This is inefficient, because with this transition model, when we move from a partial schedule s to a new one s by adding a task i, the execution times in s are already optimal with regard to the tasks scheduled in s. This means that if for example i can be placed at its desired execution time without interfering with already scheduled tasks, then there is no need to recompute the execution times of these tasks. To exploit this and a number of other optimizations, we implement a custom solver for sub-problem (3) which we do not detail here due to space limitations: the key idea is to recursively generate and evaluate permutations of the scheduled tasks while limiting the number of generated permutations by exploiting temporal constraints. Note that this way, we can check the availability of a task faster, by interrupting the recursion as soon as we find a feasible permutation.

Our transition model allows adding tasks in any order by delegating part of the optimization-ordering and time setting-to the environment. Crucially, for any schedule s reached through this transition model, the execution times are optimal given the tasks scheduled in s. (We can also limit the number of generated permutations to lower the computation time, although we then lose the optimality guarantee.) This opens new possibilities for the choice of the decision algorithm, whose role is to solve the hardest part of the problem: inclusion.

Methods

The first decision algorithm we propose is a heuristic that we call highest costlength ratio first (HCLR), which is similar to some knapsack problem heuristics. It consists in sorting tasks by their ratio between drop cost and length, then scheduling them in decreasing order (if they are still available when their turn comes). Equivalently, at each step, we choose the following action:

a = argmax a∈A C i dr L i
This heuristic empirically performs better than scheduling the task with the highest drop cost first, because it accounts for situations where for example two shorter, lower-priority tasks have a higher total drop cost than one longer, higher-priority task which they are incompatible with. A similar criterion has been proposed for radar resource management in Qu et al. [START_REF] Qu | A Machine Learning Task Selection Method for Radar Resource Management (Poster)[END_REF]; however, the authors used the ratio in a task selection phase that preceded the scheduling itself, which is based on EST. Using our transition model, we can instead directly select and schedule each task in turn.

Our next decision algorithm is a version of Monte Carlo Tree Search (MCTS) adapted to task scheduling, which is based in large part on the version of Gaafar et al. [START_REF] Gaafar | Reinforcement Learning for Cognitive Radar Task Scheduling[END_REF]. MCTS uses a search tree where nodes represent MDP states and branches correspond to actions taken in the parent node [START_REF] Browne | A Survey of Monte Carlo Tree Search Methods[END_REF]. The tree is constructed by successive rollouts: starting from the root node, which corresponds to the initial state, we select an action, apply the transition function to get the next node (which is created if needed), and repeat. Once a terminal state is reached, we can compute its total cost C, then backpropagate C up the path we just followed to update the best cost reached from each state-action pair: C(s, a) ← min{C(s, a), C}. This value is then used in the computation of the upper-confidence bound U (s, a) which determines which actions are chosen in the selection phase: a = argmax a U (s, a ) with U (s, a) = P (s,a) C(s,a) τ (1+N (s,a)) where τ is a temperature, N (s, a) is the number of rollouts where action a was taken in state s, and P (s, a) is a prior probability function over actions. This selection rule is designed to balance exploration of the search tree and exploitation around the best solutions found so far. The prior, especially, plays a prominent role in steering exploration; a simple way to parameterize it is to sort the m available tasks according to a criterion, then assign them a respective prior probability of p(1 -p) m for m ranging from 0 (for the first task) to m -1. For our experiments, we set τ = 2 and p = 0.6, similarly to [START_REF] Gaafar | Reinforcement Learning for Cognitive Radar Task Scheduling[END_REF], but we diverge by using HCLR as our sorting criterion instead of EST.

One issue is that when using our transition model, since tasks can be scheduled in any order, it is possible to reach the same terminal state via multiple different rollouts. In order to prevent this, we structure our search tree similarly to a branch-and-bound (B&B) tree [START_REF] Clausen | Branch and Bound Algorithms -Principles and Examples[END_REF]: when a new action is taken in node s, leading to a new node s , all actions explored in s in previous rollouts are made unavailable in s and its descendants. This makes sure there is only one path to each terminal state in the search tree. However, it also means that we may reach terminal nodes that are not complete schedules, when some tasks can still be scheduled, but have all been made unavailable by the previous rule. To limit the number of such situations, at each visit of a node s, we check if there exists a terminal node s descended from s such that all tasks that are unexplored in s are scheduled in s ; if so, these tasks are made unavailable in s. Additionally, to avoid performing the same rollout twice, if a node has no more available actions, the action that led to it is also made unavailable in the parent node, as in [START_REF] Gaafar | Reinforcement Learning for Cognitive Radar Task Scheduling[END_REF]. We call this algorithm B&B-MCTS.

Usually, in MCTS, when we reach a new state, we want to know which actions are available. With B&B-MCTS, this allows making the most effective use of pruning, according to the above rules. However, with our transition model, it requires partially solving (3) for each a priori available task to check if it has to be dropped. In larger instances, this involves significant computation, which reduces the number of rollouts that can be carried out in a given time. For this reason, we program B&B-MCTS so that it attempts to schedule tasks without prior verification, and drops them only if the attempt fails.

Results

To enable comparisons, we run experiments on instances from the same distribution as in [START_REF] Gaafar | Reinforcement Learning for Cognitive Radar Task Scheduling[END_REF]:

L i ∼ U (2, 15), T i s ∼ U (0, T max -12), T i du = 0, T i dr -T i s ∼ U (2, 12), C i dr ∼ U (100, 500), C i de ∼ U (1, 15
), T max = 100. The difficulty of an instance mostly depends on the density of tasks; by keeping T max fixed, the difficulty can be controlled by setting the number of tasks.

We compare our two methods, HCLR and B&B-MCTS, with the EST heuristic and with the version of MCTS proposed in [START_REF] Gaafar | Reinforcement Learning for Cognitive Radar Task Scheduling[END_REF] (which we term EST-MCTS). The run time of both versions of MCTS is limited to 1 second. All these algorithms are implemented in Python. We compute the optimal solution using MIP on instances where this resolution can be performed in a reasonable amount of time. The MIP solver we use is CBC [START_REF]COIN-OR Foundation: Cbc (COIN-OR Branch-and-Cut solver[END_REF]. These five algorithms are run on the same instances, 1000 per number of tasks. We also compare our results to those reported by [START_REF] Gaafar | Reinforcement Learning for Cognitive Radar Task Scheduling[END_REF] for a reinforcement learning-based extension of EST-MCTS inspired by AlphaZero [START_REF] Silver | Mastering the game of Go without human knowledge[END_REF].

Our results show that our approach provides a significant performance improvement over EST-MCTS, and even surpasses the reinforcement learning algorithm of [START_REF] Gaafar | Reinforcement Learning for Cognitive Radar Task Scheduling[END_REF], which used deep learning in conjunction with MCTS. Strikingly, the performance gain of B&B-MCTS over HCLR proves minimal. Moreover, with our implementation, HCLR's run time averages 36 milliseconds on 50-task instances, which would presumably make it more suitable for radar use cases than MCTS-based methods.

Unlike in [START_REF] Gaafar | Reinforcement Learning for Cognitive Radar Task Scheduling[END_REF], our approach allows due times distinct from start times, thus reflecting radar requirements more closely. We also run experiments on a similar task distribution but with T i du ∼ U (1, 4) and T i dr -T i s ∼ U (1, 8); our results match those of the first distribution very closely.

Conclusion

Through a reformulation of the problem of radar task scheduling, we were able to implement an efficient framework whose algorithmic applications can return quasi-optimal solutions in a limited amount of time. We see potential improvements for this framework, both by optimizing its run time to make it usable by real-world radars, and by increasing its flexibility; for example, being able to remove a task from a partial schedule could allow exploring the solution space more effectively. Furthermore, our B&B-MCTS algorithm could be extended with an AlphaZero-style reinforcement learning procedure which would make it able to adapt to various task distributions.

Fig. 1 .

 1 Fig. 1. Cost plotted against instance size for identical start and due times.

Table 1 .

 1 Detailed statistics on three different instance types.

	Algorithm Avg. cost	Cost std. dev.	Dropped tasks (%)	Optimal solutions (%)	Avg. runtime (milliseconds)	Avg. number of rollouts
		Number of tasks = 25, identical start and due times
	EST	4658.69 634.65	59.06	0.0	1.93	nan
	EST-MCTS 3716.55	506.0	52.15	0.87	1002.88	727.06
	HCLR	3390.6	551.68	48.2	21.35	13.12	nan
	B&B-MCTS 3299.39 526.16	48.44	57.73	975.32	96.12
	MIP-optimal 3268.43 523.85	48.65	100.0	1730.82	nan
		Number of tasks = 50, identical start and due times
	EST	12031.8 857.18	77.64	nan	2.32	nan
	EST-MCTS 10897.03 758.17	73.23	nan	1004.79	587.63
	HCLR	9130.98	799.9	63.62	nan	36.7	nan
	B&B-MCTS 9080.49 780.86	63.79	nan	991.72	30.1
		Number of tasks = 25, distinct start and due times
	HCLR	3301.15 550.93	47.53	22.0	19.98	nan
	B&B-MCTS 3219.61 524.51	47.61	56.5	994.69	70.96
	MIP-optimal 3185.86	520.0	47.88	100.0	2219.44	nan

In the rest of this article, we will use the standard terminology for scheduling, where "task" refers to the basic elements of a schedule-in our case, radar dwells. It should not be confused with the radar tasks mentioned earlier.

This can be proven via a polynomial reduction with the knapsack problem by setting T i s = C i de = 0 and T i dr = Tmax for all i in I.