K H Adjallah
email: adjallah@utt.fr

K P Adzakpa
email: adzakpa@utt.fr

J Lee
email: jaylee@uwm.edu

A new effective heuristic for the intelligent management of the preventive maintenance tasks of the distributed systems

Keywords: Tasks scheduling, weight, flow-time, release date, real-time, maintenance, decision making

We consider a class of scheduling problems of n weighted tasks on M identical, and parallel processors with an objective of minimizing the sum of the tasks weighted flow-times. A priority rule for total weighted flow-time (PRTWF), is then proposed for locally optimal scheduling of tasks with unequal release dates and processing times. Then, an algorithm based on a heuristic and the PRTWF, is worked out to minimize the total weighted flow-time of the given set of tasks on a single server. This algorithm is designed for implementation in a dynamic process of real-time decision-making. It is next extended to tasks scheduling (with unequal release dates and processing times) on parallel servers, while minimizing their total weighted flowtime. A lower bound of solutions is also proposed to evaluate the algorithm, with a complexity in O(n 3 ) in the off-line scheduling process. The rule is then used in an algorithm of on-line planning and scheduling of maintenance tasks in a large size distributed system with weighted Equipments.

Introduction

In several areas of activity as in maintenance, delays in starting tasks engender, for the user, extra costs due to the degradations of Equipments, raw materials and products' quality, and disorganization of the production process. Such cost may be very high in some cases, particularly in maintenance tasks management for several reasons: the considered tasks are not always available from the initial time t0 before the decision-making times t; in some cases, tasks cannot be started before a given date which marks the beginning of inescapable degradations, etc. As a result, the processing of many tasks may be delayed in relation to their release dates. Under these conditions, the costs include additional costs due to delayed completion of tasks. It is then necessary, in this case, to set up a real-time decision making strategy to manage tasks.

Obviously, these costs increase with the flow-times of worsening operation conditions. A way to reduce these costs is to schedule tasks so as to minimize their flowtimes in penalizing situations. When the additive cost increases *Corresponding author uniformly and in an identical way for all the tasks, the problem consists in minimizing, through optimal scheduling, the sum of the flow-times of all the tasks in penalizing situations.

Works addressing the typical problem of maintaining optimal task scheduling and processors allocation are rare in the existing literature. We mention in this respect Weinstein and Chung [START_REF] Weinstein | Integrating maintenance and production decision in a hierarchical production planning[END_REF] who proposed a mixed-integer linear model which incorporates preventive maintenance into the production policies. This method aims at minimizing the cost and the deviation of production tasks in contrast to maintenance free production policies. In regards to preventive maintenance, we also mention the heuristic method of Qi et al. [START_REF] Qi | Scheduling the maintenance on a single machine[END_REF] based on the Shortest Processing Time (SPT) priority rule to minimize the makespan in a production policy. They studied the parallel-machines scheduling problem where preventive maintenance tasks are performed on each machine, just as in Lee and Chen [15] and Graves and Lee [START_REF] Graves | Scheduling maintenance and semi resumable jobs on a single machine[END_REF]. Lee and Chen [15], Qi et al. [START_REF] Qi | Scheduling the maintenance on a single machine[END_REF] proposed a branch and bound method to minimize weighted completion time of tasks based on the partition formulation of the problem. In [START_REF] Adzakpa | On-line Maintenance Job Scheduling and assignment to Resources in Distributed Systems by Heuristic-Based Optimization[END_REF], we proposed an on-line algorithm for real-time maintenance planning and scheduling methods on a given horizon. In the given algorithm, tasks are scheduled in real-time, and the precedence constraints linking the different tasks on the same Equipment have been dealt with. But the existing methods in production are quite limited where the maintenance assets' sensitivity (importance) and tasks' set-up time are concerned. In this paper, we propose a priority rule for the total weighted flow-time. This rule, which considers task pairs, has very good properties. It can be used as well in production as in maintenance activities planning and scheduling. Basing on it, we propose an algorithm for maintenance tasks realtime scheduling and resources (processors) allocation.

In the continuation of this paper, we state in section 2 the real-time maintenance decision making problem and the link to a scheduling problem of weighted tasks with unequal release dates. In order to solve it, section 3 is devoted to a static (off-line) approach to the scheduling problem. A local optimality priority rule (PRTWF) is proposed, proved and compared to existing rules in the literature in this section. In section 4, we adapted the approach to the real-time maintenance decision making process. Experimentations are provided in section 5 and finally section 6 concludes and proposes future extensions to this work.

From maintenance activities management to scheduling problem

This paper deals with the problem of maintenance process modelling with cost minimization through tasks scheduling on the one hand and repairmen (processors) assignment to tasks on the other hand. In the remainder of this paper, we will use the term "processor" to signify the principal maintenance resource or repairman assigned to the tasks. Let us consider a distributed system composed of N sites working independently and in parallel, and sharing M repairmen for the preventive maintenance activities on the different Equipments of the system. On a given site, Equipments operate in series. Obviously, the number of repairmen is less than the total number of Equipments in the system and the repairmen are shared by the overall system, Nk being the number of Equipments on a site k. An Equipment may be a production machine or a simple equipment. It generally requires important logistic times to move a repairman from a site to another, but in the approach proposed in this paper, we assume that the logistic time are small enough to be included in the maintenance tasks' processing times.

The main problem is then to dynamically evaluate the processor needs at sites levels so as to establish priorities. The available processors must be assigned to the Equipments so as to ensure a minimum required availability to the sites while minimizing the involved cost on a working horizon.

To model this problem, we consider a planning horizon H on which each site's unavailability and maintenance cost must be minimal. We assume that the maintenance tasks are processed without pre-emption. So, once begun, each maintenance task is processed to its completion without interruption. We also consider them to be perfect maintenance tasks, which mean that an Equipment is supposed to be renewed after a preventive maintenance. The different Equipments in the system are weighted according to their sensitivity and their importance in the system. The maintenance tasks processors are supposed to have equivalent performance and can be used in parallel.

In the approach the Equipments' availabilities are assumed to follow the exponential law. But this assumption is not restrictive. The model can still be used when the Equipment behave according to other laws such as

Weibull's law. The failure and repair rates (lik and µik) of an Equipment Eik (equipment i of site k) are then assumed to be constant on the planning horizon H. The exponential availability Aik of an Equipment Eik is renewed at the end of a maintenance task at time T (considered also to be a start up date of the Equipment) as

(2.1) In order to guarantee the minimum required availability of each site, a threshold aik given in ]0, 1[ is imposed on the availability Aik of each Equipment Eik. An Equipment Eik which works for a time without failure reaches that threshold and should be submitted to a preventive maintenance task. An Equipment working under its threshold is supposed to be in a critical state with a high probability of failure. The time spent from the occurrence of such a critical state on the Equipment Eik to the completion date of the maintenance task on that Equipment (which is considered to be also the start-up of the Equipment), involves a time-unit cost wik which is the weight of Eik in the system. From the expression of the availability function of the Equipment Eik in equation (2.1) and the threshold aik, the duration from a start-up of the Equipment to the critical date is derived from the inequality Aik ≥ aik. By taking the start up date T to be the initial date 0, this duration for the Equipment Eik is then tik expressed as below:

(2.2) Each Equipment has as many start ups on the planning horizon as there are completions of maintenance tasks following a critical state. Let us note rm,ik the m th occurrence date of a critical event on the Equipment Eik and cm,ik the completion date of the corresponding maintenance intervention. Then the critical states cost on the system on the planning horizon H is expressed as

(2.3)
Each maintenance task on the Equipment Eik is assumed to have a processing time equal to the Equipment's mean time to repair (Mtp) which is 1/µik. The problem is then formulated as (P1): Minimize Ctot (H) with the M processors under the conditions Aik ≥ aik.

In scheduling, this formulation will be:

( )

<< 1 å = N k k N M )] )( ( exp[ ) ( T t t A ik ik ik ik ik ik - + - + + = µ l µ l µ ú ú û ù ê ê ë é - ÷ ÷ ø ö ç ç è ae + + - = ik ik ik ik ik ik ik ik l µ l µ a µ l t 1 ln 1 å å å = = Î ÷ ÷ ø ö ç ç è ae - = N k N i ik m ik m H r m ik tot k ik m r c w H C 1 1 , , / ) ( ) ( , (
P2): Minimize the total weighted flow-time of tasks released on unequal dates on M parallel machines (processors), under the availability conditions.

However, the problem considered herein in not a static scheduling problem as it is generally considered in scheduling problems. The maintenance tasks arrive in real-time until the end of the horizon. When all the Equipments have equal weights and the logistic times are still very small, we considered the problem in [START_REF] Adzakpa | On-line Maintenance Job Scheduling and assignment to Resources in Distributed Systems by Heuristic-Based Optimization[END_REF]. To deal with this problem with unequally weighted Equipments, we developed an approach for local optimality which will be used in a real-time decision-making algorithm. Before the section on the local optimality, let us notice the following two properties of the problem (P1). The proof of the first one is straightforward and the second one can be proved in the same way as in [START_REF] Adzakpa | On-line Maintenance Job Scheduling and assignment to Resources in Distributed Systems by Heuristic-Based Optimization[END_REF] where the Equipments are equally weighted. The flow-time of a maintenance task corresponds to the time that the corresponding Equipment spends in a critical state. See the proof in [START_REF] Adzakpa | On-line Maintenance Job Scheduling and assignment to Resources in Distributed Systems by Heuristic-Based Optimization[END_REF].

As we said above, the maintenance problem considered herein is real-time decision making problem. In the following section, we develop some tools to solve the scheduling aspect of this problem. To this end, we consider the static problem consisting in scheduling a given set of n weighted tasks with unequal release dates. As mentioned earlier in this section, in maintenance activities, the flow-time corresponds to the time an Equipment spends a critical state.

Solving the scheduling problem for minimizing the weighted flow-time

Overview of weighted flow-time scheduling problems

Authors concerned by the flow-time minimization problem, have often assumed that all tasks are of equal importance. This assumption does not necessarily hold, since in real life, tasks may, for example, be of different unit costs, different holding costs, or may carry different contractual penalties for overdue deliveries. For this reason, when it comes to minimizing the overall cost associated with the total flow-time, tasks cannot be treated as being equivalent. Now, as the evolution of the costs is not the same for all tasks, the problem then comes to minimizing the sum of the weighted flow-times of all penalized tasks through optimal scheduling. In this respect, tasks of the same release dates have received considerable attention in the literature.

Both "unweighted" and weighted flow-time minimization problems can arise for tasks on single machine, or parallel machines in flow-shop, be they uniform or not. We are interested in the minimization of the sum of weighted flow-times of n tasks released at different dates on M parallel processors (machines) (0<M<<n), inside a given time horizon H. We consider that each released task is processed by only one processor among available M processors. This problem requires an optimum scheduling of the n tasks, while minimizing the total weighted flowtime of tasks on the time horizon H. Lenstra [16] proved the NP-hardness of the flow-time minimization problem for tasks with different release dates. Over the last three decades, the flow-time minimization problem has indeed retained considerable research attention both on single and parallel machines, and different solution approaches have been developed. Among the algorithms proposed to minimize the "unweighted" flow-time of tasks with different release dates, we cite, in particular, the single machine scheduling heuristics developed by Chu [START_REF] Chu | One-machine scheduling for minimizing total flow time with release dates[END_REF] and [START_REF] Chu | Efficient heuristics to minimize total flow time with release dates[END_REF]. These heuristics are based on an efficient priority rule that enables realtime decision by local optimal tasks scheduling, as stated in our problem, and they take into account tasks' release dates and processing times. Chu uses the same rule in the branch and bound algorithm [START_REF] Chu | A branch-and-bound algorithm to minimize total flow time with unequal release dates[END_REF] proposed later for solving this problem. The weighted flow-time was considered by Bianco and Ricciardelli [START_REF] Bianco | Scheduling of a single machine to minimize total weighted completion time subject to release dates[END_REF], who developed a Branch and Bound algorithm based on a set of rules for tasks scheduling on single machine. Their work is, to our knowledge, the one to which our formulation comes closest.

Works on the NP-hard problem of weighted flow-time minimization fall roughly into two categories: those dedicated to single machine and flow-shops, and those focussing on parallel machines and on uniform machines. Among the investigations dedicated to flow-shop model, we mention four heuristics developed by Gelders and Sambandam [START_REF] Gelders | Four simple heuristics for scheduling a flow-shop[END_REF] to minimize the sum of weighted flowtime and weighted tardiness of tasks. Rajendran and Ziegler also proposed two heuristics; the first one minimizes the weighted flow-time [START_REF] Rajendran | An efficient heuristic in a flow-shop to minimize the total weighted flowtime of jobs[END_REF], while the second one [START_REF] Rajendran | A heuristic for scheduling to minimize the sum of weighted flowtime of jobs in a flowshop with sequence-dependent setup times of jobs[END_REF] minimizes the weighted flow-time in the presence of sequence-dependent set-up times. Both heuristics are based on the WSPT rule (Weighted Shortest Processing Time), adapted in some recursive relations. Rajendran [START_REF] Rajendran | Formulation and heuristics for scheduling in a kanban flow-shop to minimize the sum of weighted flowtime, weighted tardiness and weighted earliness of containers[END_REF] also developed a heuristic based on a priority rule and some recursive relations for minimizing an objective-function corresponding to the sum of weighted flow-time, weighted earliness and weighted tardiness. This priority rule was used in a scheduling improvement strategy based on sequential task insertions. Sharadapriyadarshini and Rajendran [START_REF] Sharadapriyadarshini | Heuristics for scheduling in kanban system with dual blocking mechanisms[END_REF] studied the same problem and used a convex combination of the makespan and the flow-time as objective function in the optimization. Framinan et al. [START_REF] Framinan | Efficient heuristics for flowshop sequencing with the objectives of makespan and flowtime minimization[END_REF] recently proposed efficient heuristics for this problem, where the objectivefunction is the sum of the weighted waiting-time and the weighted flow-time.

Several works have also focussed on the weighted flowtime minimization on parallel machines with tasks released on the same date. Bruno et al. [START_REF] Bruno | Scheduling independent tasks to reduce mean finishing time[END_REF] showed that this problem is NP-hard even in the case of two machines. Sarin et al. [START_REF] Sarin | An improved branching scheme for the branch and bound procedure of scheduling n jobs on m parallel machines to minimize total weighted flowtime[END_REF] developed a branch and bound method for solving this problem. Compared to the branch and bound methods of Elmaghraby and Park in [START_REF] Elmaghraby | Scheduling jobs on a number of identical machines[END_REF] and the one of Barnes and Brennan in [START_REF] Barnes | An improved algorithm for scheduling jobs on identical machines[END_REF], the algorithm of Sarin et al. is better because it is based on a better lower bound. Furthermore, Azizoglu and Kirca [START_REF] Azizoglu | On the minimization of total weighted flow time with identical and uniform parallel machines[END_REF], discussed some properties of an optimal solution and proposed a branch and bound which is better than that of Sarin et al. Webster established in [START_REF] Webster | A priority rule for minimizing weighted flow time in a class of parallel machine scheduling problems[END_REF] a sufficient condition for the weighted flow-time optimality in a class of parallel machines problems. This condition is an adaptation of the weighted shortest processing time (WSPT) rule. He also proposed in [START_REF] Webster | Weighted flow time bounds for scheduling identical processors[END_REF] two lower bounds to the problem and compared them to those in [START_REF] Sarin | An improved branching scheme for the branch and bound procedure of scheduling n jobs on m parallel machines to minimize total weighted flowtime[END_REF], [START_REF] Elmaghraby | Scheduling jobs on a number of identical machines[END_REF] and [START_REF] Barnes | An improved algorithm for scheduling jobs on identical machines[END_REF]. Belouadeh and Potts [START_REF] Belouadeh | Scheduling identical parallel machines to minimize the total weighted completion time[END_REF] proposed a method based on the dominance properties in [START_REF] Elmaghraby | Scheduling jobs on a number of identical machines[END_REF]. All the above mentioned works assume that tasks are available and released at the initial time of the optimization time window. Now, in several real-life problems, different tasks become available at different times. This is, for example, the case for maintenance tasks scheduling. Reports on works aiming at finding methods for solving total weighted flowtime minimization problems in the case of tasks with unequal release dates, are very scarce in the existing literature. In [START_REF] Rajendran | Heuristics for scheduling in flowshops and flowline-based manufacturing cells to minimize the sum of weighted flowtime and weighted tardiness of jobs[END_REF], Rajendran and Ziegler dealt with a flow-shop problem in which the objective is to minimize the sum of the weighted flow-time and weighted tardiness of tasks. They considered one case where tasks were all released at time 0 and another case where tasks were released at different dates. They proposed then a heuristic based on some recursive relations and a priority setting rule that takes into account the task's weight relative to the flow-time and the tardiness, and the lower bound of tasks completion times on the machines. The algorithm consists in generating 2m sequences (m is the number of machines) and selecting the best case among simultaneously released tasks. They proposed some modifications to deal with the case of different release dates. As for Rinaldi and Sassano [START_REF] Rinaldi | On a job scheduling problem with different ready times: Some properties and a new algorithm to determine the optimal solution[END_REF] and Bianco and Rincciardelli [START_REF] Bianco | Scheduling of a single machine to minimize total weighted completion time subject to release dates[END_REF], they proved some dominance properties for the total weighted flow-time minimization on a single machine in the presence of release dates. These dominance properties were used in an implicit enumerative algorithm based on a branch and bound concept that Bianco and Ricciardelli proposed in [START_REF] Bianco | Scheduling of a single machine to minimize total weighted completion time subject to release dates[END_REF] allowing the solution for up to 10 tasks. The dominance properties of Rinaldi and Sassano have also been used by Hariri and Potts in [START_REF] Hariri | An algorithm for single machine sequencing with release dates to minimize total weighted completion time[END_REF] who proposed a lagrangian relaxation method for lower bound determination.

In this section, we propose a local optimality priority rule for total weighted flow-time minimization with unequal release dates of tasks.

The algorithm utilizes the priority rule and the dominance concept defined in a heuristic that minimizes the total weighted flow-time on single processor and on parallel processors. We use the priority rule with relating concepts in an initial scheduling algorithm before adapting it for the on-line maintenance problem. The proposed algorithm allows the solution of large size problems in a small computational time.

Weighted flow-time problem formulation

Here is the list of notations used in the formulation of the weighted flow-time problem.

M is the number of processors n is the number of tasks to be scheduled pi is the processing time of task i ri is the release date of task i wi is the weight of task i ci is the completion time of task i [p] is a partial sequence of tasks [p,i] is the sequence obtained after task i is appended to the end of [p].

In this problem, each processor can process only one task at a time. The release dates of tasks are different, and each task can be processed from its release date on any of the M processors. Once begun, a task ought to be processed completely without preemption. The aim is to minimize the total weighted flow-time of the tasks expressed as

𝐹 " = ∑ 𝑤 & (𝑐 & -𝑟 & ) , &-.
or equivalently the mean weighted flow-time

𝐹 0 " = . , ∑ 𝑤 & (𝑐 & -𝑟 & ) , &-.
. This problem is stated as: (P): Minimize the total weighted flow-time of n tasks with unequal release dates, on M identical parallel processors.

Following the usual notation in scheduling, the problem (P) can be formulated as Pm/ri/S wici. Lenstra [16] proved that the problem of "unweighted" flow-time minimization on parallel processors of tasks with unequal release dates is NP-hard. Bruno et al. [START_REF] Bruno | Scheduling independent tasks to reduce mean finishing time[END_REF] also showed that even in the case where the release dates are the same, the problem of the weighted flow-time minimization is NP-hard. Consequently, the problem (P) is NP-hard. In our approach, we shall first focus on the case of single processor to design a locally optimal priority rule which will, in turn, be used on parallel processors as well. The priority criterion, the dominance concept and the associated properties used in the algorithm will be defined in the following subsection.

The priority rule and its properties

Turning to the problem of total weighted flow-time minimization on a single processor in the context of different release dates, we denote the release date for task i by ri and its weight and processing time by wi and pi respectively.

Concepts and definitions.

Definition 3.3.1. Consider a task-pair {i, j} to be scheduled at the end of a sequence [p] and at time t. We say that task i dominates task j at time t and symbolize this by writing i j, if the scheduling of i before j, yields a smaller value for the total cost (in term of total weighted flow-time) than the scheduling of task j before task i. Remark 3.3.2. In classical scheduling terminology, the term dominance is used for partial schedules. But in the above definition, it can be noticed that if at time t, [p] is a partial schedule, saying "i j" is equivalent to saying that "the sequence [p, i] dominates [p, j]". Let us consider the task-pair {i, j} to be scheduled at the end of the partial schedule [p], at time t. We formally define the associated function PRTWF (Priority Rule for Total Weighted Flow-time) as follows.

Definition 3.3.3. For any task-pair {i, j}, and at any time t, the function PRTWF (Priority Rule for Total Weighted Flow-time) is given by PRTWF(i, j, t) = (wi +wj ).max(ri, t) +wj.pi (3.1) We next prove the following theorem. Theorem 3.

At any time t, i j if and only if PRTWF(i, j, t) £ PRTWF( j, i, t).

Proof. The parameters ri, pi, wi are affected to the task i, and the parameters rj, pj, wj are affected to the task j. Assume that ri ≤ r j.

One can easily verify that the following are satisfied, by scheduling i and j at time t. i) If ri ≤rj≤ t then i j iff wj.pi -wi.pj ≤ 0. ii) a) If ri ≤ t ≤r j and t + pi ≤ r j then i j is obvious. ii) b) If ri ≤t ≤ r j and t + pi > r j then i j iff [(wi +wj )t +wj. pi]-[(wi + wj )r j +wi. pj ] ≤0. iii) a) If t≤ ri ≤ rj and ri + pi ≤ rj then i j is obvious. iii) b) If t ≤ ri ≤ rj and ri + pi > rj then i j iff [(wi +wj)ri +wj pi] -[(wi + wj )r j + wi pj] ≤ 0.

All the cases i), ii) b) and iii) b) can be summarized in i j if and only if (wi +wj).max(t, ri) + wj.pi ≤ (wi +wj ).max(t, rj ) + wi pj.

In the case ii) a), we have ri ≤ t ≤ rj and t + pi ≤ rj. From the second inequality, one can derive (wi +wj )(t + pi) ≤ (wi + wj )rj which leads to (wi + wj)t +wj pi ≤ (wi + wj )(t + pi) ≤ (wi + wj)rj ≤ (wi + wj )rj + wi. pj . The first member and the last member of this last inequality string in conjunction with the first inequality in the case ii) a) leads to (wi +wj).max(t, ri) +wj. pi ≤ (wi +wj ).max(t, rj) +wi.pj.

In the case iii) a), we also have t ≤ ri ≤ rj and ri + pi ≤ rj. From the second inequality, one derives (wi + wj )(ri + pi) ≤ (wi + wj)rj , which implies (wi + wj )ri +wj.pi ≤ (wi + wj )(ri + pi) ≤ (wi + wj)rj ≤ (wi +wj )rj + wi pj .

The first and the last members of this latter inequality string and the first inequality in the case iii) a) allow us to write (wi + wj).max(t, ri) + wj pi ≤ (wi + wj )max(t, rj ) + wi pj . This proves that in all the cases where ri ≤ rj we have i j if and only if (wi + wj).max(t, ri) + wj pi ≤ (wi + wj).max(t, rj) + wi pj . Now, assume that ri > rj. By inverting the roles of i and j in the previous expression, we have j i if and only if (wi + wj).max(t, rj) + wi pj ≤ (wi + wj).max(t, ri) + wj pi which is the same as i j if and only if (wi + wj).max(t, ri) + wj pi ≤ (wi + wj).max(t, rj) + wi pj.

So, in all the cases, we have i j if and only if (wi +wj).max(t, ri) +wj pi ≤ (wi +wj).max(t, rj) +wi pj. □ Remark 3.3.5. The function PRTWF can be considered as a local optimality priority rule for the total weighted flow-time in presence of different release dates.

Remark 3.3.6. In the particular case where all the tasks have the same weight wi = 1 (i=1,...,n), the function PRTWF becomes

PRTW(i,j,t) = 2.max(ri, t) + pi (3.2)
This particular function depends only on task i, not on j and is the value of the PRTF function defined in [START_REF] Chu | One-machine scheduling for minimizing total flow time with release dates[END_REF] for the priority rule for total flow-time in the case of "unweighted" (or equally weighted) tasks and unequal release dates, and which we use in [START_REF] Adzakpa | On-line Maintenance Job Scheduling and assignment to Resources in Distributed Systems by Heuristic-Based Optimization[END_REF] when Equipments in the system are equally weighted. With the matrix W as defined above, we have the following property.

Proposition 3.3.8. With W as defined above, the following two statements are equivalent

W(i,j) + W(j,i) = 1 for i ≠ j, or W(j,i) = (1 -W(i,j)).1i≠j (3.4)
The calculus of W can then be reduced to the upper triangular matrix.

Definition 3.3.9. At any time t, the strength fi of task i is the number of tasks that i dominates.

(3.5)

The strength vector verifies the following property.

Proposition 3.3.10. If n is the number of task to be scheduled at time t, then the strength vector satisfies the following relation.

(

Proof

Now, W(i, j) +W( j,i) = 1 if i ≠ j, and the number of such sums where i ≠ j, is , which is equal to n(n-1)/2.

□

With the properties of the PRTWF function, and those of the matrix W and the strength vector relating to a task, the ground is now set for stating the heuristic algorithm. The principle of the algorithm is stated in section 5. But before that, let us carry some comparative studies on the dominance rules in the literature for this kind of problem. [START_REF] Bianco | Scheduling of a single machine to minimize total weighted completion time subject to release dates[END_REF] and [START_REF] Rinaldi | On a job scheduling problem with different ready times: Some properties and a new algorithm to determine the optimal solution[END_REF] The analysis presented in this section enables us to highlight the power of the function PRTWF compared to the dominance criteria suggested in [START_REF] Bianco | Scheduling of a single machine to minimize total weighted completion time subject to release dates[END_REF] and [START_REF] Rinaldi | On a job scheduling problem with different ready times: Some properties and a new algorithm to determine the optimal solution[END_REF], for the weighted flow-time minimization problem. To this end, we shall first recall the dominance properties in [START_REF] Bianco | Scheduling of a single machine to minimize total weighted completion time subject to release dates[END_REF] and [START_REF] Rinaldi | On a job scheduling problem with different ready times: Some properties and a new algorithm to determine the optimal solution[END_REF], and compare them to the PRTWF criterion. The theorems concerning the dominance properties in these references are enumerated using the notations of the present paper. The reader can refer to [START_REF] Bianco | Scheduling of a single machine to minimize total weighted completion time subject to release dates[END_REF] and [START_REF] Rinaldi | On a job scheduling problem with different ready times: Some properties and a new algorithm to determine the optimal solution[END_REF] for the proofs of the theorems referred to here.

Comparative studies on the dominance rules in

Theorem 3.4.5. Consider a set of n tasks and a partial sequence sk (k < n) of completion time t and two tasks i, j not yet scheduled. Let K (the set of tasks not yet scheduled) be the "dense" set, i.e., the set in which no sequence has an inserted idle time. If (a) wi ≥ wj (b) max(rj, t) ≤ max(ri, t) (c) max(rj, t) + pj ≤ max(ri, t) + pi then i dominates j.

Theorems 3.4.1 to 3.4.5 describe the dominance criteria used to schedule a task at a time t at the end of a partial ( )

å W = j i j i, f 2 ) 1 ( - = å n n f i i ( ) ( ) ( ) ( ) ( ) ( ) ( ) { } ( ) ( ) ( ) { } symmetry the , , , , , 0 , because , , , , , , , , , å å å
å å å

+ = + = = + = = ³ ¹ j i i j j i j i j i i j i i i j j i i j j i j i i j j i j i f W W W W W W W W 2 n C j j i i w p w p £ å ÎQ l l w ( )( ) å å - - - + - l i j l i j l l w w w p p w . 1 d K schedule sk.
From these theorems, we formulate the following remark in the form of a proposition followed by the proof. Note also that this proposition can be thought of intuitively, the PRTWF function being a local optimality condition.

Proposition 3.4.6. Theorem 3.3.4 is a necessary condition for the assumptions in theorems 3.4.1 to 3.4.5 which check if task i dominates task j.

In other words, if one can show that task i does not dominate another task j by using theorem 3.3.4, then there is no need to try to use theorems 3.4.1 to 3.4.5, since their assumptions will not be satisfied.

For the proof of proposition 3.4.6, consider the assumptions in each of the theorems 3.4.1 to 3.4.5 on the one hand, and the function PRTWF on the other hand. We do not detail the proof in this paper, but the reader can verify that if a pair of tasks i and j satisfy at a time t these assumptions, then PRTWF(i,j,t) ≤ PRTWF(j,i,t) which means that task i dominates j.

Finally, we observe that the function PRTWF provides a more powerful tool than all the dominance criteria of 3.4.1 to 3.4.5 put together. These dominance criteria are, to our knowledge, the only ones in the literature for this kind of problem. Furthermore, as we will see later, the use function PRTWF takes very little CPU time for large size problems. That is why we base the weighted flow-time minimization on the function PRTWF and its properties. This will unable its use for real-time maintenance planning on large size distributed systems.

The off-line algorithm and the lower bound

The scheduling algorithm HPRTWF.

It is worth recalling that our aim is to minimize the sum of weighted flow-times of n tasks released at different dates on a single processor or M parallel processors (0<M<<n). We assume that each released task is processed by only one among M available processors. Each time t a processor is available, the following steps determine the task to be scheduled.

Proposition 3.5.1. The algorithm based on this principle has a complexity in O(n 3 )

where n is the number of tasks waiting to be scheduled.

Proof.

Step 1 and step 2 are done in O(n 2 ) and they are the most complex for the decision-making task. So each time a task is scheduled, it is done in O(n 2 ). As this must be done till all the n tasks awaiting are scheduled, the total complexity of the algorithm is nO(n 2 ) which comes to O(n 3 ), thereby terminating the proof. □

Lower bound to the weighted flow-time.

A lower bound for the solution based on PRTWF algorithm is obtained as follow. Assume that preemption is permitted, and let us note by e(t, pi) the remaining processing time for task i at time t. Then, the following proposition holds for the case of a single machine.

Proposition 3.5.2. The scheduling in which at each time t, the task i scheduled is the one having the least ratio e(t, pi)/wi, is a lower bound of the optimal solution.

In other words, each time, the task to be scheduled is the one with the least index among those available tasks having this least ratio. Each time t, the task being processed is preempted when there arrives another task with a less ratio. This rule is the Shortest Weighted Remaining Processing Time rule (SWRPT).

Before coming to the experimental analysis on the static scheduling problem, we present hereafter how we applied this rule for on-line maintenance planning on large size distributed systems.

Solving the on-line problem of maintenance

We recall that the problem under consideration consists in assigning maintenance tasks to M maintenance processors on the Equipments of a system distributed on N sites, each one containing a number of repairable Equipments. We aim to minimize the total maintenance cost on the planning horizon H. We also aim to keep the system in good states (in terms of availability). This problem is NPhard and there are precedence relationships linking tasks

(1) Q = Set of all tasks not yet scheduled.

(2) Calculate PRTWF(i,j,t) for all tasks i, j in Q.

(3) Calculate the matrix W associated with the set Q.

(4) While card(Q)>1, calculate the tasks' strength in Q.

(5) Redefine Q = Subset of tasks in Q with the greatest strength. Reduce the research to this subset. Go to step 4. (The task with the greatest priority is selected in step 4 and step 5.) (6) Affect the selected task to the processor having the smallest index among the earliest available processors.

All the above steps are repeated until the last task is scheduled.

on the same Equipment. The algorithm to solve it is based on the concepts defined in the previous section. Some additional concepts are defined in this section. The following proposition allows the use of the PRTWF function on the Equipments and solves the problem of the precedence conditions relating to a given Equipment. We skip the proof because it is in the same way as a similar theorem we used in [START_REF] Adzakpa | On-line Maintenance Job Scheduling and assignment to Resources in Distributed Systems by Heuristic-Based Optimization[END_REF] when the Equipments in the system were equally weighted.

Proposition 4.0.1. Taking into account theorem 3.3.4 in a scheduling implies that we also respect the order of the interventions on an Equipment Eik, whichever it is. In other words, for m1 < m2 and for any Equipment Eik, theorem 3.3.4 allows to schedule the m1 th intervention on Eik before the m2 th intervention.

So, the remaining problem is to establish priorities between the different Equipments in the system. In addition to the PRTWF function and the matrix W, we also use the concept of tasks' urgency as defined below. The reader can also refer to [START_REF] Adzakpa | On-line Maintenance Job Scheduling and assignment to Resources in Distributed Systems by Heuristic-Based Optimization[END_REF] for the initial use of this definition.

Definition 4.0.2. Let Dik(t) denote at time t, the duration between t and last start up date of an Equipment Eik (confused to the last completion date of preventive maintenance task on the Equipment) before that time. We assume that it is the (m-1) th work on Eik. We define Urgent(t) (Ut) at time t to be the set of tasks satisfying the condition Dik(t) ≥ tik where tik is defined in expression 2.2.

Dik(t) is as on Figure 1. Now, basing on the PRTWF function, the definition of the dominance matrix, the tasks' strength, their urgency and theorem 3.1.4 and proposition 4.0.1, we develop the realtime algorithm for the processors assignment to the maintenance tasks. This algorithm is called OL-MTSA-W and summarized as follow.

4.1. The on-line algorithm. Algorithm 4.1.1. OL-MTSA-W procedure for realtime decision making Any time t when a processor (repairman) is available, the tasks' subset to consider is the subset Ut. If this subset is empty, the whole set of tasks is considered. In the algorithm, each Equipment Eik is characterized by its failure rate µik, repair rate lik and the duration tik as in expression (2.2) basing on the availability threshold aik.

The following section is devoted to numerical experimentations. It provides an evaluation of the PRTWF function relating to the lower bound in a first time, experimentation of the algorithm on several parallel processors in a second time, and finally experimental results on the on-line algorithm for maintenance planning and scheduling.

Numerical experimentations

This section contains two subsections. The first one gives experimentations on static instances to minimize the weighted flow-time in presence of unequal release date.

The second subsection shows experimental results on instances for real-time decision making for maintenance planning and scheduling on a given horizon. All the programs are coded in C language. They were tested on a Compaq AlphaServer ES40 DEC6600 station, operating under UNIX with 2048 MB RAM memory

Experimentations on off-line instances

Let's recall that in the static scheduling process, the lower bound and the algorithm HPRTWF were designed to schedule a given set of n tasks so as to minimize the total (2) Compute the subset Ut .

0 Time D ik (t) ik r m-1,ik c m-1,ik r m,ik (1)
(3) If card(Ut ) 1 then the search set St = Ut . Else St = {all the Equipments of all the sites}. (4) Apply to the set St the steps described in the algorithm 3.5.1 basing on the PRTWF function and additional concepts for the tasks scheduling, to select the task that should be scheduled at time t.

Determine its completion time (the next start up date of the Equipment).

Determine its next release date by adding the quantity tik to its completion time.

Go to step 1.

(5) End.

³

weighted flow-time of tasks, where wi, ri and ci are respectively the weight, the release date and the completion time of task i. In this section, we first apply the HPRTWF algorithm to schedule a set of tasks on a single processor, and compare the results to the lower bound obtained with the SWRPT-based scheduling algorithm. In this experimentation, we scheduled sets of 4 to 100 tasks on a single processor. We applied the HPRTWF algorithm to schedule sets of 100, 200, 300, 400 and 500 tasks on groups of parallel processors. Respective release dates and processing times were obtained by absolute value of normal random data with the standard deviation equal to 1, while weights are uniform random data inside [0.1,1].

The results on a single processor for the HPRTWF algorithm and SWRPT-based algorithm plotted on the figure 2 hereafter. The curves on figure 2 present three different results compared to the lower bound obtained with the SWRPT-based algorithm. show that the results of the HPRTWF algorithm are very close to the lower bound. In these results, for more than 80% of the experiments the difference between the mean weighted flow-time and the lower bound is less than 20% of the mean weighted flow-time, and less than 8% for more than the half of the experiments. The computing times for all the results summarized in Table 1 did not exceeded 0.033 CPUs. These results confirm that the PRTWF function is a good local priority rule for weighted flow-time minimization.

The curves on figure 3 show the results when applying the HPRTWF algorithm to several data instances containing from 100 to 500 tasks on parallel processors. The number of processors varies from 2% to 8% of the total number of tasks to be scheduled. This number is 100, 200, 300, 400 or 500 in the considered instances. This means that for 100 tasks (resp. for 500 tasks), the number of processors varies from 2 to 8 (resp. from 10 to 40). The numerical results plotted on figure 3 are obtained on the basis of three different groups of data. For each one of the three groups of experiments, a total of 500 data is generated. The program is first run on a first subset of 100 data, and then

) ( another subset of 100 tasks is added to the first 100, and so on until the whole of the 500 data set is treated. The diagram of the three groups of experimental results highlights the robustness of the HPRTWF algorithm. It turns out that the flow-time has a very little variability when the number of processors varies in the same proportion as to the total number of tasks to be scheduled. Furthermore, the CPU times for six sets of randomly generated data, including those used in the previous experiments, are summarized in table 1 As it can be seen, the CPU processing times for the different data sets remain stable for the various numbers of tasks considered and evolve according to a polynomial curve in relation with the polynomial complexity of the algorithm. This contrasts with results obtained in [START_REF] Bianco | Scheduling of a single machine to minimize total weighted completion time subject to release dates[END_REF] where, to solve the same kind of problem for 10 tasks, the algorithm proposed by the author took 7 to 26 CPU seconds.

Finally, the HPRTWF algorithm, based on the PRTWF function, is also very efficient in solving the total weighted flow-time minimization problem on identical parallel processors, in cases where the tasks are of unequal release dates.

In Section 5.2, we present some results on the on-line maintenance planning.

Experimentations on for on-line maintenance planning and scheduling

The algorithm OL-MTSA-W for on-line maintenance planning using the PRTWF rule and the additional concepts is programmed in two versions on a 365-day planning horizon. In the first version, the urgency concept is used in the program whereas in the second version, it is not used. The experimentations are carried on a system with an overall number of 500 Equipments. As the efficiency of the maintenance process depends on the number of repairmen, this number is taken according to the number of Equipments, varying from 2% to 20% of the total number of Equipments in the system (from 10 to 100 repairmen). The different data characterizing the system are randomly generated. The Equipments' failure rates (lik) and repair rates (µik) are generated as absolute values of normal laws. Their weights (wik) are generated uniformly in ]0.1, 1[ and the availability thresholds (aik) are uniformly generated in the interval ]0.5, 1[ in respect to the asymptotic availability µik/(lik+µik). Some portions of the curves (a) and (b) (between 8% and 20% of the number of Equipments) on figure 4 are zoomed in order to better show their behaviour.

Figure 4. Experimental results on 500 Equipments

Because the efficiency of the maintenance process depends on the available number of repairmen, some of the maintenance tasks are postponed until the end of the planning horizon without being able to be processed. For this reason, we always represent each parameter on the whole system on the one hand and on the effectively processed maintenance tasks on the planning horizon on the other hand. On the figures 4(a) to 4(d), the different parameters used are respectively MC (Mean Cost on the maintenance tasks effectively processed), MD (Mean Delay on the maintenance tasks effectively processed relatively to the critical dates), NIpR (the mean Number of Interventions per Repairman), Tm/Res (the mean Time a repairman is used on the planning horizon), MCS (Mean Cost on the whole System), MDS (Mean Delay on the whole System relatively to the critical dates). Those parameters have the extensions U or NU. The extension U means that the result corresponds to the program in which the urgency concept is used and the extension is NU otherwise.

Figure 4(a) presents the mean cost of maintenance (equivalent to the mean weighted flow-time of the maintenance tasks). On these curves it can be seen that the costs MCS_U and MCS_NU (mean costs on the whole system) are important with little number of repairmen, and decreases when the number increases. The mean cost on the whole system is definitely more important when the urgency concept is not used than otherwise. This fact can be well observed on the zoom-in of figure 4(a). Moreover the mean cost on the whole system and the mean cost on the maintenance tasks effectively processed when the urgency concept is used (MCS_U and MC_U) converge from a number of repairmen corresponding to 10% of the total number of Equipments in the system (see in the zooin). In fact, with insufficient number of repairmen, all the maintenance tasks on all the Equipments in the system can not be processed on the planning horizon. They are then postponed several times until the end of the planning horizon. This is the reason why the mean cost on the whole system is considerably greater than the mean cost on the tasks effectively processed (for little number of repairmen). The convergence of the mean costs MC_U and MCS_U corresponds to the number of repairmen from which all the maintenance activities on the system can be completed. The convergence of the two costs is rather slow to arrive when the urgency concept is not used in the decision-making process. It can also be noticed on the zoom-in of figure 4(b) that from 10%, after the convergence of the mean cost on the system and the mean cost on the tasks effectively processed, the mean delay of the maintenance tasks from their critical date tend to 0 and is definitely null from 12% when the urgency concept is used.

Figure 4(c) represent the mean number of time each repairman is required on the planning horizon and figure 4(d) shows the mean time each processor is used on the planning horizon. It can be seen that, as the number of repairmen increases, the mean time each repairman is used decreased considerably. The difference between the mean time per processor when the urgency concept is used and not used, is important. When the urgency concept is used, the processors are used at their maximum capacity up to 10% corresponding to the sufficient number to cover the whole system. All these observations show the need to use, in addition to the local optimality rule PRTWF, the urgency concept in the decision making.

In addition, for the CPU time, we have the following observations. The smartness of the decision-making process observed in the static scheduling is replicated in the real-time decision-making process. For example for 200 Equipments with 4 repairmen, the CPU time when running the programs on a one year-horizon was 8 CPU second for 3443 tasks processed and for 16 repairmen, this CPU time was 19 CPU seconds for 9366 tasks. These CPU times are the ones when the urgency concept is used to reduce the subset of the system in which the local optimality priority rule is used. Othewise, the previous CPU time become respectively 12 CPU seconds for 4 repairmen (and 3424 interventions) and 31 CPU seconds for 16 repairmen (and 8831 interventions).

Conclusion

We presented in this paper an efficient algorithm for online tasks scheduling in a distributed system. The tasks are weighted relatively to their sensitivity or importance. We proposed a method based on a priority rule (PRTWF -Priority Rule for Total Weighted Flow-time). We proved that this rule is locally optimal for the total weighted flowtime minimization, and defined the different related concepts and spelled out the underlying properties. We also identified a lower bound which allows the rule's performance evaluation. The problem under consideration is NP-hard and existing literature proposes just a limited number of methods for solving the weighted flow-time minimization problem. The PRTWF function is of polynomial computational complexity, and this has been confirmed by the CPU computation times. This approach is adapted, with additional concepts, to real-time maintenance decision making in large size distributed systems. In extension to this work, we will propose approaches to solve the problem, first in the case of tasks with unequal release dates and set-up times, and next in the case of tasks with unequal release dates, set-up times and weights while adapting them to the maintenance decision making.

Definition 3 . 3 . 7 .

 337 The dominance matrix W helps to identify the subset of tasks to be scheduled among the set of tasks and is defined by:

Figure 1 .

 1 Figure 1. Definition of Dik(t)

Figure 2 .

 2 Figure 2. Experiment results and their lower bounds for three data sets On figure 2, the mean weighted flow-time solutions obtained, respectively with the HPRTWF and the SWRPT-based algorithms correspond respectively to the MWFT (mean weighted flow-time) curves and the LB_MWTF (lower bound of the mean weighted flowtime) curves. The three numerical experiments clearlyshow that the results of the HPRTWF algorithm are very close to the lower bound. In these results, for more than 80% of the experiments the difference between the mean weighted flow-time and the lower bound is less than 20% of the mean weighted flow-time, and less than 8% for more than the half of the experiments. The computing times for all the results summarized in Table1did not exceeded 0.033 CPUs. These results confirm that the

Proposition 2.2.1. Tasks relative

	to the same Equipment
	Eik are linked by a precedence constraint defined as
	hereafter. If cm,ik is the completion date of the m th
	preventive maintenance task on Eik, then the (m+1) th task's
	release date is determined by rm+1,ik = cm,ik +tik, where tik
	is defined in the expression (2.2)

Proposition 2.2.2. Problem (P1) is NP-hard.

Table 1 .

 1 below. The CPU times are expressed in seconds. Table of CPU processing times (in CPU seconds)

		Figure 3. Mean weighted flow-time (100 to 500 tasks)
	the sets	100 tasks 200 tasks 300 tasks 400 tasks 500 tasks
	Set 1	0.035	0.28	1.05	2.61	5.54
	Set 2	0.038	0.29	1.06	2.62	5.29
	Set 3	0.031	0.29	1.06	2.59	5.22
	Set 4	0.031	0.29	1.06	2.79	5.26
	Set 5	0.033	0.29	1.07	2.64	5.29
	Set 6	0.035	0.29	1.07	2.64	5.33