Mohamed Karim Haouchine
email: karim.haouchine@ens2m.fr

Brigitte Chebel-Morello

Noureddine Zerhouni
email: zerhouni@ens2m.fr

Case Base Maintenance Approach *

Keywords: Knowledge-based systems, case-based reasoning, case-base maintenance, competence, case deletion strategies

Case base Maintenance is an active Case Based Reasoning research area. The main stream focuses on the method for reducing the size of the case-base while maintaining case-base competence. This paper gives an overview of these works, and proposes a case deletion strategy based on competence criteria using a novel approach. The proposed method, even if inspired from existing literature, combines an algorithm with a Competence Metric (CM). A series of tests are conducted using two standards data-sets as well as a locally constructed one, on which, three Case Base Maintenance approaches were tested. This experimental study shows how this technique compares favourably to more traditional strategies across two standard data-sets.

Introduction

Case Based Reasoning (CBR) is an approach to problem solving and learning, by reusing the solutions to similar problems stored as cases in a Case Base CB [START_REF] Aamodt | Case-based reasoning: Foundational issues, methodological variation, and systems[END_REF]. An experience is explained in completely structured formats or sizes such as objects or computer data in data-bases [START_REF] Lamontagne | Textual Reuse for Email Response[END_REF]. A case is an experience and an explanation during the episode of problem decision. Representation of cases is very diverse according to the nature of the task: diagnosis, planning, decision-making help, conception and so on [START_REF] Fuchs | Representing knowledge for case-based reasoning: the rocade system[END_REF]. However, case is composed of two options: a description of the situation that represents a "problem" and a solution used to solve the given problem in this situation [START_REF] Mille | Raisonnement basé sur l'expérience pour coopérer à la prise de décision[END_REF]. A case is placed in a CB and is called source case in which one will get inspired to solve a new case that we will call target case. A CB is a collection of decision-making cases of the same problem [START_REF] Mille | Raisonnement basé sur l'expérience pour coopérer à la prise de décision[END_REF]. A general CBR cycle may be described by five processes [START_REF] Mille | Modèle conceptuel du raisonnement basé sur les cas[END_REF]:

1. DEVELOP the representation cases 2. RETRIEVE the most similar case or cases 3. REUSE the information and knowledge in that case to solve the problem 4. REVISE the proposed solution 5. RETAIN the parts of this experience likely to be useful for future problem solving A new problem is solved by first, developing a target case that consists in developing case, by possibly supplementing the description of the new problem, then by retrieving one or more cases of the CB, reusing the case and revising the solution if need be, and retaining the new experience by adding it in the CB. Our field of study is diagnosis. For a case-based diagnosis system, the quality of case data is usually a key factor of the success of the system. In our research, we are facing a diagnosis problem in a product domain. We developed a case based reasoning system [START_REF] Karim | Maintenance d'une base de cas dédiée au diagnostic et à sa réparation[END_REF], and now our problem focused in the maintenance of this system. In effect, all mature information systems, more particularly; CBR systems need to be maintained while functioning, to guarantee the quality of the system. Indeed, the maintenance of the CBR system becomes necessary for all systems that are made to work for long periods and/or are developed to deal with large amounts of information and cases. In the section 2, CBR systems, the objectives for having good quality systems and the different problems that can be seen over time and therefore the need to carry out maintenance operations will be detailed. Subsequently, a CBR study for maintenance will be explained in section 3. The CBR system arranges different knowledge sources, which can be maintained, the knowledge sources of the CB is of interest and therefore it will be elaborated in the fourth section. Finally, we will present the proposed method that consists of deleting cases after the competence criteria, before optimising the CB. The obtained results and also the comparison with different -already existing-methods will be presented in sections 7 and 8.

Historic of CBR systems

The CBR approach has been used in many industrial systems to solve problems in various implementation fields or domains. The development of CBR systems always bumps into an engineering knowledge problem. The representation and the organisation of cases, as well as specific knowledge that can take place during operations, cover an essential importance in the conception of a CBR system. To elaborate a relevant case that can reflect a common problem and expressed in coherent terms regarding the knowledge base and the adaptation of knowledge are difficult to form, the functionalities of training are limited and therefore these kinds of systems are often confronted to this difficulty [START_REF] Mathieu D'aquin | Raisonnement à partir de cas décentralisé pour le Web sémantique[END_REF]. A CBR system is a combination of processes and knowledge, often called "Knowledge containers" that allows to preserve and to exploit previous experiences [START_REF] Lamontagne | Using Statistical Word Associations for the Retrieval of Strongly-Textual Cases. Special Track on Case-Based Reasoning[END_REF]. Knowing that a knowledge base system, interested in the conception of CBR applications, also needs to be interested in the tools of knowledge representation. A Knowledge Base System (KBS) is generally seen as the automatic solution for human knowledge in a limited field of expertise [START_REF] Luxhojl | Knowledge-based systems: for maintenance[END_REF]. It is acquired to have a Knowledge Base (KB) that represents the total of knowledge with the help of a representation-language of knowledge. KB takes part of an expert system that consists out of all information, in particular rules and facts, which constitute the competence field of the system [START_REF] Frans Coenen | Verification, Validation and Integrity in Knowledge and Database Systems: Future Directions[END_REF]. The conception and the development of CBR systems are like every knowledge base systems, quite complex processes. Special environments are made to propose different methods and tools to guide conception, modelling and application of a CBR. One of the first CBR systems is CYRUS, which has been developed by Janet Kolodner. It is a system that retraces actions that revolve CYRUS Vance in its position as a state secretary [START_REF] Kolodner | Case-Based Rasoning[END_REF]. Kolodner implements the ideas of SCHANK, which means a structure of dynamic memories for searching information. A lot of systems are therefore developed according to the SCHANK model, but for different tasks like CHEF, or JUDGE [START_REF] Koton | Using experience in learning and problem solving[END_REF] or according to other models, for example a prototype model such as PROTOS [START_REF] Bareiss | PROTOS: An Exemplar-based Learning Apprentice[END_REF]. CBR are also inspired by analogical reasoning and is considered as a particular case. The successive works or actions with CBR have worked in order to realise information tools to solve problems, to press one's finger entirely on this specific reasoning. If the first researches were the solution of cognitive psychology, present-day researches are plural-disciplinary. Actually, numerous works or actions tent to use CBRs to complete other methods such as systems based on rules or systems based on models [START_REF] Kumar | Integration of case-based reasoning and model-based reasoning for adaptive design problem-solving[END_REF], or even using neural networks [START_REF] Malek | Hybrid approaches for integrating neural networks and case based reasoning: From loosely coupled to tightly coupled models[END_REF]. These systems are known as hybrid systems. CBR supply a preliminary sketch of exploitable solutions by a different reasoning model that avoids constructing completely a solution in a potential immense space.

The majority of CBR systems explain problems concerning case-research phase as well as their adaptation that can be expensive in time. To come straight with their problems, maintenance of CBR systems become necessarily for all systems that are build to work for long periods of time and/or are developed to deal with large amounts of information and cases. The growing request of CBR system maintenance led to intensive researches in the concerned fields [START_REF] Reinartz | Review and restore for Case Base Maintenance[END_REF].

Maintenance of a Case-Based Reasoning System

The performance objectives for a CBR system provide criteria for evaluating the internal behaviour and task performance of a particular system for a given initial CB and sequence of a solved problem. The choice of casebase maintenance strategies is driven by the maintainer's performance goals for the system and by constraints on the system's design and the task environment [START_REF] David | Guiding Case-Base Maintenance: Competence and Performance[END_REF]. In general, there will be multiple performance measures for a CBR system, and there is no guarantee that all of them can be maximized simultaneously. Smyth and McKenna define three types of top-level goals for CBR systems [START_REF] Smyth | Footprint-Based Retrieval[END_REF]:

1. Problem-solving efficiency goals (e.g., average problem-solving time)

2. Competence goals (the range of target problems solved)

3. Solution quality goals (e.g., the error level in solutions)

Therefore, a CBR system needs some sort of policies to achieve its maintenance goals. Its effectiveness depends on the speed and quality of the case base retrieval process, and it is related to the definition, the case representation, the CB organization, the various indexation used, and the definition of "good" similarities measurements for case search and the relation of retrieval-adaptation case. CB represents the memory and the main part of CBR systems, it can be flat or hierarchical, it contains elaborate cases which represent the experiments; an experiment constitutes a lesson which makes it possible of CBR system to achieve its goals. The information contained in a case depends on the applicability of objectives for which this case is built. In CB, we find cases which are composed of two parts, problem and solution parts. The CB is considered to be the core of any CBR system. This fact, pushed many research orientations, towards the involvement of CB Maintenance (CBM) [START_REF] David | Guiding Case-Base Maintenance: Competence and Performance[END_REF]. The knowledge of CBR systems relates directly to cases, affected by changes in knowledge sources. Moreover, the CB source may be considered as that most sensitive knowledge source for CBR systems. Thus, consulting it may be the most appropriate approach to overtake maintenance operations. When the CB size increases, the search time, increases accordingly. This leads to the increase of problems resolution time, inducing to performance degradation [START_REF] David | Categorizing case-base maintenance: dimensions and directions[END_REF].

Case-Base Maintenance

Case-base maintenance implements policies for revising the organization or contents (representation, domain content, accounting information, or implementation) of the CB in order to facilitate future reasoning for a particular set of performance objectives [START_REF] David | Categorizing case-base maintenance: dimensions and directions[END_REF]. Note that this definition considers the information defining an indexing scheme to be an intrinsic organizational component of the CB itself. CBM may involve revising indexing information, links between cases, and/or other organizational structures and their implementations [START_REF] Smyth | Tasks and Methods in Applied Artificial Intelligence[END_REF].

Maintenance in CBR may involve a number of different operations: out dated, redundant or inconsistent cases may be deleted; groups of cases may be merged to eliminate redundancy and improve reasoning power; cases may be re-described to repair incoherencies etc [START_REF] Smyth | Tasks and Methods in Applied Artificial Intelligence[END_REF].

CBM Policies

CBM approach may be divided into two policies, one concerning optimization and the other partitioning of CB (See Figure 1). The CB approach aims to reduce case research time. This may be done, on one hand, following an optimization policy that deletes least relevant cases, using case addition or deletion strategies. On the other hand, following a partitioning policy, permitting the retrieval of distributed CBs using an attribute selection case scheme. Therefore, the attribute with rich-information content are selected, and may possess more potential to cover a wider CB structure [START_REF] Yang | Keep it simple: A case-base maintenance policy based on clustering and information theory[END_REF]. The partitioning policy, allows the addition and deletion of cases in each small CB, without affecting the whole; one may cite several works using of dynamic or static neural network [18] [25]. However, there are many different ways to evaluate the quality of a CB. This is described in the following section.

Criteria for Evaluating Case Base

An "effective" CB is able to answer as many queries as possible efficiently and correctly. The criteria by which one can judge the effectiveness of a CB are given in [START_REF] Roth | Six Steps in Case-Based Reasoning: Towards a maintenance methodology for case-based reasoning systems[END_REF], [START_REF] Smyth | Remembering To Forget: A competence Preserving Deletion Policy for Case-Based Reasoning Systems[END_REF], [START_REF] Yang | A case addition policy for case-base maintenance[END_REF]. Those of interest to this work are:

• Competence, measured by the range of problems that can be satisfactorily solved.

• Performance, measured by the answer time that is necessary to compute a solution for case targets. This measure is bound directly to adaptation and result costs.

• Coverage of a case is the set of target problems that it can be used to solve. • Reachability of a target problem is the set of cases that can be used to provide a solution for the target.

After having given the definitions of the different criteria that permit the evaluation of a CB, we are going to see how they are used and estimated in the different CBM strategies. In the following paragraphs, two strategies will be developed; the addition-case and the deletion-case.

Case-addition Strategy

By the successive addition of cases to a virgin CB, reduced CB will be constructed, thus maximizing criteria. There are two methods, one maximizing the competence criterion, and the other the performance criterion.

Method maximizing the criteria of competence

Smyth and McKenna present a method that uses an explicit case competence model based on notions of coverage and reachability. Their "relative coverage" (RC) metric, provides a precise measurement of competence contributions for individual cases. The RC metric, associated with the condensed nearest-neighbour (CNN) algorithm, permits to successively retain only those cases which are not solved by a case that has already been retained, in order to obtain a new reduced CB [START_REF] Smyth | Building Compact Competent Case-Bases, Case-based reasoning research and development[END_REF]. This permits the selecting of cases, which have a big contribution concerning the CB recovery.

Q. Yang and J. Zhu describe a case-addition algorithm for CB compaction that uses a problem-neighbourhood model of case coverage. Cases are successively added based on added benefit/usefulness to the case set retained so far [START_REF] Yang | A case addition policy for case-base maintenance[END_REF].

Method maximizing the criteria of performance

By analogy to the RC metric, Leake and Wilson developed a relative performance (RP) metric aimed at assessing the contribution of a case to the adaptation performance of the system [START_REF] David | Remembering Why To Remember: Performance-guided case-base maintenance[END_REF]. To attain the benefit of adding the case to the CB, they first assume that the similarity metric will accurately select the most adaptable case for any problem. For each case that might be added to the CB, its contribution was estimated as regards to adaptation performance. The RP value for a case reflects how its contribution to adaptation performance compares to other cases. This metric can be used to guide case addition, favouring cases with low RP values. In the same manner, another metric was developed concerning a "performance benefit" (PB) metric estimating the actual numerical savings that the addition of each case provides. However, on one hand, the RC-CNN method provided a reduction rate of the CB size, better than the PR-CNN and PB-CNN methods. On the other hand, these two previous methods give a result concerning the adaptation cost of the CB cases better than RC-CNN.

Case-deletion Strategy

From a given CB, this strategy values case according to criteria in order to be able to suppress and bring the CB to a specified number of cases. The evaluation criteria such as competence, redundancy and inconsistency, have been used in different methods, which will be explained down bellow.

Suppression Method for using case-base screening

In this method, when the CB reaches a certain threshold it is screened entirely, usually followed by the process of case-deletion.

-Random Deletion is a very simple, inexpensive method and it is completely domain independent. Simply randomly select and delete a case from the CB once the CB size exceeds some predefined limit [START_REF] Markovitch | The Role of Forgetting in Learning[END_REF].

-Ironically, is a slightly more complicated method, it calculates the frequency of each case that is retrieved and it deletes cases which are not frequently accessed in the CB [START_REF] Minton | Qualitative Results Concerning the Utility of Explanation-Based Learning[END_REF].

-Utility Deletion (UD) is based on Minton's utility metric which chooses a case item for deletion by estimating its performance benefits. This utility deletion method removes case items with negative utility [START_REF] Smyth | The Utility Problem Analysed: A Case-Based Reasoning Perspective[END_REF].

The utility problem manifests itself as a trade-off between the solution quality associated with large CBs and the efficiency problem of working with a large CB. System efficiency is measured by taking the mean time to solve a target problem; note that the decreasing solution times correspond to an increase in efficiency. The solution quality is bound to the percentage of good answers, provided by the system. Solution quality increases with CB size [START_REF] Smyth | Modelling the Competence of Case-Bases[END_REF].

-Deletion based on redundancy and inconsistency contains two modules of detection, one with redundancy and the other with inconsistency. After a series of test concerning each CB case, by these two modules, the specific cases can be removed -or kept-after the user approval [START_REF] Racine | On the consistency Management of Large Case Bases: the Case for Validation[END_REF].

-Deletion based on CB size and density, this deletion method was proposed by B. Smyth and M.T. Keane and it studies the size of the CB, the density and the distribution of cases in a CB. It tries to homogenize the case density [START_REF] Smyth | Modelling the Competence of Case-Bases[END_REF].

Method from categorization of the cases

These methods, call on a modelling of the CB competence, proposed by B. Smyth and M.T. Keane [START_REF] Smyth | Modelling the Competence of Case-Bases[END_REF], [START_REF] Smyth | Footprint-Based Retrieval[END_REF], [START_REF] Smyth | Special Issue on Maintaining Case-Based Reasoning Systems[END_REF] and [START_REF] Yang | A case addition policy for case-base maintenance[END_REF]. Cases in the CB are categorized according to their competence. The key concepts in categorising cases are coverage and reachability. -Footprint deletion: this strategy works to remove irrelevant cases by guiding the CB towards an optimal configuration. Optimal in the sense that it maximises competence while minimising size. The case categories described above provide a means of ordering cases for deletion in terms of their competence contributions. Auxiliary cases are selected for deletion before support cases, which in turn are chosen before spanning and pivotal cases. The optimal CB can be constructed from all the pivotal cases plus one case from each support group. This strategy is not designed to eliminate the need for performancebased methods such as utility deletion [START_REF] Smyth | Remembering To Forget: A competence Preserving Deletion Policy for Case-Based Reasoning Systems[END_REF].

-Footprint Utility deletion: is the hybrid strategy between footprint deletion and utility deletion. First, the footprint method is used to select candidates for deletion. If there is only one such candidate then it is deleted. If there are a number of candidates, therefore rather than selecting the one with the least coverage or the largest reachability set, the candidate with the lowest utility is chosen [START_REF] Smyth | Remembering To Forget: A competence Preserving Deletion Policy for Case-Based Reasoning Systems[END_REF].

Methodology

Keeping in mind that no metric was developed in most case suppression approaches, a suppression method using a novel algorithm associated to a Competence Metric (CM) is proposed for CB optimisation. This method is a combination of Smyth and Keane approach [START_REF] Smyth | Remembering To Forget: A competence Preserving Deletion Policy for Case-Based Reasoning Systems[END_REF] and the Relative Coverage metric [START_REF] Smyth | Building Compact Competent Case-Bases, Case-based reasoning research and development[END_REF].

RC(c) = ∑ ∈ ) ( ' ') ( Re 1 c t CoverageSe c c Set achability (1)
Therefore, the developed metric is based on the notions of recovering and reachability. CM is defined as the individual contribution to a case as regards to its recovering group size by attributing two values, noted recovering value (Vr) and, reachability value (Va).

CompetenceMetric(c) = Vr(c)/Va(c)
This metric is used as a benchmark for the suppression of cases within the CB. The cases which have a high CM value are favoured while the rest are dropped. The algorithm developed is as follows:

• Calculate the Vr and Va value of every case in the CB using the K Nearest Neighbour (KNN) algorithm with Euclidean norm, dsc = [ ∑ = p i 1 (xs -xc) ² ] 1/2 (p represents the total number of attributes).

• Associate to each case its recovery unit and its reachability factor • Determine the support cases and the support groups of each class and sort them according to their CM values

• Suppress the support cases with the lower CM values, keeping one case from each group with the most important CM

• Determine auxiliary inter and intra classes

• Suppress auxiliary cases according to their CM values

• Stop the algorithm if and only if each case covers its own case among existing ones, in its own class Algorithm 1. Algorithm of the implemented method

This method aims at reducing the CB size by preserving maximum competence.

Experiments

The used method is based on a specific model of competence for case-based reasoning. We argue that it has more potential for guiding the construction of smaller CBs than some existing editing methods without compromising competence, specifically CNN on its own, CNN with NUN and RC distance ordering. In this section we compare the size, the reduction rate and competence of the CBs produced using different editing techniques on a range of standard data-sets. Knowing that NUN "Nearest Unlike Neighbor" is a concept which started from the idea that examples belonging to different classes are close only if they are close to the borders of the respective classes. For a base with Nc classes, Nc -1 NUN (one per class) of each example are identified. Subsequently, the NUN of all initial base examples is gathered. The NUN Subsets are created which can be seen as optimal borders representatives between the classes belonging to the base. The CNN algorithm was the first reduction technique for the reference base size, based on static considerations [START_REF] Belur | Nearest Neighbor Norms: NN Pattern Classification Techniques[END_REF]. The algorithm aims at reducing the entire input space into a representative subspace with the same properties.

Four different editing techniques are compared for this experimental study 1) CNN-the standard CNN approach; 2) NUN -CNN with cases ordered according to their NUN distances; 3) RC -CNN with cases ordered according to their relative coverage values; 4) CM with cases ordered according to their CM values and according to the following associated algorithm. [START_REF] Blake | UCI Repository of machine learning databases[END_REF] .The third CB relates to an industrial diagnosis dedicated to an E-maintenance high board (SORMEL) [START_REF] Karim | Maintenance d'une base de cas dédiée au diagnostic et à sa réparation[END_REF] (69 cases, 10 attributes and 9 classes). In the latter, the class to be found is an equipment class to be repaired, and that is formalized in example form.

7

Assessment of the proposed method

In the SORMEL CB, the space is taken from the target cases represents the total CB space. Firstly, by applying the algorithm, prior to the cases suppression, the following results were obtained: The obtained results are promising and by applying the proposed method on the SORMEL CB, a reduced CB obtained. Indeed, the obtained CB is roughly reduced by half, keeping the same initial competence.

Comparative study

In this section, the sizes of the CBs as regards their competence on unseen target problems are compared. Each editing strategy is used to generate CBs for the 3 used data-sets. However, this time 100 random test problems are removed from the training set before CB construction. The final size of the CBs and their competence over the 100 test problems is noted. The upper value in each cell is the value of the "credit" CBs and the lower value is the value of the "Ionosphere" CBs. The results are shown in From Table 2, it can be clearly seen that the reduction rate provided by the developed approach is notably higher than the one provided by the three traditional approaches, particularly for the "Credit" data-set. The competence value is significantly better for the "Credit" data-set; however, it is almost the same as the traditional method concerning the "Ionosphere" data-set. Here, is the graph with the results from the comparison study: As in figure [START_REF] Bareiss | PROTOS: An Exemplar-based Learning Apprentice[END_REF], the CM method is better than the other approaches at achieving a cases reduction rate which has competence more for both data-sets "Credit" and "Ionosphere". Figure (3) focuses on the variation of the competence concerning the reduction ratio of the data-sets which is obtained by using the CM metric.

(a) Credit data-set (b) Ionosphere data-set Fig. 3. Competence versus reduction rate with CM method It can be seen that for both data-sets, competence can although it has keeps the same reduction rate. This implies that the competence and the size of the data-sets obtained after suppression are highly dependant on the sample chosen cases. It can be seen that for both data-sets, competence differs although it keeps the same reduction ratio. This implies that the competence and the size of the data-sets obtained after suppression, is highly dependant on the sample chosen cases. It is noted, that with a larger data-sets size, a larger competence value is obtained for the "Credit" base. However, the opposite is verified for the "Ionosphere" base.

Conclusions and future work

Three Case Based Maintenance methods (CNN, RC-CNN and NUN-CNN) were tested over three data-sets. These data-sets representing classification problems. The proposed method which used a novel algorithm combined with a Competence Metric (CM) is more efficient in terms of Case-Base reduction size and competence when applied to the studied fields.

Following this project, we plan to elaborate a method that is more complex and will merge our competence measure with a different performance measure to obtain an optimal Case Base. Finally, we will further investigate complete CBR systems.

Fig. 1 .

 1 Fig. 1. Different strategies and criteria used in CBM

  Given a case-base C = {c1,…, cn} and c© is the set of target cases in the CB. Formally: -Coverage(c) = {c©∈C: Adaptable (c, c©)}, For c∈C, -Reachable(c) = {c©∈C: Adaptable (c©, c)}, For c∈C, As a result, 4 categories of cases are considered: • Pivotal Cases: Pivot(c) iff Reachable(c)-{c}= Ø • Support Cases: Support(c) iff  c©∈ Reachable(c)-{c}: Coverage(c©) ⊂ Coverage(c) • Spanning Cases: Spanning(c) iff Pivot(c) Λ Coverage(c) ∩ U c©∈ Reachable(c)-{c} Coverage(c) ≠ Ø • Auxiliary Cases: Auxiliary (c) iff  c©∈ Reachable(c)-{c}: Coverage(c) ⊄ Coverage(c©)

Fig. 2 .

 2 Fig. 2. Comparison of the different strategies

Figure ( 4 )Fig. 4 .

 44 Figure[START_REF] Frans Coenen | Verification, Validation and Integrity in Knowledge and Database Systems: Future Directions[END_REF] shows the variation of the competence as regards the data-sets size which is obtained by using the CM

  In order to strengthen the comparison, three different CB are used. Tow, Credit (690 cases, 15 attributes and 2 classes) and Ionosphere (351 cases, 34 attributes and 2 classes), represent classification problems from the UCI Machine Learning Repository (www.ics.uci.edu/~mlearn/MLRepository.html)

	O-SET Original training example
	E-SET	{}
	Changes true
	While Changes Do
	Changes false
	For each case C ∈ O-SET Do
		If E-SET cannot solve C Then
		Changes true
		Add C to E-SET
		Remove C from O-SET
		EndIf
	End For
	EndWhile
		Algorithm 2. Condensed Nearest-Neighbour Algorithm

Table 2 :

 2

	Property/Method	CNN	NUN	RC	CM

Table 2 .

 2 A comparison of different editing strategies over the Case-Base test in terms of mean case-base size, reduction rate and competence.


François Marmier
email: fmarmier@ens2m.fr

Christophe Varnier
email: cvarnier@ens2m.fr

Noureddine Zerhouni
email: nzerhouni@ens2m.fr

Dynamic Scheduling of Maintenance Activities Under Uncertainties

Keywords: Competence, Human Resources, Lateness, Maintenance, Scheduling, Tasks Insertions, Uncertainties, Unrelated Parallel Machines

Competencies management in the industry is one of the most important keys in order to obtain good performance with production means. Especially in maintenance services field where the different practical knowledges or skills are their working tools. We address, in this paper, the both assignment and scheduling problem that can be found in a maintenance service. Each task that has to be performed is characterized by a competence level required. Then, the decision problem of assignment and scheduling lead to find the good resource and the good time to do the task. For human resources, all competence levels are different, they are considered as unrelated parallel machines. Our aim is to assign dynamically new tasks to the adequate resources by giving to the maintenance expert a choice between the robustest possibilities.

Introduction

To stay competitive, companies must decrease their costs as much as possible and optimize their production means operations. In order to support better equipments' availabilities, and through them the company one, the maintenance service intervenes. It deals with problems before or after the breakdowns, at any place. This improvement mainly requires a better management of the workforce and its competencies.

It is difficult to determine precisely the required human resource number in a maintenance service [START_REF] Mjema | An analysis of personnel capacity requirement in the maintenance departement by using a simulation method[END_REF]. Indeed, factors making enabling capacity adaptation are prone to uncertainties. Those are due to several parameters (variations of the intervention requests which are never similar, arrival dates of requests, requests' contents, required treatment duration and equipments availabilities as well as elements related to the real intervention treatments). Thus, the different tasks are well known when they occur. The reactivity and the organization of the maintenance service will depend on the importance of the required treatment.

There are mainly two types of maintenance activities: the preventive maintenance, whose activities can be long term planned, and the corrective maintenance which is related to the non foreseeable breakdowns. Within the service of maintenance, employees have different competencies and different qualification levels. Treatment speed and thus the service reactivity will depend on the choice of the employees assigned to the task.

We give in this paper a method to take care of the new tasks apparition and we propose a decision support to insert it in the current schedule. We work on the case where the task assignment has already been realized (for example with the heuristique presented in [START_REF] Marmier | Maintenance activities scheduling under competencies constraints[END_REF]). The goal is to disturb as less as possible the current schedule. However, the whole schedules are subject to uncertainties and variation between theory and reality. In order to propose insertion solutions for a new task, we have to determine which places in the schedule are the more flexible in order to obtain a scheduling which would be the most robust (the less sensible to uncertainties). The fact to propose schedule solutions taking care of variation by anticipating show that our scheduling method is proactive.

In this article, we detail a methodology which will allow us to assign tasks to resources by considering disturbances. The rest of the paper is organized as followed: In the second section, we will introduce how maintenance services can be managed. In the third part, we will present our scheduling problem. Then we develop our model and a resolution approach. Finally, we will discuss the different obtained results.

MAINTENANCE MANAGEMENT

There are various forms of management of maintenance. Indeed, if the company itself does not assume maintenance, this one can then be sub-contracted. The monitoring, the preventive and corrective maintenance can thus be entrusted directly to the manufacturer of the equipment (expert on this type of equipment) or with a company specialized in industrial maintenance (expert in monitoring and in remote maintenance field but general practitioner as for the monitored equipment). The equipment can also be rented, and if maintenance is not assumed by the user company, it can be sub-contracted too.

Tasks management

A maintenance service has to answer to its customers service demand. To do so, it disposes of human and material resources. Human resources are all different due to their qualification level in the required technical fields. Human resource being in limited number. Each operator can perform only one task at any time. The duration of a task will depend on the resource assigned to and their competencies. However, all the resources must be occupied. Then it will not necessary be the most efficient resource who will be assigned to the task's treatment. The tasks' assignment corresponds to a succession of tasks within human resources working time.

The maintenance distant management has its own computerized way of communication. When a breakdown occurs, the service asking for a maintenance intervention makes a work request. This one is recorded in the Computerized Maintenance Management Systems databases (CMMS) and contains the problem informations. These informations will help the maintenance service to determine which resource will be assigned to the task treatment.

Regularly, the maintenance service manager collects the work requests in the databases from the expert station (figure 1). The expert station corresponds to the manager work computer on which will be realized the assignment process. When the manager has collected data, with the help of the scheduling program, he assigns tasks. He determines for each maintenance task, the best timing in employees planning. Then he published assignments as work orders in the databases which are consultable on all computers connected to the databases.

Human resources management

The human resource are not considered as identical, then the assignement decision has to take care of several parameters.

Competencies management

Boumane and al. [START_REF] Boumane | Contribution méthodologique à la construction d'un référentiel de compétences en maintenance industrielle[END_REF] studied the different competency types which can be generic and used in various professional situations, or specific to the activity. During her thesis, Agnès Letouzey carried out a study on nineteen companies to obtain their opinions on the operators' assignment problem [START_REF] Letouzey | Ordonnancement interactif basé sur des indicateurs : Application à la gestion de commandes incertaines et à l'affectation des opérateurs[END_REF]. It shows that operators' management, according to their competencies, is important for industry leaders and that there is still no software taking this into account. 79% of the companies think that operators' management is useful or essential in scheduling. Whereas in current softwares the operational duration is fixed, for the industry leaders, the consideration of the operators' qualification is very important to determine their assignments. For them, the qualification level has (sometimes for 47% of them and always for 27% of them) an influence over the task's duration of realization. It appears the need for further development linking the competencies of human resources and the operational durations like in the determination of the potential of the company. However, if the competency levels of each one are known, an other problem has to be solved : balancing the workload of resources and try reach a compromise between the reactivity and the perturbation due to the modification of the employees planning.

A parallel machine problem A maintenance service is an environment composed of m operators working in parallel. We assume that all can perform each task, but not with the same efficiency. Moreover, the resource which is the most effective for a task, would not necessary be effective for all tasks.The multiplicity of competencies shows that we have a parallel machine problem, but with unrelated machines which is noted R or R m | β| γ , [START_REF] Pinedo | Scheduling, Theory, Algorithms and Systems[END_REF] [3].

CONTEXT OF THE PROBLEM

In scheduling and planning, the time horizon is often split in periods (the short, medium and long term). Then, we can study events on each time interval and not on a continuous scale of time. The context of this article takes place in the short term horizon. In this approach, we consider that maintenance tasks have to be scheduled when they occur (generally it is the case of corrective maintenance). The manpower is then the limiting factor in the scheduling realization. Human resources are then organized in the maintenance service which has to plan their work.

Equipment

Within each plant, the maintenance service has to maintain equipment under operation. The level of the results to reach by the maintenance services is generally predetermined. Either a contract is signed between two (or more) partners fixed their cooperation terms, or there is a moral agreement inside the compagny between production and maintenance service, that fixe the equipment efficiency required. In both case, the objectives of the maintenance are defined by a level of availability (that can be different from one equipment to another). The guaranteed availability is a percentage of the opening time. This one is located in a range of value (a class). If, for a machine or a group of machines, the objective of availability is not achieved, penalties have to be paid by the service provider. Conditions concerning the penalties are defined while elaborating the contract and are function of the non availability duration. We will consider in our model the minimisation of those penalties.

Tasks

On medium-term, the maintenance service has to plan and assign the best human resource for the treatment of the different maintenance tasks. Preventive and conditional maintenances have for parameters a known duration, a starting date: r j and a completion date: d j . The corrective maintenance tasks generally occurs in the short-term horizon. They also have a duration, which is only evaluated since it depends on a correct diagnosis. Their earliest starting date r j is not necessarily immediate, since spare parts are not necessarily available (they can be expected from a supplier) or the availability level of the equipment is quite good and then the intervention can be done latter. These characteristics of maintenance tasks allow us to use the same model. The task j is composed by a face duration p j and the type of competence required (for example, the competence could be mechanic, electricity, automation or a certification). The competence required will be denoted as an integer value k with (k = 1...o). The effective duration of a task j will be known only when we will know the resource that will perform it.

Human resources

The maintenance service is composed by m human resources (i = 1...m), characterized by a competence profile. Relative speeds do not depend only on the tasks. Each resource has a corresponding qualification level for each task. Operators will perform them more or less quickly. The duration of the job j, by the human resource i is denoted by p ij . With:

p ij = f (p j , C ik ), ∀i ∈ {1, ..., m} (1)
Where C ik is the competence rate of resource i in the competence which is required to achieve the task type k. It can be represented with a matrix in which, for each different kind of job, the rate corresponding to the required competence can be found.

     C 1,1 • • • C 1,n . . . . . . . . . C m,1 • • • C m,n     
The treatment duration of two different tasks by two different resources enables observing that for one kind of task, a resource can be more powerful than one other, whereas, for the second task, it is the second one which is the most effective.

SCHEDULING PROBLEM WITH UNCERTAINTIES

Problem syntheses

In this problem while tasks have not been really treated, their data are stochastic. In order to propose a robust (and proactive) solution, our simulation will consider variations on release-dates, due-dates and of course on the duration of each tasks within the scheduling.

Scheduling under uncertainty

In classical scheduling problems, the data are generally supposed to be known and fixed. However, the reality does not check this hypothesis, of course because of variations, but also because a lot of data are only previsions or estimations. Optimal solutions to such scheduling problems which are based on fixed data and do not show the reality, will have only few chances to be applicable and will be subject to modifications.

In the existing model taking into account uncertainty, we find mainly the Davenport and Beck one which present three approaches: proactive, reactive and proactive-reactive approaches [START_REF] Davenport | A survey of techniques for scheduling with uncertainty[END_REF]. Proactivity is the fact to anticipate disturbances before that they really occur. Reactive approaches work in real time, during the scheduling phases. Proactive-reactive methodologies, will try to combined both approaches in order to take into account uncertainties during all the scheduling life cycle and ensure a maximum of performance [18] [10]. A schedule is robust if this performance is few sensible to data uncertainties and variations [START_REF] Billaut | Flexibilité et robustesse en ordonnancement[END_REF]. Moreover a schedule has to be flexible to be adaptable to the possible disturbance. We can identify a static flexibility as the temporal flexibility (concerning tasks starting date), the sequential flexibility (which authorises the permutation between tasks, and which supposes the temporal flexibility) or the assignment flexibility (which allows changing of resource after a first assignment). There is also the dynamic flexibility which is the scheduling capacity to adapt itself to disturbances [START_REF] Hoang | Utilisation d'ordres partiels pour la caractérisation de solutions robustes en ordonnancement[END_REF].

In this paper, we consider that, in a given schedule, task data are subject to more or less variations in order to be representative of the reality. Earliest and latest starting dates of each task may vary. Indeed, they are obtained from the tasks release-dates and due-dates, and variations on this one introduce modifications on the earliest and latest starting dates. Tasks durations may also be increased or shortened if the task treatment is longer or shorter than envisaged. Finally, the most delicate disturbance, that may happen, is a new task arrival which has to be inserted in the current schedule. Its parameters are of course subject to an estimation, and there precision depend on the diagnosis exactness.

Tasks insertion problems

We introduce quickly the different work in the literature, that deal with the scheduling disturbance problem. Monostrie and al. have made a state of the art of the proactive approaches and reactive approaches with disturbance [START_REF] Monostori | Management of changes and disturbances in manufacturing systems[END_REF]. Laguna and al. worked on minimizing the weighted lateness on parallel machine. Uncertainties are due to tasks interruptions by stop with a stochastic duration [START_REF] Laguna | Minimizing weighted tardiness of jobs with stochastic interruptions in parallel machines[END_REF]. Sun and al. presented an approach in order to take into account changes in production orders [START_REF] Sun | A dynamic reactive scheduling mechanism for responding to changes of production orders and manufacturing resources[END_REF]. They propose a reactive and dynamic scheduling methodology in order to modify the current schedule in case of additional work or suppression of existing work. Their approach considers machines breakdowns and employees absenteeism. Kis and al. but also Groflin and al. treat the tasks insertion problem in job-shop. They tried to minimize the scheduling total duration when a new task appears [11] [9]. In the Resource Constrained Project scheduling Problem, knwon as RCPSP, Artigues and al. consider a dynamic approach which is based on a first and static schedule [START_REF] Artigues | Insertion techniques for static and dynamic resourceconstrained project scheduling[END_REF]. They take into account two kinds of uncertainties [START_REF] Artigues | Allocation de ressources en planification de projets pour la construction d'ordonnancement in Flexibilité et robustesse en ordonnancement[END_REF]: the duration variation and the fact that new tasks can occurs. A polynomial algorithm has been developed in order to insert new tasks aiming to minimize the makespan increase. A project scheduling bibliography under uncertainties had been published by Herroelen and al. [START_REF] Herroelen | Project scheduling under uncertainty : Survey and research potentials[END_REF]. It considers reactive approaches, robust or proactive approaches and approaches with stochastic data. Their conclusion is: in the project management area, new work in order to develop mechanism to repair reactive schedule would be necessary. Duront and al. presented an approach for the radars management [START_REF] Duron | Insertion of random task in a schedule: a real-time approach[END_REF]. This approach integrate new tasks in a current schedule. New tasks duration and due-date are really known when the tasks appear, their objectives being to minimize the total lateness.

MODEL

Data

We first describe some notations needed for the explaination of the model. For each task j:

• p j : face duration of the task j (this duration will be subject to variation depending of the resource assignment), • d j : due date of the task j (this value is estimated in function of the current availability of the equipment concerned), • w j : penalty which could be claimed if the treatment of the task j is not performed on time.

Variables

The variables of our problem are the following ones for each task j:

• t j (j = 1...n) : starting of the task j, • x ij (j = 1...n and i = 1...m) : 0-1 value representing the tasks assignment. x ij = 1 if the task j is assigned to a resource i, else x ij = 0, • T j (j = 1...n) : lateness of the task j, • ES j (j = 1...n) : earliest starting date of the task j, • LS j (j = 1...n) : latest starting date of the task j.

Constraints

Each task has to be assigned only once to only one resource:

n j=1 x ij = 1, ∀i ∈ {1, ..., m} (2)
A task j cannot be planned before the equipment i is available:

∀j, t j r i (3)

Objectives

In order to consider corrective maintenance, we have to insert dynamically tasks in a current schedule. However it is difficult to insert tasks in a schedule which is subject to variations between the proposed one and the reality. In order to find new task insertion solutions, we have to determine which place are the most flexible and consequently propose the most robust schedule (the less sensible to variations). The fact to propose solutions taking into account variations by anticipating them, signify that our scheduling approach is proactive. Tasks which are finished late decreasing the equipment availability ratio imply that we have to minimize the total weighted tardiness.

min

n j=1 w j T j , (4)
The aim of our work beeing to schedule human resources activities, our methodology will take into acount their individual performances to find the best resource for each task. But it will also consider the existing workload in order to distribute activities between employees.

PROBLEM RESOLUTION

Graph modelisation

In our problem, we consider a current schedule (previously computerised). This schedule already integrates n tasks that had been already assigned to m human resource. The current schedule can be modelized as a graph. Its structure is represented on the first picture in the figure 2. The graph is a unit of branches which represent each one the a human resource schedule. They are composed of nodes which represent tasks and arcs which are the potential constraint between to tasks (precedence). The valuation of arcs are the duration of the origine task. Tasks are placed between a fictive beginning task B and fictive end task E. Moreover, each node is linked with the B node. This link is valuated by r ( i) and correspond to the constraint (3). There is no link between branches, because resources work independently. Bellmann long way algorithm can be performed to find earliest starting dates of each task (graph "Earliest Starting Date Graph" on the figure 2).

For finding latest starting time it is necessary to consider the due date of each task. We propose to construct a second graph, in which we keep the same node and the potential constraints as previously, but we add arcs between each task j and the fictive end task E. These new links are valuated, for each task j, by the difference between the branch last task due-date d B and d j -p ij (where i is the resource assigned to task j). Then, an adaptation of Bellmann algorithm allows to find (in reverse order) the relative latest starting time LS E j . We call LS E j , the relative latest starting time, since, for a resource i, it represents the duration between the end of the last task assigned to i and starting time of task j.

In both graphs presented on the right of the figure 2, we can not have any positive circuit, if they would have a lateness, we could not observe it. However, the difference between results obtain in each of them allow to know if we will have some lateness. It could occur that the earliest starting date of the task j ES j is after its relative latest starting date of the task j. But one task could not begin before its release date r j , then it is not possible to start a task treatment before its ES j . The real latest starting date of a task j is obtain as follow:

LS E j > ES j → LS j = LS E j ( 5
)
ES j > LS E j → LS j = ES j (6)

Time windows

In order to study the different place, within the schedule, where a new task could be inserted, we have to check time windows between tasks.

The computation of earliest and latest time for each task allows us to evaluate all the available time windows of the current schedule.

The situation, presented on the figure 3, describes a time window in a schedule. We observe here the classical case where earliest starting dates are before relative latest starting dates.

Insertion windows

A new task will have different characteristics which will allow us to evaluate the best place where insert it in the schedule. We have to search window large enough within time windows which are localized between the release-date and the due-date of the new task.

Windows will be sorted by their robustness level. If there is no window large enough within the totally robust windows, we will extend our research trough the most robust windows we can find. Within a windows set with an equivalent robustness level, we will work on ours secondary selection criteria which are the load balancing between ressources and the minimisation of the total working duration. Then we select the window which,after insertion, will minimize the workload standard deviation. As describe in figure 4, the deduction of the adequate insertion window will be done by variation simulation on the scheduling. The current planning and its possible variations will be simulated hundred times in order to obtain datas concerning the windows robustness.

In the next simulations, we will compare two cases. The aim of the first one will be to find the best location place to insert a new task as the maintenance manager would do it. The choice will be done by throuh minimisation of the workload standard deviation on the totality of the proposed windows. The second one has the same objective but it will use our methodology by simulating disturbances on the existing planning. That means that we will have to find the robustest insertion windows for new tasks. The minimisation of the workload standard deviation will be applied only on the set of the robustest windows.

Fig. 4. Task insertion methode

After each task insertion the current planning is modified. Then, in case of a next insertion task, the new obtained planning will be used as the current planning and the last inserted task will also present variations.

computational method

As announced previously, we work in the case where a current planning exists. We will use the heuristic presented in [START_REF] Marmier | Maintenance activities scheduling under competencies constraints[END_REF]. Disturbance will be randomly generating on this planning, in order to observe the reality impact. Tasks which check ES j > LS E j does not have neither freedom movement degre nor temporal flexibility. They are also the sign of lateness observed byES j + p j > d j . This disturbances allow us to observe variations on the insertions windows sizes, as shown in the figure 3. While some might be shorter or longer than before, some might appear or disappear.

In a second time, windows will be compared to a new task j which has to be inserted. Being in an unrelated parallel machine context, the p ij duration will depend on the resource who has the planning on which the window is studied. In order to show the interest of our proposition, we will insert teen tasks consecutively, in an existing planning. We will work on different sizes of problem and a large instances number. Insertion results will be obtain in polynomial time.

COMPUTATIONAL RESULTS

Data generation

We carried out a computational experiment on a Pentium IV 3.00GHz considering tests obtained by generating randomly the p ij values. p ij values are principally obtained by the combination of the basic tasks' duration (in time unit) which is an integer from the uniform distribution [1 , 7200]. This duration is multiplied by the competence level of the resource in the corresponding competence. For each task, a corresponding competence is determined by an integer from the uniform distribution [1 , 3]. It refers for each resource to a level, which is a real from the uniform distribution [1.01 , 2.00], in this competence. These data are determined before the simulation. Considering the resources and tasks number, the complexity is then O(n * m). Penalties are determined as integers from the uniform distribution [1 , 10]. They are assigned if the task treatment is finished after its due-date, which is also obtained following a uniform distribution.The release-dates r j are obtain as reels from the uniform distribution [N ow , 86400u.t.] (N ow being the simulation launching time) and the due-dates d j are obtained as reels from the uniform distribution [r j + 2 * p j , r j + 2 * p j + 86400u.t.].

Concerning tasks duration perturbations, we assume that just a part of the total treatment time is sensible to a variation. The duration being composed by an incompressible part and variable part. Contrary to Esswein and al. who use a probability law in order to decide of the variations presence, we think that a schedule is made with tasks duration previsions [START_REF] Esswein | Vers la validation par la simulation d'une approche proactiveréactive d'ordonnancement robuste[END_REF]. Then the totality of the tasks is subjects to variations. The p ij , r j or d j real values will be obtained by using a normal law on their variable part. Each time we generate disturbances, we make it hundred times and conserve the average.

Insertion algorithm results

A classical schedule, which does not take into account the possible disturbance, will search the different windows and will obtain a certain number of position. Our procedure consider the different disturbances

XX

as explained before that is why we will compare insertion propositions on the same problem instances with and without uncertainties.

Insertion of one task

On the first graph in the figure 5, we compared the number of insertion windows which are proposed, in order to insert a task k, randomly generated. Perturbations are generated on 35% of each task duration with a standard deviation of 30%. The numbers of tasks (n) and human resource (hr) have been chosen to be representative from the reality. Results have been obtained on hundred computed instances. Our objective is to insert dynamically tasks in a current schedule. However, we can have a large set of possible choices. Windows real sizes can be longer and then it will be fine, but they could also be shorter. If the manager had chosen an insertion place which is, in reality, shorter than imagined, one task or more will be late. That is why it is really necessary to consider possible disturbance when we have to insert dynamically a new task. In the observed case with five human resources and twenty-five tasks, on the first graph in the figure 5, only 45% of the windows could be considerd as robust.

On the second graph on the figure 5 we observe total weighted tardiness obtained by three differents case studies. Here we show the efficiency of the method with an increasing existant load in a five human resources schedule. We based our study on three different load levels: fifty, sixty and seventy tasks already assigned in their plannings and generated within the same period. Results obtained are averages on teen simulations of insertions in each kind of planning. The interest for this method which has been shown here will now be completed with the case of insertions succession.

Insertion of teen tasks

In a second time we inserted dynamicaly teen new tasks in an existing planning composed of five human resources and fifty tasks. The table 1 show the results on six different current plannings. The comparison is the result of the average of hundred disturbances simulations on both final plannings. We can observed that the total weighted tardiness is really less important with our methodology.

We checked also the evolution of the total weighted tardiness, through the second example of the table 1, presented on the figure 6. When inserting the second task, results show that the location was not really performant. It comes from the fact that the simulation reflect the reality and even if we are in a proactive raisonning, the reality could be different than imagined. However, globaly results are better and after the insertion of the tenth task, results are nearly four times better with our method.

CONCLUSIONS

In this paper we observed uncertainties effect on existing schedules in an unrelated parallel machine context. In order to insert dynamically new tasks in a current schedule, we worked on the proactivity to find the set of robust places. We show, through exemples that the consequences of a bad choice (a non robust window) for dynamic insertions could, in case of variations, induce lateness. By inserting consecutive tasks in a current planning, we confirme that good results previously obtain on one dynamic insertion are valid and necessary in the multiple insertions case, which is closer to the reality. The fact to choose insertion windows by considering uncertainties, is a contribution in order to anticipate and to minimize the possible lateness. By minimizing the workload standard deviation between resources, we developed an approach which allow the load balancing between ressources but also the minimisation of

Fig. 1 .

 1 Fig. 1. Database communication

Fig. 2 .Fig. 3 .

 23 Fig. 2. Graph use to model the scheduling problem

Fig. 5 .

 5 Fig. 5. Robustness and flexibility results

the total working duration. Our next works will consider cases where it is necessary to reschedule some tasks. We will also develop the multi-objectives aspect of this problem by considering also the workload balancing and the rescheduling impact on plannings.