Andrés Boza
email: aboza@cigip.upv.es

Angel Ortiz
email: aortiz@cigip.upv.es

Llanos Cuenca
email: llcuenca@cigip.upv.es

A Framework for Developing a Web-Based Optimization Decision Support System for Intra/Inter-Organizational Decision-Making Processes

Keywords: Decision Support Systems, optimization, web services

The evolution in information technology has allowed the development of new DSS architectures. This paper presents a framework for developing a web-based optimization decision support system for intra/interorganizational decision-making processes. Data exchange in interorganizational decision, separate decision and data models, and web services technology have been raised. Considering these factors a framework for developing a DSS with web services have been defined. In a business context, these web services could be offered for different web services provider companies and used by the different participants in an intra/inter-organizational decision-making process. In order to contextualize this framework, three scenarios have been defined and different relationships have been identified between the participating enterprises.

Introduction

Decision Support Systems (DSS) have been used to help in a wide range of enterprise decision-making processes. The evolution in information technology has allowed the development of new DSS architectures, from stand-alone DSS to Group Decision Support Systems, OLAP and data warehouse technology in DSS, agent-based DSS or Web-based DSS [START_REF] Carlsson | DSS: directions for the next decade[END_REF][2] [START_REF] Power | Model-driven decision support systems: Concepts and research directions[END_REF]. Power [START_REF] Power | Supporting Decision-Makers: An Expanded Framework[END_REF] defined the expanded DSS framework with five categories: data-driven, model-driven, knowledge-driven, document-driven and communication-driven DSS.

A new generation of web-based model-driven DSS is beginning to emerge [START_REF] Power | Model-driven decision support systems: Concepts and research directions[END_REF]. These systems take advantage of the web services concept. A single DSS problem may be solved using multiple modelling or solution paradigms developed by different sources as separate web services and the results are then presented to the user in an aggregated or summarized form. Developing a web-based model-driven DSS requires identifying its components and describing their functionalities.

This paper presents a web-based optimization DSS framework for intra and interorganizational decision-making processes in order to be used in the early design stages of a DSS. The framework is focused on service-oriented architectures (SOA) using web services. This paper deals with the model-driven DSS, specifically about optimizations models, and increasing their potential by means of web technology.

Data exchange in inter-organizational decisions

Huxham [START_REF] Huxham | Creating Collaborative Advantage[END_REF] defines inter-organizational collaboration as a "process in which organizations exchange information, alter activities, share resources and enhance each other capacity for mutual benefit and a common purpose by sharing risks, responsibilities and rewards". Relationships among trading partners in a supply network have been categorized as [START_REF] Amr | Are we moving from buyers and sellers to collaborators?[END_REF]: 1) Transactional (automation of buyer-seller EDI-based transactions), 2) Information-Sharing (the partners are given access to a system that has the shared information in it, or one partner transmits shared information to the other partner), and 3) Collaborative (information is not just exchanged and transmitted, but it is also jointly developed by the trading partners working together). According to Vernadat [START_REF] Vernadat | Interoperable enterprise systems: Principles, concepts, and methods[END_REF] in enterprise interoperability the main challenge is operations optimization via these co-decision, co-ordination, and even negotiation mechanisms.

DSS in inter-organizational systems have been defined for SCM [START_REF] Julka | Agent-based supply chain management-1: framework[END_REF], X-networks [START_REF] Zolghadri | A DSS for production and procurement planning of enterprises X-networks[END_REF], Extended Enterprise [START_REF] Boza | A Framework for a DSS in a Hierarchical Extended Enterprise Decision Context[END_REF], Virtual Enterprise [START_REF] Zhou | An Information Management Architecture for Production Planning in a Virtual Enterprise[END_REF] or in the broad area of distributed decision making contexts [START_REF] Shneeweiss | Distributed decision making--a unified approach[END_REF]. European initiatives have been elaborated to develop interoperability of enterprise (decision) applications [START_REF] Chen | European initiatives to develop interoperability of enterprise applications-basic concepts, framework and roadmap[END_REF] and will be elaborate in future internet enterprise systems to support inter-and intraorganisational collaboration [START_REF]FInES: Future Internet Enterprise Systems Cluster[END_REF].

The internal/external enterprise decision structures are changing. For example, planning collaboration cannot be just a solution between close partners, but needs to be implemented with a large number of different business partners [START_REF] Holmström | Collaborative planning forecasting and replenishment: new solutions needed for mass collaboration[END_REF]. The goal today must be solutions that enable mass collaboration. In the Virtual Enterprise (VE) paradigm, enterprises must share and exchange a part of their internal local information in order to interact and cooperate with each other towards the achievement of the global VE goals [START_REF] Frenkel | Supporting information access rights and visibility levels in virtual enterprises[END_REF]. A member of the VE may decide to give access to its partners, with different levels of visibility according to their cooperation agreements, to part of the information it owns [START_REF] Camarinha-Matos | Cooperation coordination in virtual enterprises[END_REF]. About technological aspects, the major principles and technological waves that have prevailed in building integrated or interoperable enterprise systems so far have been [START_REF] Vernadat | Interoperable enterprise systems: Principles, concepts, and methods[END_REF]: 1) Data integration, 2) Objectoriented approaches and object request brokers (ORBs), 3) Business process modelling (BPM) and process-oriented approaches, 4) Enterprise application integration (EAI), 5) Web services and service-oriented architectures (SOAs). The architectural style of next generation technological platforms intended to support design, deployment, and execution of extended business processes inside organizational networks, must be guided by interoperability principles at the processes, services, or data level, and service-oriented architectures attempt to address these issues [START_REF] Franco | Modeling extended manufacturing processes with service-oriented entities[END_REF]. Web Services are a key component of the emerging, loosely coupled, web-based computing architecture. Other systems may interact with a web service in a manner prescribed by its definition, using XML based messages conveyed by Internet protocols. The web services specifications offer a communication bridge between the heterogeneous computational environments used to develop and host applications [START_REF]Web Services Choreography Description Language Version 1[END_REF]. The web environment is emerging as a very important DSS development and delivery platform [START_REF] Shim | Past, present, and future of decision support technology[END_REF]. DSS built for this environment, named webbased DSS [START_REF] Power | Supporting Decision-Makers: An Expanded Framework[END_REF], use different technologies [START_REF] Power | Building Web-based decision support systems[END_REF] [START_REF] Bhargava | Progress in Web-based decision support technologies[END_REF]. Among these technologies, web services are considered a viable technological platform for web-based optimization [START_REF] Valente | The evolution of web-based optimisation: From ASP to e-Services[END_REF].

DSS with separate decision and data models

Data Modelling, Decision Modelling, and Model Analysis and Investigation, are logical constructs, which play a leading role both in the interaction of information systems and decision technologies, as well as in rational decision making [START_REF] Dominguez-Ballesteros | Modelling and solving environments of mathematical programming (MP): a status review and new directions[END_REF]: 1) Data Modelling refers to the "structured" internal representation and external presentation of recorded facts. Broadly speaking this provides the decision-maker with information about their decision problem. 2) Decision Modelling is the development of a model, or a range of models that captures the structure as well as the decisions in respect of a given problem. These models are used to evaluate possible decisions in a given problem domain, and the probable outcomes. 3) Model Analysis and Investigation refers to the instantiation of the model with data, and the evaluation of the model parameters as well as the results in order to gain confidence and insight into the model. This separation between data and models, already included in [START_REF] Geoffrion | An introduction to structured modelling[END_REF], has been used in multiple DSS designs [START_REF] Dolk | Integrated model management in the data warehouse era[END_REF][26][27] [START_REF] Liu | Integration of decision support systems to improve decision support performance[END_REF]. [START_REF] Boza | A Framework for a DSS in a Hierarchical Extended Enterprise Decision Context[END_REF] proposes a framework for a decision support system in a hierarchical extended enterprise decision context. Figure 1 illustrates, in a simplified form, some of the components defined and its relationships without include hierarchical decision details. Fig. 1. Separate decision and data models (adapted from [START_REF] Boza | A Framework for a DSS in a Hierarchical Extended Enterprise Decision Context[END_REF]). [START_REF] Valente | The evolution of web-based optimisation: From ASP to e-Services[END_REF] shows this separation in web-based environments for optimization. A web enabled system for optimization should aim at: a) Providing each single optimisation tool as an independent service, b) Enabling remote interaction between the optimization components to provide a complete problem solving environment, c) Combining the provision of the tools with the provision of user support and security. This can be achieved by adopting an IT architecture based on web services, so we propose to use this technology.

A Framework for Developing a DSS Using Web Services for Separate Intra/Inter-Organizational Data and Decision Models

The components have been identified and classified as Web Services, Data exchange, Roles and Organization"s Data Sources (figure 2).

The Proposed Framework in Three Scenarios

In order to contextualize the framework in an intra/inter-organizational environment, three scenarios has been defined (figure 3): Scenario 1: Intra-organizational data and decision model. There is not information or decision model sharing between organizations. Scenario 2: Inter-organizational data and intra-organizational decision model. There exists information sharing between organizations but not a joint decision model. Scenario 3: Inter-organizational data and decision model. There is information sharing and joint decision model between organizations.

Intra-organizational data and decision model

In this context, Decision Model Designers and Decision-Makers interact with the Model Manager Web Service in order to define Decision Models and Decision Data Models, which will be later instanced. Defining separate Decision Models and Decision Data Models allows Decision Model Designer and Decision-Makers to define some Decision Models that use a same Decision Data Model.

Information System Designer interacts with the Data Models Manager web service and Decision Data Model Instantiation web service in order to define the instantiation process to obtain Analytical Data. Decision-Maker use Model Analysis and Investigation web service in order to instance a Decision Model with a data set, resolve it and make a decision. In this sense, Decision-Makers could resolve different previously defined Decision Models, and these could be instanced with different data sets (different companies, departments or simulations data) that fit with its Decision Data Model.

It is possible to implement a DSS platform in the organization with all these web services, but using the web services technology facilitates that they can be provided by web services provider companies. In this sense, a web services provider company with mathematical model specialized staff could advice on model definitions and host the defined models, another provider could offer web services for data management and a third could provide solver web services. Therefore, the main advantage of the framework in this scenario for the organizations is reuse decision models, and from a technological perspective, the main advantage is to build a DSS with components provided for different web services companies.

Inter-organizational data and intra-organizational decision model

In this scenario, there is information-sharing between organizations but not joint decision models. Besides the features included in the previous scenario, additional features can be identified: Participating organizations must work jointly in the data model definition that each organization shares with the other. Also, it is necessary to define a Decision Data Model Instantiation in order to retrieve data, not for its DSS but for the partner organization. In these sense, the participating organization require establishing the data exchange periodicity in order to orchestrate the web services.

An advantage in this case is to use web services technology to exchange data between DSS web-based or uses a common data-manage web services provider company.

Inter-organizational data and decision model

There are decision models defined jointly by the participating organization and information sharing. Besides the features included in the previous scenarios, additional features can be identified:

In this scenario, the Models Manager web service is a common tool to jointly define share Decision Models and Decision Data Models. Each organization must define its Decision Data Model Instantiation web service in order to retrieve its data subset that participates in the joint Decision Data Model. The participating organizations require establishing a common schedule in order to resolve its share Decision Models and the necessary mechanisms to define a definitive decision in function of the (inter-organizational) decision-makers judgments and choices.

A DSS developed from the framework for this scenario allows defining decision models, share data and solve shared decisions with a web-based technology to be used in intra/inter-organizations decision-making processes.

Conclusions

DSS for intra and inter-organizational decision have been defined in a wide range of decision making situations. The technological advances in the Internet make available new DSS advances. In this sense, service-oriented architectures using web services allow defining new web-based DSS. The proposed framework for developing DSS using web services for separate intra/inter-organizational data and decision models draws on web technology to design Decision Models and Decision Data Models which will be later instanced and solved to make a decision. Its components have been identified and classified as web services, data exchange, roles and organization"s data sources. Designing a DSS with web services allows splitting its functionality using these web services. Different web services providers can offer these and can be used by the different participants in an intra/inter-organizational decision-making process. Contextualizing the proposed framework using three scenarios has allowed identifying different aspects of the proposal with the participating enterprises in an intra/inter-organizational decision process and web services providers companies.

  Web Services: Models Manager: Makes possible the definition and links of Decision Models and Data Models. Decision Models Manager: Enables the definition and storage of Decision Models. Data Models Manager: Enables the definition and storage of Decision Data Models. Model Analysis and Investigation: Makes possible the instantiation of the Decision Data Model to solve Decision Models and obtain a Definitive Decision Data. Decision Data Model Instantiation: Carries out the extraction and transform of data from Organization"s Data Sources to instance a Decision Data Model with organizations" data. Solver Process: Performs the resolution process which is capable of understanding a Decision Model Instance to solve and obtain the Decision Data. Definitive Decision Process: Allows decisionmakers to consider additional factors in order to make its definitive decision.

Fig. 2 .

 2 Fig. 2.A framework to developing a DSS using web services for separate intra/interorganizational data and decision models.

Fig. 3 .

 3 Fig. 3. Three inter/intra-organizational DSS scenarios.


Seyed Behrouz Khodadadi
email: bkhodadadi@ut.ac.ir

Jafar Razmi

A Threshold Based Dynamic Routing for Jobs with QoS Ranking

Keywords: Dynamic Routing, Quality of Service, Heterogeneous Servers, Threshold Base Policy

We consider a set of n heterogeneous servers which differ in processing time and Quality of Service (QoS). Jobs are divided into m levels with regard to their service ranks. We present a Threshold Policy (TP) depending on number of different jobs in the queues as a practical and flexible dynamic routing policy to control the QoS. Two performance measures are discussed: the QoS and the Average Waiting Time (AWT) in the queues. The TP is compared with both a static routing policy which maximizes the QoS level and the Minimum Expected Delay (MED) policy which minimizes the AWT. Numerical example validate that the proposed TP is more effective when both measures are considered. The TP balances the trade-off between QoS and AWT and therefore it is superior to the MED policy and any static routing which keeps the QoS in a certain level.

Introduction

Routing policies have widely used to control queuing systems and they can highly improve the system performance. The application of routing policies arise in several areas such as manufacturing industries, computer and communication systems. We deal with dynamic routing of jobs among heterogeneous parallel servers which are ranked by their QoS. Jobs are also divided into several levels of service. Jobs of different quality levels enter to the system with different stream of arrivals and a router must dispatch the jobs to one of the servers immediately after their arrival. Service times are independent of arrival process and job's level.

Routing policies are concerned with the assignment of arrived jobs to the queues of machines. Mostly the assignment decision should be made immediately after job arrival and it is a routing decision based on number of jobs in each queue [START_REF] Down | Dynamic load balancing in parallel queueing systems: Stability and optimal control[END_REF]. Obviously there is no routing policy which can optimize various performance measures all together. There has been presented variety of policies by investigators, which each of them has its own performance measures and cost functions and is appropriate for specific problems. One common objective function which is frequently discussed by researchers is waiting time minimization. In this direction, the JSQ policy for identical parallel machines has been investigated by Winston [START_REF]Optimality of the shortest line discipline[END_REF] and Nelson and Philips [START_REF] Nelson | An approximation for the mean response time for shortest queue routing with general interarrival and service times[END_REF], [START_REF] Nelson | An approximation to the response time for shortest queue routing[END_REF]. The performance of the Minimum Expected Delay (MED) policy which is derived from JSQ policy and is appropriate for non-identical parallel machines -also called heterogeneous servers -is analyzed by Lui et al. [START_REF] Lui | Bounding the mean response time of a minimum expected delay routing system: an algorithmic approach[END_REF].

Routing policies are divided into static policies and dynamic policies. In static scheme no information exchanges are used at decision epoch. Static policies are appropriate when all jobs are available at time zero or situations in which the system characteristics are under the control. For instance the Joining-Shortest-Queue (JSQ) policy assigns each job to the machine with the minimum number of waiting jobs.

Threshold-based policies, which are a kind of dynamic routing, are frequently used to control queuing systems. In this mode, the analysis of heterogeneous servers is mainly limited to two servers because of high complexity of such systems. ( [START_REF] Kumar | Optimal control of a queueing system with two heterogeneous servers[END_REF], [START_REF] Koole | A simple proof of the optimality of a threshold policy in a two-server queueing system[END_REF], [START_REF] The | Critical Thresholds for Dynamic Routing in Queueing Networks[END_REF], [START_REF] Feng | A two-queue and two-server model with a threshold-based control service policy[END_REF], [START_REF] Sun | Equilibrium threshold strategies in observable queueing systems with setup/closedown times[END_REF] and [START_REF] Altman | Optimality of a Threshold Policy in the M/M/1 Queue with Repeated Vacations[END_REF]). In this paper we consider several streams of arrivals, parallel queues and several heterogeneous servers.

It is common in manufacturing, service and computer systems to categorize jobs or customers and rank them in order of their importance. Usually the QoS is not at the same level for different servers. In this scheme, more valued jobs are processed by higher quality machines. On the other hand, it is a common practice to provide high quality services even for the low graded jobs as much as possible. An example of this situation is dispatching automobile bodies to paint shops in Iran Khodro Company (IKCO) -the biggest car producer factory in the Middle East. Each paint shop has a specific production rate and QoS due to its technology specifications. Different model of automobiles can be painted in any of paint shops but usually the capacities of higher quality paint shops are assigned to higher valued automobiles. Each automobile body is released from its own body shop. Conveyors carry automobile bodies from body shops to White Body Stocks. Finally automobile bodies are dispatched to paint shops regard to their quality level. To the best of our knowledge, analysis of QoS performance measure has not been studied in dynamic routing policies. Most of researches are focused on AWT and utilization balancing analysis.

The presentation of the rest of this paper is organized as follows. In section 2 we present the problem statement. Section 3 contains the proposed algorithm and the development process. Numerical examples are presented in section 4 and conclusions are stated in section 5.

Problem Statement

The problem regarded in this paper consists of a set of n parallel heterogeneous servers and m level of jobs. All servers can perform the same operation, but with different performances i.e. they have different service time and QoS. Servers are arranged in order of their quality ranking. The quality ranking is in increasing order from 1 to n whereby top ranked server indicates that the server has greater quality. In the same manner jobs are ranked in order of their quality level from 1 to m. There is a separate stream of arrivals for each level. Arrivals of each level of jobs are independently distributed. The arrival of a new job occurs only after the current job is dispatched. The dispatched job waits in the queue of corresponding server until the server becomes idle. Queues are assumed to have infinite capacity and their discipline is FCFS. No preemption or jockeying is allowed. Each job is processed in only one server. The service times are independently distributed and they are also independent of the job's quality level. Table 1 summarizes the main parameters of the model. Processing period > 0 Total number of processed jobs with rank i in period T 0,1..∞ Processed jobs with rank i in server j in period T 0,1..Pi q i,j Number of jobs with rank i waiting in queue of server j 0,1..∞

The necessary condition for stability is as follows ( [START_REF] Thomas | Applications of queuing theory, Industrial engineering handbook[END_REF]).

(

) 1
3 Proposed Method

Threshold Policy

We propose a TP based on the number of jobs with different levels in each queue. When a job with quality level i arrives, the number of jobs with levels 1 to i which currently await service in the queue of the first ranked server are counted and the summation is compared with a predefined threshold. If the summation is smaller than the threshold, then the job is dispatched to the server; otherwise the summation of jobs with levels 1 to i await service in the queue of the second ranked server is compared with its corresponding threshold. The above routine continues until a server is selected and the job is dispatched. The procedure of the proposed threshold routing is depicted in procedure 1. Where S denotes the selected server. c i,j is a constant threshold and it is a cell of matrix C . Note that the last machine is a reserved machine in case of heavy traffic conditions. If none of j=1 to n-1 servers are selected for a job then the job is dispatched to the last server. Thus we have excluded the last column of matrix C. If we consider c j =(c 0,j , c 1,j , …, c m,j ) T then c i,j values are integer and c j is in non-increasing order. Our main idea to find effective thresholds is to solve the problem for deterministic situation and use the same solutions for stochastic model. In this section we present an algorithm for the deterministic model which determines the thresholds so that the total QoS is maximized. In this direction the following statement determines a feasible solution.

(2) Statement (2) denotes that the lower quality machines should not be used unless the higher quality ones are completely utilized. In deterministic model, t i and T j are assumed to be constant values. Using the Kendall [START_REF] Kendall | Stochastic processes occurring in the theory of queues and their analysis by the method of imbedded Markov Chains[END_REF]'s notation the model can be described as D/D/n with m arrival streams. The following statement represents an optimal assignment for the deterministic model.

(3) Statement (3) implies that the high ranked jobs should be prior in assigning to higher quality machines. In the other word, if a server with a short service time has low quality, it is not allowed to dispatch any jobs to it unless constraint (2) is satisfied. Thus, statement (3) is sufficient to consider a solution as optimal. It is noteworthy that an easy way to reach optimal solutions is to use zero or big integer values for the thresholds to force the system to dispatch jobs to a specific server or avoid dispatching to some other servers. Such thresholds actually function like static rules and therefore reduce the flexibility of the routing method. The main reason for development of the proposed threshold policy is to construct a flexible routing policy for stochastic situation. Therefore it is not appropriate to use extreme values.

Initial Solutions

By solving a variety of problems, we concluded a general initial solution for threshold values which has advantages over random ones. Procedure 2 shows the initialization procedure. The proposed initial solution not only makes the algorithm reaching the optimal solution earlier, but also increases the flexibility of routing policy under uncertainty. End for End for

Objective Function Value

We carried out a simulation model to evaluate the performance of the proposed routing policy against the optimal assignment. The simulation model evaluates the OFVs and indicates the critical servers which have discrepancies in relation to optimal ones. The OFV is defined for each machine as stated in procedure 3. The routine counts the number of discrepancies between the optimal assignment and the dynamic routing policy for each server. The objective of the proposed algorithm is to minimize the discrepancies of all servers ( =0). The simulation model also determines the critical jobs for each critical server. Jobs which are assigned wrongly to a critical server are called excessive jobs. Jobs which are not assigned to the correct server are called lacking jobs. Procedure 3 For i=1 to m End for

Performance Measures

Two performance measures are considered, first the percentage of incorrect assignments to total assignments which is denoted by , and second the AWT. The proposed threshold policy tends to maximize the QoS but it does not deal with other performance measures such as waiting time. Thus, a policy should be developed to reach a desirable level for both QoS and AWT.

Tune-up

An algorithm is developed to tune up the threshold policy. The algorithm consists of an initialization stage and four repetitive steps. The proposed algorithm is as follows.

Step 0: procedure initialization

Step 1: if the solution is feasible and then C is an optimal solution, stop. Else if the solution was infeasible go to step 2. Else go to step 3

Step 2: select server y={min(j)|j≠n and utilization(j)<100%} . select job x={min(i)|p i,y+1 >0}. Make an increase of 1 in cell c x,y of matrix C. update values of c i,y for i<x and go to step 1.

Step 3: select the first critical server (y= min{critical servers}). For the selected server select the first lacking job (x=min{lacking jobs of server y}). make an increase of 1 in cell c x,y of matrix C. if the OFVc y is decreased update values of c i,y for i>x so and go to step 1 else c x,y --and go to step 4.

Step 4: select the first critical server (y= min{critical servers}). For the selected server select the last excessive job (x=max{excessive jobs of server y}). make a decrease of 1 in cell c x,y of matrix C. if the OFVc y was decreased update values of c i,y for i<x and go to step 1 else c x,y ++ and go to step 1.

In the first step the OFVs are calculated and the critical servers and critical jobs are determined. If the current solution is both feasible and optimal the algorithm is stopped and the current solution is regarded as optimal solution, otherwise the algorithm tries to overcome the discrepancies of job assignment in a top-down order. If the current solution is not feasible (i.e. there is at least one server that its utilization is not equal to 100% excluding the last server), then step 2 aims to reach a feasible solution by increasing the corresponding thresholds. There are two reasons that may cause a solution not to be optimal. First, a job with a low quality level has been wrongly assigned to a high quality server and second, a job with a high quality level has been wrongly assigned to a low quality server. To resolve these mismatches, the algorithm decreases/increases the threshold of corresponding jobs (step 3 and 4).

Numerical Examples

To evaluate the performance of the justified TP presented in section 3.3, it was compared with a static routing policy, the modified version of static policy and the MED policy. The static routing policy maximizes the quality of service whereas the MED policy minimizes the AWT. The modified static policy keeps the quality in a lower level in comparison with the static policy. Instead, in stochastic models the system is stable by using the modified version. We consider three types of uncertainty: stochastic arrivals, stochastic service times and unexpected breakdowns. To put it more clearly, a numerical experiment is addressed as follows As it is shown in table 2, five different systems are considered. The exponential distribution is used for stochastic systems. m, n and E(T j ) are identical in each of five systems. To keep the traffic volume in a constant level while a variety of problems to be evaluated, ten random combinations of arrival times were generated so that was considered fixed. The system parameters are (m,n)=(4,3), the deterministic Tj is {288,576,432}, the stochastic Tj is {expo(288), expo(576), expo(432)}, {mttf, mttr} = {expo(7200), expo(600)} and .The simulation model was run for each of five systems for 10000 hours with 2 hours warm-up period. The average OFVs and the average of AWTs for four policies are shown in table 2.

As it has been mentioned before, the static routing is suitable for the deterministic situation. Although in the MED policy the AWT is about 15% smaller than the static policy but the OFV is about 16% greater. In contrast, the static policy is not appropriate for stochastic models. Because the servers are planned to be fully utilized the system becomes unstable and therefore modifications are needed if intended to be used in such systems. In the modified static (MS) policy, the assignment is scheduled with 90% of capacity of each server to prevent instability. However, in this paper we focus on the dynamic routing policies. A Wilcoxon signed rank test for ten samples of each group shows that the TP in average provides jobs with higher QoS in comparison with the MED policy. For example in the M/M*/n model which arrival times of jobs and the s times, mean time to failure (MTTF) and mean time to repair (MTTR) of servers are exponentially distributed, the hypothesis µ TP = µ MED is rejected with P-value 0.005 against µ TP <µ MED . The TP is superior to MED policy in QoS level and it is superior to static routing policies in AWT. Table 2 also implies that if the average waiting time is decreased, some quality priorities would be ignored.

2 2 i=4 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Fig. 1. Cumulative-sum control chart with two-sided V-mask (h:4.0, k:0.5) for OFV.

Table 3 shows the threshold variation in response to changes in its mean arrival time of a level of jobs in a 4 3 M/M/n system. The corresponding cumulative-sum control chart with two-sided V-mask for OFV of this system after 10000 hours simulation is illustrated in figure 1. V-masks are used to warn about abnormal conditions. The sensitivity analysis implies that algorithm 3.3 justifies thresholds so that the QoS is kept under the control.

Conclusions

A threshold policy was presented for dynamic routing of jobs with service ranking among servers with different QoS. In contrast with traditional dynamic routing policies which have not considered the QoS, the proposed policy assigns jobs to servers with QoS considerations. The algorithm, which is developed on the basis of deterministic situation, tunes-up the thresholds in order to increase the QoS. The tuneup procedure is simple to implement and it reaches certain thresholds for each set of input parameters. Numerical experiments show that the adjusted TP keeps the QoS in a high level while maintains the stability of system. A sample problem was solved by the proposed algorithm to compare it with other policies. The TP balances the tradeoff between QoS and AWT and therefore it is more effective than the MED policy which only minimizes the AWT and any static routing which keeps the QoS in a certain level. The proposed method is useful to control the QoS in production, service and communication systems. Distinguished advantages of the threshold policy are simplicity and flexibility. The decision maker can change the thresholds manually to change the utilization of servers or to root a level of jobs in a specific way. Mathematical analysis of the system is a problem yet to be resolved.

  m-n+j then cx,y = n-j+1 else cx,y = m-x+1

Table 1 .

 1 Model parameters

	ter	Parame	Description	Range
		i	Job rank	1,2..m
		j	Server rank	1,2..n
		t i	Inter arrival time of jobs with rank i	> 0
		T j	Service time of server j	> 0
		T

Table 2 .

 2 Simulation results.

			D/D/n		M/D/n		D/M/n		M/M/n	M/M*/n
	Policy OFV AWT	OFV AWT	OFV AWT	OFV AWT	OFV AWT
	Static	0	274.8	0	55280.2 0	40214.2 0	98901.7 0	∞
	MS	8.1	551.53 8.1	1308.06 8.1	1638.68 8.1	2556.6	8.1	11553.8
	TP	0	641.4	11.7	742.4	11.6	828.4	17.1	1236.7	23.8	3931.8
	MED	16.3	233.0	26.6	428.4	28.9	453.9	28.4	775.4	32.4	1893.0

Table 3 .

 3 Variation of thresholds with different mean of arrival time

		t 2 =125	t 2 =150	t 2 =175	t 2 =200	t 2 =225	t 2 =250	t 2 =275
		j=1 j=2 j=1 j=2 j=1 j=2 j=1 j=2 j=1 j=2 j=1 j=2 j=1 j=2
	i=1	3	2	3	2	3	2	3	2	3	3	4	4	3	3
	i=2	3	2	3	2	3	2	3	2	3	3	4	4	3	3
	i=3	2	2	2	2	2	2	2	2	2	3	2	3


Ander Errasti

Claudia Chackelson

Raul Poler

An Expert System for Inventory Replenishment Optimization

Keywords: Ander Errasti, Claudia Chackelson, Raul Poler

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Some authors argue that Operational Research could contribute by developing models that link the effectiveness of new forecasting methods to the organizational context in which the models will be applied [START_REF] Fildes | Forecasting and operational research: a review[END_REF] Even if future demand information is scarce, Make to Stock Production systems needs more accurate demand forecasting in order to improve quality service and reduce holding costs.

This paper explores the development of a expert system based on a periodic review inventory control, which forecast future demands more accurately beneath the time series techniques with less forecast error and proposing the most effective replenishment strategy for each supply classed derived of an ABC/XYZ analysis.

This research has also conducted a case study from Original Equipment Manufacturers (OEM) point of view answering the difficulties mentioned above.

The research methodology behind the work presented in this paper, consists of a theory-building phase, a theory-testing phase and a synthesis phase:

-Theory-building: started with an extensive literature review to identify the issues/factors to be considered in the implementation of an inventory management optimization based on time series forecasting. -Theory-testing: designed around action research principles. Action

Research can be seen as a variation of case research [START_REF] Voss | Case research in operations management[END_REF], in which the action researcher is not an independent observer [START_REF] Westbrook | Action Research: a new paradigm for research in production and operations management[END_REF]. -Conclusions/Synthesis: in the synthesis phase the conclusions of the case study and the findings are shown, which increase the understanding of the reengineering process and the techniques based on time series forecasting techniques.

2 Literature Review

Supply Chain Management

Companies have to survive in saturated markets through competitiveness, trying to be more productive, more efficient or more innovative [START_REF] Lummus | Defining supply chain management: a historical perspective and practical guidelines[END_REF]. The APICS Dictionary [START_REF] Blackstone | APICS Dictionary: 11th Edition, CFPIM, CIRM[END_REF] describes the supply chain as the processes from the initial raw materials to the ultimate consumption of the finished product, via different agents (suppliers, manufacturing plants, warehouses, customers, etc,). Supply Chain Management coordinates and integrates all activities of planning, sourcing, manufacturing and delivery. Some authors [START_REF] Vollmann | Manufacturing Planning and Control Systems 4th ed[END_REF] classify and define the production strategies as make-toorder (MTO), make-to-stock (MTS) and assemble-to-order (ATO). They relate these approaches to choosing the master production scheduling (MPS) approach. Other authors [START_REF] Rudberg | Mass customization in terms of the customer order decoupling point[END_REF] add the engineer-to-order production strategy and state that the decoupling point is a key issue [START_REF] Hoekstra | Integrated Logistics Structures: Developing Customer Oriented Goods Flow[END_REF]. The decoupling point concept is also known as order penetration point [START_REF] Olhager | Strategic positioning of the order penetration point[END_REF]. The customer order decoupling point decouples operations in two parts. Upstream this point the activities are performed to forecast and downstream they are performed to customer order (see Figure 1). The product differentiation point is the point where the firm's product is configured and it takes on specific features.

Fig. 1. MTS, ATO and ETO production strategy

In make-to-stock (MTS), the MPS is based on end items, and these end products are produced to meet forecast demand. Li [START_REF] Li | The role of inventory in delivery-time competition[END_REF] cited by Van Donk [START_REF] Van Donk | Make to stock or make to order: The decoupling point in the food processing industries[END_REF] states that competition can breed a demand for MTS, just as other economic phenomenon such as economies of scale, uncertainty and seasonality. Competitive pressure have shortened the life cycles for many products and increased the penalty of holding obsolete finished goods inventories. Standard planning methods lead to high forecasting errors and-as a consequence-to high safety inventories.

Demand information and accuracy is a critical factor for achieving end product lower inventory levels and providing better customer service [START_REF] Buffa | Production Inventory Systems: Planning and Control[END_REF], [START_REF] Hax | Production and Inventory Management[END_REF] and [START_REF] Silver | Inventory Management and Production Planning and Scheduling[END_REF]. This issue could be essential to improve customer service and warehousing costs in make to stock production systems.

ABC/XYZ Analysis

The Pareto principle (also known as the 80-20 rule, the law of the vital few, and the principles of factor sparcity) serves as a baseline for ABC-analysis and XYZanalysis. The ABC/XYZ Analysis is used to generate the supply and inventory control and production strategy. Rushton et al [START_REF] Rushton | The handbook of logistics and distribution management[END_REF] state that it is useful in logistics and procurement for the purpose of optimizing stock of goods. The analysis consists of a procedure of stock management with which on the basis empirical experiences, results are usually assigned to a classification by the determination by variation and/or fluctuation coefficients of goods concerning its turnover regularity (consumption and its predictability). Items with high sales are called A-articles, while C-articles have low consumption. Articles which are sold very regularly and in some extent constant are called X-Articles, while Z-class runs very irregularly or even stochastically (see Figure 2). ABC/XYZ Analysis would be automatically generated by means of a tool, and finished goods would be checked and then assigned to the proper supply classes. After that, for each supply classes the most effective replenishment strategy is settled to increase service and optimize stock.

Demand Forecasting

Demand forecasting qualitative and quantitative methods can aid in establishing the right replenishment strategy [16]. To sort out the adequate qualitative and/or quantitative method some authors propose selection decision trees [START_REF] Armstrong | Demand Forecasting: Evidence-based Methods, Strategic Marketing Management: A Business Process Approach edited by Luiz Moutinho and Geoff Southern[END_REF].

In recent decades, numerous time series forecasting models have been proposed. De Gooijer and Hyndman [START_REF] De Gooijer | 25 Years of IIF Time Series Forecasting: A Selective Review[END_REF]performed a review of the last 25 years. Time series forecasting software tools usually offer a variety of techniques, some of which provide the user the possibility to automatically define parameters or, even, to select the best forecasting method.

Model predictive inventory control systems have been previously applied to supply chain problems with promising results [START_REF] Doganis | A combined model predictive control and time series forecasting framework for production-inventory systems[END_REF], however most systems that have been proposed so far possess no information on future demand. The incorporation of a forecasting methodology for individual item forecasts could promote the efficiency of control actions by providing insight in the future. This efficiency would be based on more accurate predictions to forecast demand extrapolating historical data aided on time series forecasting.

Demand is one of the greatest sources of uncertainty and, selecting the best time series forecasting model for each time series to be dealt with is still a complex problem [START_REF] Poler | Parameterisation of demand forecasting models through out-of-sample errors on a rolling horizon[END_REF]. This could be the reason why only 2% of 120 interviewed companies a forecasting system based on forecasting software [START_REF] Errasti | Proyecto: Sistemas de previsión de la demanda y su aplicación a la gestión de almacenes, Cluster de Transporte y Logística de Euskadi 22[END_REF].

According to Shah [22] the sense in which accuracy is defined may vary. Examples include the mean square error (MSE) and the mean absolute deviation (MAD) as two possible ways of stating the forecast accuracy. The main advantage of those measures is that could be used for intermittent demand, while others have problems.

Commercial software packages often report the mean absolute percentage error (MAPE) distinguishing between in-sample and out-of-sample evaluations. But there are special cases, e.g. intermittent demand, in which these error measures are not appropriate [START_REF] Syntetos | The accuracy of intermittent demand estimates[END_REF].

In-sample and out-of-sample errors have been used for time series forecasting model selection. In-sample tests are used when the real values are known and out-ofsample test when the real values are unknown. However, some authors use out-ofsample simulation [START_REF] Coccari | Average two best forecasts can reduce forecasting risk[END_REF]. Makridakis [START_REF] Makridakis | Sliding simulation: a new approach to time series forecasting[END_REF] used this procedure with a rolling temporal horizon as a selection method for estimation of parameters.

Makridakis et al [START_REF] Makridakis | The accuracy of extrapolation (time series) methods: results of a forecasting competition[END_REF] applied out-of-sample simulation on time series, and demonstrated that forecast accuracy improves when forecasting parameters were defined out-of-sample errors rather than in-sample ones.

An alternative model selection method is the so-called cross validation method [START_REF] Stone | Cross validation choice and assessment of statistical predictions[END_REF]. Data is partitioned into subsets in such a way that the analysis is initially performed on a single subset, while the other subset(s) is/are retained for subsequent use in confirming and validating the initial analysis. The mean squared prediction errors in the subsets left out defines the cross validation error.

Forecast accuracy can be improved by the consideration of relevant information beyond historical data. Collaborative forecasting is based on the fact that each interrelated company (customers and suppliers, or nodes in an enterprise network) has relevant information available to forecast what the rest do not have. It is a question of managing all sources of relevant information and of eliminating "analysis islands". Poler et al. [START_REF] Poler | Collaborative forecasting in networked manufacturing enterprises[END_REF] proposed a structured model for the collaboration among firms of a network in the demand forecast and production planning settings and analysed the impact of collaboration mechanisms on forecast accuracy.

The Inventory Replenishment Expert System

The Inventory Replenishment Expert System (IRES) is composed by four main modules (see Figure 3).

Fig. 3. The Inventory Replenishment Expert System (IRES)

The first module performs ABC/XYZ analysis for each reference type. All types of references, according to this analysis, are sorted out taking into account the demand behavior for a given past horizon.

The second module simulates possible service policies aided with Stock to Service curves, which relate service and stock level, and allow comparing service level policies with performance rates such as stock turnover and stock out.

The third module selects the most appropriate time series forecasting model. Depending on the pattern of time series, different forecasting models might be used. The selection of the most accurate forecasting method among a set of forecasting methods is made. The selection criteria pursue to minimize a concrete forecast error measure (MSE, MAD, MAPE, etc.), which depends on each particular case, using an out-of-sample simulation with rolling time horizon was carried out.

The fourth module proposes the best replenishment strategy taking into account the demand forecasts obtained by the selected method. The Spanish Household Appliances Sector is a saturated market, with an increasing number of multinational competitors. Besides, there has been a process of concentration of Retailers and Wholesalers, which has caused loss of margins to the OEM and the stock ownership has passed to the OEM. In this context, the Washing machine Business Unit tried to gain a sustainable competitive advantage.

The goal of the research was to reduce the total cost of the supply chain and increase the customer service, through the implementation of an expert system for inventory management.

The implementation of the new production system was monitored with key performance indicators related to cost (stock) and customer service (order fulfillment). The results obtained are shown at Table 1 The recalculation of safety stocks considering pick consume, and the assumption of a variable lot size replenishment strategy based on forecasts, was effective in reducing up to an 88% the number of stock-out.

Conclusions

This paper present a new Inventory Replenishment Expert System (IRES) based on the combination of ABC/XYZ analysis, Stock to Service curves, Time Series Forecasting and Replenishment Strategies.

The multidisciplinary team involved in the reengineering project has found that IRES is useful for minimizing inventory level and increasing service quality.

Future research could be done in the following areas: a) increasing the forecasting techniques of the expert system; b) analyzing the impact of different forecasting methods selection criteria; c) improving the forecasting model selection module by integrating qualitative methods such as judgmental and statistical methods; d) testing IRES in supply chains of different sectors.

Fig. 2 .

 2 Fig. 2. ABC/XYZ References demand characteristics chart

Fig. 4 .

 4 Fig. 4. Internal and external supply chain considered in the case study

Table 1 .

 1 . Recommended Forecasting methods and Replenishment strategies depending on make to stock references ABC/XYZ classification

			X: Regular	Y: With Trend (T) or Seasonality (S)	Z: Irregular
		Replenishment	Variable lot size	Variable lot size based on	Safety stock equal
	A: High	Strategy:	based on Forecasts	Forecasts	pick consume
		Forecasting method:	Moving Average	(T) Exponential Smoothing with trend	Moving Average
		Replenishment	Variable lot size	Variable lot size based on	Safety stock equal
		Strategy:	based on Forecasts	Forecasts	pick consume
	B: Medium	Forecasting method:	Moving Average	Seasonality Smoothing with (S) Exponential	Smoothing Exponential
		Replenishment	Variable lot size	Variable lot size based on	Safety stock equal
		Strategy:	based on Forecasts	Forecasts	pick consume
	C: Low	Forecasting method:	Exponential Smoothing	and Seasonality Smoothing with Trend (T) + (S) Exponential	Smoothing Exponential

INFORMATION TECHNOLOGY FOR BALANCED AUTOMATION SYSTEMS

Empirical Study

The OEM, which led the supply chain improvement, was a Washing Machine Business Unit devoted to design, production and distribution of washing machines on the European market.

In order to ease the comprehension of the case study, the main characteristics of the external supply chain (distributors or customers and suppliers network) and the internal supply chain (finished product warehouse and manufacturing plant) are presented (see Figure 4).


François Rioult
email: francois.rioult@unicaen.fr

Sylvain Ferrandiz
email: predicsissylvain.ferrandiz@predicsis.com

Monique Bastien

Marc Boullé
email: marc.boulle@orange.com

Information enhancement in a voluminous forum with automatic co-clustering

Any web forum is a typical example of a structured source of textual data. Maintaining such a forum requires many manual processing from the webmaster, even more as the volume of data grows. The quality of the structure and the moderation process is thus strongly dependent on the available time. In this article, we are interested in applying data mining tools, especially coclustering algorithms, in order to propose some automation. We illustrate and validate our proposal on cameravideo.net's forum 1 . The website cameravideo.net was the premier french website dealing with amateur and professional video.

I. Introduction

On the Internet, forums allow users to exchange information about their favorite subjects, such as video (hardware, shooting, editing, etc.). Wellknown usages are related to questions/answers: information gathering, support, contact. These forums are also useful to deal with users' contributions, tutorials and various articles. They lastly establish a place for a social community sharing a common interest by proposing additional services such as mails and feeds, that stimulate exchanges.

Although forum softwares are efficient for dealing with users and content, information management and enhancement are not taken into account. Firstly, the forum layout is often rigid while a member may like to post a comment in several categories. Secondly, search in a forum is limited to basic text matching, even if the writer may tag his/her contribution in order to promote its access. There are methods that automatically index the content but enhancing this index to optimize its structure requires a colossal human effort. The daily management is also tedious and costly because it requires a lot of moderation.

Our aim is to study how data mining techniques can lead management tasks to automation, in order to better present and enhance information in forums. We more precisely focus on applying co-clustering methods to text content in a forum, improving the flexibility of its structure and making its daily management easier. We are interested in building a pro-cess that evaluates the relevancy of the used models, focused on the forum of the website cameravideo.net.

In particular, we study the impact of filtering and lemmatizing the vocabulary.

Co-clustering will provide groups of words that could allow to improve the forum structure. Different categories could then be suggested to the user, helping the new content to be indexed in the right place. Co-clustering will also group texts, a new group allowing to detect new trends and to affect the structure of the forum.

The article is organized as follows: in Section II, we describe a methodology for enhancing and assessing the information in the textual data. Enhancing information relies on using a co-clustering algorithm and assessing relies on a supervised analysis. We review the state of the art and justify our choices. In Section III, we describe the data, coming from the forum cameravideo.net, on which we applied our methodology. In Section IV, we put the methodology to the test through an unsupervised analysis, a descriptive analysis then a supervised analysis of the forum data.

II. Method and statistical tools

Computing the vocabulary is the first stage of natural language processing with bag-of-words approach. There are different strategies and we do not want to build a new one but rather develop a non parametric and non agnostic methodology for enhancing the information. We here describe this methodology and the statistical tools we used.

I. Methodology

We proposed the following methodology:

1. Define the textual units, for example the thread title, the title of the first post, etc.

2. Define a vocabulary and get an occurrence matrix textual unit × words of the vocabulary.

3. Evaluate the correlation between the texts and the words with the help of a co-clustering algorithm.

4.

Validate the groups of texts with projecting a target variable.

The first two steps consisted in transforming the raw textual data into a data table from which a sta-tistical analysis could be handled. Different strategies may lead to extract the vocabulary into different tables. For example, a lemmatization task could be used or not.

For each representation stemming from this choice, we led a statistical analysis in order to assess its relevancy. This analysis was based upon applying a co-clustering algorithm (Step 3). This algorithm should allow the methodology to be non parametric: in particular, the number of groups of each partition should be an output of the algorithm and not an input.

In order to complete this non-parametric assessment, we also propose to use a supervised assessment (Step 4). It estimates the results of the non supervised one through a correlation between the groups and a target variable which is explicable by the user. Moreover, it takes advantage of a usual and easily explicable criterion: the empirical risk.

II. Co-clustering algorithms

Co-clustering algorithms have been brought up to date by the need for analyzing large binary matrices, for example coming from consumers' bags, textual corpus, gene expression data, etc. Such algorithms compute a partition of the rows and a partition of the columns2 of the matrix. It is now a usual unsupervised classification technique in statistics and data mining.

Our strategy consisted in first applying a classical clustering algorithm on the rows and then on the columns [START_REF] Slonim | Document clustering using word clusters via the information bottleneck method[END_REF] with the information bottleneck principle (the best trade-off between accuracy and complexity) and the clustering algorithm stemming from it. This kind of approach builds a conditional analysis.

The works of [START_REF] Inderjit | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF] and [START_REF] Inderjit | Information-theoretic coclustering[END_REF] led to co-clustering algorithms allowing a joint analysis of both the columns and the rows of the matrix. Such method lies on considering a global evaluation criterion, that compares the quality of two couples of partitions. The method also optimizes this criterion using a heuristic. In [START_REF] Inderjit | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF], a cutting criterion for bipartite graphs is minimized and the algorithmic solution searches for singular vectors. In [START_REF] Inderjit | Information-theoretic coclustering[END_REF], the criteria is the Kullback-Leibler divergence between the initial joint density and the one obtained after partitioning the rows and columns. Analyzing the criteria led to an iterative algorithm that alternatively optimizes the partition. An approach generalizing to the Bregman divergences was studied in [START_REF] Banerjee | Clustering with Bregman divergences[END_REF].

These algorithms however require the user to set the number of groups in the partitions. That is why we focused on the Khiops algorithm, described in [START_REF] Boullé | Data grid models for preparation and modeling in supervised learning[END_REF], whose theoretical background in based upon in [START_REF] Boullé | Recherche d'une représentation des données efficace pour la fouille des grandes bases de données[END_REF]. This method has proved to be efficient during a challenge [START_REF] Boullé | Data grid models for preparation and modeling in supervised learning[END_REF] and provides a probabilistic criteria mea-suring the ability of the model to explain the data. This measure is very useful for comparing different models.

III. Models for supervised classification

There are a lot of data analysis softwares. We chose to use Khiops3 [START_REF] Guerraz | Khiops coviz: A tool for visual exploratory analysis of k-coclustering results[END_REF] from the Orange Labs. It lies on the MODL approach [START_REF] Boullé | Recherche d'une représentation des données efficace pour la fouille des grandes bases de données[END_REF], that leads to non parametric (no assumption about the underlying distribution) learning algorithms that are time efficient and provide reliable models. It is also based upon [START_REF] Boullé | Compression-based averaging of selective naive Bayes classifiers[END_REF] for selecting the variables and averaging the models.

The supervised model uses a naive Bayes algorithm which is improved by the three following points:

1. The single-variable conditional probabilities are estimated by MODL algorithms for discretizing the numerical variables and grouping the categorical ones.

2. The descriptive variables are selected through the MODL approach.

3. The models are weighted by a Bayesian averaging scheme.

The modeling method is efficient in terms of the predictive performance of the built models. On several different challenges, the method indeed frequently produced the best predictive model.

The theoretical complexity of Khiops is O(N √ N log(N )) [START_REF] Boullé | Data grid models for preparation and modeling in supervised learning[END_REF] where N is the number of instances in the database. In a corpus of texts over W words, the instances are the pairs (text, word) then N if the number of use of words in the texts. For example, on 20,000 texts over 10,000 words, N = 20, 000, 000. In practice, on a modern computer, a few hours are necessary for each billion of instances. It is quite long, but this analysis has not to be done every day.

III. Description of the data

The forum of the website cameravideo.net was organized with categories, each one consisted of threads. Each thread consisted of comments that were posted by the users.

There were 49 categories, for example "video news", "rent, buy, sell", "Sony Vegas -DVD architect", "Apple -Mac software". They structured the forum and the moderators a priori decided on them. Through long term observation, the moderators may consider modifying this structure, by adding new categories or by merging some of them.

We had 8,528 threads. They are non uniformly distributed among the categories; for example, "video news" has 1,303 threads but "Apple -Mac software" has only two threads. Each thread had a title, such as "Welcome on the forum" or "Which Super-8 camera should be chosen?". Lastly, there were 61,044 comments posted on these threads.

Bottleneck The moderation task consists in validating the subject of a thread, potentially replacing the thread in the dedicated category and making sure the comments fit the policy of the site and stay in the perimeter of the thread. Facing the volume of the contributions, many moderators are needed.

Tools for vocabulary retrieval Even if the relation between terms was a promising aim for information retrieval, we did only simple processing of the text and stayed very far from complex approaches such as ontologies [START_REF] Baziz | The Use of Ontology for Semantic Representation of Documents[END_REF][START_REF] Khan | Ontology-based Information Selection[END_REF]. Our goal was namely related to the design of a simple, effective and not time-consuming method, without resources such as dictionaries, taxonomies or ontologies.

The vocabulary was defined as follows: a word is a string of non-space characters delimited by two spaces. One-letter words were removed. The lemmatization was optional but could be carried out by the treetagger 4 : it needed only a few minutes for the whole corpus.

IV. Information enhancement through co-clustering: experiments

In this section, we show that a co-clustering algorithm is an operational way to the enhancement of information in voluminous forums. We analyzed the results of this algorithm in order to validate the choices regarding the pre-treatment stage (definition of the textual unit, filter the words according to their size or frequency, lemmatization). To this aim, we first used an unsupervised approach then a supervised one.

I. Unsupervised analysis

In order to study the possibilities of automatically structuring and moderating the forum, we asked the following question, illustrating the interest of an unsupervised analysis:

Question 1. -Were the titles of the thread enough for categorizing the threads?

To answer this question, we prepared the raw data as follows: the textual unit was the title of the thread; we got a vocabulary of 12,902 words, thus the occurrence matrix with 8,528 rows (one row each textual unit) and 12,902 columns (one column each word in the vocabulary).

We applied the co-clustering algorithm on this matrix in order to obtain a partition of the rows and a partition of the columns. The underlying MODL approach allows the algorithm to consider and compare partitions with different sizes: the user does not have to set the number of groups of words or texts a priori. In this case, the solution proposed by the algorithm had only one single 4 http://www.ims.uni-stuttgart.de/projekte/corplex/TreeTagger/ group of words and one single group of texts. We then rejected the hypothesis that the words of the title could categorize the threads. On a statistical point of view, the words of the titles did not bring any information about the thread.

From this analysis, we considered the first comment of each thread and asked the question: Question 2. -Did the first comment of each thread allow to compute a categorization for the threads?

To answer this question, we considered the textual unit as the concatenation of the title and the first comment. The matrix had 8,528 rows and 53,119 columns and we applied the co-clustering algorithm. This time, we got 278 groups of words and 214 groups of threads. The first comment then brought enough information for the threads to be categorized.

Note that we have no clue about the quality of these groups, this will be further discussed in the descriptive analysis (next section).

We then asked the last question: Question 3. -What was the contribution of the lemmatization for defining the vocabulary?

For the titles and the first comments of each thread, we computed a lemmatized vocabulary. The matrix had 8,528 rows and 41,582 columns. The co-clustering algorithm provided 282 groups of words and 204 groups of threads.

We used the a posteriori probability of each model, knowing the data D, for comparing the two co-clustering M1 and M2: p(M1/D) and p(M2/D). The co-clustering namely optimizes this criteria and returns the couple of partitions whose a posteriori probability is the highest. A linear transformation of this criteria provides an explicable indicator: the compression gain. It is null when the co-clustering gives only one group for the rows and columns, it tends to 1 when the correlation is higher and the occurrence matrix is near to a diagonal one. In our situation, the compression gain for the raw vocabulary was 0.0229 and 0.0233 for the lemmatized one.

We could then conclude:

1. The first comment allows to categorize the thread.

2. Using the lemmatization does not provide any significantly better result.

This conclusion was confirmed when detailing the groups of threads or words. Such analysis is yet tedious. One more efficient way to interpret the group consisted in leading a supervised analysis. The results are given below.

II. Descriptive analysis

For the raw vocabulary (no lemmatization). -When applied to the occurrence matrix of the raw vocabulary from the title and the first comment, the coclustering algorithm partitioned the vocabulary into 278 groups and the threads in 214 groups. Figure 1 shows the distribution of the relative size of each group. Some groups of words covered a typical theme, that could be interpreted without knowing the threads. For example, 6 groups had only one word: {on}, {is}, {in}, {and}, {the}, {of}. One group had three similar words: These sizes are from 1 to 846 for the words, from 1 to 122 for the threads.

{#8217, #8230, #339 }. One group had 266 words containing {90, 44, street, 35, 44, fax, . . . , tel:, avenue, fax:, province, mail:, 92414, . . . }, used for writing postal coordinates or telephone numbers. One group of 185 words contained only English words 5 . One group of 131 words contained {buy, advice, expensive, budget, think, old, how much, good deal, purchase, provide, consider} that are linked to the buying theme. One group had 141 words related to vehicle (brand names). Most of the groups were of course related to the video theme of the forum: broadcasting, system (linux, PC, Mac), encoding, software, etc. These groups of words were useful to improve the forum structure. On one side, according to the vocabulary detected while the writing of the first comment, different categories could be proposed to the user, so that the new content is indexed in the right place. On the other side, the emergence of a new group could allow to detect new trends and to affect the structure of the forum. The groups of words could also help to improve the human interface of the search functions.

About the threads, we found one group of two threads whose first comment were identical and written in English. They related to a single user promoting electronic accessories (pocket PC, cameras, PDA, smartphone) and only the titles differed: "For Sell::apple iPhone 8gb-$300usd/nokia N95 8gb(black)--$400usd" and "For Sell::apple iPhone 48gb-$230usd/apple 16gb Ipod Touch -$190usd". One group gathered two very similar threads with redundant titles: "Canon XH A1 and G1 (HDV, 1080i, 24p) for replacing the XM2" and "the new Canon HDV HX A1 and G1 replace the XM2". This example showed how co-clustering could detect unwanted comments. Another use is related to the improvement of the forum structure, in order to present groups of homogeneous contributions, leading to a point of view which is different from the static structure of the categories.

Refining the analysis of the groups of threads would require a human effort and the design of interfaces. We however give details about the supervised evaluation of our results in the next section.

For the lemmatized vocabulary. -When applied to the occurrence matrix of the lemmatized vocabulary 5 The language for the cameravideo.net forum is French.

from the title and the first comment, the co-clustering algorithm partitioned the vocabulary into 282 groups and the threads in 204 groups. Figure 2 shows the distribution of the relative size of each group. Some groups of words were explicable. For example, five groups had only one word: {on}, {in}, {of}, {the}. One group of 247 words contained {channel, TNT, satellite, decoder, TF1, ADSL, M6, DVB, receiving, VOD, box, TVHD, . . . }. This group covered the television theme. One group of 199 english words contained {home, equity, href, loan, used, buy, Man, mitsubichi, yong, ssang, porsche, Fiat, nissan, alfa, Mercedes, chrysler, seat, fuel, efficient, highly, cheap, mortgage, approach, prices, energy, viagra, phentermine, cell, didrex, zoloft, xenical, prozac . . . }, related to unwanted content or spam.

For the threads, we again found the group of two threads written by the electronic retailer. Another retailer for SIM-unlocked iPhones was also detected.

Manual analysis of the difference which are induced by the lemmatization generally did not reveal any advantage of this treatment. In both cases, the groups of words were consistent, easily explicable and easy to enhance. There were only slight differences when redundancy appeared, for example between "camera" and "cameras". Lemmatization could then simply be applied to improve the presentation of the results.

III. Supervised analysis

We led a supervised analysis of the previous results. Its principle [START_REF] Candillier | Cascade evaluation of clustering algorithms[END_REF] is based upon estimating the quality of the co-clustering by measuring the improvement on a supervised classification, when the group values (provided by the co-clustering) were added as a new variable. For the supervised classification, we chose the category which the thread was attached to as the target variable.

This analysis was automatic and provided a numerical evaluation based on a classical indicator: the empirical risk. It was less tedious than a descriptive analysis of the groups.

Building the classifier. -The previous unsupervised analysis allowed to design a new descriptive variable for the threads: the index of the group which they belonged to. In fact we had two such variables, one related to the raw vocabulary and the other related to the lemmatized vocabulary. To both variables, we associated a single These sizes are from 1 to 698 for the words, from 1 to 136 for the threads.

variable classifier, that assigns a thread to the tag that was majority in the group of threads.

We split the threads into two disjoint sets for learning and testing. The test performances of the classifiers are detailed in Table 1. We can observe that the impact of the lemmatized vocabulary is light: only Projecting the target variable on the thread groups allowed a direct interpretation. For example, in the case of the lemmatized vocabulary, the threads of the group #57 belonged to the category "Welcome in our forum!" for 60% and to the category "Meeting the team" for 23%. The threads of the group #144 belonged to the category "rent, buy, sell" for 94%. Supervised modeling. -We led a second supervised experiment: we applied a supervised classification algorithm on the bag-of-words representation of the threads. This experiment allowed to give a reference performance for predicting the category of a thread, which we compared to the one obtained by adding the variable generated by the clustering.

For each vocabulary, we removed the words whose frequency was below a k threshold. Each word then allowed to build a descriptive variable: the frequency of the word in the title and the first comment. The Khiops tools was able to model the corresponding table. The predictive performances, measured by the empirical risk, are given in Table 2.

Two facts could be considered: using a lemmatized vocabulary and removing the few frequent words had no impact on the predictive performance. When compared with the results of the first experiment, we moreover could observe that the co-clustering, by aggregating information, did not destroy the correlation between the threads and the forum categories. We observed that including the index of the group given by the co-clustering significantly (4.5%) improved the performance of the supervised model, for both raw and lemmatized vocabulary. The impact of lemmatizing stayed marginal (1.2%). We conclude that lemmatizing or filtering the less frequent words has a low impact: these steps can be avoided. Provided by a simple and non parametric method, the co-clustering is efficient and directly usable.

V. Conclusion

The animation of a forum is a heavy task with few automation. In this article, we aimed at exploring some ways of automation with the help of efficient and non parametric tools for data analysis. We proposed and applied an agnostic and automatic method for enhancing and evaluating the information in structured textual data.

The first conclusion is technical: firstly, lemmatizing the vocabulary or pruning it according to a minimum frequency threshold did not bring any supplementary information when associating a thread to a forum category. Secondly, the co-clustering algorithm correctly and comprehensively summarized the information contained in the first comment of each thread.

The second conclusion is functional: apart from the ability to automatically detect the spam, the clusters could enhance the use of the forum and its content, in order to increase the audience. For example, a keyword-oriented search in the content could lead to a theme-oriented search. A technical advisor could easily extract the content useful to build a tutorial. The main appeal of the proposed methodology lies in the use of a co-clustering algorithm that avoids tedious text processing, while alternative approaches require a huge manual effort to extract the keywords.

Figure 1 :

 1 Figure 1: Distribution of the sizes of the groups of words or threads, regarding the total number of words or threads.These sizes are from 1 to 846 for the words, from 1 to 122 for the threads.

Figure 2 :

 2 Figure 2: Distribution of the sizes of the groups of words or threads, regarding the total number of words or threads.These sizes are from 1 to 698 for the words, from 1 to 136 for the threads.

Table 1 :

 1 1.2%. Empirical risk while testing the majority and univaried classifiers.

	classifier	empirical risk
	Majority	84.95%
	Raw vocabulary	56.83%
	Lemmatized vocabulary	55.66%

  Supervised modeling with augmented representation. -We led a third and last supervised experi-

	Vocabulary k number of	empirical risk
			attributes learning	test
		2	25,789	34.67% 54.67%
	raw	5	11,970	31.26% 54.27%
		10	7,249	33.75% 54.69%
		2	20,889	31.47% 54.47%
	lemmatized 5	10,010	31.33% 54.53%
		10	6,198	30.97% 54.72%

Table 2 :

 2 Empirical risk for learning and test of the Khiops classifiers on a bag-of-words representation of the threads. The words whose frequency is above k were removed.

	ment. We redone the previous experiment this time with
	considering an extra descriptive variable: the index of
	the group which the thread belonged to. For each vocab-
	ulary, we led a supervised modeling with Khiops. The
	predictive performances were measured by the empirical
	risk and reported to Table 3. Following the conclusion
	about the previous experiment, we limited ourselves to
	k = 10.
	Vocabulary k number of	empirical risk
			attributes learning	test
	raw	10	7,249	25.63% 51.43%
	lemmatized 10	6,198	27.47% 50.17%

Table 3 :

 3 Empirical risk for learning and test of the Khiops classifiers on a bag-of-words representation of the threads, considering for each thread the index of its group.

Since the beginning of this study, one of its author (Monique Bastien) passed away. She was the webmaster of the website http://www.cameravideo.net, that also disappeared, though it is still accessible with the web archive, see for example https://web.archive.org/web/20121115053234/http:// www.cameravideo.net/.

Bi-clustering computes associations between a group of rows and a group of columns.

http://www.khiops.predicsis.com/


des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Modern Machine Learning techniques and their applications to medical diagnostics

Alexander Gammerman

Computer Learning Research Centre, Royal Holloway, University of London, UK.

A.Gammerman@cs.rhul.ac.uk

Abstract. The talk presents several machine learning techniques and their applications to clinical decision-making. In many problems of computer-aided medical diagnosis and treatment a program must be capable of learning from previously accumulated past patients data records, and extrapolating to make diagnosis for new patient by considering their symptoms. Many machine learning and statisitical techniques have been developed to help in clinical decision making. Among them decision trees, the Bayesian techniques, dicriminant analysis, neural networks and many others. These techniques usually deal with conventional, small-scale, lowdimensional problems, and the application of these techniques to modern high-dimensional data sets with many thousand attributes (symptoms) usually leads to serious computational problems. Several new techniques such as Support Vector Machine (SVM) have been developed to tackle the problem of dimensionality by transferring the problem into highdimensional space, and solving it in that space. They based on so-called kernal methods and can very often solve some high-dimensional problems. These techniques perform very well with good accuracy. However, a typical drawback of techniques such as the SVM is that they usually do not provide any useful measure of confidence of new, unclassified examples (new pattients). Recently a new set of techniques, called Conformal Predictors, have been developed that allows to make predictions with valid measures of confidence. The approach is based on approximations to the universal measures of confidence given by the algorithmic theory of randomness and allows us to compute diagnostic classes and estimate confidence of the diagnostics for high-dimensional data. The talk will present Conformal Predictors and their applications in medicine.