Une fois le modèle validé sur les aspects structurels et comportementaux, il s'agit dans une deuxième phase d'étudier les performances du workow an de l'optimiser. Notre choix dans ce travail a été d'utiliser dans un premier temps les réseaux de Petri colorés pour simuler les performances à l'aide de l'outil CPN Tool. Ce qui nous a permis de constater la présence d'un goulet d'étranglement au niveau du traitement d'acceptation des demandes de crédit. C'est donc à ce niveau qu'une analyse de performance sera faite pour optimiser la répartition des dossiers entre les collaborateurs avec appel si nécessaire à des intérimaires pour supporter l'excédent de charge de travail.

Pour cela, nous sommes repartis sur le modèle déplié du Réseau de Petri.

Il permet en eet une analyse ne des performances du workow en évaluant précisément les charges de travail de chaque ressource (ici les collaborateurs).

Le modèle Réseau de Petri nous a permis à l'aide du modèle mathématique sous-jacent de formuler mathématiquement le problème de répartition des charges de travail suivant les collaborateurs et intérimaires. La résolution de ce problème va permettre d'orir aux décideurs, c'est-à-dire les chefs de services, des indicateurs quant au nombre minimum d'intérimaires à engager au jour le jour pour absorber la charge de travail quotidien, de choisir entre diérents critères d'optimisation (équilibrage de charge, minimisation du max des charges de travail, ...) pour la meilleure politique de répartition des dossiers. De plus à partir de l'historique des arrivées de courrier et en estimant l'arrivée de courriers sur une période donnée (une semaine, voire un mois), il va être possible d'ajuster et de limiter le surcoût nancier engendré par les appels ponctuels et quotidiens de ces intérimaires en lissant la surcharge occasionnée par une campagne marketing sur une semaine par exemple en prenant en compte la disponibilité de leurs collaborateurs.

A partir de l'analyse de performance du modèle Réseau de Petri In business process reengineering process, many notions appear and use the dierent process aspects such as Business Process Management (BPM), Workow, Business Activity Monitoring (BAM) and Decision-making Support systems (DMSS). In the next few paragraphs we try to present and dene briey each of these notions.

Business Process Management (BPM) is dened as "the art of modeling, managing and optimizing business processes in order to increase business performance". This means managing the entire business process lifecycle which includes analyzing, executing, monitoring, and ensuring business process integrity and optimality. This can be realized through employing recent technologies and standards in BPM domain. Figure 1 demonstrates a business process lifecycle. A business process is composed of a sequence of activities and each activity is composed of roles and actions. These roles and actions are performed by one or more actors to achieve business objectives Modeling and Business Process Management can occur since they have the same acronym (BPM). Business Process Modeling is the act of representing a process using text, diagram and notations. Theses processes can be the current processes ("as is") or the wished improved process ("to be"). Business

Process Modeling is only one phase of the dierent phases within Business process management lifecycle.

Another important emerging technology for business process is known as Workow. Workow is the automation of business process through multiple participants by passing task from one participant to another. It permits to know which action or actions will be performed, by which actor or actors, and in which order.

According to Workow Management Coalition 1 (WfMC), workow is de- ned as: "The automation of a business process, in whole or part, during which documents, information or tasks are passed from one participant to another for action, according to a set of procedural rules."

Any product developed to support workow is called workow management system (WfMS). WfMC has dened WfMS as: "A system that denes, creates, and manages the execution of workows through the use of software, running on one or more workow engines, which is able to interpret the process denition, interact with other workow participants and, where required, invoke the use of IT tools and applications."

So what are the dierences between BPM and workow? In fact, BPM and workow can be used to dene, test and use business process. Still, some people distinguish between the two notions in that BPM is used more for business process that is done entirely by machine and in fast manner, whereas workow focus on operation or process that need human intervention and decision and that take more time to be executed. In general, workow systems deal with operations that are often distributed over a large numbers of actors. Thus, both BPM and workow systems task are overlapped and complementary.

In order to seize BPM and workow advantages, business process progress must be managed and controlled in real time. This allows decision makers to detect early any unexpected events or dysfunctions that threaten or disturb the normal business process ow. And anticipate them by taking the correct 1 The Workow Management Coalition (WfMC) is a global organization of adopters, developers, consultants, analysts, as well as university and research groups engaged in workow and BPM. http://www.wfmc.org/ decision in the right time.

In the past, companies depend on managers' experiences to detect and to prevision any improbable problems in the system. Nowadays, companies become large and larger day after day, and business process by consequence is more and more complicated.

Project objectives

The main objective for the project GOCD is to install a new paperless workow system and decision making tool to replace the current paper based system. The new workow system aims to manage and optimize received mails at COFIDIS in all mails lifecycle, starting by their arrival and ending by archiving them. In the other hand, the decision making tool will interest in optimizing mails assignment process by providing decision makers with the suitable Key Performance Indicator. At the same time, mails traceabil-ity is kept over the dierent handling phases and monitoring mails handling progress at any time.

In

Problematic: mail ow optimization COFIDIS

Workow is a key factor for the success of modern and developed enterprises.

It permits the ease and the fast transformation of data and information between dierent internal and external enterprises actors, especially with the new globalized world and enterprises fusion tendency. However designing and implementing an ecient and optimized workow is not trivial task and needs a lot of eort and analysis. In this work, we propose a new framework to model, optimize and implement company's workow applied to a real case study of mails ow at COFIDIS.

Every day, the French credit company COFIDIS receives from the post oce thousands of mails containing contracts and credit demands of dierent types. For facility, we will use the term contracts for both contracts and credit demands. Contracts types and the quantity of each type change from day to day. They can only be known in the morning of each day. This variation in quantities and types is due to marketing policies followed by COFIDIS.

Each received contract should be handled by only one company collaborator.

When contract treatment is started, it must be nished at the same day.

Each collaborator has its own bin. This bin is lled in the morning with the daily loads of dierent contracts that must be handled throughout the day. the current contract are not violated". This distribution is not optimal, but hoped to be approximated to the optimal one. If collaborators capacity in some sector is overloaded, sector responsible should take the right decision to reduce company expenses. The decision can be either to allow collaborators to take their overtime hours, to postpone some contracts to the next days or to calls temporary workers to handle the overloaded contracts.

The major concern to any decision maker is to reduce company's expenses.

To realize this in our problem, manager must know if company's current resources are capable to handle the totality of daily received contracts or not? And if not, what will be more expensive to hire temporary workers or to pay the overtime hours for company collaborators? And to answer the last question, managers must be able to estimate precisely the exact number of temporary works that will be needed to handle the overloaded contracts.

Decision maker may desire to achieve other operational and marketing objectives, even if this will lead to non optimal distribution. One objective can be giving high priority to certain types of contracts that can not be delayed or to some contracts types that are considered more protable to the company than the other types. Another objective could be to handle important contracts uniquely by company collaborators and not by temporary workers, since company collaborators have best experience and skills than temporary workers. Thus, guaranty service quality for these type of contracts. Load balancing between company collaborators can be signicance objective from the social vision of point. Maximizing protability rate by collaborator can be an interesting objective from economic vision.

Workow reengineering

Workow systems are considered as one of the key successes for modern and developed enterprises, especially with modern enterprise that took the choice of outsourcing or the choice of diusion with other enterprises. This requires a exible and a robust reengineering process that is capable to modify or even to completely replace installed workow system with a new one without aecting enterprise activities.

In general, this process starts by modeling current workow system. This gives a complete vision on the dierent steps that the workow traverses from the beginning to the end of a process, which permits a deep analysis from operational point of view. This analysis permits to identify and underline system dysfunctions and drawbacks. Knowing system deciencies help system analyst and designers to conceive and design the new workow system.

The new model is then used as the base for developing and implementing the workow system. Figure (1.1) shows the dierent steps in a classical workow reengineering process.

In the next section, we present and discuss the most recent standards and technologies that can be used for modeling and implanting workow systems. First and third steps in the workow reengineering process are modeling both the existed workow system and the expected nal workow system. The choice of the modeling notation will have a direct impact on the workow reengineering process. A complete and understandable notation will facilitate system analyst's work. For this reason, we propose to use Object Management Group (OMG) 1 adopted modeling notation for workow and business process modeling the BPMN. In the next subsection, we present the origin and the motivations for choosing BPMN as a modeling notation.

1 OMG: is an international, open membership, not-for-prot computer industry consortium. OMG Task Forces develop enterprise integration standards for a wide range of technologies, and an even wider range of industries. http://www.omg.org/ For the implementation step, it is crucial to choice xable technology that enables systems interoperability and integrity, especially with the new globalization world and the enormous development in networks and internet.

Service Oriented Architecture (SOA) and web services appear as the new tendency to answer these questions. In SOA, business application is exposed as web services that propose one or more functionalities for each service.

Still, creating and exposing services is not an easy task. We need to know how these services are organized and the dependencies between them. In addition, business processes are always the subject of changes as more and more enterprises take the choice of mergers and acquisitions. For the implementation of web services, the Web Services Business Process Execution Language (WS-BPEL, known also as BPEL) locks as the best answer as we will see later in this chapter. In the next subsections, we briey introduce both BPMN and BPEL and the motivation behind each choice for both mod-

Motivation

As we said before, BPMN is designed to deliver an understandable notation for all business users. The use of an understandable notation will reduce and remove any confusion between dierent system users in all levels. This includes business managers, system analysts, IT developers and simple employers. For this purpose, BPMN uses rich library of symbols that cover all business process details and can treat all workow pattern dened by the Workow Patterns initiative

2 [Whit 04b].
BPMN oers also the ability to have dierent end-to-end models. It can be used to model private business processes (internal workow), abstract process (process sequence which informs external user in how to contact and communicate with the process), and nally interactions between two or more business entities (collaboration process with our partners).

Another important motivation for choosing BPMN as a modeling notation is that, it has already been adopted by more than 40 modeling software producer, and many other producers are planning to incorporate BPMN in they future products. Such enterprises that have already adopted BOMN are IBM, ILOG, IDS-Scheer, SAP, Intalio. As a result, more and more ana- The answer is, while UML is mostly addressed to help in software reengineering and development, BPMN is designed to be used in business process management and to be understandable for both managers and developers. In other worlds, UML is used to model applications in an object orient approach and BPMN is used to model business process in a process-oriented approach.

The two notations are not in competition, but they are two dierent views for the system.

BPMN Element

BPMN is designed to ease and simplify business process representation for both business managers and IT specialists. As a result, OMG has chosen in its specication[OMG 06] a set of distinguishable graphical elements that are famous and well known to most business process modelers. For example, business activity is represented by using rounded-corner rectangle, whereas decision is represented using diamonds shape. The dierent elements are organized in four categories:

1. Flow Objects 2. Connecting Objects 3. Swimlanes

Artifacts

In the next sections, we present each category in more details.

Flow Objects

In this category we nd three core elements of BPDs, which are:

GateWays

A Gateway is represented as a diamond shape and is used to control

Connecting Objects

The connecting objects are used to connect Flow Objects within a diagram.

There exist three types of Connecting Objects. • Group:is used to group dierent activities without aect the ow in the diagram.

• Annotation:is used to give more information and commentaries about the diagram.

For the complete list, readers are refereed to [OMG 06].

WS-BPEL

Service oriented architecture (SOA) and web services appear as the best answer to implement and realize company's application. In SOA, business processes are exposed as web services that can be integrated and used by dierent application and dierent users. This concept is similar to the con- Many platforms support the execution of BPEL processes. Some of them provide graphical editing tools for dening BPEL processes. However, these tools reect in general the syntax and the requirements of BPEL process.

cept
From the Commercial engines that support BPEL we mention, BPEL Process Manager "Oracle", WebSphere and BPWS4J "IBM", and Biztalk "Microsoft". Other open source engines include ActiveBPEL, PXE, Twister and BEXEE.

The advantages of WS-BPEL come from its ability to be used between or within dierent enterprises applications, where each application can be exposed as web services with its own functionalities. Since BPEL is designed to cope with the Service Oriented Architecture (SOA), this leads to standardize enterprises applications and increase their interpretability in ecient and easy manner. The increasing use of web services technology will in parallel increase the importance of WS-BPEL.

The BPEL process appears for the external world as one Web service.

It uses several interfaces with a set of port types to communicate with the external services, and provides operations like any other Web service.

It can be either synchronous or asynchronous process. An asynchronous process is used for long time operations whereas synchronous process is used for operations that return a result in a relatively short time. When a synchronous process is used, it blocks its client until the process is nished and returns the result to the client. An asynchronous process does not block the client; instead it returns the results by a call-back. A BPEL process consists of activities which can be either primitive (basic) activities or structured activities. Primitive activities are basic constructs and are used for common tasks. The primitive activities can be combined using structured activities to represent business process.

In the following we show some primitive activities and their functionalities:

• <invoke> invoks other Web services,

• <receive> waits client message to invoke the business process,

• <reply> generating a response for synchronous operations,

• <assign> manipulats data variables,

• <wait> used to wait some time.

Some structured activities are listed below:

• Sequence ( <sequence>), which allows us to dene a set of activities that will be invoked in an ordered sequence

• <sequence> allows activities to be invoked in sequential ordered,

• <ow> allows parallel invocation of a set of activities,

• <switch> for implementing branches,

• <pick> to select one of a number of alternative paths(conditions)

In order to communication with the external services, a BPEL process declares partner links. These partner links interact with external web services either by invoking operations on other web services, or by receiving invocations from clients. Each BPEL process has at least one client partner link, because it must have a client that invokes the BPEL process.

BPEL document validation

As we have said before, BPEL is an XML based language. And a valid BPEL document must correspond to the BPEL specication published by OASIS.

This specication determines the structure, the tags, the attributes of a valid document and additional constraints written in a natural language. However,

several

Event handler based transformation

The rst proposed transformation approach depends on BPEL event handler construct. This approach is applicable only to a core subset of BPMN and in the condition that the diagram doesn't contain live-lock. This approach is continued to be used in every later works, as there is always some parts of BPM diagram that can not be translated with the new approaches[Ouya 07,

Ouya, Ouya 06a, Ouya 06b].
The importance of BPEL event handler comes from the possibility to have multiple simultaneously active instances in a single process instances. Each event handle in BPEL process is associated with a scope and it is enabled when the associated scope is under execution. When an associated event is triggered for some reason the body of its handler is executed. This approach is consists of three steps 1. Finding the precondition sets for all activities 2. Translate the precondition set into event condition rules (ECRs)

Translate ECRs into BPEL code

A precondition set is a combination of events and conditions to be held in order to execute certain activity in a process. For every activity several precondition set and several ways to execute it can be found. • Start events have an indegree of zero and an outdegree of one,

• End events have an outdegree of zero and an indegree of one,

• Task and intermediate events have an indegree of one and an outdegree of one,

• Fork or decision gateways have an indegree of one and an outdegree of more than one,

• Join or merge gateways have an outdegree of one and an indegree of more than one,

• Event-based XOR decision gateways must be followed by intermediate events or receive tasks,

• There is a default ow among all the outgoing ows of a gateway,

• Every object is on a path from a start event to an end event.

From the well-formed diagram, seven well structured components can be found. These components can then be mapped into the corresponding BPEL construct. The example in gure 1.10 demonstrates this mapping which is presented in [Ouya 06b].

In this approach, they propose also the use of FOLD function which replaces every well-formed component by a task object. This task object can be then used to perform iterative reduction of a componentized BPD until no component is left. Finally, ECR method is used to transfer the rest of BPD into BPEL code.

Quasi-structured pattern transformation

A new attempt to have more readable code is demonstrated in [ Ouya 07]. In this paper, we do not only try to detect the perfect structured components, but also we search quasi structured component that can be redened and modied in order to be transformed by the previous mentioned technique.

The modied components should not aect the original process semantic.

As an example, we can modify the incompatible part of the BPMN diagram by split a gateway into two gateways. In this paper, three types of quasistructured components are rened (FLOW, SWITCH and PICK component).

See gure 1.12. Since BPMN has no formal semantic, Petri-net is used in [Ouya, Dijk 07] to dene a formal semantic for a sub set of BPMN and to verify its soundness and safeness. Component that can be transferred using the control link construct is called (Synchronizing process component). The synchronizing process component is transformed into BPEL code by translating the controlow relation between all its tasks and event objects into a set of control links.

For a complete example and details on using control link construct in mapping acyclic BPMN, we refer reader to [Ouya, Ouya 07]. workow system works correctly is a good thing, still we need to ensure that it works eciently. Thus, we need more analysis to identify workow shortcoming and bottlenecks. As a consequence, system designers and analyst can solve and optimize these problems with the best manner.

To answer these issues, we propose at rst to use BPMN to model the asis workow. This will allows a deep understanding of the current workow and permits more precise operational analysis to design the wished to-be workow. The new workow is then passes through an additional phase of verication, validation and optimization, as we have proposed in[Shra 09], before being adopted to generate BPEL code. This phase can be realized by transforming BPMN model to any of modeling languages with strong formal semantics. Our choice in this work was to use Petri net as the target formal language. However, other important works in this domain exist. One of them depend on the transformation of BPMN into the Calculus of Orchestration of Web Services (COWS)[ Pran 08]. The transformation of BPMN to a set of Communicating Sequential Processes (CSP) process and events[ Wong 08] is another attempt in the domain. This method is suitable when BPMN model size is small, since the size of CSP model produced from a small BPMN model can be considerable. In [Puhl 06], static analysis is proposed after transforming a subset of BPMN to π-calculus. However this method does not cover error handling that can be represented in BPMN and this approach is restricted only to a very small size of BPMN models.

The choice of using Petri nets is justied by that i) Petri nets are particularly suitable to model systems behavior in terms of ow. ii) Since BPMN is ow-oriented, Petri nets seems to be the natural candidate for formally dening BPMN models semantics. iii) Petri nets has taken a lot of attention and has been studied from a theoretical point of view for several decades.

And there exist many tools that able to perform automated analysis on it. For a given Petri nets N (P, T,Pre, Post) and marking M 1 : • M 1 t → M 2 : transition t is enabled in state M 1 and ring t in M 1 results

in state M 2 • M 1 σ → M n : the ring sequence σ = t 1 t 2 t 3 ... t n-1 leads from state M 1 to state M n , i.e., M 1 t 1 → M 2 t 2 → ... t n-1 → M n A state M n is called reachable from state M 1 (represented by M 1 * → M n ) i there is a ring sequence σ = t 1 t 2 t 3 ... t n-1 such that M 1 σ → M n .
Ordinary nets are Petri nets whose pre and post incidence functions take values in {0, 1}. The incidence function of a given arc in non-ordinary nets is called weight or multiplicity.

A place p is called an input place of a transition t i there exists a directed arc from p to t. The notation •t is used to denote the set of input places for a transition t. At the same time, a place p is called an output place of transition t i there exists a directed arc from t to p, and the notation t• is used to denote the set of output places for a transition t. Similarly, •p is used to denote the set of input transitions for a place p, and p• is used to denote the set of output transitions for a place p. Formally, the preand post-sets

Y ≥ 0 is called P -semif low if Y T .C = 0.
Liveness is one of the most important Petri nets properties. A Petri net N is called live i for every reachable state M and every transition t, there is a state M reachable from M which enables t Boundness is another property for Petri net. A Petri net N is bounded i for each place p there is a natural number n such that for every reachable state the number of tokens in p is less than n. The net is called safe i for each place the maximum number of tokens does not exceed 1. Every other place or transition is on a path between the start place and the end place. For workow nets, the initial marking is a marking where there is one token in the initial place of the process. The nal marking is a marking with a token in the nal place of the process. A strong correctness criterion of workow nets is the soundness property. Workow Net is sound if i) the token in the source place ends in the sink place (consumed by the sink place) after a sequence of ring and there is no other token in the Nets. A strong correctness criterion of workow nets is the soundness property.

A subclass of classical

A process is sound when for each marking that can be reached from the initial marking, the nal marking is reachable.

However, using classical Petri to describe COFIDIS contracts workow tend to be complex and extremely large and does not allow modeling data or time. For this end, one can use any of the many extensions of the classical Petri net. In this thesis, we are interested in only two extensions. (i) The colored Petri nets (CP-nets or CPN) , used to model data, (ii) Timed Petri nets used to represent time. A Petri net extended with color or time is called a high -level P etri net. In the next subsection, we present these Nets in an informal manner.

Colored Petri nets

In colored Petri nets, tokens often represent objects in the modeled system. These objects in general have attributes. If a credit demand arrives to a credit company, the demand is modeled by a token in the Petri net, and we want other information such as, client name, identication number, and amount. In order to ease workow analysis and comprehension, we model the current workow "the as-is workow" at COFIDIS that we have described in section 1.2 using BPMN, see Figure 1.19. This model describes in details the dierent phases that mails have to pass in the current workow system to handle the daily received mails. As we can see from Figure 1.19, each mail must be opened and classied by type of contracts. After that, contracts are sent to the decision makers in order to assignment the contracts. When a collaborator receives a contract, he checks if the contract contains all the documents needed to correctly handle the contract. If any document is missed, collaborator contact contracts sender to reclaim missed document. At the Figure 1.19: Current mails workow within COFIDIS same time, the collaborator keeps the contracts on his desk waiting for the missed document. From this process is easily to notice that joining received missed documents to the corresponding contracts is a hard task and time consuming, since there is no trace for the contract after it has been assigned. More, the current contracts ow is performed completely in manual manner. Thus, losing some contracts components or even the entire contract is very probable, especially for those incomplete contracts. And the worst thing in the current workow is that decision maker does not have any information about the contract process progress within the dierent phases of contracts handling.

Another important problem appears concern collaborators capacities. Although the competence per contract type for each collaborator are dened in the competence matrix, in reality collaborators may spend less or more time than expected for each contract. Especially for incomplete contracts that will need properly less time than expected if they were completed ones. Thus, if the percentage of the daily incomplete contracts is(α), then the percentage of complete contracts will be (1 -α).

As a result, collaborators real capacities are not xe and vary during the day. This means, contracts assignment that has been done in the morning is no more optimal (if it was supposed to be optimal) during the day.

Another important problem is contracts assignment policy. This assignment policy is not optimal, but hoped to be near to optimal. It depends on manager experience. Bad contracts assignment may force managers to call unnecessary temporary workers to process all received contracts. Each unnecessary worker represents a considerable additional charge for the enterprise. Moreover, current contracts assignment is a static and irreversible.

Once contracts are assigned, no later modications can be realized in order to cope with any eventual work necessity or events e.g. the eventual departure of some collaborators for personal reasons. Finally, incomplete contracts kept by collaborators on their desk may represent additional load if the missed documents of incomplete contract arrive. This additional load is not counted in the current assignment method.

In order to overcome the previous mentioned problems and optimize contract handling process, we propose to replace current paper ow system by a new automated paperless workow system. Figure 1.20 demonstrates in details the proposed workow.

To ensure contracts integrality and traceability, received contracts with theirs attached documents are scanned at their arrival to form one integral electronic pack. Each electronic pack is then given a unique id (barcode). This id will be used to trace and follow contract progress from its arrival Figure 1.20: New proposed mails workow through handling process and ending by archiving. When some documents are missed for a contract, enterprise collaborator contacts concerned client by mailing him a list of missed documents. This mail contains pack id in which missed documents must be integrated. If a received mail contains new contract, it enters the assignment process. If a mail contains missed paper with a pack id, it is assembled with the corresponding pack automatically, otherwise enterprises worker search manually the corresponding pack by using enterprise information system and the client information in the missed document. This process is time consuming and may delay some contracts assemblage for one or more day.

When an incomplete contract is received, it is sent for being assembled and waits the arrival of missed documents. History for each contract is kept for further use. This history contains helpful information such as the collaborator that has already handled the contract in the past. Once missed documents are assembled to their pack, the contract is injected in the assignment process. Each incomplete contract can be reassigned to the same collaborator that has already started processing it, or assigned to a new different collaborator. In the rst case, expected processing time registered in the collaborator competence matrix is reduced since the collaborator has already studied this contract. In the second case, collaborators competences remain intact as this will be the rst time they will process the contract.

In the next two sections, we continue demonstrating the fourth and fth phases of our framework by using always COFIDIS contracts ow example. These sections will deal with validating and optimization of BPMN models.

Workow analysis

In this section, we discuss and explain how to employ Petri nets to analyze, verify and validate BPMN model. This additional phase can reveal serious problems and system deciencies that ware hidden by BPMN model. Finding system deciencies and problems will help system designers in solving and improving them in the modeling phase and before system implementation. This means, less modications and debugging time, and so, reduced cost.

In literature, many eorts exist in the transformation of BPMN model to the corresponding Petri nets or one of its extensions. Raedts and al[ Raed 07] transform BPMN model to the an extended Petri nets known as YASPER (Yet Another Smart Process EditoR). This transformation is realized in order to verify soundness property. However, no others important analysis are possible directly. In stead, authors propose to transform YASPER to classical Petri nets and then perform the wished analysis. Another attempts were done In this work, we are concerned in both behavioral properties such as Reachability, liveness and boundedness and in the structural property the P-semiow. Behavioral properties permit testing and analyzing all possible scenarios (markings) that the new system may reach from the initial state.

As a result, serious problems in the designed system can be revealed in the modeling phase. These problems are in general produced either by human mistakes or by bad interpretation of BPMN specication. System reachability is important to ensure that every possible task designed in the new workow system will be executed if the corresponding conditions and circumferences are held. Still, it is not sucient only to ensure system reachability without guaranty that the system is live (deadlock free). Liveness is important to ensure that the new workow system will never arrive at a point where it can not be advanced (blocked). Finally, the boundedness property and it particular case the safeness is important to verify that the model will handle only one taken each time.

The Figure 1.23, gives an example of a BPMN model with some errors and the corresponding Petrin nets result from the transformation proposed in [Dijk 07]. This example represents the process of funding a project proposed by one of enterprise clients. To accept funding this project, two conditions must be held. The rst condition is to convince the enterprise by the project marked study, and the second condition is to have availablenancial resources at the enterprise to fund the project. It is clear in this example that if one of the two conditions is validated to true and the other is validated to false the process will be blocked (deadlock). The example is a simple and can be veried manually in short time. In business real world, a process is in general bigger and more complicated, which requires more time and eort to verify any of the past mention properties. However, current transformation will result in unreachable marking after process termination.

To a void this problem, the ends places of the model are connected to the initial place in order to insure process continuity. And in this case only the real unreachable marking can be veried. See

Workow optimization

In the last section, we have shown how to use classical Petri net to simulate and verify some important properties of a workow system represented by BPMN model. Although verifying workow correctness is a good thing, it will be better if we can also ensure that it works eciently. Classical Petri nets are limited when they are used to represent dierent type of data 9 Toolbox for editing and analyzing Petri nets and time Petri nets (tokens). Thus, its capacity to perform performance analysis is also limited.

Representing additional information in a model may dramatically change its performance results.

For this reason, in this subsection we propose to transform the BPMN model to colored Petri nets[Jens 03]. This transformation will permit simulating and representing additional information and data in our system. As a result, perform more performance analysis on the business process to clarify its bottle-necks.

In our problem, the additional information that could be presented in the colored Petri nets includes contracts types; collaborator matrix competence (need time to handle each contract type); and complete/incomplete contracts. In colored Petri nets each color can be used to represent contract type, contract description (complete/incomplete). At the same time, each collaborator transition that used to model contract processing can dene a dierent delay for each colored token. And this will represent collaborator competences regarding contract type. We have used the famous CPN tool[Jens 07] to represent and realize our performance analysis. To distribute contracts, we simulate the same process that is used currently by COFIDIS. This distribution is done randomly without any concern to collaborator competence. To test current contract ow at COFIDIS, we simulate the contracts workow with a load of 500 contracts of 10 dierent quantities per type and for ten collaborators. The load of every collaborators was checked at dierent moment of time in the day, at the morning (time=0), at the end of work day (time=80) and nally the time for each collaborator to handle his entire daily load was also noted.

Simulation results show clearly that the current contract assignment policy is the main factor that obstacles the improvement of current contract workow at COFIDIS. Result shows that even though collaborators start their day with nearly equal load of contracts, at the end of the day the dierence in collaborators loads are very large. This situation persists even with multiple executions of the simulator for the same sample of contracts. This is a normal result as the assignment process is performed randomly. The only thing that changes with dierent executions of the simulator is the persons with highest or lowest load. Even with new samples with new quantities of contract per type, we observe the same situation. Figure 1.26 shows a part of the colored Petri nets with dierent loads of three collaborators (Col 5, Col 6 and Col 7) after passing 80 unit of time since starting contracts handling process. As we can notice collaborator 5 and 6 have respectively 27 and 29 contracts in their buers waiting to be handled. This represents nearly the half of the number of the contracts in the buer for the collaborator 7 with 57 contracts.

The following table, Table 1.3, demonstrates the simulation results for the ten collaborators in the same sample. It demonstrates the number of contracts to handle per collaborator at two times, at time=0 (contract processing is started) and at time=80 (the work hours is terminated).

To calculate the needed unit of times to handle all received contracts using current assignment algorithm, we keep executing the simulator until there is no more contract in collaborators buers. Table 1.4 shows the total unit of times needed to handle all contracts when using two dierent contracts assignment for the same sample of contracts. From the Table 1.4, we can notice that the current assignment process is far a way to be optimal or even constants. Not only, every contracts assignment needs dierent number of work unit time but also company collaborators must exceed theirs daily work hours (80 unites of time) to handle all contracts. Thus, bad contracts assignment could lead to duplicate the number of work unit time according to the number of work unit if the contracts were assigned optimally. And that means to decision makers either to postpone some contracts or hire temporary workers which forms additional unjustied costs for the company. In order to solve this problem and ensure contract assignment optimality, contracts assignment process must rely either on proofed exact algorithm or on a robust mathematical formulation. This formulation must be capable to cover all the aspects of the problem and give the solution in reasonable time.

Col_ID

In this thesis, we have chosen the later choice since we can prot essentially from the Petri nets formulation of the problem and induce some important information.

The advantage of using Petri nets is its ability to be used in the analysis of the dierent ow in a workow. More precisely; the analysis of Petri necks, but it also can help in inducing some useful mathematical formulation.

Thus, we can these formulations with additional information from enterprise information system, to optimize contracts ow.

In[Camp 90], Campos present the formulation (1.1) to be used in analyzing Petri nets P-semiow.

Y T i .W -.Z (f ) t Y T i .M o , ∀ P -semif low representing collaborator i. (1.1)
Where

• Y T i : P-semiow for collaborator i

• W -: Weight of the arc to transition from its input place

• Z (f ) t : Represents the weighted workload vector of transition with their corresponding routing ration (normalized with feedback transition TF )

• M o : The initial marking For this purpose, at rst we have presented the dierent operators that are working in the company and the competence matrix that determine the needed time for each operator by contract type. This is can be done by duplicating the part c in the Figure 1.24 N × M times, where N is the number of operators and M is the number of dierent types of contracts. For each contract type related to a certain operator, the corresponding Contract processing type transition is associated to processing time in the operator competence matrix. Figure 1.27 demonstrates an example of Petri nets resulted from unfolding colored Petri nets for two operators and for two contract type. For facility in this example we use two contract types with two colors RED and BLUE.

After these transformations, Campos's formulation can be applied and collaborators daily loads can be induced with the help of additional information from company registration as seen in (1.2. J j=1

X ij × T ij + K k=1, C ik × (a ik × T new ik + I l=1,l =i a lk × T old lk ), ∀i ∈ {1, 2, .., I} (1.2)
Where

• X ij : The number of contracts of type j assigned to worker i,

• T ij : Needed time for primary, secondary workers i to handle contract type j for the rst time,

• K: The number of assembled contracts from the day before and had not been handled yet,

• A IK : two dimensional matrix representing the historic of assembled contracts k, where

a ik =    1 if contract k was treated by collaborator i, 0 otherwise.
• C ik : Binary variable, where • T new ik : needed time to treat assembled contract k if it is assigned to the same collaborator i that has already treated it,

C ik =          1 if assembled contract k is assigned to collaborator i, 0 otherwise.
• T old ik : needed time to treat the assembled contract k if it is assigned to a new collaborator i

Since the formulation in (1.1) demonstrates collaborator i possible load, this charge must not exceed collaborator daily capacity CAP i , which is determined in the morning of each day. As a result formulation (1.2) becomes the left hand side of the inequality in (1.3). This inequality must be respected at each time contracts are assigned.

J j=1 X ij × T ij + K k=1, C ik × (a ik × T new ik + I l=1,l =i a lk × T old lk ) ≤ Cap i ∀i ∈ {1, 2, .., I} (1.3)
This constraint now can be used to optimize contracts assignment process and as a result minimize the number of called temporary workers needed to handle all received contract. The formulation of all problem aspect has gen-

Conclusion

In this chapter, we have presented a new framework for workow reengineering. The proposed framework uses the most recent and promising language to model and execute workow, the Business Process Execution Language (BPEL) and the Business Process Modeling Notation (BPMN). It uses BPMN to model the as-is and to-be workow and it uses BPEL to implement the target workow application as web service. The choice of BPMN is justied by its capacity and richness to represent dierent workow patterns and dierent business process. BPMN is a comprehensive notation for both managers and system analysts and it eases the exchange of ideas between them to have a ne and deep operational analysis for the system. This permits to identify system weakness and draw backs from operational point of view.

Thus, a new ecient and optimized workow can be designed using BPMN.

The target BPMN model is then can be used to generate BPEL code. Different approaches and techniques used to generate BPEL code from BPMN model have been briey introduced. These approaches have passed considerable steps toward complete and automatic code generation. They have been grouped and implemented in one open source tool called BPMN2BPEL. The tool takes as an input a BPMN model that conforms to a particular XML format and outputs BPEL process. Thus, it is sucient only to model the wished workow using BPMN to obtain the nal workow implementation.

However, BPMN exibility may leads to undesired properties, such as deadlocks and livelock. These properties will be directly reected in the nal code implementing the target workow. More, BPMN is process oriented notation, and it is limited when it come to represent data. Thus, to overcome these problems, two additional phases are applied to BPMN representing tobe model before being adopted to generate BPEL code. A verication and a formal language and has taken a lot of attention and consideration where many tools are consecrated to verify their undesired properties. Additional advantage of using Petri nets is the ability to perform performance analysis in which mathematical formulation can be induced and so mathematically formulate the problem. This formulation can then be solved by any mathematical solvers to have exact optimal solution. Real case study has been used to demonstrate the dierent phases of the proposed frameworks. And new assignment problem is appeared within the new workow.

Related Problems

In literature, we nd many assignment problems with dierent formulation and constraints. In this section we are interested in only two assignment problems that relate contract assignment problem at COFIDIS. Resolution methods for these problems are discussed and similarities and dierences to our problem are underlined.

Bin packing problem BPP

M inimize z = n i=1 y i (2.1) Subject to m j=1 wx ij ≤ cy i , ∀i ∈ {1, 2, ..., n} (2.2)
m j=1 x ij = 1, ∀i ∈ {1, 2, ..., n} (2.3)
y i , x ij ∈ {0, 1} (2.4)
Where • Next-t: The algorithm starts by lling the rst bin. When the bin is full, the algorithm opens new bin and starts lling it. The process continues until there are no more elements in our list. There is no concern in this algorithm to verify if the next element in the list may t to any previous bins.

y i =    1 if bin i is used; 0 otherwise.
• First-t: The algorithm puts the current element in the list in the rst open bin that can hold this element. If there is no capable open bin, a new bin is opened to place the current element.

• Best-t: The algorithm puts the current element in the list in the opened bin with the smallest free space that can hold this element. If there is no capable open bin, a new bin is opened to place the current element.

• Worst-t: The algorithm puts the current element in the list in the opened bin with the largest free space that can hold this element. If In two dimensional bin packing problem, objects have two dimensions (criteria) that must be respected when packing the object. A good example of two dimensions BPP is when packing objects with a width and a length for each. In three dimensions BPP, objects have three dimensions that must be respected when packing these objects. In most literatures, three dimensions BPP objects are represented by boxes with dierent volumes. In fact, BPP can have as many dimensions as we wish. These dimensions can be either physical or imaginational dimensions.

Another well studied variant of BPP is the extendable bin packing problem [Dell 98, Co 06]. In this BPP type, bins have initial capacities that can be extended later. The extension is applied if the original bins capacities were incapable to pack all objects. This variant can be useful in presenting work hours and to determine the exact needed over timed hours.

The previous variants of BPP can be either on-line [GGal 95, L Ep 07,

Csir 98] or o-line [Dawa 01, Dell 98] bin packing problem. In the on-line BPP, object information is known once that the object is packed and there is no concern to objects sequences. In other words, objects are packed according to their arrival. Whenever an object is packed, it can not be repacked later.

Packing objects in production chain is a good example on on-line bin packing.

In the contrary, the o-line bin packing problem, complete information about all objects is available before starting packing process. Objects can be packed and repacked as will as packing process did not terminate. This allows a better exploitation for bins capacities.

Generalized assignment problem GAP

Another famous assignment problem is the generalized assignment problem (GAP). The GAP is a generalization of the Multi-knapsack problem

M aximize z = n i=1 m j=1 p ij x ij (2.5) Subject to m i=1 w ij x ij ≤ cap i , ∀i ∈ {1, 2, ..., n} (2.6) m j=1
x ij ≤ 1, ∀i ∈ {1, 2, ..., n}

(2.7)

x ij ∈ {0, 1}

(2.8)

Where

x ij =    1 if

The suitability of BPP and GAP to represent COFIDIS contracts assignment problem

In studying the two presented problems, we notice the following. The two problems have dierent objectives and dierent formulation. BPP searches to minimize the number of used bins to pack all objects in the object list without any consideration to prot, whereas GAP problem considers prot for each packed object and the allocation of all objects is not considered as a constraint. This means it is possible to have an optimal solution in GAP problem without distributing all objects. More, in BPP the objects have an equal value whatever was the bin used to pack them, which is not the case in the GAP problem, the prot of an object depends on the object and on the agent treating that object.

Comparing the previous BPP and GAP problem description, with COFIDIS contract assignment problem, we see that COFIDIS assignment problem corresponds to both the GAP and BPP problem. Each collaborator at COFIDIS represents a bin with a capacity (daily work ours), and each contract represents an object. Processing time for each contract dened in the competence matrix is the weight for the contract regarding the collaborator that will handle it.

However, COFIDIS assignment problem corresponds to GAP problem in searching optimal treatment time for company workers. Still, GAP problem searches optimal solution without any concern to the number of used bins.

This means it is possible to have optimal solution that assigns contracts to temporary workers despite the existence of available free time to company collaborators. However, COFIDIS wants to assign contracts to their collaborators and to ll their capacities before calling any additional temporary worker.

2.3

The Generalized assignment problem with identied rst-used bins (GAPIFB)

In order to overcome BPP and GAP weakness to present COFIDIS contract assignment problem, we present in this section our new assignment problem.

The new problem will be called the Generalized Assignment Problem with Identied First-used Bins (GAPIFB). GAPIFB regroups characteristics from well known assignment problems, the Bin Packing Problem and the Generalized Assignment Problem. The new problem can be dened as a set of tasks (objects) that must be assigned to a set of bins (agents). Each task size is not xed and depends on the bin that will be used to pack the task, according to a predened competence matrix. Bins can be of two types, primary bin (to present company collaborators) and secondary bins (to present temporary workers). The use of secondary bin is allowed only when the use of all primary bins are incapable to pack all tasks. The objective function is to minimize the number of used secondary bins.

GAPIFB mathematical formulation

In order to formulate the new GAPIFB problem, we use a set of binary and integer variables instead of using completely binary variable to present the problem. We use binary variable U i only to represent both primary workers and secondary workers. Where U i takes the value 1 if the worker i is used , otherwise it takes 0. And since our objects consist of contracts of several types, we use an integer variables X ij that represent the number of contracts of the same type j assigned to worker i. Notice that J represents contracts types number. In this way, we reduce total variables number that is normally used when formulating BPP. In fact, we pass from linear problem with binary variables to linear problem with integer variables.

For example, an instance of the problem with N primary workers, M The following is a generic formulation for the new assignment problem. Any additional specications for this model to adapt the real case at COFIDIS are not covered her for simplicity reasons. Thus the mathematical formulation to represent GAPIFB is the following:

M in I i=1 U i (2.9) Subject to J j=1 X ij × T ij ≤ CAP i × U i ,
∀i ∈ {1, 2, .., I}

(2.10)

I i=1 X ij = QT j , ∀j ∈ {1, 2, .., J} (2.11) N i=1 U i = N,
(2.12) • N : Is the number of primary bins (company Collaborators),

U i ∈ {0, 1} ∀i ∈ I, ∀ (2.13) X ij ∈ Z + , ∀i ∈ {1,
• M : Is the number of available secondary bins (temporary workers),

• I: Is the number of primary bins and available secondary bins, I = N + M ,

• U i : Boolean variable to present primary, secondary bin i, where : ∀ U i ∈ {U 1 , U 2 , ..., U N }, U i represents primary bins, : ∀ U i ∈ {U N +1 , U N +2 , ..., U I }, U i represents secondary bins,

• CAP i : Is primary, secondary bins capacities,

• J: Is the number objects types (number of contracts type),

• T ij : Needed time (cost) for primary, secondary workers i to handle task of typej,

• X ij : The number of task of type j assigned to primary or secondary bin i.

Constraint (2.16) ensures that the capacity of agents is not violated. Constraint (2.17) ensures that all tasks are allocated and each task is assigned to only one agent. To ensure the use of all primary agents (which was a the main problem in classical BPP), we add constraint (2.18). This constraint forces the solver to search solution where U i =1, ∀ i ∈{1,2,...,N}, this set contains only primary agents and N is the number of company primary agents.

GAPIFB and decision making tool

As we have said before, one of the major GOCD projects aims is to install a new decision making tool at COFIDIS. The purpose of this tool is to optimize contracts handling process for both short-term (daily received contracts) and for the mid-term (received contracts for a predened period). In the shorttem, decision makers are concerned by the following issues.

• Is company resources are capable to handle all received contract?

If yes, what contracts assignment they must follow?

If not, what is the minimum number of temporary workers are needed to handle all received contracts;

• Can they choose another objective function to distribute contracts?

• How can they optimize company resources in real time, to cope with eventual events, such as,

The sudden departure of some employers,

The increase of collaborators free capacity caused by handling incomplete contracts or assembled contract as we have seen in 1.5.

The last point is very essential, since collaborators free capacities change during the day as we have explained in the operational analysis in 1.5. This change is result from handling incomplete contracts which take less time than completed ones and from handling complete contracts that have more or less time than it was expected in the competence matrix. Thus, even though contracts assignment was optimal in the morning, it will not be so as time passes. And it is probable that collaborators will have free capacity to handle more contracts. To optimize company resources, we propose to calculate for each collaborator the real processing time for each contract ha has handled.

When the accumulation of this time reached a predened threshold, an alert is triggered to inform decision maker to lance contracts assignment process again with the new parameters. Thus, more contracts can be assigned to collaborators or a better optimal solution can be found. The new decision process will modify the proposed workow in Figure 1.20 to be as the one in In the mid-term, decision makers would like to know if they can postpone some contracts in over loaded days to those days with weak load (underloaded days) to avoid hiring unnecessary workers in the current day.

In the following we present an approach to handle contract handling optimization for both short-term and mid-term duration. The approach depends mainly on an interactive decision making tool. This tool will allow decision makers to simulate contracts assignment process and see the impact of their decisions in real time. In both approaches, minimizing the number of called temporary workers is the major objective. This is very important, since humane resources are the main nancial consumer for any services company.

Each approach will be presented as an integer linear problem, where there exist several advanced algorithms for solving it such as, a branch and bound, branch-and-cut and branch-and-price.

Short-term approach

For the short-term approach, we propose a two stages decision making approach. In the rst stage, the GAPIFP formulation is used to know if company current resources are capable to handle daily received contracts, and if not, the formulation will determine in exact the minimum number of temporary workers needed to handle all received contracts. In the second stage, contract assignment can be optimized according dierent criteria, where a set of objective functions to assign contracts is proposed to the decision maker.

These new objectives are limited by the number of temporary workers that the manager has decided to hire in the rst stage. Thus decision makers have the possibility to see and evaluate the direct eect of their choices concerning contracts assignment. of secondary workers needed to treat all contracts will be given to decision maker. Decision maker then decide whether to hire secondary workers or not.

If the decision was to hire temporary workers, he must decide if either to hire the totality needed secondary workers or to hire certain number dened as "L"? In the second stage, the nal choice of the used objective function is left to decision makers. One objective can be to give high treatment priority to contracts that can not be delayed or to contracts considered as protable to the company. Another objective could be to treat important contracts types uniquely by company collaborators as they have the best experience and skills. The fairness of collaborators loads can be signicance objective from the social vision of point. To maximize the rate of protability by collaborators can be an interesting objective from economic vision. Notice that the second objective is always limited by the number of temporary workers that the decision makers decide to take. The following represents the notations used to formulate the rst stage:

• N : The number of primary workers (company collaborators),

• M : The number of available secondary workers (temporary workers),

• I: The number of primary workers and secondary workers, I = N + M , • QT j (t) : Quantity of contract type j at time t, QT j (t) ∈ {QT 1 (t), QT 2 (t), ..., QT J (t)},

• T ij : Needed time for primary, secondary workers i to handle a contract of type j,

• K: Number of assembled contracts during the day before and had not been handled yet,

• A IK : Two dimensional matrix representing the historic of assembled contracts, where a ik =    1 if contract k was handled by worker i , 0 otherwise.

• C ik : binary variable, where

C ik =    1 if assembled contract k is assigned to worker i, 0 otherwise.
• T new ik : Needed time to handle assembled contract k if it is assigned to the same worker i that has already handled it,

• T old ik : Needed time to handle the assembled contract k if it is assigned to a new worker i,

• P rs(t): Set contains company workers present at time t,

• Abs(t): Set contains company workers absent at time t.

The adapted GAPIFB mathematical formulation to minimize the number of temporary workers is the following:

M in I i=1 U i (t) (2.15) Subject to K k=1, C ik × (a ik × T new ik + I l=1,l =i a lk × T old lk )+ J j=1 X ij × T ij ≤ Cap i (t) × U i (t), ∀i ∈ {1, 2, .., I} (2.16) I i=1 X ij = QT j (t), ∀j ∈ {1, 2, .., J} (2.17) K k=1 C ik = K, ∀i ∈ {1, 2, .., I} (2.18) N i=1 U i (t) = |P rs(t)|, (2.19) U i (t) = 0, ∀U i (t) ∈ Abs(t),
(2.20)

U i ∈ {0, 1} ∀i ∈ I, (2.21) X ij ∈ Z + , ∀i ∈ {1, 2, ..., I}, ∀j ∈ {1, 2, ..., J} (2.22)
The rst stage is computed at the morning of each day and before handling any contract (at time equal 0). Constraint (2.16) ensures that the capacity of agents is not violated. Constraints (2.17) and (2.18) ensures that all contracts are allocated and each contracts is assigned to only one agent. To ensure the use of all primary workers (which was a problem in classical BPP), we add constraints (2.19) and (2.20) . These constraint forces the solver to search solution where U i (t)=1, ∀i ∈ P rs(t). |P rs(t)| is the cardinality of the set P rs(t) (the number of element in the set). This set contains only primary worker that are available at time t.

The second stage is formulated as GAP problem and the decision of manager from the rst stage is used to determine the number of hired temporary workers. In this stage, L is the number of secondary worker the manager decide to hire.

Although, the two stage are executed at the morning of each day, the second stage can also be executed at any time t of the day, for example when workers accumulated free capacity is attained the predened threshold as we demonstrated in Figure 2.1.

As we said before many objectives can be used in the second stage, but for facility we chose here one objective which is to minimize the total treatment time for all agents.

M in

N +L i=1 J j=1 X ij × T ij + N +L i=1 K k=1, C ik × (a ik × T new ik + N +L l=1,l =i a lk × T old lk ) (2.23) K k=1, C ik × (a ik × T new ik + I l=1,l =i a lk × T old lk )+ J j=1 X ij × T ij ≤ Cap i (t) × U i (t), ∀i ∈ {1, 2, .., I} (

Mid-term approach

In the short-term approach, we consider received contracts for only one day only. And we suppose that the daily received contracts must be treated at their arrival day.

In reality, decision maker can decide to postpone some contracts and not to call any temporary workers to treat the overloaded contracts. This decision could be taken, for example, when the nancial resources do not permit to employ temporary workers, or when these contracts are not of great importance. On the other hand, COFIDIS is not always overloaded, and received contracts can be less than COFIDIS capacity, which result in loss of work-hours in under loaded days. Add to that, capable workers can be absent when the company receives their favor contracts.

In this section we improve the previous approach by considering contracts ow over a given period D instead of only one day. We suppose that each contract type can be delayed for some days before being treated. This delay allows decision makers to postpone some contracts that are received in overloaded days to those days which are under loaded or even to those days when capable workers are present. We argue that, this will reduce the number of called temporary workers in overloaded days, and at the same time, will ensure entire exploitation of company resources in under loaded days. Figure 2.3 demonstrates this process. In our model, we assume a xed number for both company workers and available temporary workers during a given period D. To meet work condition reality, where some company workers can be absent in some days, we dene two sets, Prs set and Abs set. The rst set contains company workers present at day d=1 to d=D, whereas the second (Abs set), contains company workers absent in the same period.

The formulation and the used notation for the improved model is dened in the following • M : Number of available secondary workers (temporary workers),

• I: Number of primary worker and available secondary workers, I = N + M ,

• U di : Boolean variable. It presents if primary/secondary worker i, is used in day d,

• QT dj : Expected received quantity of contract type j in day d,

• CAP di : Primary/secondary workers i capacities in day d,

• X dij : Number of contracts of type j assigned to primary/secondary worker i in day d, integer variable. ensures that the capacity of worker i in day d will not be violated. To be sure that all received contracts in the period [1, D] will be assigned, we add constraint (2.34).

M in

D d=1 I i=1 U di (2.30) Subject to D d=1 N i=1 U di = |P rs| (2.31) U di = 0, ∀U di ∈ Abs (2.32) J j=1 X dij × T ij ≤ CAP di × U di , ∀i ∈ {1,
To show that the contracts can be postponed before the date D (D excluded), constraint (2.35) is used, which is induced from inequality (2.38).

X dβj ≤ d α=1 QT αj -( d-1 α=1 I i=1 X αij + I i=1 i =β X dij ) (2.38)

Simulation and test results

In order to test and evaluate our two approaches, we use CPLEX 1 solver which uses branch and bound method to compute optimal solutions for both approaches, short-term and mid-term 2 . Considered results in the short-terms are only for the rst stages i.e. the results for the GAPIFB formulation.

There is no interest to present second stage results, as they are qualitative issue left to decision makers.

In the short-term approach, we use real samples registered in COFIDIS historical records. The results of our approach are then compared to the results obtained by COFIDIS current used method. Our approach is capable to detect overloaded and under loaded situation. In overloaded situation, it

gives the exact number of needed temporary workers to treat all received contracts, which is always less than or equal the number realized by COFIDIS current used method. No company worker is excluded from any of the proposed solutions. This is a major problem when solving the problem by a classical BPP formulation. Using BPP formulation could exclude some company workers from the solution, if the use of temporary workers gives better results. The execution time within the size of our problem, is ordered by milliseconds, and this is very satisfactory to COFIDIS decision makers.

For condentiality reasons, the used samples are generated randomly.

Each sample simulates the received contracts over a period of twelve days.

The number of company worker and available temporary workers is assumed to be xed over the twelve days and to be 100 and 10 consecutively. between 4200 and 5200 contracts per day. Company workers competence matrix is also generated randomly. We suppose that all temporary workers have the same competence by contract type. Simulation results of the shortterm approach and for the rst stage with a period of 12 days can be seen in Table 2.1.

Zeros in the column, Needed temporary workers, implies that these days are under loaded and there is no need to call any temporary worker.

With the current assignment method at COFIDIS, it is probable to call unnecessary temporary worker in these days as the optimality is not guaranteed.

This can be seen clearly by examining the generated sample for the days 4 and 8. In these days, we receive the same quantity of contracts (4,600 contracts), but in day 4 we need four additional temporary workers than what we need in day 8. This is justied by the dierences in quantities for each contract type from one day to another.

To verify our mid-term approach credibility, we use the same samples that we have used in Table 2.1. We dene four periods of time that the received contracts can be postponed to, when the company is overloaded. These periods are dened by three, six, nine and twelve days. Optimal solution for each period can be seen in Table 2.2 in the rst line. The corresponding cumulative sum of the obtained solutions for the same period using shortterm approach can be seen in the second line of the same table.

From Table 2.2, we see that 25% of used temporary workers in short-term approach could be saved by using our proposed mid-term approach, which is signicant to company decision makers. Prot average over ten random generated samples and for four period of times are demonstrated in The originality in the new problem is the existence of two types for bins, primary bins and secondary bins. Primary bins must be used and lled at rst, before any use of any other secondary bins.

This problem represents a real assignment problem obtained from COFIDIS Credit Company, where tasks represent contracts and bins represent company collaborators and temporary workers that treat these contracts.

The problem has been formulated as an integer linear problem (ILP) with help of the results obtained from the performance analysis in the optimization phase of the framework proposed in the last chapter. The optimal solution was then calculated using CPLEX solver, which uses an advanced constraintbased optimization techniques to nd problem optimal solution. Problem execution time is ordered by milliseconds. Our model shows the capacity to detect overloaded and under loaded situations. Secondary bins are used only and only if tasks load exceeds primary bins capacities. In both, under loaded and overloaded situation, all primary bins appear in the optimal solution.

size is in millisecond, there is no interest to develop our own exact solution method. However, a dedicated resolution method to solve GAPIFB can form a rich subject to be explored.

Chapter 3

Conclusion and perspectives

This thesis has been realized in the context of the GOCD project, to install a new dematerialized workow system and helping decision tool. Through this project, new problems have been emerged leaving wide horizon for other researches.

In the rst part of this work, we have presented and discussed a new framework to model, verify, optimize and implement workow systems. The proposed framework uses the most recent and promising language to model and execute workow, the Business Process Execution Language (BPEL) and the Business Process Modeling Notation (BPMN). It uses BPMN to model the as-is and to-be workow and it uses BPEL to implement the target workow application as web service. The choice of BPMN is due to its capacity and richness to represent dierent workow patterns and dierent business process. BPMN is a comprehensive notation for both managers and system analysts and it eases the exchange of ideas between them to have a ne and deep operational analysis for the system. This permits to identify system weakness and draw backs from operational point of view. Thus, a new ecient and optimized workow can be designed using BPMN. The target BPMN model is then can be used to generate BPEL code. Dierent Generalized Assignment Problem with Identied First-used Bins (GAPIFB).

As BPP, the new GAPIFB problem consists of allocating a set of dierent tasks to a set of bins with dierent capacity for each bin. On the other hand, tasks' weights in the new problem change from one bin to another according to a predened competence matrix, as it is dened in the GAP problem.

The objective function in the new problem is to nd the minimum number of needed secondary bins to pack all existing tasks, if the use of primary bins was not sucient. The originality in the new problem is the existence of two types for bins, primary bins and secondary bins. Primary bins must be used and lled at rst, before any use of any other secondary bins.

This new problem has been formulated mathematically and its entire dimensions have been covered. This formulation was realized with the help of the performance analysis realized in the optimization phase of the proposed framework.

It has been formulated as an integer linear problem (ILP). The optimal solution was then calculated using CPLEX solver, which uses an advanced constraint-based optimization techniques to nd problem optimal solution.

Problem execution time, within the size of the problem at COFIDIS, is ordered in milliseconds. The mathematical model for the new problem has proved that it was capable to detect overloaded and under loaded situations.

Secondary bins are used only, and only if, tasks load exceeds primary bins capacities. In both, under loaded and overloaded situation, all primary bins appear in the optimal solution. This forms a real problem if we try to solve our problem by classical BPP formulation. Classical BPP formulation does not distinguish bins types when it searches the optimal solution, which makes it possible to exclude some primary bins if the use of secondary bin gives best result. In addition, BPP denes constant weight per task type, whatever the used bin was, which does not represent the case in the GAPIFB. Simulation results show that GAPIFB model ensures optimal tasks distribution.

We propose to integrate the new assignment problem in decision making tool. This tool helps decision makers in taking theirs decisions for both short-term "daily decision" and mid-term "decision over several days". In the short-term, the proposed approach allows a real time optimization for contracts assignment where contract assignment process is controlled and monitored all long the day.

The proposed mid-term approach allows COFIDIS to get advantages when company capacity is under loaded. Thus, distributing the loads in overloaded day over these day where the company is under loaded.

Real samples from COFIDIS have been used to test the proposed approaches for both terms, short-term and mid-term. Simulation results show that our approaches are more ecient than the current used method at COFIDIS. With short-term approach, COFIDIS decision maker knows in advance the exact number of temporary worker that they will need to treat all received contract, which forbids unnecessary call to temporary workers.

Mid-term approach shows the ability to save up 25% of temporary workers when considering contract distribution over a predened period. The only problem in this approach is to predict correctly received contracts quantities and theirs types over this period. We believe this is not a problem, since COFIDIS has large historical data on the received contracts types and quantities over years. These data can be used with any known prediction method to estimate the expected received contract over a given year period.

Figure 1 :

 1 Figure 1: Process lifecycle

Figure 1 . 1 :

 11 Figure 1.1: Workow reengineering process

  eling and implementation business process and workow. Thus, the graph in Figure (1.1) becomes the one in Figure (1.2) after adding the proposed modeling standard and technologies.

  lysts and system architects have become familiar with BPMN and adopt it in theirs business process modeling. Another important motivation to choose BPMN for business process modeling is the possibility of generating automatic executable BPEL code from a BPMN diagram. Although the proposed transformation in BPMN specication is not complete, current researches are 2 The Workow Patterns initiative is a joint eort of Eindhoven University of Technology and Queensland University of Technology which started in 1999. The aim of this initiative is to provide a conceptual basis for process technology. http://www.workowpatterns.com/ promising. We believe it is only a question of time before obtaining a complete code generated from a BPMN diagram. But why to chose BPMN instead of UML activity diagram to model business process, knowing that UML is the most famous modeling standard for software development.

  represented by a circle. It can be of three types, Start, Intermediate or End event. Each event represents something that happens during business process. They can aect the ow of the process and usually have a cause or a result. See gure 1.3.

Figure

  Figure 1.3: Events Objects

Figure 1

 1 Figure 1.4: Activities Objects

Figure 1

 1 Figure 1.5: Gate Ways Objects

•

  Flow: represented by solid line and arrowhead to shows in which order the activities will be performed. To indicate a default choice of decision • Message Flow: A Message Flow is represented with a dashed line and an open arrowhead. It shows what the messages ow between two process participants. • Association: An Association is represented with a dotted line and a line arrowhead. It is used to associate an Artifact,data or text to a Flow Object. See gure 1.6.

Figure 1

 1 Figure 1.6: Connecting Objects

Figure 1 . 8 :

 18 Figure 1.8: Artifacts in BPMN

  already used by object brokers DCOM and CORBA. The Organization for the Advancement of Structured Information Standards (OASIS) 3 . has adapted the Web Services Business Process Execution Language (WS-BPEL, known also as BPEL) as standards for web services implementation. According OASIS, WS-BPEL is dened as "a language enabling users to describe business process activities as Web services and dene how they can be connected to accomplish specic tasks[Arki 05]". WS-BPEL is an XML-based language enable task-sharing across multiple organizations using a combination of Web services. It uses the Simple Object Access Protocol (SOAP), Web Services Description Language (WSDL), and the Universal Description, Discovery, and Integration (UDDI). BPEL comes from a combination of two early workow languages, XLANG language designed by Microsoft and Web Services Flow Language (WSFL) designed by IBM. The later based on the concept of directed graphs, whereas the former based on a block-structured language. In 2003, BPEL was submitted to OASIS for standardization, and this gave WS-BPEL more acceptances 3 OASIS: is a not-for-prot consortium that drives the development, convergence and adoption of open standards for the global information society. http://www.oasis-open.org in industrial world.

  Figure 1.9: Example of BPEL Process

4

  with the collabo- ration of Eindhoven University 5 in Netherlands. These approaches can be are classied into three categories (event handler based transformation, pattern based transformation and control link based transformation). Each time a new approach is proposed, it aims to improve the readability and the completeness of others approaches.

Figure 1 .

 1 Figure 1.11, demonstrates the use of FOLD proposed in [Ouya 06b].

Figure 1 .

 1 Figure 1.10: Mapping well-structured componants into BPEL

Figure 1 .

 1 Figure 1.13: Example of acyclic component neither safe nor sound

Figure 1 .

 1 Figure 1.14: Model transformation in order to use BPMN2BPEL tool as proposed by Pau et al.

  Figure 1.15: Proposed framework for workow reengineering

Figure ( 1

 1 Figure (1.16).b, represents the same Petri nets but after t1 has red. So, The new marking for this net become 2p 1 +0p 2 +2p 3 . Formally, Petri net is 4-tuple N = (P, T, Pre, Post), where

Figure 1 .

 1 Figure 1.16: An example of Petri nets.

  of a transition t ∈ T are dened respectively as •t = {p|P re(p, t) > 0} and t• = {p|P ost(p, t) > 0}, and the preand post -sets of a place p ∈ P are dened respectively as •p = {t|P ost(p, t) > 0} and p• = {t|P re(p, t) > 0}. C = P OST -P RE is a n × m incidence matrix for the net N with n places and m transition . The vector X ≥ 0 is called T -semif low if C.X = 0, and the vector

  Petri nets class is Workow Nets. A workow net is a Petri net with a clear starting and ending point; the start place i and the end place o. It is used as a tool for the representation, validation and verication of workow procedures, see Figure (1.17).

Figure 1 .

 1 Figure 1.17: Workow Net

  These attributes can not be easily represented by a token in a classical Petri net. By using colored Petri nets, each token has a value referred to as 'color', and transitions determine the values of the produced tokens depending on the basis of the values of the consumed tokens. This mans, each transition describes the relation between the values of the consumed token 'input tokens' and the values of the produced taken 'output tokens'. Preconditions on the tokens values can be set and the transitions will re only if these preconditions are satised. For more details on colored Petri nets, readers are refereed to [Jens 03] 1.4.2.2 Timed Petri nets In timed Petri nets time is used to describe system durations and delays (temporal behavior). Time can be introduced in Petri nets in many ways. It can be associated to tokens, places, and transitions or to any combination of them. In this work, we are interested by time associated to transition. For this type class of Petri nets, for each transition t we dene a lower bound d and an upper bound D of time, [d, D] with d ≤ D. The lower bound d must be ≥ 0 and the upper bound D must be ≤ +∞. When the transition t is enabled, it can re only when d time unites are passed and before D times unites are reached. For example, in Figure (1.18), If one token arrives at P 0 at time 3 and another token arrives at P 1 at time 5, then the transition t0 can re only after 8 unit of time. If a transition has no explicit temporal constraint, then [0, +∞] is assumed by default.

Figure 1 .

 1 Figure 1.18: Timed Petri nets

  using a new promising extension to Petri nets called YAWL (Yet Another Workow Language)[Aals 05, Deck 08, Ye 08]. YAWAL is a new workow modeling language with formal semantics that extend Petri nets. It was developed by Eindhoven University of Technology and Queensland University of Technology. However, verication YAWL model is computationally more complex than the corresponding Petri nets. The most remarkable work on the transformation of BPMN to Petri nets is that one done by Dijkman and al in[Dijk 07]. The authors extend BPMN transformation to Petri nets that was already initiated in[Ouya] to ensure a core subset of BPMN is deadlocks and livelocks free before transforming it to BPEL. The authors succeeded in transforming most BPMN objects such as subprocess and exception handling. Message ow and initial state of BPMN model have been also included in their paper. Still, the mapping does not

Figure 1 .

 1 Figure 1.21: The mapping of task, events, and gateways to Petri-net as proposed by Dijkman

  Figure 1.22: Funding project process and the corresponding Petri nets model

Figure 1 .

 1 Figure 1.25: Behavioral and structural analysis

  nets P-semiow presented by Campos in [Camp 90][Sifa 80]. This analysis does not permit only the identication of workow shortcoming and bottle-

Figure 1 .

 1 Figure 1.27: Petri nets representing two enterprises operators and their corresponding processing time for two dierent contract type(RED, BLUE).

  erated a new assignment problem[Shra 08b]. This new assignment problem was not discussed before in literature. In the next chapter we represent the new problem with all its dimensions and represent it as linear programming problem. This linear programming problem can then be solved by using any mathematical solver such as Cplex 10 solver which uses a branch and bound method to guaranty solution optimality. Related problems to the new 10 CPLEX : an optimization software package produced by ILOG, which uses an advanced mathematical programming and constraint-based optimization techniques to nd problem optimal solution. http://www.ilog.com/ problem are also discussed. Similarities and dierences are explained. And proposition to use the new problem in decision taking is presented as we have demonstrated in[Shra 08a].

  validation phase and an optimization phase. These phases are realized by the transformation of BPMN model to classical and colored Petri nets. Classical Petri net are used to validate and verify model behavioral properties, whereas colored Petri nets are used to simulate and realize a performance analysis for the new model. When ever a problem is detected in the Petri net model, the BPMN model is remodeled to avoid this problem. The nal BPMN model is then used to generate BPEL execution code. Petri net is

  Bin packing problem (BPP) is one of the most famous and widely studied assignment problems. It is well known for being one of the combinatorial NP-hard problems [M Ga 79]. Its simplest form described as a set of bins Y ={y 1 , y 2 , ..., y n } of equal capacity c, and a list of objects I ={1, ..., m}. All objects have the same weight w regarding all bins. The objective is to nd the minimum number of bins to pack all the objects without exceeding bins capacities. A binary mathematical representation for the problem is:

1

  if object j is assigned to bin i; 0 otherwise. Many researches were realized to nd approximated solution for this problem [Brow 79, Csir 98, L Ep 07], and more few researches were destinated to nd exact solution[Mart 90, chol 97]. The most famous approximated algorithm for the BPP are:

  there is no capable open bin, a new bin is opened to place the current element. BPP variants include, two dimensional BPP [Chun 82, Berk 87, Lodi 99, Lodi 02, JPuc 07, Poly 07] and three dimensional BPP [Mart 00, Miya 07].

[

  Mart 90]. In GAP problem, a set of objects J ={1, 2, ...,m} with cost (weight) w j and prot p ij must be assigned to a set of agents (bins) Y ={y 1 , y 2 , ..., y n } with capacities CAP={cap 1 , cap 2 , ..., cap n }. Each object can be allocated to any but only one agent. Objects treatment requests resources which change, depending on the object and the agent treating it. Each agent can have dierent capacity. The objective is to maximize the prot without exceeding agent's capacities. A mathematical representation of the problem is the following:

  available secondary workers, J contract types and NC contracts, needs (N + M )+(N +M ) * N C binary variables when using binary representation (N +M variable to present agents and (N + M ) * N C to present contracts). Whereas grouping contracts by type requires (N + M ) + (N + M ) * J variables (N + M variables to present agents and (N +M ) * J to present the assigned contracts).

Figure

  Figure 2.1.

Figure 2 . 1 :

 21 Figure 2.1: New workow with decision making support

  Figure (2.2) demonstrates decision making process for short-term approach.

Figure 2 . 2 :

 22 Figure 2.2: Interactive decision-making process

Figure 2 . 3 :

 23 Figure 2.3: Postponed contracts ow over D days

  approaches and techniques used to generate BPEL code from BPMN model have been briey presented. These approaches have passed considerable steps toward complete and automatic code generation.However, BPMN exibility may leads to undesired properties, such as deadlocks and livelock. These properties will be directly reected in the nal code implementing the target workow. More, BPMN notation was designed to model business process, and little consideration was concentrated to represent data. To overcome these problems, two additional phases are applied to the BPMN model representing the to-be workow model before being adopted to generate BPEL code. A verication and validation phase and an optimization phase. These phases are realized by the transformation of BPMN model to classical and colored Petri nets. Classical Petri net are used to validate and verify model behavioral properties, whereas colored Petri nets are used to simulate and realize a performance analysis for the new model. When ever a problem is detected in the Petri net model, the BPMN model is remodeled to avoid this problem. The nal BPMN model is then used to generate BPEL execution code. Petri nets are a formal language and it has taken a lot of attention and consideration. And many tools were consecrated to verify their undesired properties. Additional advantage of using Petri nets is the ability to perform performance analysis in which mathematical formulations can be induced. These formulations can then be used to solve the problem with any mathematical solvers. Real case study has been used to demonstrate the dierent phases of the proposed frameworks. And new assignment problem within the new workow has been emerged. The formulation and the employment of the new problem in a decision making tool is the second contribution of this thesis.The new problem is a real world assignment problem where contracts represent a list of objects, and company collaborators and temporary worker represent a group of bins to pack these objects. The new problem has been called

  Timed Petri nets . . . . . . . . . . . . . . . . . . . . . . . . . 1.19 Current mails workow within COFIDIS . . . . . . . . . . . . 1.20 New proposed mails workow . . . . . . . . . . . . . . . . . . 1.21 The mapping of task, events, and gateways to Petri-net as proposed by Dijkman . . . . . . . . . . . . . . . . . . . . . . . 1.22 Funding project process and the corresponding Petri nets model 1.23 Modied Petri nets model to represent continuous funding project process . . . . . . . . . . . . . . . . . . . . . . . . . . Pour pouvoir vérier les propriétés structurelles et comportementales du processus métier, nous avons utilisé les Réseaux de Petri ordinaires en passant par un dépliage de celui-ci pour vérier qu'il n'y aura pas de présence de blocage pour telle ou telle couleur par exemple. Les RdP ordinaires sont utilisés pour valider et vérier les propriétés telles que la vivacité (deadlock free, liveness) et la nitude (boundedness). Cette recherche de propriétés donne de précieuses informations sur le processus ainsi conçu. Les problèmes que l'on peut identier à cette étape ne sont pas forcément visibles avec le modèle BPMN. Ils sont dus en général à des erreurs humaines de conception ou à une mauvaise interprétation des spécications de BPMN. Cette phase de vérication est donc indispensable pour valider dans un deuxième temps le modèle du processus après retour et correction si nécessaire sur la conception du processus et donc sur le modèle BPMN.

	y sont donc peu représentées. Peu de formalisation sur l'aspect comporte-1.18 Une première analyse et retour d'existant du processus actuel ont abouti mental des ux a été faite. En conséquence, l'analyse de performance sur un
	à certains dysfonctionnements : diculté pour rattacher des documents com-modèle BPMN est quasi inexistante et d'autant plus sur l'aspect optimisation
	plémentaires envoyés par un client à sa demande initiale de crédit, éventuelles de ux.
	pertes d'information notamment des dossiers incomplets mis en attente par An de surmonter ces problèmes, nous proposons d'insérer dans le frame-
	les collaborateurs, mauvaise répartition des dossiers suivants les équipes ; work deux nouvelles phases. Ces deux phases sont appliquées à partir de
	appel non justié d'intérimaires pour venir épauler les équipes permanentes l'obtention du modèle BPMN. La première est une phase de vérication et
	Introduction
	1 From business process modeling to workow analysis and
	optimization
	1.1 Cependant BPMN est un langage orienté description car il doit être facilement compréhensible par toutes les personnes du projet depuis les util-isateurs jusqu'aux responsables en passant par les analystes métier et les développeurs. La exibilité oerte par BPMN peut conduire à des propriétés Introduction . . 1.3.2.1 Event handler based transformation . . . . . indésirables du processus tels que blocage et inaccessibilité. Il est donc di-
	1.3.2.2 cile de vérier de bonnes propriétés du modèle. De plus, BPMN a été conçu Pattern based transformation . . . . . . . . .
	1.3.2.3 pour fournir des modèles Orientés Processus. Les données ou les ressources BPMN2BPEL tool . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Problematic: mail ow optimization COFIDIS . . . . . . . . . 1.3 Workow reengineering . . . . . . . . . . . . . . . . . . . . . . 1.3.1 Proposed standards to be used in workow reengineering process . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.1.1 BPMN . . . . . . . . . . . . . . . . . . . . . . 1.3.1.2 WS-BPEL . . . . . . . . . . . . . . . . . . . . 1.3.2 BPMN to BPEL . . . . . . . . . . . . . . . . . . . . . 1.24 Petri nets model for the proposed workow. a) Handling a contract by a collaborator. b) Client response. . . . . . . . . . 1.25 Behavioral and structural analysis . . . . . . . . . . . . . . . . 1.26 A part of the colored Petri nets that simulate contracts workow at time stamp 80. . . . . . . . . . . . . . . . . . . . . . . 1.27 Petri nets representing two enterprises operators and their corresponding processing time for two dierent contract type(RED, BLUE). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 New workow with decision making support . . . . . . . . . . 2.2 Interactive decision-making process . . . . . . . . . . . . . . . 2.3 Postponed contracts ow over D days . . . . . . . . . . . . . . List of Tables 1.1 Competence matrix example . . . . . . . . . . . . . . . . . . . 30 1.2 Daily tasks table example for two services . . . . . . . . . . . 31 1.3 Results extracted from simulating contracts assignment process using colored Petri nets. . . . . . . . . . . . . . . . . . . . 78 1.4 Result from two dierent contracts assignments for the same contracts sample. Dierent contracts assignments needed different number of work time units. . . . . . . . . . . . . . . . . 79 2.1 Simulation results of the short-term approach for the rst stage110 2.2 First stage results for the short-term approach and the midterm approach . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 2.3 Average prot of using mid-term approach over 10 random samples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 Résumé Cette thèse a été réalisée dans le cadre du projet " Gestion et Optimisation de la Chaîne Documentaire " (GOCD), projet labellisé par le Pôle de compétitivité des Industries du Commerce (PICOM). Le projet a pour but de concevoir et de développer un nouveau workow et un outil d'aide à la décision. Ce système s'inscrit dans la démarche de dématérialisation de ux courriers dans l'entreprise COFIDIS. Nous nous intéressons ici à la gestion des demandes de crédit envoyés par les clients sous la forme de contrats. Ceux-ci dans la nouvelle organisation devront être, dans un premier temps, scannés, puis identiés, triés et envoyés au département chargé d'étudier la recevabilité de cette demande. Cette étude est réalisée par des collaborateurs dont le degré de compétences inue sur le temps de traitement de chaque dossier. Après examen, le dossier peut être soit refusé, soit directement accepté et dans ce cas il est archivé. Enn si celui-ci est jugé incomplet par le collaborateur, une information est transmise au client concerné (via mail, téléphone, courrier, ...) pour une demande de complément d'information (pièce d'identité, relevé bancaire, justicatif de domicile, ...). Le dossier est alors mis en attente jusqu'à réception des documents manquant. L'outil de décision sera en partie utilisé par les chefs de service en charge de répartir les dossiers à leurs équipes de collaborateurs. Actuellement la répartition des dossiers se fait selon une heuristique (outil DISPATCH) limitée à une vision court terme (quotidien) du ux courrier. en charge des études de demande de crédit. Cette analyse a été prise en compte dans la conception du nouveau processus métier de gestion des ux dématérialisés courrier. Un premier modèle a été réalisé en utilisant BPMN (Business Process Management Notation). Cette notation est particulièrement adaptée pour les processus d'entreprise avec diérentes phases de traitement et validation. Le choix de BPMN s'inscrit dans le cadre d'un framework complet de conception -développement de workow composé de BPMN et de BPEL (Business Process Execution Language). Il propose l'utilisation de BPEL pour implémenter et exécuter l'application nale de workow en tant que services web. Les motivations derrière le choix de BPMN et BPEL dans ce cadre de travail sont soulignées. Les approches pour générer du code BPEL à partir d'un model BPMN sont présentées. de validation et la deuxième une phase d'optimisation. Ces deux phases sont réalisées en transformant le modèle BPMN vers un langage formel. Notre choix s'est porté sur les Réseaux de Petri. Il existe dans la littérature des travaux qui proposent la transformation par étapes du modèle BPMN en un modèle Réseau de Petri. Nous présentons ces approches et nous les adaptons au processus qui nous intéresse ici. Mais pour prendre en compte l'aspect discret du problème (gestion des dossiers clients) ainsi que les contraintes ressources spéciques (matrice de compétence des collaborateurs, c'est-à-dire le temps de traitement des dossiers dépendant du niveau de compétence du collaborateur et du type de dossiers et disponibilité des ressources), nous avons apporté ces informations supplémentaires par rapport au modèle initial BPMN, qui n'est pas capable de gérer ces données et ces contraintes de ressources. Nous avons d'abord utilisé les Réseaux de Petri colorés pour représenter facilement et lisiblement la diversité des chemins liés aux nombreux types de dossiers à étudier.

  individual attempts were done to dened a proper BPEL metamodel from its specication[Bare 06, Bord 04]. These attempts were neither com-

	since BPMN and BPEL represent two fundamentally dierent classes of lan-
	guages (BPMN is graphical oriented languages and BPEL is block-structured
	language)[Reck 06, Wohe 05]. The reclamation of generating BPEL code
	from BPMN diagram in BPMN specication is not really accurate. The
	specication supposes that the designer will follow certain restrictions and
	rules, which do not reect business process reality. For example, in the speci-
	cation they suppose that every loop must have one entry point and one exit
	1.3.2 BPMN to BPEL
	One important motivation to use BPMN in business process modeling is the
	possibility to generate executable BPEL code from the BPMN diagram. This
	is a crucial step in the end-to-end development process for process-oriented
	systems. The mapping of BPMN to BPEL code is a challenge process,

plete nor constrained as the authors admit themselves. They represent only individual eorts to interpret BPEL metamodel from its specication. Others attempts were done within bigger software projects such as eclipse BPMN modeler. Yet none of these metamodel has been reviewed or standardized by OASIS consortium, and by consequence, they are not reliable and can not be considered as conformable to OASIS recommendations and specications. In [Akeh 04], the author uses the Unied Modelling Language (UML) and the Object Constraint Language (OCL) to provide a model for XML based BPEL languages. Using this model, the author shows how OCL can be used to precise the used natural language in OASIS specication. This work is used then to create a validation tool for any BPEL document. This tool reduces development time by ensuring the conformability of BPEL document in automatic manner. point. Another example, they suppose also that each AND-split corresponds to AND-join[Whit 04a, Whit 05]. Add to that, some control-ow patterns which are allowed in BPMN (such multi-merge, arbitrary cycle and spawning instances) can't be mapped to a single BPEL process. Some tools in the market propose an automatic transformation between BPMN and BPEL. However these tools are either incomplete (need human intervention) or impose certain restriction on BPMN diagram to facilities the transformation process. The use of unstructured cycles is a good example for these restrictions.

A transformation method is considered good, if the generated code is understandable for human and there is no need for a major developer's interventions. Having understandable code is important issue for developers who will rene and modify this code later. Modifying and developing code is indispensible since business process is in continuous change and progress.

Existing approaches to map BPMN to BPEL code are proposed by business process management group in Queensland University

  eclipse.org/stp/ 8 A model transformation language and toolkit developed by the ATLAS Group (INRIA Thus, the exibility oered by BPMN can also lead to undesirable properties for business process such as deadlocks and livelock. Since one of the important objects of using BPMN is to generate executed BPEL code, any problem in BPMN model will be directly reected in the obtained code and in the implemented process. More, since BPMN is a process ori-Another issue in BPMN diagram is that there is no way to perform any performance evaluation and optimization to test and compare the proposed workow model presented by BPMN with the old one. Verifying that the new

	1.3.3 BPMN limits In spite of BPMN advantages, BPMN suers from serious problems regard-ing it s semantic. The last BPMN specication (V1.2 January 2009), does not contain a formal semantic denition for BPMN[Ouya].This specication is written in verbal way which allows dierent interpretations of the same 1.4.1 Framework for workow reengineering As we have discussed in section 1.3.1.1, BPMN has been adopted by the OMG as the standard to model and represent business process workow. known. Will OMG keep BPDM as BPMN metamodel or they will adopt a pattern. 1.4 Proposed framework for workow reengi-new dedicated metamodel for BPMN. To answer this question we must wait neering OMG BPMN 2.0 specication.
	This makes it the natural modeling choice for any business analysts to model
	and represent business process.
	The new BPMN 2.0 must contain a dedicated meta-model for the BPMN, a
	graphical notation to represent dierent business processes, an interchange
	format to exchange business process models without losing semantic integrity
	and an extension to model a choreography process. BPMN acronym in the
	new BPMN 2.0 will stand for Business Process Metamodel and Notation and
	no more to Business Process Modeling Notation.
	and LINA) http://www.eclipse.org/m2m/atl/ The debate about BPMN metamodel is not terminated. And the nal
	decision regarding BPMN metamodel that will be taken by OMG is not

ented notation, little attention was dedicated to represent data or resources availability[

Aals 06

]. As a result, one can not realize performance analysis or evaluation for the target system. Verifying that the new workow system works correctly is a good thing, still we need to ensure that it works eciently. Recently, OMG has issued request for proposals for version 2.0 of BPMN. The new BPMN 2.0 must contain a dedicated meta-model for the BPMN, a graphical notation to represent dierent business processes, an interchange format to exchange business process models without losing semantic integrity and an extension to model a choreography process. The debate about BPMN metamodel is not terminated. And the nal decision regarding BPMN metamodel that will be taken by OMG is not known. In the next sections we propose an approach to avoid these problems.

However, BPMN suers from serious problems due to the lack of formal semantics. Within the last BPMN specication (V1.2 January 2009), OMG does not denes a dedicated meta-model for BPMN. This specication is written in verbal way which allows dierent interpretations of the same pattern. The exibility oered by BPMN can also lead to undesirable properties for business process such as deadlocks and unreachablity. Since one of the important objects of using BPMN is to generate executed BPEL code, any problem in the model will be directly reected in the obtained code and in the implemented process. Unfortunately there is no way to verify BPMN structural properties.

Recently, OMG has issued request for proposals for version 2.0 of BPMN.

  object j is assigned to agent i;

	0 otherwise.
	Recent works on approximated algorithms to solve GAP problem can be
	found in [Nuto 06, Cohe 06] and for exact method [Save 97, Ross 75]. Read-
	ers are refereed to [Catt 92] for a survey on algorithms used to solve GAP
	problem.

  2, ..., I}, ∀j ∈ {1, 2, ..., J}

	(2.14)
	Where

  EN>L, then constraint(2.25) become as shown in (2.29). Where α is a real number ∈ [0,1] that represents the percentage of contract of type j that must be handled. This percentage can be changed every time the problem is not solvable.

	N +L
	X ij = QT j (t) × α j ,	∀j ∈ {1, 2, .., J}	(2.29)
	i=1
				2.24)
	N +L
	X ij = QT j (t),		∀j ∈ {1, 2, .., J}	(2.25)
	i=1
	K
	C ik = K,	∀i ∈ {1, 2, .., I}	(2.26)
	k=1
	U i (t) = 0,	∀U it ∈ Abs t	(2.27)
	N
	U i (t) = |P rs t |	(2.28)
	i=1
	Constraint (2.24) ensures that workers capacities will not be violated. Con-
	straints (2.25) and (2.26) ensure that all received contracts will be dis-
	tributed. Note that the equality in constraints (2.25) and (2.26) are correct
	only when the number of exact temporary workers needed to handle all re-
	ceived contract equal the number of really hired temporary workers EN=L.

When

  Given period in days D={d 1 , d 2 ,..., d D }, • Abs: Primary workers absent set, U di ∈ Abs, if primary worker i is absent in day d • P rs: Primary workers present set, U di ∈ P rs, if primary worker i is present in day d

• D:

• N : Number of primary workers (company workers),

  2, .., I}, ∀d ∈ {1, 2, .., D} (2.33)

		D	I	D
				X dij =	QT dj , ∀j ∈ {1, 2, .., J}	(2.34)
		d=1	i=1	d=1
	d	I	d
		X αij ≤		QT αj ,	∀d ∈ {1, 2, .., D}, ∀j ∈ {1, 2, .., J}	(2.35)
	α=1	i=1	α=1
		U di ∈ {0, 1} ∀i ∈ {1, 2, .., I}, ∀d ∈ {1, 2, .., D}	(2.36)

X dij ∈ Z + , ∀d ∈ {1,

2, .., D}, ∀i ∈ {1, 2, .., I}, ∀j ∈ {1, 2, .., J} (2.37) Objective function (2.30), minimizes the total number of used workers whither they are primary workers or temporary workers, which is not what we are looking for. To overcome this problem, we add constraint (2.31) to search only solutions containing all primary workers present in the period [1, D]. |P rs| in (2.31) represents the cardinality (number of elements) in the Prs set. Constraint (2.32) guarantees that no primary worker i in day d is chosen, if he is absent in that day (exist in the Abs set). Constraint (2.33),

Table 2 .

 2 1: Simulation results of the short-term approach for the rst stage day, contracts quantities and their types are generated randomly, and varied

	For each

Table 2

 2

	.3.

Table 2 .

 2 3: Average prot of using mid-term approach over 10 random samples2.5 ConclusionIn this chapter, we have presented and dened a new real world assignment problem. The new problem regroups characteristics from both well known problems, Bin Packing Problem (BPP) and Generalized Assignment Problem (GAP). We have called our problem Generalized Assignment Problem with Identied First-used Bins (GAPIFB). As BPP, the new GAPIFB problem consists of allocating a set of dierent tasks to a set of bins with dierent capacity for each bin. On the other hand, tasks' weights in the new problem change from one bin to another according to a predened competence matrix, as it is dened in the GAP problem. The objective function in the new problem is to nd the minimum number of needed secondary bins to pack all existing tasks, if the use of primary bins was not sucient.

proches de résolution du GAFPIB problem, on peut améliorer l'approche liée à la programmation sous contrainte en apportant de nouvelles contraintes qui permettront de couper plus rapidement des branches entières de l'arbre de recherche qui n'apporteront pas de solution optimale. Dans un deuxième temps, comme ce n'est pas l'approche optimale d'autres approches de résolution pourront être étudiés pour des problèmes se rapprochant permettant la mise en place d'un algorithme spécique de résolution de ce type de problème en un temps minimal.

http://www.bpm.t.qut.edu.au

http://w3.tue.nl/en/

Remerciements

En premier lieu, je tiens à exprimer ma profonde gratitude aux directeurs de cette thèse le Professeur Pascal YIM et à Hervé CAMUS, Maître de Conférences. Je veux les remercier pour leur encadrement plein d'enthousiasme et de rigueur et pour la conance dont ils ont fait preuve à mon égard. De plus, je tiens à leur manifester ma sincère reconnaissance pour leurs grandes qualités humaines qui ont fait que cette thèse se passe dans la bonne humeur.

Ces remerciements ne seraient pas complets si je n'y associais pas toutes les personnes qui ont contribué de près ou de loin à la réalisation de ce travail, en particulier, mes collègues, tout le personnel du LAGIS et de l'École Centrale de Lille pour leur bonne humeur et leur disponibilité.

Col_ID

Number of contracts to be handled time=0 time=80 for this problem is demonstrated in details. In section 2.4, we present our approach to exploit and integrate the new assignment problem in the proposed decision making tool. This followed by the simulation and test result.

We terminate by our conclusion and perspectives.

Similarly, using BPP to distribute COFIDIS contracts does not answer COFIDIS requirements. BPP does not consider objects prots. More, when distributing COFIDIS contracts using BPP, it is probable to have optimal solution that assigns contracts to secondary bins and excludes some primary bins. This is because BPP does not distinguish between bins representing company collaborator "Primary bin"from those bins representing temporary workers"Secondary bin" .

As we can see neither BPP nor GAP problem answers COFIDIS assignment problem needs. For that, in the next section we present and detail new assignment problem that can answer COFIDIS assignment problem.

This forms a real problem if we try to solve our problem by classical BPP form. Classical BPP form does not distinguish bins types when it searches the optimal solution, which makes it possible to exclude some primary bins if the use of secondary bin gives best result. In addition, BPP denes constant weight per task type, whatever the used bin was, which is not the case in GAPIFB. Simulation results show that GAPIFB model ensures optimal tasks distribution.

We propose to integrate the new assignment problem in decision making tool. This tool helps decision makers in taking their decisions for both short-term "daily decision" and mid-term "decision over several days". In the short-term, the proposed approach allows a real time optimization for contracts assignment.

Real samples from COFIDIS have been used to test the proposed approaches for both terms, short-term and mid-term. Simulation results show that our approaches are more ecient than the current used method at COFIDIS. With short-term approach, COFIDIS decision maker knows in advance the exact number of temporary worker that they will need to treat all received contract. This forbids unnecessary call to temporary workers.

The proposed mid-term approach allows COFIDIS to save up 25% of temporary workers when considering contract distribution over a predened period. The only problem in this approach is to predict correctly received contracts quantities and theirs types over this period. We believe this is not a problem, since COFIDIS has large historical data on the received contracts types and quantities over years. These data can be used with any known prediction method to estimate the expected received contract over a given year period.

Since Cplex execution time to solve the GAPIFB and within its current This work is only the rst step in the reengineering process for company's workow. Generalizing this approach is our next objective.

Future works on the transformation of BPMN to BPEL using Model Driven Architecture (MDA) seems to be a very promising research domain.

This will permit the implementation of a workow by dierent BPLE workow engine.

Although the execution time to solve GAPIFB problem is ordered in milliseconds, we believe that increasing problem size or its structure will yield in exploding the execution time to nd optimal solution. And since GAPIFB problem is unique in its characteristic, dedicated exact or approximated resolution methods to solve this problem represent rich domains for concerned researchers to be developed and explored.