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

Pawe L Zieliński
email: pawel.zielinski@pwr.wroc.pl

Didier Dubois
email: dubois@irit.fr

Hélène Fargier
email: fargier@irit.fr

Criticality analysis of activity networks under interval uncertainty * †

Keywords: Project scheduling, Interval PERT, Criticality, Interval uncertainty

This paper reconsiders the PERT scheduling problem when information about task duration is incomplete. We model uncertainty on task durations by intervals. With this problem formulation, our goal is to assert possible and necessary criticality of the different tasks and to compute their possible earliest starting dates, latest starting dates and floats. This paper puts together various results and provides a complete solution to the problem. We present the complexity results of all considered subproblems and efficient algorithms to solve them.

Introduction

An activity network is a partially ordered set of activities with given duration times, forming a directed acyclic graph. One basic problem when scheduling an activity network representing a project, is that of finding critical activities, and determining optimal starting times of activities, so as to minimize the makespan. The first step is to determine the earliest ending time of the project. This problem was posed in the fifties, in the framework of project management, by Malcolm et al. [START_REF] Malcolm | Application of a Technique for Research and Development Program Evaluation[END_REF] and the basic underlying graph-theoretic approach, called Project Evaluation and Review Technique, is now popularized under the acronym PERT. The determination of critical activities is carried out via the so-called critical path method (Kelley [31]). The usual assumption in scheduling is that the duration of each task is precisely known, so that solving the PERT problem is rather simple. However, in project management, the durations of tasks are seldom precisely known in advance, at the time when the plan of the project is designed. Detailed specifications of the methods and resources involved for the realization of activities are often not available when the tentative plan is made up. This difficulty has been noticed very early by the authors that introduced the PERT approach. They proposed to model the duration of tasks by probability distributions, and tried to estimate the mean value and standard deviation of earliest starting times of activities. Since then, there is an extensive literature on probabilistic PERT (see Elmaghraby [START_REF] Elmaghraby | Activity Networks: Project Planning and Control by Network Models[END_REF], and Adlakha and Kulkarni [START_REF] Adlakha | A classified bibliography of research on stochastic PERT networks: 1966-1987[END_REF] and Elmaghraby [START_REF] Elmaghraby | On criticality and sensitivity in activity networks[END_REF] for a bibliography and recent views). Even if the task duration times are independent random variables, it is admitted that the problem of finding the distribution of the ending time of a project is intractable, due to the dependencies induced by the topology of the network [START_REF] Hagstrom | Computational complexity of pert problems[END_REF][START_REF] Kleindorfer | Bounding distributions for a stochastic acyclic network[END_REF][START_REF] Ludwig | A Computational Study on Bounding the Makespan Distribution in Stochastic Project Networks[END_REF][START_REF] Meilijson | Convex majorization with an application to the length of critical paths[END_REF][START_REF] Shogan | Bounding Distributions for a Stochastic PERT Network[END_REF]. Another difficulty, not always pointed out, is the possible lack of statistical data validating the choice of activity duration distributions. In fact probability distributions permit to model the variability of repetitive tasks, but not uncertainty due to a lack of information [START_REF] Dubois | Representing partial ignorance[END_REF][START_REF] Ferson | Different methods are needed to propagate ignorance and variability[END_REF]. Even if statistical data are available, they may be partially inadequate because each project takes place in a specific environment, and is not the exact replica of past projects.

The simplest form of non-committal uncertainty representation for activity duration is the interval. Assigning some time interval I to an activity duration means that the actual duration of this activity will take some value within I, but it is not possible at present to predict which one. In this paper, every precise instantiation of duration times will be called a configuration (it is also called a scenario in the optimisation literature [START_REF] Kouvelis | Robust Discrete Optimization and its applications[END_REF] and a possible world in formal logic). Using intervals for representing uncertainty in scheduling means that the part of uncertainty about task duration due to partial ignorance prevails because the available statistical information is considered too scarce or irrelevant. So our model is more adapted to unique projects involving non-repetitive tasks. The managerial value of intervals can be questioned. Indeed, experts may find it difficult to provide narrow intervals (because they may be wrong). Moreover using too wide intervals may make further analysis useless because non-informative. So, we do not propose the use of intervals as the definite answer to scheduling uncertainty. However the importance of studying interval PERT is motivated by several considerations:

• Interval uncertainty is present as soon as information is incomplete. So, solving the extreme case of pure intervals is a first step before considering more elaborate representations of uncertainty where both probability and intervals are combined.

• By and large, an expert working on a project may be reluctant to provide point values for the expected duration for each task. Allowing the collection of a minimal and a maximal duration may be felt more realistic, even if the elicitation process should force the expert to provide as narrow intervals as possible.

• A more elaborate approach could be to collect both intervals and plausible values from experts. Then the interval PERT results could be seen as providing safeguards on the expected behaviour of the project while a precise reference plan based on plausible estimates could still be used.

Note that resorting to subjective probability for eliciting duration times of non-repetitive tasks is not very convincing. Eliciting subjective probabilities would be burdensome to experts, and it is well-known that subjective probability is neither a faithful nor a stable representation of partial ignorance [START_REF] Dubois | Representing partial ignorance[END_REF]. More precisely, if all that is known of an activity duration time d is that it lies between two bounds a < b, some may consider it natural to model this lack of knowledge by a uniform probability on [a, b]. However, if the scale were distorted by a monotonic function, say f , whereby f (a) < f (d) < f (b), then it is clear that the resulting probability distribution on [f (a), f (b)] would not be uniform. If one describes ignorance by uniform probabilities, then the rescaling function seems to generate information out of the blue. Moreover, it seems paradoxical to know the probability distribution precisely, while claiming ignorance. The interval representation stands for all probability distributions with support inside [a, b], which can hardly be challenged as representing ignorance. Of course, following the betting procedure of Bayesians, ignorance forces the expert to bet using a uniform probability. The same betting rates would be produced if the expert knew that the values of d are indeed uniformly distributed. So, the subjective probabilities produced have an ambiguous meaning, and, under a cautious approach one should perhaps on the contrary interpret a subjective uniform probability as a mere interval, unless the expert knows that there is a genuine underlying random phenomenon. See [START_REF] Dubois | A definition of subjective possibility[END_REF] for a general approach to re-interpret subjective probabilities as expressing partial ignorance.

Strangely enough, the PERT analysis with ill-known processing times modeled by simple intervals does not seem to have received much attention in the literature. Yet, the computation of the minimal completion time of a project, the determination of critical paths and activities, the determination of activity floats have been considered as important problems and have been widely acknowledged to be pervaded with uncertainty. However the overwhelming part of the literature devoted to this topic adopts an orthodox stochastic approach, thus leading to a very complex problem that is still partially unsolved to-date [START_REF] Hagstrom | Computational complexity of pert problems[END_REF]. To the best of the authors' knowledge, interval-valued PERT analysis seems to have existed only as a special case of fuzzy PERT studies that have been proposed since the late seventies [START_REF] Chanas | The use of fuzzy variables in PERT[END_REF][START_REF] Dubois | Modèles mathématiques de l'imprécis et de l'incertain en vue d'applications aux techniques d'aide à la décision[END_REF][START_REF] Hapke | Fuzzy project scheduling system for software development[END_REF][START_REF] Hapke | Fuzzy priority heuristics for project scheduling[END_REF][START_REF] Loostma | Fuzzy logic for planning and decision-making[END_REF][START_REF] Mccahon | Project network analysis with fuzzy activity times[END_REF][START_REF] Mccahon | Using PERT as an Approximation of Fuzzy Project-Network Analysis[END_REF][START_REF] Nasution | Fuzzy critical path method[END_REF][START_REF] Prade | Using fuzzy sets theory in a scheduling problem: a case study[END_REF][START_REF] Rommelfanger | Network analysis and information flow in fuzzy environment[END_REF]. Recently, Conde [START_REF] Conde | A minmax regret approach to the critical path method with task interval times[END_REF] has used the min-max regret criterion to find a robust set of critical tasks in a project with interval task durations. This criterion is discussed in the book [START_REF] Kouvelis | Robust Discrete Optimization and its applications[END_REF], which is entirely devoted to robust discrete optimization. In [START_REF] Conde | A minmax regret approach to the critical path method with task interval times[END_REF], exact and approximation algorithms are proposed to solve the min-max regret version of the longest path problem with interval weights in acyclic graphs (see [START_REF] Averbakh | Interval data minmax regret network optimization problems[END_REF][START_REF] Karasan | The robust shortest path problem with interval data[END_REF][START_REF] Kasperski | The robust shortest path problem in series-parallel multidigraphs with interval data[END_REF] for a formulation and complexity results). A determined optimal min-max regret path, that minimizes the maximal deviation (regret) from optimum over all configurations, represents a robust set of critical tasks.

A basic result in standard (deterministic) activity network analysis states that a task is critical if and only if its earliest and latest starting dates are equal, and that critical tasks form critical paths, that is, longest paths from the initial node (event) to the final one. So finding the critical paths yields the critical tasks. When the tasks have ill-known durations, modeled by intervals, these results are no longer valid. Namely, floats can no longer be recovered from the intervals containing earliest and latest starting dates, and critical paths may no longer exist, even when critical tasks are present. Instead of being critical or not, as in the deterministic activity network analysis, three cases may be now observed for every task or path: it is either surely not critical (necessarily not critical) or surely critical (necessarily critical) or possibly critical. A task (a path) is necessarily critical if it is critical whatever the actual values of task durations turn out to be. A task (a path) is possibly critical if there are values of task durations leading to a configuration, in which it is critical. Necessarily critical paths may fail to exist while necessarily critical tasks may be isolated.

The notions of possible and necessary criticality of tasks and paths are closely related to the min-max regret version of the longest path problem in acyclic directed graphs with interval weights [START_REF] Karasan | The robust shortest path problem with interval data[END_REF][START_REF] Kasperski | The robust shortest path problem in series-parallel multidigraphs with interval data[END_REF]. Namely, every optimal min-max regret path is possibly critical and every necessary critical path is optimal min-max regret with zero maximal regret. Hence, an optimal min-max regret path can be viewed as a possibly critical one, which minimizes a "distance" to the necessary criticality. Furthermore, necessarily non-critical tasks can be removed from an instance of the minmax regret longest path without violating optimal min-max regret paths and necessarily critical tasks can be automatically added to a constructed optimal min-max regret path (see [START_REF] Kasperski | Minmax regret approach and optimality evaluation in combinatorial optimization problems with interval and fuzzy weights[END_REF] for a deep discussion concerning the above relations).

This paper puts together various existing partial results about the complexity of finding intervals containing earliest and latest starting times and floats of tasks [START_REF] Chanas | The computational complexity of the criticality problems in a network with interval activity times[END_REF][START_REF] Chanas | On the hardness of evaluating criticality of activities in planar network with duration intervals[END_REF][START_REF] Dubois | Computational methods for determining the latest starting times and floats of tasks in interval-valued activity networks[END_REF][START_REF] Dubois | On latest starting times and floats in activity networks with ill-known durations[END_REF][START_REF] Zieliński | On computing the latest starting times and floats of activities in a network with imprecise durations[END_REF] and proposes new results, especially about evaluating necessary criticality, computing the maximal float of a task and computing the minimal latest starting times for all tasks, thus providing a complete solution to the PERT scheduling problem under the representation of interval-based uncertainty. A set of efficient algorithms for determining the criticality of tasks, the optimal intervals containing their earliest starting dates, latest starting dates, and their floats is provided. It is shown that the only strongly NP-hard problem is the one of finding minimal floats [START_REF] Chanas | On the hardness of evaluating criticality of activities in planar network with duration intervals[END_REF], which is closely related to asserting the possible criticality of a task that turned out to be strongly NP-complete [START_REF] Chanas | The computational complexity of the criticality problems in a network with interval activity times[END_REF]. All other problems turn out to be polynomial.

The paper is organized as follows. Section 2 motivates the work by showing the collapse of the usual criticality analysis concepts and techniques when duration times of tasks are imprecisely known. Section 3 proposes an exponential but practically efficient algorithm for achieving the complete criticality analysis under incomplete knowledge and a polynomial algorithm for computing the minima of latest starting dates for all task in a in network, based on an enumeration of paths. Section 4 presents polynomial algorithms for asserting necessary criticality of tasks, and computing the optimal intervals containing their latest starting dates, as well as the maximum of float values. These algorithms are constructive in the sense that they select appropriate values of task duration times in a step by step manner, such that the computation of some bound comes down to computing a standard PERT problem. An illustrative example is provided in Section 5. Section 6 contains exhaustive complexity results and experimental evidence of the efficiency of algorithms.

Definition and challenge of the interval valued model

In this section, we briefly recall how to solve the classical PERT model. Then we formally introduce the interval-valued PERT model, and explain why the classical approach no longer works.

Solving standard PERT problem

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 G =< V, A >, where V is the set of nodes (events), |V | = n, and A ⊆ V × V is the set of arcs (activities), |A| = m. We use the activity-on-arc convention. The set V = {1, 2, . . . , n} is labeled in such a way that i < j for each activity (i, j) ∈ A. Activity duration times d ij (the weights of the arcs) (i, j) ∈ A are known. Two nodes 1 and n are distinguished as the initial node (source) and final node (sink), respectively, (no activity enters 1 and no activity leaves n). Of major concern, is to minimize the ending time of the last task, also called the makespan of the network. Of interest to the project manager are earliest starting dates, latest starting dates and floats of activities. The critical activities have zero float. The essence of the PERT method are two recurrence formulae, forward and backward recursions. The earliest starting dates of events k ∈ V and tasks (k, l) ∈ A, denoted by est k and est kl respectively, are determined by means of the forward recursion:

est k = 0 if k = 1, max j∈P red(k) (est j + d jk ) otherwise, ( 1
)
est kl = est k , (2)
where P red(i) refers to the set of nodes that immediately precede node i ∈ V . The earliest starting date est k of event k is the length of a longest path from the beginning of the project, represented by node 1, to node k. We arbitrarily 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 earliest ending time of the project is the earliest starting date of the last event n. In order to ensure minimal duration of the project, the latest date of event n, denoted by lst n , is equal to its earliest starting date, lst n = est n . The latest starting date lst k of event k is the latest time to complete tasks that are ended at k without delaying the end of the project and thus it is the latest finishing date of tasks ending at k. Difference lst n -lst k is the length of a longest path from node k to node n. Hence, the latest starting date of task (k, l), denoted by lst kl , is equal to lst l -d kl . The latest starting dates of events and tasks can be found by the use of the backward recursion:

lst k = est n if k = n, min l∈Succ(k) (lst l -d kl ) otherwise, ( 3
)
lst kl = lst l -d kl , (4)
where Succ(i) refers to the set of nodes that immediately follow node i ∈ V . The float of 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 . (5)
The PERT method computes the earliest starting dates, latest starting dates and floats of tasks in O(m + n) time. One can also determine, simultaneously, critical tasks and critical paths and thus a subgraph consisting of all critical tasks and paths.

In the next section, we will see that some obvious properties of this scheduling model such as: "there exists at least one critical path, which is a longest path in the network", or, "one can form a critical path with critical activities", or yet "each critical activity belongs to a critical path", do not hold anymore under incomplete information.

Interval valued problem definition

In practice, duration times of tasks are not well known for several reasons: Some design choices are not fixed because we design a predictive plan. We can also suppose that there can be some uncertainty about the duration times of tasks. It is clearly the case for subcontracted tasks. To take into account this uncertainty, we now model each task duration by an interval. It is easy for an expert working on a project to give a minimal and a maximal expected duration for each task. So activity duration times d ij (weights of the arcs) (i, j) ∈ A are only known to belong to time intervals

D ij = [d - ij , d + ij ], d - ij ≥ 0.
This means that we neither know the exact duration times of tasks, nor can we set them precisely. Now, depending on the effective duration of each task (that we do not precisely know), several earliest starting dates, latest starting dates and floats can be considered. We assume that the task durations are unrelated to one another. A vector Ω = (d ij ) (i,j)∈A , d ij ∈ D ij , that represents an assignment of duration times d ij to task (i, j) ∈ A is called a configuration [START_REF] Buckley | Fuzzy PERT[END_REF]. Thus every configuration expresses a realization of the duration times. We denote by C the set of all the configurations, i.e.

C = × (i,j)∈A [d - ij , d + ij ]. The duration of task (i, j) in configuration Ω is denoted by d ij (Ω), d ij (Ω) ∈ D ij .
F kl = [f - kl , f + kl ]
for the float f kl can be rigorously defined as follows [START_REF] Dubois | On latest starting times and floats in activity networks with ill-known durations[END_REF][START_REF] Fargier | Fuzzy PERT in series-parallel graphs[END_REF]:

est - kl = min Ω∈C est kl (Ω), est + kl = max Ω∈C est kl (Ω), (6)
lst - kl = min Ω∈C lst kl (Ω), lst + kl = max Ω∈C lst kl (Ω), (7)
f - kl = min Ω∈C f kl (Ω), f + kl = max Ω∈C f kl (Ω), (8)
where est kl (Ω), lst kl (Ω) and f kl (Ω) denote the earliest and the latest starting date and the float of activity (k, l) in configuration Ω, respectively. Criticality in interval-valued problems is defined as follows [START_REF] Chanas | On the sure criticality of tasks in activity networks with imprecise durations[END_REF] :

a task (k, l) ∈ A (resp. a path p in network G from node 1 to node n) is possibly critical if there exists a configuration Ω ∈ C in which (k, l) (resp. path p) is critical in the usual sense. A task (k, l) ∈ A (resp. a path p in network G from 1 to n) is necessarily critical if (k, l) (resp. path p) is critical in the usual sense in all configurations Ω ∈ C .
In order to compute the intervals of possible values of earliest starting dates, latest starting dates and floats (see ( 6)-( 8)), the same PERT algorithm has been traditionally used (see formulae (1)-( 5)), the only difference being the use of the interval arithmetic instead of the classical arithmetic. For such a straightforward extension of the PERT algorithm, it turns out the forward recursion correctly computes the interval of possible earliest starting dates [START_REF] Chanas | The use of fuzzy variables in PERT[END_REF][START_REF] Dubois | Fuzzy Sets and Systems: Theory and Applications[END_REF][START_REF] Gazdik | Fuzzy network planning[END_REF]. Indeed, one can obtain all the optimal lower and upper bounds of earliest starting dates of tasks by applying the forward recursion (formulae: (1), ( 2)) for configurations Ω - A and Ω + A , respectively. But the backward recursion fails to compute the set of possible latest starting dates [START_REF] Mccahon | Using PERT as an Approximation of Fuzzy Project-Network Analysis[END_REF][START_REF] Mccahon | Project network analysis with fuzzy activity times[END_REF][START_REF] Prade | Using fuzzy sets theory in a scheduling problem: a case study[END_REF] and in

(c) 1 2 3 4 5 [1,1] [0,2] [1,1] [0,2] [3,3] [0,2] [0,2] 1 4 [1,2] [0,0] [1,2] [1,2] 2 3 [3,4] 1 [3,3] 4 [5,5] [1,3] [2,2] 3 2 [0,1] (a) (b)
Figure 1: (a) A network in which the necessary criticality of (3, 4) cannot be deduced from EST 34 = LST 34 (b) A network in which possibly critical activities do not form a possibly critical path (c) Dashed tasks form possibly critical paths, and the bold task is necessarily critical consequence floats can no longer be recovered from this procedure. Let us illustrate the point that the backward recursion can not be used to compute the latest starting dates and the floats. We first recall definitions of arithmetical operations on intervals (see [START_REF] Moore | Methods and Applications of Interval Analysis[END_REF]). Let * ∈ {+, -, min, max} and let U = [u -, u + ] and W = [w -, w + ] be two intervals such that u -≤ u + and w -≤ w + . Then the following expression

Z = U * I W = {u * w | u ∈ U, w ∈ W } defines operation * I ∈ {+ I , -I , min I , max I } on intervals and Z = [z -, z + ] is a resulting interval such z -≤ z + .
The following formulae are instrumental when performing interval operations as defined above:

U + I W = [u -+ w -, u + + w + ], U -I W = [u --w + , u + -w -], min I {U, W } = [min{u -, w -}, min{u + , w + }] and max I {U, W } = [max{u -, w -}, max{u + , w + }].
Consider the one activity network with duration time . This error comes from the fact that the variable which represents the duration appears two times in the computations: once in the forward recursion, and once in the backward one. Thus, applying interval arithmetic with linked variables always results in an over-imprecise bracketing of the exact result. For example, for all [START_REF] Adlakha | A classified bibliography of research on stochastic PERT networks: 1966-1987[END_REF]. Some authors tried to repair this propagation error in several ways: one classical approach is the use of a non-standard interval arithmetic [START_REF] Hapke | Fuzzy priority heuristics for project scheduling[END_REF][START_REF] Kaufmann | Fuzzy Mathematical Models in Engineering and Management Science[END_REF][START_REF] Rommelfanger | Network analysis and information flow in fuzzy environment[END_REF]. For example, some authors use for subtraction an "inverse" of the interval addition [START_REF] Hapke | Fuzzy priority heuristics for project scheduling[END_REF]. These operations are defined for fuzzy intervals, but their interval counterparts can be expressed as follows:

d 12 ∈ D 12 = [0, 1]. Its earliest starting date is EST 1 = EST 12 = [0, 0].
x ∈ [0, 1] x -x = 0, but [0, 1] -I [0, 1] = [-1,
[u -, u + ] -[w -, w + ] = [u --w -, u + -w + ]
. The use of this particular arithmetic does not lead to correct results for computing neither latest starting dates nor floats of tasks. In particular, the results may not be well formed intervals. For example, the difference between the intervals [0, 1] and [0, 2] would lead to [0, -1] which is not an interval, 0 ≤ -1. Thus, techniques using non-standard interval arithmetic will generally fail to produce the correct values. In [START_REF] Nasution | Fuzzy critical path method[END_REF], symbolic computations on variable duration times were suggested. However, this technique is unwieldy and highly combinatorial. Accordingly, no complete, correct and efficient solution to the problem of scheduling under interval uncertainty has been reached up until now.

There are obvious relations between the criticality of a task and the possible values of its floats and its earliest and latest starting dates, namely, task (k, l) is possibly (resp. necessarily) critical if and only if f - kl = 0 (resp. f + kl = 0). Moreover, if task (k, l) is necessarily critical then EST kl = LST kl . As shown in Figure 1a, the converse statement is false: task [START_REF] Buckley | Fuzzy PERT[END_REF][START_REF] Chanas | On the sure criticality of tasks in activity networks with imprecise durations[END_REF] has EST 34 = LST 34 = [START_REF] Buckley | Fuzzy PERT[END_REF][START_REF] Chanas | On the sure criticality of tasks in activity networks with imprecise durations[END_REF] for intervals of possible values of earliest and latest starting dates, but its interval of possible values of floats is F 34 = [0, 1]. It can be also noted that the float is no longer the difference between the latest starting date and the earliest starting date, for instance LST 34 -I EST 34 = [-1, 1] = F 34 . In fact, when EST kl = LST kl , task (k, l) is only possibly critical. The last example makes it clear that the interval containing the floats of a task cannot be calculated by means of the intervals containing the earliest and latest starting dates of this task. The float, from which the criticality of the task can be assessed, must be computed separately.

Many intuitions learned on the deterministic problem fail in the interval version. For example, when duration times are precisely set, critical activities always form a critical path. But in the interval case, possibly critical activities do not always form a possibly critical path. In Figure 1b, task [START_REF] Adlakha | A classified bibliography of research on stochastic PERT networks: 1966-1987[END_REF][START_REF] Buckley | Fuzzy PERT[END_REF] (1,3,5) is never critical. In Figure 1c, dashed arcs represent possibly critical tasks and the bold task (1, 2) is the only necessarily critical task. So, it can be seen that some necessarily critical tasks can be isolated. There is no necessarily critical path, but several paths are possibly critical (paths consisting of dashed arcs in Figure 1c). However, it is easy to check that if there exists a necessarily critical path, then it is unique (under the assumption that all duration times are intervals) and it is then easy to identify [START_REF] Chanas | On the sure criticality of tasks in activity networks with imprecise durations[END_REF]. But this case seems to appear rarely in practice. Therefore, the classical PERT results and algorithms cannot be directly adapted to the interval-valued problem.

The first important step for the resolution of the problems of computing the optimal bounds on the intervals of earliest starting dates, latest starting dates and floats (see ( 6)-( 8)) was taken by Dubois et al. [START_REF] Dubois | On latest starting times and floats in activity networks with ill-known durations[END_REF]. They showed that these bounds are attained on extreme configurations due to the monotonicity of functions that compute the quantities under concern. So a naive algorithm is to perform one PERT analysis on each extreme configuration which implies an O((m + n)2 m ) algorithm.

Other approaches have been developed to compute latest starting dates and floats. The first idea is to find a small subset of extreme configurations on which the bounds of the quantities of interest are attained. One such subset is defined by all extreme configurations in which all tasks have minimal duration times, but on a path from the initial node to the final one. On this path, task duration times are set to their upper bounds. The optimal upper bound on latest starting dates, the optimal lower and upper bounds on floats are reached on a configuration of this form. This idea will be presented in Section 3.

Another idea, called constructive approach, consists in a direct construction of one configuration (and just one) for which the extrema of the quantity of interest (for instance the optimal upper bound on latest starting dates of a task), is attained. In practice, we have to consecutively instantiate duration times of all tasks in a network without changing the result of the quantity of concern. The way of instantiation of a task duration to its least or greatest value is not simple. If we can assign precise duration times task by task in order to construct an extreme configuration, of course without changing the result of the quantity of concern, then this approach will lead to polynomial algorithms (see Section 4). Unfortunately, such approach cannot be applied to compute the optimal lower bound on floats of a task -this problem is known to be strongly NP-hard in a general acyclic network [START_REF] Chanas | The computational complexity of the criticality problems in a network with interval activity times[END_REF] and NP-hard in a planar acyclic network [START_REF] Chanas | On the hardness of evaluating criticality of activities in planar network with duration intervals[END_REF]. These results follow from the fact that the problem of deciding possible criticality of a given task is strongly NP-complete in a general acyclic network and remains NP-complete even in acyclic planar network of node degree 3 [START_REF] Chanas | The computational complexity of the criticality problems in a network with interval activity times[END_REF][START_REF] Chanas | On the hardness of evaluating criticality of activities in planar network with duration intervals[END_REF]. Moreover, if P =NP, then the problem of computing the minimal float value of a task is not at all approximable even in acyclic planar networks of node degree 3 [START_REF] Zieliński | On computing the latest starting times and floats of activities in a network with imprecise durations[END_REF].

It is worth pointing out that all considered interval problems have been completely solved when a network is series-parallel [START_REF] Dubois | On latest starting times and floats in activity networks with ill-known durations[END_REF][START_REF] Fargier | Fuzzy PERT in series-parallel graphs[END_REF][START_REF] Zieliński | Efficient Computation of Project Characteristics in a Series-Parallel Activity Network with Interval Durations[END_REF]. A graph is said to be series-parallel if it is recursively defined as follows [START_REF] Valdes | The recognition of series parallel digraphs[END_REF]. A graph consisting of two nodes joined by a single arc is series-parallel. If G 1 and G 2 are series-parallel, so are the graphs constructed by each of the operations: parallel composition -identify the source of G 1 with the source of G 2 and the sink of G 1 with the sink of G 2 ; series composition -identify the sink of G 1 with the source of G 2 . It results from this definition that each series-parallel graph is acyclic, planar and has exactly one source and exactly one sink. For example, the graph pictured in Figure 1b is series-parallel, but the graph shown in Figure 1c is not. Fargier et al. [START_REF] Fargier | Fuzzy PERT in series-parallel graphs[END_REF] proposed an O(n) algorithm for computing bounds on possible values of latest starting dates and bounds on possible values of floats of a task and O(n) algorithms for evaluating possible and necessary criticality of a task in a series-parallel network. Therefore, applying algorithms provided in [START_REF] Fargier | Fuzzy PERT in series-parallel graphs[END_REF] to each task in a network for computing bounds on floats and bounds on latest starting dates of all tasks leads to methods that require O(n 2 ) time (note that for series-parallel graphs m = O(n)). In [START_REF] Zieliński | Efficient Computation of Project Characteristics in a Series-Parallel Activity Network with Interval Durations[END_REF], the time for computing bounds on floats and bounds on latest starting dates and for evaluating the possible and necessary criticality for one task in a series-parallel network has been reduced to O(log n) by applying a more clever data structure. Therefore, computing bounds on floats and bounds on latest starting dates and evaluating the possible and necessary criticality of all tasks in a series-parallel network requires O(n log n) time.

In order to deal with the interval PERT problem in the general case, we introduce some additional notations.

-SU CC(i, j) (resp. P RED(i, j)) denotes the set of all arcs that come after (resp. before) (i, j) ∈ A, and SU CC(j) (resp. P RED(j)) stands for the set of all nodes that come after (resp. before) j ∈ V .

-P u,v is the set of paths p(u, v) in G from node u to node v. We denote by P the set of all paths in G from node 1 to node n.

-P 1,(k,l),n is the set of paths in G from node 1 to node n traversing task (k, l) and P (k,l),n represents the set of paths in G from node k to node n traversing task (k, l).

-l p (Ω) denotes the length of a path p

∈ P u,v in Ω, l p (Ω) = (i,j)∈p d ij (Ω).
-G(i, j) is the subgraph of G composed of nodes succeeding i and preceding j.

-

G(d ij = d) is the graph G in which duration of task (i, j) is replaced by d.

Path enumeration approach

In this section, we give two algorithms based on some properties in which paths have particular interest. The first one, proposed in [START_REF] Dubois | Computational methods for determining the latest starting times and floats of tasks in interval-valued activity networks[END_REF], computes maximal latest starting dates, minimal and maximal floats of each task of a network in one execution. We call it the path algorithm. The second algorithm only computes minimal latest starting dates in polynomial time. It is called the polynomial path algorithm.

Path algorithm

We first recall that maximal latest starting dates and minimal and maximal floats of tasks are attained on extreme configurations in which task duration times on a path from node 1 to node n are set to their maximal values and all the remaining task duration times are set to their minimal ones.

Proposition 1 ( [START_REF] Dubois | Computational methods for determining the latest starting times and floats of tasks in interval-valued activity networks[END_REF]). Let (k, l) ∈ A be a task of G. There exist paths p 1 , p 2 , p 3 ∈ P such that Ω + p1 maximizes lst kl (.), Ω + p2 minimizes f kl (.), Ω + p3 maximizes f kl (.) over the set C . The key to construct the path algorithm (Algorithm 1), proposed in [START_REF] Dubois | Computational methods for determining the latest starting times and floats of tasks in interval-valued activity networks[END_REF], is Proposition 1. The idea of the algorithm consists in performing the classical PERT analysis for each configuration Ω + p such that p is a path in network G from 1 to n. Clearly, the number of tested configurations is potentially exponential, but in practice the algorithm runs fast on realistic problems (see Section 6).

Polynomial path algorithm

We first recall a result given in [START_REF] Dubois | Computational methods for determining the latest starting times and floats of tasks in interval-valued activity networks[END_REF], that describes the form of configurations where the minimal latest starting date of a given task (k, l) in a network G is attained.

Proposition 2 ( [START_REF] Dubois | Computational methods for determining the latest starting times and floats of tasks in interval-valued activity networks[END_REF]). Let (k, l) ∈ A be a task of network G. There exists a path p kl ∈ P (k,l),n that induces the extreme configuration such that Ω + p kl = arg min Ω∈C lst kl (Ω) and lst - kl = lst kl (Ω + p kl ).

foreach task (k, l) ∈ A do if lst + kl < lst kl (Ω + p ) then lst + kl ← lst kl (Ω + p ); if f + kl < f kl (Ω + p ) then f + kl ← f kl (Ω + p ); if f - kl > f kl (Ω + p ) then f - kl ← f kl (Ω + p ); end
It is easily seen that optimal path p kl ∈ P (k,l),n , which induces configuration Ω + p kl , is a longest path from k to n traversing l in Ω + p kl . We will show that this path can be recursively constructed. Suppose that a path p lu ∈ P (l,u),n which induces configuration Ω + p lu such that Ω + p lu = arg min Ω∈C lst lu (Ω) is known for each node u ∈ Succ(l). Then one can construct an optimal path p kl among paths p lu , where u ∈ Succ(l). Proposition 3. Let (k, l) be a task of network G and let p lu ∈ P (l,u),n be a path such that lst - lu = lst lu (Ω + p lu ), where u ∈ Succ(l). Then lst - kl = min u∈Succ(l) lst kl (Ω + {(k,l)}∪p lu ).

Proof. From Proposition 2, it follows that there exists a path p kl ∈ P (k,l),n such that Ω + p kl = arg min Ω∈C lst kl (Ω). Assume on the contrary that lst - kl = lst kl (Ω + p kl ) < lst kl (Ω + {(k,l)}∪p lu ), ∀u ∈ Succ(l). Clearly, lst - kl = lst kl (Ω + p kl ) = max p∈P l p (Ω + p kl ) -l p kl (Ω + p kl ) and thus

lst lu (Ω + p kl ) = max p∈P l p (Ω + p kl ) -max p∈P (l,u),n l p (Ω + p kl ) = max p∈P l p (Ω + p kl ) -l p kl + d + kl = lst - kl + d + kl which forces lst - kl = lst lu (Ω + p kl ) -d + kl .
On the other hand, formula for lst lu (Ω + {(k,l)}∪p lu ) can be rewritten:

lst lu (Ω + {(k,l)}∪p lu ) = max p∈P l p (Ω + {(k,l)}∪p lu ) -l p lu (Ω + {(k,l)}∪p lu ) -d + kl .
From the assumption, we have:

lst - kl = lst lu (Ω + p kl ) -d + kl < lst kl (Ω + {(k,l)}∪p lu ) which yields lst lu (Ω + p kl ) < max p∈P l p (Ω + {(k,l)}∪p lu ) -l p lu (Ω + {(k,l)}∪p lu ). Let p ′ ∈ P be a longest path in G in the config- uration Ω + {(k,l)}∪p lu . We consider two cases. (i) if (k, l) / ∈ p ′ then max p∈P l p (Ω + {(k,l)}∪p lu ) = max p∈P l p (Ω + p lu ) and so lst lu (Ω + p lu ) < lst - lu , which contradicts the definition of lst - lu . (ii) if (k, l) ∈ p ′ then (k, l) is critical in Ω + {(k,l)}∪p lu and consequently lst kl (Ω + {(k,l)}∪p lu ) = est - kl and lst kl (Ω + {(k,l)}∪p lu ) = lst - kl , which contradicts the fact that lst kl (Ω + p kl ) < lst k l(Ω + {(k,l)}∪p lu ). There- fore, lst - kl = lst kl (Ω + p kl ) ≥ lst kl (Ω + {(k,l)}∪p lu ).
From Proposition 3, we deduce a polynomial algorithm for computing the minimal starting date of each task. Namely, the algorithm recursively finds a path p kl for which configuration Ω + p kl minimizes lst kl (Ω) making use of paths p lu such that lst - lu = lst lu (Ω + p lu ), where u ∈ Succ(l), starting from nodes in P red(n). Its overall running time is O(m 2 (m + n)). Fortunately, it is possible to reduce the complexity of the algorithm to O(m 2 ). It is enough to store the length of a longest path p * ∈ P in optimal configuration Ω + p lu for (l, u), denoted by l * lu , and the length of path p lu in Ω + p lu denoted by l lu , for every u ∈ Succ(l). Obviously, lst - lu = l * lu -l lu . Let (l, v) be a task such that lst - kl = lst kl (Ω + {(k,l)}∪p lv ) (such task always exists, see Proposition 3). The length l kl of path p kl in optimal configuration Ω + {(k,l)}∪p lv for (k, l) equals d + kl + l lv . Let p * ∈ P be a longest path in Ω + {(k,l)}∪p lv . We consider two cases: (i) if (k, l) ∈ p * then the length l * kl of

p * equals est - kl + d + kl + l lv (note that est - kl = est kl (Ω - A ) = est kl (Ω + {(k,l)}∪p lv )). Hence lst - kl = est - kl . (ii) if (k, l) / ∈ p * then l * kl =
G in Ω - A ; lst - nn+1 ← estnn+1(Ω - A ); l * nn+1 ← estnn+1(Ω - A ); lnn+1 ← 0; foreach (k, l) such that k ← n -1 downto 1 do Let (l, v) be a task such that v ∈ Succ(l); l kl ← d + kl + l lv ; if est kl (Ω - A ) + l kl > l * lv then l * kl ← est kl (Ω - A ) + l kl ; lst - kl ← est kl (Ω - A ); else l * kl ← l * lv ; lst - kl ← l * kl -l kl ; foreach (l, u) such that u ∈ Succ(l) \ {v} do if est kl (Ω - A ) + d + kl + l lu > l * lu then l * kl ← est kl (Ω - A ) + d + kl + l lu ; l kl ← d + kl + l lu ; lst - kl ← est kl (Ω - A ); else if l * lu -d + kl -l lu < lst - kl then l * kl ← l * lu ; l kl ← d + kl + l lu ; lst - kl ← l * kl -l kl ; end 4 Constructive approach
Zieliński [START_REF] Zieliński | On computing the latest starting times and floats of activities in a network with imprecise durations[END_REF] gave polynomial algorithms for computing optimal upper and lower bounds on latest starting times. We do the same for the optimal upper bound of floats. The basic structure is the same for the three algorithms. The first step instantiates the duration times of some tasks in a network without changing the result of the quantity of concern for a distinguished task. The next step instantiates the duration times of the remaining tasks in the network, while preserving the global possible or necessary criticality of the task. Once duration times of all tasks are precisely set, we need to compute the minimal duration ∆ that, added to the duration time of the distinguished task, makes it possibly or necessarily critical in this particular configuration. Duration ∆ will easily provide the concerned quantity.

Evaluating criticality

This section presents methods which can decide in polynomial time if a given task (k, l) is necessarily or possibly critical. First, under the assumption that the duration times of the predecessors of task (k, l) are precisely known, we recall algorithms, proposed in [START_REF] Zieliński | On computing the latest starting times and floats of activities in a network with imprecise durations[END_REF], that decide if (k, l) is necessarily or possibly critical. They constitute the basis for computing minimal and the maximal latest starting dates in polynomial time in [START_REF] Zieliński | On computing the latest starting times and floats of activities in a network with imprecise durations[END_REF]. We extend some of these results and give a general algorithm that asserts if (k, l) is necessarily critical in a network G in polynomial time without any consideration of the duration times of tasks preceding (k, l). This result will lead in Section 4.3 to a polynomial algorithm which computes the maximal float of a task. Let us recall characteristic conditions of the non-necessary criticality of tasks.

Lemma 1 ([11]

). A task (k, l) ∈ A is not necessarily critical in G if and only if there exists a path p ∈ P such that (k, l) ∈ p, p is critical in configuration Ω + p and no critical path in Ω + p includes (k, l).

Observation 1 ([47]

). A task (k, l) ∈ A is not necessarily critical in G if and only if (k, l) is not critical in an extreme configuration in which the duration of (k, l) is at its lower bound and all tasks from set A \ (SU CC(k, l) ∪ P RED(k, l) ∪ {(k, l)}) have duration times set to their upper bounds.

Now under the assumption that tasks preceding (k, l) have precise duration times, we can set the ones of tasks succeeding (k, l) at precise values while maintaining the status of (k, l) in terms of necessary criticality. It yields a configuration where (k, l) is critical if and only if it is necessarily critical in the interval-valued network. These duration times are given by Propositions 4 and 5.

Proposition 4. Let (k, l) ∈ A be a distinguished task, and (i, j) be a task such that (i, j) ∈ SU CC(k, l). Assume that every task (u, v) ∈ P RED(i, j) has precise duration. If (k, l) is critical in G(1, i), then the following conditions are equivalent:

(i) (k, l) is necessarily critical in G, (ii) (k, l) is necessarily critical in G(d ij = d - ij ).
Proof. (i) =⇒ (ii) Obvious.

(i) ⇐= (ii) We use a proof by contraposition. We need to prove that if

(k, l) is critical in G(1, i) and (k, l) is not necessarily critical in G, then (k, l) is not necessarily critical in G(d ij = d - ij ).
By assumption, (k, l) is not necessarily critical in G. From Lemma 1, it follows that there exists a path p ∈ P such that (k, l) ∈ p, p is critical in configuration Ω + p and no critical path in Ω + p includes (k, l).

Since (k, l) is critical in G(1, i), (i, j) ∈ p in Ω + p . Observe that d ij (Ω + p ) = d - ij .
From this and the fact that (k, l) is not critical in Ω + p , we conclude that (k, l) is not necessarily critical in

G(d ij = d - ij ).
Proposition 5. Let (k, l) ∈ A be a distinguished task, and (i, j) be a task such that (i, j) ∈ SU CC(k, l). Assume that every task (u, v) ∈ P RED(i, j) has precise duration. If (k, l) is not critical in G(1, i), then the following conditions are equivalent:

(i) (k, l) is necessarily critical in G, (ii) (k, l) is necessarily critical in G(d ij = d + ij ).
Proof. A proof follows the definition of necessary criticality.

Propositions 4 and 5, together with Observation 1, lead us to Algorithm 3 for asserting the necessary criticality of a given task (k, l) in a network in which all tasks that precede (k, l) have precise durations. The algorithm works as follows: first all duration times of tasks neither succeeding nor preceding (k, l) are set to their upper bounds and the earliest starting times of events not succeeding event l are computed by the classical PERT. Then the algorithm tests if (k, l) is critical in the subnetwork G(1, l). We denote by f kl (u, v) the float of (k, l) computed in the network G(u, v). Precise duration times are fixed for tasks immediately succeeding node l. This step is repeated recursively for network G(1, l + 1), . . . , G(1, n -1). At the end of this process, all duration times are precisely set, and (k, l) is necessarily critical in the network with the interval durations if and only if (k, l) is critical in the network with the fixed durations. Computing f kl (1, i) and testing if (k, l) is critical in G(1, i) can be done in constant time, since we already know est j for all j ∈ P red(i), and so Algorithm 3 runs in O(m).

Lemma 1, Propositions 4, 5 and Observation 1 have counterparts for asserting possible criticality. It suffices to swap duration times d - uv and d + uv . This leads to an O(m) algorithm (see Algorithm 3: Asserting whether a task is necessarily critical when duration times of predecessors are precisely known

Input: A network G, task (k, l), interval duration times Duv, (u, v) ∈ A and for every task in P RED(k, l) the duration is precisely given.

Output: If f kl (1, n) = 0, (k, l) is necessarily critical in G; and if f kl (1, n) > 0, (k, l) is not necessarily critical in G. /* Initialization */ foreach (u, v) ∈ A \ (SU CC(k, l) ∪ P RED(k, l) ∪ {(k, l)}) do duv ← d + uv ; d kl ← d -
kl ; /* the partially instantiated configuration */ /* Computation */ Compute esti of events i ∈ V \ (SU CC(l) ∪ {l}) by the classical PERT in the partial configuration;

for i ← l to n -1 such that i ∈ SU CC(l) ∪ {l} do Compute f kl (1, i); if f kl (1, i) = 0 /* (k, l) critical in G(1, i)*/ then foreach j ∈ Succ(i) do dij ← d - ij else foreach j ∈ Succ(i) do dij ← d + ij Compute f kl (1, n); return f kl (1, n);
Algorithm 4: Asserting whether a task is possibly critical when duration times of its predecessors are precisely known

Input: A network G, task (k, l), interval duration times Duv, (u, v) ∈ A and for every task in P RED(k, l) the duration is precisely given.

Output: If f kl (1, n) = 0, (k, l) is possibly critical in G; and if f kl (1, n) > 0, (k, l) is not possibly critical in G. /* Initialization */ foreach (u, v) ∈ A \ (SU CC(k, l) ∪ P RED(k, l) ∪ {(k, l)}) do duv ← d - uv ; d kl ← d +
kl ; /* the partially instantiated configuration */ /* Computation */ Compute esti of events i ∈ V \ (SU CC(l) ∪ {l}) by the classical PERT in the partial configuration; ′ (tasks with the maximal duration times are in bold) Algorithm 4) for asserting the possible criticality of tasks whose predecessors have deterministic durations [START_REF] Zieliński | On computing the latest starting times and floats of activities in a network with imprecise durations[END_REF].

for i ← l to n -1 such that i ∈ SU CC(l) ∪ {l} do Compute f kl (1, i); if f kl (1, i) = 0 /* (k, l) is critical in G(1, i) */ then foreach j ∈ Succ(i) do dij ← d + ij else foreach j ∈ Succ(i) do dij ← d - ij Compute f kl (1, n); return f kl (1, n) (a) (b) p p p p r r 1 1 n n i i j j p * k k l l r r p ′ p * (r, k)
We now present an algorithm for evaluating the necessary criticality of a fixed task (k, l) ∈ A in network G with interval duration times, without any restriction. The key to the algorithm lies in Propositions 6 and 7 that enable a network with interval duration times to be replaced by another network with precise durations for tasks preceding a fixed (k, l), in such a way that (k, l) is necessarily critical in the former if and only if it is necessarily critical in the latter. Proposition 6. Let (k, l) ∈ A be a distinguished task, and (i, j) be a task such that (i, j) ∈ P RED(k, l). If (k, l) is necessarily critical in G(j, n), then the following conditions are equivalent:

(i) (k, l) is necessarily critical in G, (ii) (k, l) is necessarily critical in G(d ij = d - ij ).
Proof. The proof goes in the similar manner to the one of Proposition 4.

Proposition 7. Let (k, l) ∈ A be a distinguished task, and (i, j) be a task such that (i, j) ∈ P RED(k, l). If (k, l) is not necessarily critical in G(j, n), then the following conditions are equivalent:

(i) (k, l) is necessarily critical in G, (ii) (k, l) is necessarily critical in G(d ij = d + ij ). Proof. (i) =⇒ (ii) Straightforward. (i) ⇐= (ii) We need to show that if (k, l) is not necessarily critical in G(j, n) and (k, l) is necessarily critical in G(d ij = d + ij ), then (k, l) is necessarily critical in G.
To prove this, assume on the contrary that (k, l) is not necessarily critical in G and (k, l) is necessarily critical in G(d ij = d + ij ). From Lemma 1, it follows that there exists a path p ∈ P such that (k, l) ∈ p, p is critical in configuration Ω + p and no critical path in Ω + p includes (k, l) or equivalently (k, l) is not critical in Ω + p . We will show that for each such configuration, where (k, l) is not critical, the other assumptions lead to construct a critical path that traverses (k, l), which results in a contradiction. By assumption, (k, l) is not necessarily critical in G(j, n). Then there exists a path p ∈ P (j, n) such that (k, l) ∈ p, p is critical in configuration Ω + p and no critical path of G(j, n) traverses (k, l) in Ω + p (see Lemma 1). Consider the extreme configuration induced by p ∪ p ∪ {(i, j)} and denote it by

Ω * (Ω * = Ω + p∪ p∪{(i,j)} ). Note that (k, l) is critical in Ω * , because (k, l) is necessarily critical in G(d ij = d + ij )
. Thus there exists a critical path p * ∈ P using (k, l) in Ω * . We define r to be the last common node of p * (1, k) and p (r = max{v | v ∈ V, v ∈ p * (1, k), v ∈ p}) and define r to be the last common node of p * (1, k) and p (r = max{v

| v ∈ V, v ∈ p * (1, k), v ∈ p}).
We claim that if node r exists, then r = r or node r lies on p * before node r. Suppose, contrary to our claim, that r lies on p * after r (see Figure 2a). Then subpath p * (r, n), p * (r, n) = p * (r, k) ∪ p * (k, n), is at least as long as subpath p(r, n) in configuration Ω * . Notice that p * (r, k) is one of the longest paths from r to k in Ω * . We may now decrease some task duration times to their lower bounds in configuration Ω * in the following way (see Figure 2b): for every (u, v) ∈ A,

d uv (Ω ′ ) = d + uv if (u, v) ∈ p or (u, v) = (i, j); d - uv otherwise. Duration d ij (Ω ′ ) = d + ij ,
(Ω * ) = l p * (r,k) (Ω ′ ). Therefore path p * (r, k) ∪ p ′ (k, n) is at least as long as subpath p(r, n) in configuration Ω ′ . Decreasing d ij (Ω ′ )
to its lower bound gives configuration Ω + p . Observe that the lengths of paths p * (r, k) ∪ p ′ (k, n) and p(r, n) remain unchanged. Hence, there exists a path in G(j, n) composed of two subpaths p(j, r) and p * (r, k) ∪ p ′ (k, n) that is at least as long as p, which is impossible because we have assumed that no critical path goes through (k, l) in G(j, n) in configuration Ω + p . We can now return to the main proof. Consider configuration Ω * . The previous claim shows that if node r exists, then r = r or node r lies on p * before node r (see Figure 3a). In the case that r does not exist, the proof proceeds in the same manner. From the above and the criticality of p * in Ω * , it follows that subpath p * (r, n) = p * (r, k) ∪ p * (k, n), is at least as long as subpath p(r, n) in this configuration. Notice that p * (r, k) is one of longest paths from r to k in Ω * . Decreasing some of duration times in Ω * to their lower bounds, we obtain configuration Ω ′′ in the following form (see Figure 3b): for every is at least as long as p and moreover p(1, r) ∪ p * (r, k) ∪ p ′′ (k, n) uses (k, l). This contradicts our assumption that no critical path in Ω + p includes (k, l).

(u, v) ∈ A, d uv (Ω ′′ ) = d + uv if (u, v) ∈ p or (u, v) = (i, j); d uv (Ω ′′ ) = d - uv otherwise. Duration d ij (Ω ′′ ) = d + ij , by assumption, (k, l) is necessarily critical in G(d ij = d + ij ),
We are now in a position to give an algorithm (Algorithm 5) for asserting the necessary criticality of a prescribed task in a general acyclic network. At each step of the algorithm, tasks between j and k have precise duration times (so Algorithm 3 can be invoked), and Algorithm 5 assigns precise duration times to tasks preceding j, while preserving the criticality of task (k, l). Since Algorithm 3 runs in O(m), Algorithm 5 requires O(mn) time.

Unfortunately, Propositions 6 and 7 can not be adapted to the study of possible criticality, and asserting if a task is possibly critical, in general, is strongly NP-complete [START_REF] Chanas | The computational complexity of the criticality problems in a network with interval activity times[END_REF]. So, while these results are instrumental for computing maximal floats, the same approach cannot be applied to compute minimal floats.

Computing tightest bounds on latest starting dates

Let us present a polynomial algorithm, proposed in [START_REF] Zieliński | On computing the latest starting times and floats of activities in a network with imprecise durations[END_REF], that computes maximal latest starting dates. Let us recall the following simple but important result that allows us to reduce the set of configurations C .

Proposition 8 ([12]). The minimal upper bound on latest starting dates lst +

kl of task (k, l) in G is attained on an extreme configuration in which the duration of (k, l) is at its lower bound and all tasks that do not belong to set SU CC(k, l) have duration times at their upper bounds.

Algorithm 5: Asserting necessary criticality of task (k, l)

Input: A network G =< V, A >, activity (k, l), interval duration times Duv, (u, v) ∈ A. Output: If f kl (1, n) = 0, (k, l) is necessarily critical in G; and if f kl (1, n) > 0, (k, l) is not necessarily critical in G. /* Initialization */ foreach (u, v) ∈ A \ (SU CC(k, l) ∪ P RED(k, l) ∪ {(k, l)}) do duv ← d + uv ; d kl ← d - kl ; /* Computation */ for j ← k downto 2 such that j ∈ P RED(k) ∪ {k} do f kl (j, n) ← Algorithm 3 with G(j, n) and without the initialization phase; if f kl (j, n) = 0 then foreach i ∈ P red(j) do dij ← d - ij else foreach i ∈ P red(j) do dij ← d + ij f kl (j, n) ← Algorithm 3 with G(1, n
) and without the initialization phase; return f kl (j, n);

The main idea of the algorithm for determining lst + kl of a given task (k, l) ∈ A is based on Lemma 2. It consists in determining the minimal nonnegative real number f * kl that, added to the lower bound of the duration interval of a specified task (k, l), makes it necessarily critical.

Lemma 2 ([47]

). Let f * kl be the least nonnegative real number such that (k, l) is necessarily critical with a duration d - kl + f * kl . Then lst + kl = est + kl + f * kl . Thus, Proposition 8 and Lemma 2 suggest an algorithm for determining maximal latest starting dates (Algorithm 6). The algorithm proceeds as follows. First the duration times of tasks not succeeding (k, l) are set to their maximal values, and the duration of (k, l) is set to d - kl (see Proposition 8). From this point on, it computes maximal earliest starting dates of (k, l). Then it tests if (k, l) is necessarily critical in the partially instantiated configuration by calling Algorithm 3. During this call, the algorithm retains all values f kl (1, i) determined by Algorithm 3. If (k, l) is not necessarily critical, the smallest f kl (1, i), previously computed, is the least duration δ to be added to d kl . Then, the algorithm adds this δ to d kl and repeats the previous steps. Since Algorithm 6 makes at most n calls to Algorithm 3, its complexity is O(nm). There exist counterparts to Proposition 8, Lemma 2 and Algorithm 6 for minimal latest starting dates. They are exactly symmetrical. Hence, the sketch of the algorithm for computing minimal latest starting dates (Algorithm 7), proposed in [START_REF] Zieliński | On computing the latest starting times and floats of activities in a network with imprecise durations[END_REF], is the same as Algorithm 6 and it also runs in O(nm) time.

Algorithm 6: Computation of maximal latest starting dates of a given task

Input: A network G, task (k, l), interval duration times Duv, (u, v) ∈ A. Output: The maximal latest starting date lst + kl . /* Initialization */ foreach (u, v) ∈ A \ (SU CC(k, l) ∪ {(k, l)}) do duv ← d + uv ; d kl ← d - kl ; Compute est + kl by the classical PERT; ∆ ← 0; /* Computation */ f kl (1, n) ← Algorithm 3 without the initialization; /* we can retain all the values f kl (1, i) computed by Algorithm 3 */ while f kl (1, n) > 0 do δ ← min i∈SU CC(l) {f kl (1, i)|f kl (1, i) = 0}; ∆ ← ∆ + δ; d kl ← d - kl + ∆; f kl (1, n) ← Algorithm
Algorithm 7: Computation of the minimal latest starting date of a given task

Input: A network G, activity (k, l), interval duration times Duv, (u, v) ∈ A. Output: Minimal latest starting date lst - kl . /* Initialization */ foreach (u, v) ∈ A \ (SU CC(k, l) ∪ {(k, l)}) do duv ← d - uv ; d kl ← d + kl ; Compute est - kl by the classical PERT; ∆ ← 0; /* Computation */ f kl (1, n) ← Algorithm 4; /* we can retain all the values f kl (1, i) computed by Algorithm 4 */ while f kl (1, n) > 0 do δ ← min i∈SU CC(l) {f kl (1, i)|f kl (1, i) = 0}; ∆ ← ∆ + δ; d kl ← d + kl + ∆; f kl (1, n) ←

Computing maximal floats

In order to compute the maximal float of task (k, l) ∈ A, we first set the duration times of the tasks neither preceding nor succeeding (k, l) according to the following Lemma 3. The maximal float of (k, l) after this partial instantiation is the same as in the original network G.

Lemma 3 ([12]

). The maximal float f + kl of task (k, l) in G is attained on an extreme configuration in which the duration of (k, l) is at its lower bound and all tasks from set A \ (SU CC(k, l) ∪ P RED(k, l) ∪ {(k, l)}) have duration times at their upper bounds.

Then we increase step by step the duration of (k, l) from d kl = d - kl until (k, l) becomes necessarily critical. Testing can be done in O(mn) time (see Algorithm 5). Lemmas 4 and 6 give the hint to find the increment of d kl at each step of the algorithm. According to Proposition 9, this incremental technique eventually yields f + kl . Lemma 4. Let tasks (i, j) ∈ P RED(k, l) have precise durations in G. Then (k, l) is necessarily critical in G if and only if there exists a path p ∈ P (1, k) such that for every node j ∈ p, (k, l) is necessarily critical in G(j, n).

Proof. (=⇒) Let us denote by p a longest path from 1 to k. Note that tasks (i, j) ∈ P RED(k, l) have precise durations. From the necessary criticality of (k, l) in G, it follows that path p is part of a longest path from 1 to n and this path uses (k, l) for each configuration. Thus for every node j ∈ p, the subpath p(j, n) is critical path in G(j, n). Since this holds true for each configuration, (k, l) is necessarily critical in G(j, n).

(⇐=) Just take j = 1. G(1, n) = G and so (k, l) is necessarily critical in G.
There is a link between the maximal latest starting date lst + kl and the maximal float value f + kl of task (k, l) under the assumption that tasks (i, j) ∈ P RED(k, l) have precise duration times.

Lemma 5 ([47]

). Let tasks (i, j) ∈ P RED(k, l) have precise durations in G. Then

f + kl = lst + kl - est + kl .
Thus, the maximal float value f + kl can be computed by means of the algorithms for determining lst + kl presented previously.

Lemma 6. Let ∆ = min j {f + kl (j, n) | (k, l) is not necessarily critical in G(j, n)} where f + kl (j, n) is the maximal float of (k, l) in G(j, n), j ∈ P RED(k). Then for all ǫ < ∆, task (k, l) is not necessarily critical in G(j, n), j ∈ P RED(k), with duration d kl = d - kl + ǫ. Moreover there exists j * ∈ P RED(k) such that (k, l) is not necessarily critical in G(j * , n) with duration d kl = d - kl , and (k, l) becomes necessarily critical in G(j * , n) with duration d kl = d - kl + ∆. Proof. Consider a node j such that (k, l) is not necessarily critical in G(j, n). By Observation 1, one can assume that task (k, l) has duration time of the form d kl = d - kl . Let Ω be an extreme configuration where the float of (k, l) attains its maximal value f + kl (j, n) > 0 in G(j, n), and

ǫ < ∆ ≤ f + kl (j, n) (d kl (Ω) = d - kl ). p ′ denotes a longest path in G(j, n) in Ω, while p ′′ stands for a longest path in G(j, n) in Ω using (k, l). Therefore, f + kl (j, n) = l p ′ (Ω) -l p ′′ (Ω) > ǫ. Let us define the configuration Ω ′ such that d uv (Ω ′ ) = d - kl + ǫ if (u, v) = (k, l); d uv (Ω ′ ) = d uv (Ω) otherwise.
Path p ′ remains a longest path in Ω ′ with same length, and p ′′ is still a longest path traversing (k, l) with length

l p ′′ (Ω ′ ) = l p ′′ (Ω) + ǫ. Since the float of (k, l) in Ω ′ is l p ′ (Ω ′ ) -l p ′′ (Ω ′ ) > 0, (k, l) is not necessarily critical in G(j, n), j ∈ P RED(k), with duration d kl = d - kl + ǫ.
Consider a node j * such that (k, l) is not necessarily critical in G(j * , n), and set ∆ = f + kl (j * , n). Then for all configurations, the difference between a longest path in G(j * , n) and a longest path using (k, l) is less or equal than ∆. If we increase the duration of (k, l) to d - kl + ∆, a longest path, in this new configuration, will traverse (k, l) and thus (k, l) will be necessarily critical in G(j * , n) with duration

d kl = d - kl + ∆. Proposition 9. Let f * kl be the least nonnegative real number such that (k, l) is necessarily critical in G(d kl = d - kl + f * kl ). Then f + kl = f * kl .
Proof. Consider any configuration Ω. Let p ′ be a longest path in Ω and p ′′ be a longest path including (k, l) in Ω. Note that f kl (Ω) = l p ′ (Ω) -l p ′′ (Ω). Let us now modify configuration Ω and denote it by Ω x . Configuration Ω x is defined as follows: for every (u, v) ∈ A d uv (Ω x ) = d uv (Ω) + x if (u, v) = (k, l); d uv (Ω x ) = d uv (Ω) otherwise, where x is a nonnegative real number. It is clear that l p ′′ (Ω x ) = l p ′′ (Ω) + x and p ′′ remains a longest path including (k, l) in new configuration Ω x .

Consider the following two cases: (x < f kl (Ω)). Then l p ′′ (Ω x ) ≤ l p ′ (Ω), and so p ′ is still a critical path in Ω x and has the same length as in Ω. This gives f kl (Ω x ) = f kl (Ω) -x. (x ≥ f kl (Ω)). Then p ′′ becomes a critical path and so f kl (Ω x ) = 0. Thus, for all Ω and x, equation f kl (Ω x ) = max(f kl (Ω) -x, 0) holds. In particular, for x = f * kl and configuration Ω = Ω * such that Ω * maximizes the float of task (k, l) in G. From the definition of f * kl we get f kl (Ω f * kl ) = 0, hence f kl (Ω * ) -f * kl ≤ 0, and finally f + kl ≤ f * kl . Suppose that f + kl < f * kl . Set y = (f * kl +f + kl )/2. Then, for every Ω, f kl (Ω y ) = max(f kl (Ω)-y, 0) = 0. Note that y is a nonnegative real number, smaller than f * kl , such that (k, l) is necessarily critical in G(d kl = d - kl + y), which contradicts the definition of f * kl . Hence, we conclude that f + kl = f * kl . From the above results, it follows an algorithm that computes the maximal float of task (k, l) in polynomial time (Algorithm 8). The algorithm first tests the necessary criticality of (k, l) in G by calling Algorithm 5. If so, then its float is null. Otherwise, it determines the minimal duration δ that must be added to the duration of (k, l) to change the instantiation made by Algorithm 5 for at least one task preceding (k, l). Moreover, the instantiation made by Algorithm 5 will change if and only if (k, l) becomes necessarily critical for at least one new subnetwork G(i, n). This δ is the least positive value of the maximal float of (k, l) in networks G(i, n), where i ∈ P RED(k). Since the duration times of predecessors were previously fixed, these values of the maxima of floats are differences between the maxima of latest starting dates and the minima of earliest starting dates (see Lemma 5). Algorithm 8 executes at most n times the while loop. At each iteration of while loop, (k, l) becomes necessarily critical in at least one new subnetwork G(j, n). Thus the loop is executed at most n times, and thus Algorithm 8 requires O(n 3 m) time.

Illustrative example

In order to illustrate the presented algorithms, let us consider the execution of the algorithms on the project network given in Figure 4. We wish to compute the maximal float of task [START_REF] Averbakh | Interval data minmax regret network optimization problems[END_REF][START_REF] Buckley | Fuzzy PERT[END_REF] by means of Algorithm 8. In this section, Ω par represents a partial configuration, that is, the precise duration times of instantiated tasks and the interval duration times of the non-instantiated tasks. In our example, the knowledge about duration times is represented by the partial configuration Ω par (initially the duration times are ill-known):

D 12 = [1, 2], D 23 = [0, 3], D 34 = [1, 3], D 24 = [0, 2], D 14 = [0, 1].
We now analyze a complete execution of Algorithm 8 in order to compute the maximal float of task [START_REF] Averbakh | Interval data minmax regret network optimization problems[END_REF][START_REF] Buckley | Fuzzy PERT[END_REF].

Algorithm 8 After initializing ∆ to 0, Algorithm 8 calls Algorithm 5.

Algorithm 5

The initialization of Algorithm 5 assigns precise duration times to tasks (2, 3), [START_REF] Averbakh | Interval data minmax regret network optimization problems[END_REF][START_REF] Chanas | On the sure criticality of tasks in activity networks with imprecise durations[END_REF] and [START_REF] Adlakha | A classified bibliography of research on stochastic PERT networks: 1966-1987[END_REF][START_REF] Chanas | On the sure criticality of tasks in activity networks with imprecise durations[END_REF] obtaining the partial configuration Ω par :

D 12 = [1, 2], D 23 = 0, D 34 = [1, 3], D 24 = 2, D 14 = 1.
Then the for loop is executed. At the first iteration, Algorithm 3 is called for the subnetwork G(2, 4) without the initialization. It means that Algorithm 3 only considers the network composed of tasks: (2, 3) with duration 0, [START_REF] Buckley | Fuzzy PERT[END_REF][START_REF] Chanas | On the sure criticality of tasks in activity networks with imprecise durations[END_REF] with duration [START_REF] Adlakha | A classified bibliography of research on stochastic PERT networks: 1966-1987[END_REF][START_REF] Buckley | Fuzzy PERT[END_REF] and task [START_REF] Averbakh | Interval data minmax regret network optimization problems[END_REF][START_REF] Chanas | On the sure criticality of tasks in activity networks with imprecise durations[END_REF] with duration 2 (see the next network). Algorithm 3 The classical PERT is first performed for determining the earliest starting time of event 2, which is equal to null. Then the for loop of Algorithm 3 is executed and the float of (2, 3) is computed in the network constituted only by this task [START_REF] Averbakh | Interval data minmax regret network optimization problems[END_REF][START_REF] Buckley | Fuzzy PERT[END_REF]. Its float is obviously null and then Algorithm 3 assigns the minimal duration to task [START_REF] Buckley | Fuzzy PERT[END_REF][START_REF] Chanas | On the sure criticality of tasks in activity networks with imprecise durations[END_REF]. The partial configuration Ω par is then

D 12 = [1, 2], D 23 = 0, D 34 = 1, D 24 = 2, D 14 = 1.
At the second iteration of the for loop of Algorithm 3, the float of (2, 3) is computed in the subnetwork G(2, 4) with durations: D 23 = 0, D 34 = 1, D 24 = 2. The float is 1 in this subnetwork. Thus, Algorithm 3 returns 1 to Algorithm 5.

Task [START_REF] Averbakh | Interval data minmax regret network optimization problems[END_REF][START_REF] Chanas | On the sure criticality of tasks in activity networks with imprecise durations[END_REF] is not critical in G(2, 4), in consequence Algorithm 5 sets the duration times of the tasks preceding node 2 to their upper bounds. This leads to the partial configuration Ω par : D 12 = 2, D 23 = 0, D 34 = [1, 3], D 24 = 2, D 14 = 1. The for loop terminates. Before the end of Algorithm 5, Algorithm 3 is invoked for G [START_REF] Adlakha | A classified bibliography of research on stochastic PERT networks: 1966-1987[END_REF][START_REF] Chanas | On the sure criticality of tasks in activity networks with imprecise durations[END_REF]. This call is the same as an execution of the for loop with j = 1.

Algorithm 3

The classical PERT is first called for determining the earliest starting times of events 1 and 2, which are equal to 0 and 2, respectively. Then the for loop of Algorithm 3 is executed and the float of task [START_REF] Averbakh | Interval data minmax regret network optimization problems[END_REF][START_REF] Buckley | Fuzzy PERT[END_REF] is computed in G(1, 3) (the network is constituted by only tasks (1, 2) and (2, 3)). Its float is obviously null and then Algorithm 3 assigns the minimal duration to task [START_REF] Buckley | Fuzzy PERT[END_REF][START_REF] Chanas | On the sure criticality of tasks in activity networks with imprecise durations[END_REF]. The partial configuration Ω par is then D 12 = 2, D 23 = 0, D 34 = 1, D 24 = 2, D 14 = 1. At the second iteration of the for loop of Algorithm 3, the float of (2, 3) is computed in the subnetwork G(1, 4) with the partial configuration. The float of (2, 3) is 1 in this subnetwork and Algorithm 3 returns 1 to Algorithm 5. (2, 3) is not necessarily critical in G so Algorithm 8 runs the while loop. In this loop, maximal latest starting dates are computed in all subnetworks G(i, 4), i ∈ P RED(2) (for loop). Algorithm 6 is first called in G(2, 4).

Algorithm 6 lst +

23 is determined in G(2, 4) as follows : the duration times of tasks not succeeding (2, 3) are set to their upper bounds and duration of (2, 3) is set to its lower bound. Thus, the partial configuration Ω par is D 23 = 0, D 34 = [1, 3], D 24 = 2 (see the network below). In the considered network, the maximal earliest starting date of (2, 3) is 0. Then, Algorithm 6 calls Algorithm 3 without the initialization.

Algorithm 3 f 23 is null in G(2, 3), since there is only task [START_REF] Averbakh | Interval data minmax regret network optimization problems[END_REF][START_REF] Buckley | Fuzzy PERT[END_REF] in the network (this float is retained by Algorithm 6). Then the duration of task [START_REF] Buckley | Fuzzy PERT[END_REF][START_REF] Chanas | On the sure criticality of tasks in activity networks with imprecise durations[END_REF] Table 1: The intervals of values of earliest and latest starting times and of floats and criticality evaluations for all tasks of the network given in Figure 4 task (i, j) ESTij LSTij Fij possibly critical. necessarily critical

(1, 2) [0, 0] [0, 0] [0, 0] yes yes (1, 4) [0, 0] [1, 8] [1, 8] no no (2, 3) [1, 2] [1, 3] [0, 1] yes no (2, 4) [1, 2] [1, 8] [0, 6] yes no (3, 4) [1, 5] [1, 6] [0, 1] yes no
The minimal float computed by the previous algorithm is ∆ = 1, and thus the duration of (2, 3) is increased by 1. Then Algorithm 3 is called one more time in G(2, 4), with duration times Ω par : D 23 = 1, D 34 = [1, 3], D 24 = 2 (see the network below). (2, 3) is necessarily critical in G(2, 4), for a duration of (2, 4) of d 23 = d - 23 + 1, so the latest starting date of (2, 3) is 1 in G(2, 4).

In the configuration constructed by the previous Algorithm 6, the earliest starting date of (2, 3) is null. Thus, the value f * kl is equal to 1, and δ is set to 1. In the second iteration of the for loop, Algorithm 8 calls Algorithm 6 in G(1, 4) to compute the upper bound on the latest starting dates of (2, 3) when its duration is d 23 = 0. Algorithm 6 After the initialization, the partial configuration Ω par is D 12 = 2, D 23 = 0, D 34 = [1, 3], D 24 = 2, D 14 = 1. The Algorithm is executed as previously and returns 3 for the latest starting date of (2, 3) in G(1, 4).

In the constructed configuration, the earliest starting date of (2, 3) is 2, f * kl = 1 and δ still equals 1. Now Algorithm 8 sets the duration of (2, 3) to d - 23 + δ. Algorithm 5 is called with the possible durations Ω par :

D 12 = [1, 2], D 23 = 1, D 34 = [1, 3], D 24 = [0, 2], D 14 = [0, 1].
Algorithm 5 The algorithm works as previously. This time task (2, 3) is necessarily critical and Algorithm 5 returns 0. Task (2, 3) is necessarily critical in the constructed network, so the while loop terminates. Algorithm 8 returns 1. This value is the total duration added to the lower bound of (2, 3) to make it necessarily critical. Therefore, the maximal float of (2, 3) is 1. Task (2, 3) is not necessarily critical. Table 1 reports all the computational results on the intervals of possible values of earliest and latest starting times and floats and on criticality evaluations for all tasks of the project network given in Figure 4.

Complexity and experimental results

Table 2 summarizes the complexity of the different problems of the PERT on intervals. Moreover, Table 2 gives the running times of the best known algorithms that compute the quantities of interest. In particular, the path algorithm that computes minimal and maximal floats and maximal latest starting dates requires O((n + m)|P |) time, where |P | is the number of paths of a network. This running time depends on the topology of a network. Note that, some algorithms need only one execution to compute a quantity (for example, minimal starting dates) for all tasks of a network. Other ones need to be executed for each task. This means that the comparison of their running times can be difficult. Table 3 gives the running time of each of the proposed algorithm for computing the quantity of interest for all tasks in a network and recalls the quantities computed by the algorithms. MaxLST, MinLST, MaxF and MinF denote maximal latest starting dates, minimal latest starting dates, maximal floats and minimal floats, respectively. We now present some computational results in order to evaluate the performance of all the considered algorithms on a scheduling problem library of 600 networks having 120 tasks. Those instances of problems can be found in the PSPLIB library. They have been generated by ProGen, the program for activity network generation [START_REF] Kolisch | Psplib -a project scheduling library[END_REF], which can be downloaded from the PSPLIB web site1 . We have added a range of 20% to task duration times to obtain intervals. Table 4 reports minimal, maximal and average execution times (in milliseconds) of five algorithms tested on those 600 problems. All the algorithms were written in C language and ran on a PC computer equipped with 2.5GHz CPU. As seen from the experimental results, the path algorithm (potentially exponential) for simultaneously computing the maxima of latest starting dates and the minima and maxima of floats is very efficient in practice. This comes from the fact that the number of paths in these networks is not so huge, i.e. between 408 and 6559 different paths. Of course, one can construct more complex networks, but PSPLIB is known to be relevant to realistic scheduling problems. On the other hand, the polynomial algorithm that computes maximal floats is not so efficient for these scheduling problems. These results show that the proposed algorithms are very efficient for problems involving about one hundred tasks. We have made a second batch of experiments in order to evaluate the algorithms on networks with different complexities. For this purpose we have used the RANGEN 1 project generator which can be downloaded from the RANGEN web page2 . RANGEN 1 is particularly useful because it can generate networks with various order strengths, denoted by OS. This coefficient measures the hardness of a problem instance. The order strength is the number of precedence relations divided by the theoretical maximal number of precedence relations in a network. More details on RANGEN can be found in [START_REF] Demeulemeester | A random network generator for activity-on-the-node networks[END_REF]. We have generated by RANGEN nine sets of 100 networks with 100 tasks in which the values of OS are equal to i • 0.1, i = 1, . . . , 9, one network with OS equals 0 (all tasks of this network can be executed in parallel) and one network in which OS equals 1 (all tasks are series). Again, we have ignored resource constraints of these problems and added a range of 20% to task duration times to obtain intervals. Table 5 reports execution times of the algorithms on the generated problems by RANGEN. It is easy to observe that the computational time of most of the algorithms depends on values of OS. Figure 5 presents execution times of the algorithms. The computational time of the path algorithm drastically increases when the value of OS increases. This is due to the fact that the number of potential paths in the networks increases when OS is increased (if OS is very close to 1 then networks become parallel ones). The other algorithms are quite efficient. In particular, the polynomial algorithm for computing maximal floats is more efficient than the path algorithm when OS is greater than 0.7. Each polynomial algorithm achieves its maximal execution time on networks with OS parameter between 0.5 and 0.7.

Conclusion

This paper provides a complete solution to the criticality analysis of activity networks when the duration times of tasks are modeled by means of intervals. It is shown that moving from precise to imprecise durations radically changes the nature and complexity of the problem, ruining the classical critical path method. The part of the problem pertaining to computing minimal float values, becomes strongly NP-hard [START_REF] Chanas | The computational complexity of the criticality problems in a network with interval activity times[END_REF] and remains NP-hard even if in acyclic planar network of node degree 3 [START_REF] Chanas | On the hardness of evaluating criticality of activities in planar network with duration intervals[END_REF]. Moreover, it is not at all approximable, unless P=NP [START_REF] Zieliński | On computing the latest starting times and floats of activities in a network with imprecise durations[END_REF]. The other questions remain polynomially solvable, although not straightforwardly so. An interesting question is how to exploit the results of an interval criticality analysis. The end-user may not be accustomed to obtaining imprecise floats or latest starting times. A task that has a large maximal float is less likely to become critical in practice on a real configuration, than a task that has a small maximal float . On the other hand, all tasks having positive minimal float are ensured not to be critical whatever the actual configuration turns out to be. So any interval PERT software would present results to the user by eliminating tasks with positive minimal floats first, and drawing the user's attention on necessary critical tasks first and then on tasks having small maximal floats. It is clear that, insofar as obtained results are sufficiently precise, the information derived from an interval criticality analysis is richer than the one provided by a standard criticality analysis, because it is supposed to cover many possible scenarios at the same time.

The presented results can be also applied to the criticality analysis of activity networks with imprecise duration times of tasks modeled by fuzzy intervals, whose membership functions are regarded as possibility distributions for the values of the unknown duration times called fuzzyvalued PERT. Fuzzy intervals are more informative than crisp ones as they also account for plausible values of task duration times. They address the dilemma between safe but uniformative intervals and narrow but possibly wrong ones. This gradual extension of interval PERT can be computed via the standard decomposition in α-cuts that consists in decomposing the fuzzy-valued PERT into a family of the interval-valued PERT problems, which can be solved by algorithms presented here (see for details [START_REF] Dubois | On latest starting times and floats in activity networks with ill-known durations[END_REF][START_REF] Zieliński | On computing the latest starting times and floats of activities in a network with imprecise durations[END_REF]). Another method for addressing fuzzy interval PERT exploits a notion of gradual number [START_REF] Fortin | Gradual numbers and their application to fuzzy interval analysis[END_REF]. Gradual numbers provide a new outlook on fuzzy intervals that can be viewed as classical intervals of gradual numbers. This allows us to directly apply the interval algorithms, proposed in this paper to the fuzzy-valued PERT problems (see [START_REF] Fortin | Solving Fuzzy PERT using gradual real numbers[END_REF] for an example of algorithms for computing upper bounds on floats).

It is worth pointing out that the presented results can be useful tools for min-max regret version of the longest (shortest) path problem with interval weights in acyclic graphs (see [START_REF] Averbakh | Interval data minmax regret network optimization problems[END_REF][START_REF] Karasan | The robust shortest path problem with interval data[END_REF][START_REF] Kasperski | The robust shortest path problem in series-parallel multidigraphs with interval data[END_REF]). In particular, the algorithms for evaluating the necessary criticality and for computing the maximal float of an activity (arc) are useful in a preprocessing of an instance of the problem, since a necessarily critical activity (arc) can be automatically added to a constructed min-max regret path. In consequence, one can decompose an instance with a necessarily critical arc into two separate instances in smaller subgraphs [START_REF] Kasperski | Minmax regret approach and optimality evaluation in combinatorial optimization problems with interval and fuzzy weights[END_REF]. An activity (arc) with a small maximal float can be considered as a candidate for belonging to a min-max regret path.

  The earliest ending time of the project is ill-known: EST 2 = EST 1 + I D 12 = [0, 1]. And thus the backward recursion yields the following information EST 2 -I D 12 = [0, 1]-I [0, 1] = [-1, 1] on latest starting dates LST 1 and LST 12 , which is of course false since the latest starting dates of event 1 and activity (1, 2) are always null in order to ensure a minimal project duration, LST 1 = LST 12 = [0, 0] ⊂ EST 2 -I D 12 = [-1, 1]

  is critical in the configuration where d 12 = d 23 = 0 and d 34 = d 45 = 2, and task (3, 5) is critical in the configuration where d 12 = d 23 = 2 and d 34 = d 45 = 0, but the path

  l * lv and lst - kl = l * kl -l kl . The above remarks allow us to construct an O(m 2 ) algorithm (see Algorithm 2). Algorithm 2: [Polynomial path algorithm] Calculation of the minima of latest starting dates of all tasks in a network Input: A network G, interval duration times Duv, (u, v) ∈ A. Output: The minima of latest starting dates of all the tasks in a network G. begin V ← V ∪ {n + 1}; A ← A ∪ {(n, n + 1)}; Dnn+1 ← [0, 0]; Use the classical PERT to compute earliest starting date of each task of

Figure 2 :

 2 Figure 2: (a) Configuration Ω * -r on p * after r (b) Configuration Ω ′ (tasks with the maximal duration times are in bold)

Figure 3 :

 3 Figure 3: (a) Configuration Ω * -r on p * before r (b) Configuration Ω ′′

  3 without the initialization; /* we can retain all the values f kl (1, i) computed by Algorithm 3 */ return est + kl + ∆

Figure 4 :

 4 Figure 4: A project network

Algorithm 5 returns 1 to

 1 Algorithm 8.

is set to d - 23 = 1 ,

 231 and finally f 23 in G(2, 4) is computed in configuration Ω par : D 23 = 0, D 34 = 1, D 24 = 2. This float is equal to 1 and is returned to Algorithm 6.

Algorithm 3

 3 During the execution of the algorithm, the partial configuration Ω par : D 23 = 1, D 34 = 1, D 24 = 2 is constructed. This allows to deduce that (2, 3) is necessarily critical in the network G(2, 4) (with the possible duration times set before the call of the algorithm).

Figure 5 :

 5 Figure 5: Execution times of of the algorithms on RANGEN benchmark

  Among the configurations of C a crucial role is played by the extreme ones, which belong to × (i,j)∈A {d -

	ij , d + ij }. Let B ⊆ A be B as the configuration where a given subset of activities. We define the extreme configuration Ω + all activities (i, j) ∈ B have duration times d + ij and all the remaining activities have duration
	times d -ij . Similarly, in configuration Ω -B all activities (i, j) ∈ B have duration times d -ij and all the remaining activities have duration times d + ij . Using configurations, the possible values EST kl = [est -kl , est + kl ] for the earliest starting date est kl , the possible values LST kl = [lst -kl , lst + kl ] for the latest starting date lst kl and the possible values

  Algorithm 1: [Path Algorithm] A calculation of the maximal latest starting dates, the minimal and maximal floats of each task in network G The maximal latest starting dates, the minimal and maximal floats of each task in G.

	begin
	foreach task (k, l) ∈ A do
	lst + kl ← 0; f + kl ← 0; f -kl ← +∞;
	foreach path p ∈ P do
	Compute lst kl (Ω + p ) and f kl (Ω +

Input: A network G, interval duration times Duv, (u, v) ∈ A. Output: p ) for each (k, l) ∈ A by the classical PERT;

  It is easily seen that this new configuration is equal to Ω +

	p . If
	(i, j) ∈ p, configurations Ω

which implies the criticality of (k, l) in this new configuration Ω ′′ . Hence, there exists a critical path p ′′ ∈ P using (k, l). By the claim,

l p * (r,k) (Ω * ) = l p * (r,k) (Ω ′′ ). It follows that path p * (r, k) ∪ p ′′ (k, n) is

at least as long as subpath p(r, n) in configuration Ω ′′ . If (i, j) ∈ p, we may decrease duration d ij (Ω ′′ ) to its lower bound. Again by the claim, the lengths of subpaths p * (r, k) ∪ p ′′ (k, n) and p(r, n) remain unchanged in this new configuration and so p * (r, k) ∪ p ′′ (k, n) is still at least as long as p(r, n). ′′ p and Ω + p are equal. Consequently, path p(1, r) ∪ p * (r, k) ∪ p ′′ (k, n)

  Algorithm 4; /* we can retain all the values f kl (1, i) computed by Algorithm 4 */

	return est -kl + ∆

Algorithm 8 :

 8 Computation of the maximal float of a given taskInput: A network G, task (k, l), interval duration times Duv, (u, v) ∈ A.

	Output: The maximal float f + kl .
	∆ ← 0;
	f kl (1, n) ← Algorithm 5;
	while f kl (1, n) > 0 do
	δ ← ∞;
	foreach i ∈ P RED(k) do
	[est * kl , lst * kl ] ← Algorithm 6 in G(i, n);/*Algorithm 6 returns additionally est + kl */ f * kl ← lst * kl -est * kl ; if f * kl > 0 then δ ← min{δ, f * kl };
	∆ ← ∆ + δ;
	d kl ← d -kl + ∆;
	f kl (1, n) ← Algorithm 5 without the initialization;
	return ∆

Table 2 :

 2 The complexity of the interval problems and the running times of the algorithms

	Earliest starting date (all tasks) MinEST	P	O(n + m)	[5]
		MaxEST	P	O(n + m)	[5]
	Latest starting date (one task) MinLST	P	O(mn)	Algorithm 6 [47]
		MaxLST	P	O(mn)	Algorithm 7 [47]
	Latest starting date (all tasks) MinLST	P	O(m 2 )	Algorithm 2
	Float (all tasks)	MinF	NP-hard O((m + n)|P |) Algorithm 1 [11]
	Float (one task)	MaxF	P	O(n 3 m)	Algorithm 8

Table 3 :

 3 The running times of the algorithms for computing quantities for all tasks in a network

	Algorithm 1 (Path Algorithm MaxLST, MinF, MaxF) O((m + n)|P |)
	Algorithm 2 (Polynomial Path Algorithm MinLST)	O(m 2 )
	Algorithm 6 (MaxLST)	O(m 2 n)
	Algorithm 7 (MinLST)	O(m 2 n)
	Algorithm 8 (MaxF)	O(n 3 m 2 )

Table 4 :

 4 Minimal, maximal and average execution times (in milliseconds) of five algorithms tested on 600 problems from PSPLIB

	Min	Max	Avg.

Table 5 :

 5 Average execution times (in milliseconds) of the algorithms tested on problems from RANGEN

				Order Strength OS
	0 0.1 0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9 1
	Algorithm 1 4 35 111 249 583 1 534 5 161 27 000 303 117		2
	Algorithm 2 1 5	6	6	6	6	5	4	3	2	1
	Algorithm 6 4 28 57	76	87	89	79	58	30	12 2
	Algorithm 7 5 44 96	138 174	195	181	142	80	21 2
	Algorithm 8 16 600 2 280 4 926 9 520 16 321 22 100 23 712 16 625 5 562 78

http://129.187.106.231/psplib/

http://www.projectmanagement.ugent.be/rangen.php

Pawe l Zieliński was partially supported by Polish Committee for Scientific Research, grant 3T11C05430.