Lucio Bianco
email: bianco@disp.uniroma2.it

Massimiliano Caramia
email: caramia@disp.uniroma2.it

Advanced Topics in Project Management Process

Keywords: Project scheduling, Generalized precedence relations, Resource constraints, Feeding precedences

In this paper we present the evolution of project scheduling models with emphasis on temporal constraints.

Introduction

In today's competitive global environment it is crucial to deliver quality product on time and within an established budget. "Management by projects" has became the principal way to pursue this goal since it is a powerful way to integrate organizational functions and motivate groups to achieve higher levels of performance and productivity. Therefore it is not surprising to see that, in the last few decades, project management has became a hot topic and has been recognized as a central management discipline. Major industrial companies now use project management as their principal management style. Nevertheless the impression is that the contribution that project management can make to management at all is still underrated and poorly known. Moreover, in spite of numerous books on the argument, a very limited number of these put emphasis on the mathematical tools and on the quantitative methods necessary to make project management more effective in dealing with increasing complexity organizations. To better understand this aspect, it is useful to recall that project management is a process which involves the planning, scheduling and control of project activities to achieve performance, cost and time objectives for a given scope of work, while using resources efficiently and effectively (see [START_REF] Lewis | Project Planning, Scheduling and Control. A Hands On Guide to Bringing Projects in on Time and on Budget[END_REF]. The planning phase involves the following crucial steps: identify the project activities, their interdependencies, and estimate times, resources and costs necessary to perform them. The scheduling phase involves the construction of a project base plan which specifies, for each activity, the precedence and resource feasible start and completions times, the amounts of the various resource types necessary during each time period, and, as result, the budget. The control phase focuses on the comparison between the project base plan and the actual performance once the project has started. If this comparison reveals some difference on the schedule, or on the budget or also on some technical specifications, a corrective action must be taken to get the project back on the right track.

In this paper we mainly focus on project scheduling phase often identified, on the basis of management experience, as the most critical with respect to project failure [START_REF] Goldratt | Critical Chain[END_REF][START_REF] Lewis | Project Planning, Scheduling and Control. A Hands On Guide to Bringing Projects in on Time and on Budget[END_REF]. In fact, especially in the case of product innovation and new product development projects, delays in the completion time are more heavily penalized than budget overruns [START_REF] Goldratt | Critical Chain[END_REF]. [START_REF] Suri | Quick Response Manufacturing[END_REF] reports an experience of Hewlett-Packard related to a high-growth market which confirms the greater importance of time schedule than the cost. In fact, Hewlett-Packard found that a delay of six months in a new product project could cause a loss of 33% in profits while, if the project overran its cost by 50% but was completed on time, the loss was only 3.5%. For this reason we consider the project scheduling problem assuming that all input data are know in advance (deterministic case) and that the objective is minimizing project duration. Of course other objective functions, like resource levelling, resource cost, tardiness or earliness, could be considered. In particular, we analyse the evolution of project scheduling models with emphasis on temporal constraints. We start from the well known basic case of resource unconstrained project scheduling with Finish-to-Start precedence constraints and zero time lag (PERT, CPM). Then we analyse the problems arising when other types of precedence constraints with minimum and maximum time lags are considered, that is the "Generalized Precedence Relations" (GPRs).

The next step is Resource Constrained Project Scheduling Problem (RCPSP) with GPRs. With respect to the previous problems, that from the computational point of view are polynomial, the RCPSP is NP-hard and not optimally solvable for large instances, within a reasonable computing time.

Finally a further extension of the classical RCPSP, arising when the activity durations are not defined and known in advance, is considered. This problem happens in that production planning environment, like make-to-order manufacturing, where the resources are often shared among different simultaneous activities in proportion variable over time.

In this case the duration of each activity is not univocally defined, and consequently the traditional Finish-to-Start precedence constraints, so as the GPRs, cannot be used any longer. Then, we need to introduce the so called "Feeding Precedences" (FP) [START_REF] Kis | Rcps with variable intensity activities and feeding precedence constraints[END_REF]

The Resource Unconstrained Project Scheduling Problem

A project consists of a number of events and activities that have to be performed according to a set of precedence constraints. Each event refers to a stage of accomplishment of a certain activity (in general its starting time or its finishing time). Each activity has a duration and typically requires resources for its execution.

In order to represent activities and their relationships it is a common practice to use networks; the latter allow one to represent precedence relationships more efficiently than other representation techniques like Gantt charts [START_REF] Clark | The Gantt Chart[END_REF], track planning [START_REF] Herroelen | Projectbeheersing in de Bouw, Vlaamse Confederatie Bouw[END_REF], and line balance planning [START_REF] Lumsden | Line of Balance Method[END_REF].

A project network is a graph G = (N, A) consisting of a set N of nodes and a set A of arcs. There are two possible representations of a project by means of a graph G. One is the Activity-On-Arc-representation (AOA) which uses the set of arcs A to represent the activities and the set of nodes N to represent the events; the other is the Activity-On-Node representation (AON) which uses the set of nodes N to denote the activities and the set of arcs to represent the precedence relations, i.e., an arc (i, j) in A means that activity i constrains or is constrained by activity j.

If we assume that resources are unlimited, or are available in huge amounts, a project network is in general used into two fundamental techniques: CPM (Critical Path Method) and PERT (Program and Evaluation Review Technique). These two methodologies study the temporal development of a project taking into account only precedence relations among activities of the so called Finishto-Start type, i.e., if an arc (i, j) exists in an AON representation then activity j cannot start before the finishing time of activity i. The temporal analysis gives answers to some important questions like how long the project will take, i.e., what is the completion time (makespan) of the project; how early a particular activity may be started; how far an activity can be delayed without causing a delay of the entire project.

It is well known in project scheduling that PERT/CPM methods can be applied under two assumptions. The first one is that resources are available in infinite amounts, and the second is that the precedence relationships between two activities are only of the Finish-to-Start type with time-lags equal to zero; this implies that an activity can start only as soon as all its predecessors activities have finished.

In this context, one can define an acyclic projet network and compute the minimum project completion time as the length of the critical path, i.e., the longest path from the initial activity (source node) to the final activity (sink node) in such an activity network (see, e.g., [START_REF] Moder | Project management with CPM, PERT and precedence diagramming[END_REF][START_REF] Radermacher | Scheduling of project networks[END_REF].

The computation of the critical path can be accomplished by means of the well-known forward pass recursion algorithm (see, e.g., [START_REF] Kelley | The critical path method: Resource planning and scheduling, Industrial Scheduling[END_REF], that is a classical label setting algorithm for longest path calculation. The computational complexity of this algorithm is O(m), where m is the number of arcs of the network; when the graph has a high density, the complexity tends to O(n 2 ), where n is the number of activities.

However, in a project, it is often necessary to specify other kinds of temporal constraints besides the Finish-to-Start precedence relations with zero-time-lags. Accordingly to Elmaghraby and Kamburoski (1992), we denote such constraints as Generalized Precedence Relations (GPRs). GPRs allow one to model minimum and maximum time-lags between a pair of activities (see, e.g., [START_REF] Dorndorf | Project scheduling with time windows[END_REF][START_REF] Neumann | Project scheduling with time windows and scarce resources[END_REF].

Four types of GPRs can be distinguished: Start-to-Start (SS), Start-to-Finish (SF ), Finish-to-Start (F S) and Finish-to-Finish (F F ).

A minimum time-lag (SS min ij (δ), SF min ij (δ), F S min ij (δ), F F min ij (δ)) specifies that activity j can start (finish) only if its predecessor i has started (finished) at least δ time units before.

Analogously, a maximum time-lag

(SS max ij (δ), SF max ij (δ), F S max ij (δ), F F max ij (δ)
) imposes that activity j can be started (finished) at most δ time slots beyond the starting (finishing) time of activity i.

In order to better understand GPRs we report some examples. If, for instance, a company must place a pipe (activity j) in a given region, it is necessary to prepare the ground (activity i) in advance. This situation can be represented by a constraint SS min ij (δ), since the start of activity j must be δ units of time after the starting time of activity i. In another project, if a company must supply a client with a certain number of products which must be also assembled within 100 days, this relationship can be modeled as SF max ij (100), which says that the assembly process (activity j) must finish at most 100 days after the starting time of the delivery (activity i) of the products.

GPRs can be represented in a so-called standardized form by transforming them e.g. into minimum Start-to-Start precedence relationships by means of the so-called Bartusch et al.'s transformations [START_REF] Bartusch | Scheduling Project Networks with Resource Constraints and Time Windows[END_REF]. Thus, applying to a given AON activity network with GPRs such transformations leads to a standardized activity network where associated with each arc is a label ℓ ij representing the time-lag between the two activities i and j (De Reyck, 1988). If more than one time-lag ℓ ij between i and j exists, only the largest ℓ ij is considered.

It should be noted that standardized networks, unlike the networks without GPRs, may contain cycles. This implies that a Resource Unconstrained Project Scheduling Problem (RUPSP) with GPRs and minimum completion time objective:

cannot be solved by the classical forward and backward recursion algorithm mentioned before;

can be solved by computing the longest path from the source node to the sink node, whose length is the sum of the time-lags associated with its arcs, using an algorithm working on "general" networks with a worst-case complexity O(n • m) (see, e.g., [START_REF] Ahuja | Network flows[END_REF];

does not admit feasible solutions when the topology of the network and the arc-length function induce one or more directed cycles of positive length [START_REF] Bartusch | Scheduling Project Networks with Resource Constraints and Time Windows[END_REF].

In Bianco andCaramia (2008, 2010), it has been proposed a new network formulation and a new mathematical program for the RUPSP with GPRs which can be easily solved in O(m) time by means of dynamic programming. Starting from this new complexity result, it has been further proved that, by exploiting the dual formulation of the proposed mathematical program, the minimum completion time can be also computed, with the same computational complexity O(m), by finding an augmenting path of longest length in the proposed acyclic network in which a unit capacity is installed on each arc. An experimental study comparing the performance of the proposed approach and the traditional one confirmed the better performance of the former method also in practice.

The Resource Constrained Project Scheduling Problem with GPRs

The basic Resource Constrained Project Scheduling Problem (RCPSP) deals with scheduling project activities subject to Finish-to-Start precedence constraints with zero time-lags and renewable resources under the minimum project completion time objective. The RCPSP is NP-hard in strong sense (see, e.g., [START_REF] Blazewicz | Scheduling subject to resource constraints: Classification and complexity[END_REF]. When this kind of temporal constraints are taken into account, an activity can start only as soon as all its predecessors have finished, and, therefore, the resource constraints exist only between two or more independent activities.

As we mentioned in the previous section, when no resource constraint is concerned, GPRs can be represented in a so called "standardized" form by transforming them, for instance, in minimum Start-to-Start precedence relationships obtaining a possibly cyclic network (see [START_REF] Bartusch | Scheduling Project Networks with Resource Constraints and Time Windows[END_REF], or can be represented be means of an acyclic network by transforming them into Finish-to-Start relations (Bianco andCaramia, 2008, 2010).

When resources come into play, the RCPSP with GPRs is strongly NP-hard; also the easier problem of detecting whether a feasible solution exists is intractable (NP-complete, [START_REF] Bartusch | Scheduling Project Networks with Resource Constraints and Time Windows[END_REF]. To the best of our knowledge, the exact procedures presented in the literature are the branch-and-bound algorithms by [START_REF] Bartusch | Scheduling Project Networks with Resource Constraints and Time Windows[END_REF], Demeulemeester and Herroelen (1997b), and De Reyck and Herroelen (1998). The paper by [START_REF] Bartusch | Scheduling Project Networks with Resource Constraints and Time Windows[END_REF] reports a limited computational experience on a case study; the paper by Demeulemeester and Herroelen (1997b) is conceived to work on minimum time-lags only; the third approach, that works with both minimum and maximum time-lags, presents results on projects with 30 activities and percentages of maximum time-lags of 10% and 20% with respect to the total number of generalized precedence relations.

Also lower bounds are available for this problem. In particular, two classes of lower bounds are well known in the literature, i.e., constructive and destructive lower bounds. The first class is formed by those lower bounds associated with relaxations of the mathematical formulation of the problem (for instance, the critical-path lower bound and the basic resource-based lower bound; see, e.g., [START_REF] Demeulemeester | Project Scheduling -A Research Handbook[END_REF]. Destructive lower bounds, instead, are obtained by means of an iterated binary search based routine as reported, e.g., in [START_REF] Klein | Computing lower bounds by destructive improvement: An application to resource-constrained project scheduling[END_REF]. Also De Reyck and Herroelen (1998) proposed a lower bound for the RCPSP-GPRs denoted with lb3 -gpr that is the extension of the lower bound lb 3 proposed by Demeulemeester and Herroelen (1997a) for the RCPSP.

Recently, Bianco and Caramia (2009a) proposed a new lower bound for the RCPSP-GPRs based on a relaxation of the resource constraints among independent activities and on a solution of the relaxed problem suitably represented by means of an AON acyclic network. In particular, for the project scheduling problem with GPRs and scarce resources, the authors exploited the network model proposed in Bianco andCaramia (2008, 2010) and tried to get rid of the resource constraints. The analysis has been restricted to only those pairs of activities for which a GPR exists to determine a lower bound on the minimum project completion time. For each of these pairs it has been verified whether the amount of resources requested exceeds the resource availability, for at least one resource type. In case of a positive answer, some results which allow the reduction of the problem to a new RUPSP with different lags and additional disjunctive constraints have been proved. This last problem can be formulated as an integer linear program whose linear relaxation can be solved by means of a network flow approach (see also Bianco andCaramia, 2008, 2010). Computational results confirmed a better practical performance of the proposed lower bound with respect to the aforementioned ones. This problem happens in that production planning environment, like maketo-order manufacturing, which commonly requires the so-called project-oriented approach. In this approach a project consists of tasks each one representing a manufacturing process.

Due to the physical characteristics of these processes, the effort associated with a certain activity for its execution may vary over time. An example is that of the human resources that can be shared among a set of simultaneous activities in proportion variable over time. In this case the amount of work per time unit devoted to each activity, and therefore its duration, are not univocally defined.

This kind of problems is in general modelled by means of the so called Variable Intensity formulation, that is a variant of the Resource Constrained Project Scheduling Problem (see, e.g., [START_REF] Kis | A branch-and-cut algorithm for scheduling of projects with variableintensity activities[END_REF]. As the durations of the activities cannot be taken into play, the traditional Finish-to-Start precedence relations, so as the generalized precedence relations, cannot be used any longer, and there is the need for the feeding precedences. Feeding precedences are of four types:

-Start-to-%Completed (S%C) between two activities (i, j). This constraint imposes that the processed percentage of activity j successor of i can be greater than 0 ≤ g ij ≤ 1 only if the execution of i has already started.

-%Completed-to-Start (%CS) between two activities (i, j). This constraint is used to impose that activity j successor of i can be executed only if i has been processed for at least a fractional amount 0 ≤ q ij ≤ 1.

-Finish-to-%Completed (F%C) constraints between two activities (i, j). This constraint imposes that the processed fraction of activity j successor of i can be greater than 0 ≤ g ij ≤ 1 only if the execution of i has been completed.

-%Completed-to-Finish (%CF) constraints between two activities (i, j). This constraint imposes that the execution of activity j successor of i can be completed only if the fraction of i processed is at least 0 ≤ q ij ≤ 1.

For this problem, Bianco and Caramia (2009b) proposed a lower bound based on a Lagrangian relaxation of the resource constraints. Regarding exact approaches, only two exact algorithms have been presented in the literature. One is the branch and cut algorithm by [START_REF] Kis | Rcps with variable intensity activities and feeding precedence constraints[END_REF], with the objective of minimizing the external resource cost; the other is the exact algorithm by Bianco and Caramia (2009c) based on branch and bound rules.

Conclusions

In this paper we presented the main advanced topics emerging in the scheduling phase of the project management process. Our analysis mainly focused on the evaluation of project scheduling models with emphasis on different kinds of temporal constraints.


Yue Ming

Raymond Houé

Coordination in Supply Chains: from case studies to reference models

Keywords: Supply Chain, Coordination, Modeling, Performance

Intensive competition has forced companies to focus on their core business and as a consequence to participate to more and more complex supply networks. The necessity to preserve the autonomy of each partner makes such networks usually managed in a decentralized way. Consequently, problems and conflicts emerge during the coordination processes. This paper describes some coordination problems identified through interviews and locates them within the activities of the coordination processes. Interpretations of the aspects influencing coordination are suggested, allowing to better explain the origins of these problems.

Introduction

Nowadays, the growing intensive competition has forced enterprises to focus on their core business and participate in more and more complex Supply Networks (SNs). To build an efficient partnership, the crucial element is the coordination between partners, including selecting a suitable partner, executing and measuring the performance of coordination.

For years, various literatures have related efforts in giving mechanisms, models and tools of coordination in order to improve the overall performance of a supply chain. In the marketing literature, coordination mechanisms have mainly focused on pricing decisions, for instance linked to contract [START_REF] Cachon | Supply Chain Coordination with Revenue-Sharing Contracts: Strengths and Limitations[END_REF], demand [START_REF] Qi | Supply Chain coordination with demand disruptions[END_REF] and advertising [START_REF] Huang | An Analysis of Manufacturer-Retailer Supply Chain Coordination in Cooperative Advertising[END_REF].

In the operations research literature, most of works on coordination of supply chain are related to the optimal process parameters and policy, such as inventory policy [START_REF] Cachon | Competitive and Cooperative Inventory Policies in a Two-Stage Supply Chain[END_REF], delivery [START_REF] Zimmer | Supply Chain coordination with uncertain just-in-time delivery[END_REF] or order processing [START_REF] Li | Supply Chain coordination with quantity discount policy[END_REF]. Besides, works on tools and techniques for supporting coordination are widely presented, such as agent-based frameworks [START_REF] Xue | An agent-based framework for supply chain coordination in construction[END_REF], attribute-based approach [START_REF] Xu | Supply Chain Coordination and Cooperation Mechanisms: An Attribute-Based Approach[END_REF] or Virtual e-Chain [START_REF] Manthou | Virtual e-Chain (VeC) model for supply chain collaboration[END_REF]. Commonly, coordination in a supply chain can be interpreted as exchanging information, plans and executions which have been performed in isolation but may take into account the partner's constraints and expectations. Building a consistent coordination framework on that base is a complex process, not only dealing with models and techniques but also related to other aspects, such as characteristics of partners, types of supply chains, or communication means. Marcotte et al. [START_REF] Marcotte | Cooperation models for supply chain management[END_REF] suggest for instance coordination models based on the mutual influence of the partner and network. However, as a first step, it is critical to track the problems linked to the various activities of the cooperation process. Identifying possible dysfunctions, diagnosing reasons and tracing the resources which may facilitate coordination are basic but critical issues. This paper focuses on identifying real problems in coordination processes, based on case studies, and at identifying the causes of these problems.

The communication is organized as follows: in section 2, is introduced the background of the case studies. The typical structure of the Supply Networks of the interviewed companies is given. In section 3 are introduced two models giving an overview of the activities involved in typical cooperation processes and allowing to localize some coordination problems. We then list the aspects which influence coordination, in order to better explain the origin of these problems. In section 4, we propose two models that interpret the relationships according to these aspects in order to provide directions for a better cooperation.

Case studies in the aeronautic industry

As stated above, more attention is usually paid to supply chain planning rather than to coordination models. Coordination processes are more than the juxtaposition of purchasing, production and delivery, which are the main operational processes in a supply chain. In order to approach real industry situations, we have conducted interviews in various contexts, all aiming at analyzing problems arising in the coordination between large and small companies belonging to supply chains in the aeronautic sector of the South-West region of France. Interviews in more than thirty companies of various sizes have allowed to identify a considerable list of problems, either linked to technical or behavioral issues [START_REF] Marcotte | Cooperation models for supply chain management[END_REF], [START_REF] Galasso | Decision support framework for supply chain planning with flexible demand[END_REF]. Only some of them will be discussed here.

From the case studies, it is first clear that the structure of a supply chain is in practice more complex than a unidirectional flow (see Figure 1): it also includes loops which may be the origin of internal conflicts. Usually, the coordination in the interviewed companies is managed at three levels, namely long term, middle term and short term. The long term coordination process focuses on the definition of the partnership and dimensioning of the chain without any detailed information. This long term process defines average flows and provides information for all the partners in the chain, while forecasts are exchanged at middle term in order to adjust the capacities. The short term level is more operational and includes information such as purchasing orders or production orders. However, uncertainty of forecast in the middle term process and urgent orders at short term induce much instability. The changes between different slide planning are also source of conflicts during coordination. Considering the case studies, it is apparent that managing partnerships and eliminate barriers are critical elements that indeed exist in each activity of coordination. Problems usually emerge during coordination since actors are sometimes focusing on their own interpretation and benefits, without consideration of a win-win mechanism which would sometimes require negotiation. This point will be addressed in next section. Qualitative models of coordination processes Many models have already been suggested in the literature for describing logistic processes in supply chain (see SCOR [START_REF]SCOR 9.0 Reference Guide[END_REF], ASLOG [13], etc.), with the idea that applying these processes would allow increasing performance. We would like to show in this section that whenever the processes are "correct", problems may arise due to other aspects which are not included in these models. We have here used the ARIS [START_REF] Davis | ARIS Design Platform: Advanced Processes Modeling and Administration[END_REF] formalism for describing our process models.

Long term coordination

In the long term coordination process, the main activities can be identified as in Figure 2. When selecting a sub-contractor for a given long-term relationship, the customer defines its own standards, which are more and more elective. A result is that a multiplication of certifications is required from the sub-contractors, since standard certifications are often particularized by the customers to their own case. The customer also takes into account the results of his previous relationships with the subcontractor, for instance through its key performance indicators (KPIs) (service ratio, etc.). As a consequence, the sub-contractors complain about the high cost and work induced by this over-assessment, which can in some cases hardly be linked to real performance.

Reaching a common agreement may be difficult since it usually includes not only conditions on price and cycle times, but a commitment for constantly decreasing these values through time. A problem often related is that the people involved at the customer's are more and more buyers, with a poor experience in technical aspects. Therefore, most of the discussion concern prices, which may induce at short term technical problems. Once the contract has been signed, the sub-contractor has to perform local adjustments (investments, contacts with its own sub-contractors or suppliers) for being able to execute the contact. The availability of efficient information systems and production management tools play an important role in making plans in long term, middle term and short term. Indeed, this complex task requires the sub-contractor to be capable of processing forecasts from his customer, using his information tools and assessing risk due to forecast uncertainty. Tools are here an issue, but also the competence and motivation of sub-contractors for tasks that they consider as "administrative", not belonging to their core business.

Fig. 2. Long term coordination process model

Short term coordination

In the short term coordination process (see Figure 3), the sub-contractor usually tries to improve its internal efficiency for being able to decrease its costs through time. This necessity makes that different orders having similar characteristics are often grouped, resulting in problems for meeting the due dates and decreasing the cycle times. In addition, planning is often disturbed by urgent orders or returned goods. In many cases, the urgency of the orders is questionable (and may rapidly change through time) while parts are often returned due to cosmetic reasons (aspect of the parts, not linked to functional issues), to over-tolerances or to different interpretations from the customer and the sub-contractor. On the other hand, sub-contractors often have some difficulty for performing their internal planning, and as a consequence for not being able to control their own suppliers. Therefore, it is very usual that a subcontractor only detects a problem concerning the availability of an order when the delivery has to be performed. On the customer side, measure of performance indicators may become more important than good sense: several sub-contractors mentioned cases when their performance was good, but considered as poor according to the customer's performance indicators, and conversely.

Fig. 3. Short term coordination process model

Concepts to be added to the coordination models

From the coordination models and the described problems, we suggest interpreting some influence aspects that impact the coordination performance and are not usually taken into account.

Trust. Trust is interpreted as the degree of partners' confidence in each other for accomplishing behaviors and achieving benefits as the agreements. In supply chain coordination, partners need to trust each other for exchanging internal information, such as purchase lead time, internal costs or inventory level. Both coordination actors are confident that exchanging information leads to better cooperation rather than losing confidential data or competitive advantages. In practice, trust has a strong influence in the cooperation processes since it allows each partner to share information and to have a positive view on the partner's behave.

Common Understanding. Common understanding is a kind of agreed interpretation between customers and sub-contractors, which is required in several issues in which misunderstanding often occur, like uncertainty of forecasts, urgency, standards of quality and etc.

Willing to Cooperate. As an individual entity that pursues benefits, enterprise, in certain case, chooses to concentrate on its own interests without the considerations of the overall chain. For instance, the customer sends a consultant to its sub-contractor in order to improve the supply performance. However, the consultant only pays attention to the works related to his employer, or even raises the priority of these works ignoring the overall plan of its sub-contractor. These self protective activates of the customer possibly reduce the willing of cooperate of the sub-contractor.

Balance of Power. Balance of power is a very important condition of cooperation in a supply chain, and may result from various issues: size of the partner, specialty (critical for the partner or not), power in the whole supplier chain, competence, access to markets etc.

It is clear that these aspects are interrelated. For instance, balance of power strongly impacts the communication atmosphere and accordingly influences common understanding between partners. We shall try in next section to investigate these relationships at a quite global level, and then try to correlate them with some of the problems observed during the case studies.

4

Towards and extended model for cooperation

From the case studies, we introduce four main concepts that could be taken into account when considering the cooperation not only focusing on formalized processes but also tracing the influence issues of the conflicts. It is also apparent that these aspects are interrelated and relevant to certain cooperation processes. In this section, we suggest two simplified models to presents the relationships at a global view, from both the customer and the sub-contractor's points of view.

In Figure 4 are positioned the relationships between the concepts suggested in the previous section with the customer's point of view. A key point is that the customer has a very positive view on all his incentives towards his suppliers: for him, audits, certification, and competition with other suppliers are good means for increasing the motivation of the partner, and so its performance. Similarly, having a common understanding with the suppliers mainly comes from common standards, brought by certification. Balance of power is only of interest for allowing sharing risk, which is one of the ultimate goals of large companies within supply chains.

Fig. 4. Relationships between concepts -the customer's side

On the opposite, the same concepts are positioned in Figure 5 according to the subcontractor point of view. Most of the initiatives of the customer aiming at improving its maturity and motivation are considered as a proof of distrust, and have a negative influence on motivation and willing to cooperate. The idea of mutual respect is here of prime importance, since the small companies want to be recognized for their skills. This need for mutual respect is struck by the tentative of the customer to change their suppliers (in his view, "increase its maturity"). The origin of most of these misunderstandings is certainly in a lack of dialogue: in the customer's mind, standardization of the relationship leads to performance (through the use of common tools, common processes, etc.). For the small and medium enterprises, dialogue and actions are more important than standards. Balance of power is here only pursued in order to have an influence on the contracts, which is clearly not the idea of the large companies.

Fig. 5. Relationships between concepts -the sub-contractor's side

These two simplified models provide a first interpretation of the relationships between suggested concepts according to the interviews from the case studies. The results suggest that influence concepts that induce conflicts during the cooperation play opposite roles in different sides of partners. The same concepts which are considered as positives issues for cooperation in the customer's point of view are reversely treated as negative facts from the sub-contractor side. Only an increased dialogue could solve such an issue.

Conclusion

In this paper, we suggest reference models to describe the cooperation processes according to real case studies. These processes are close to the main activities described in existing models, such as SCOR etc. Accordingly, the purpose of proposed models is locating problems that may arise due to other aspects which are not included in the existing models. Then, we focus on interpreting the concepts that induce the cooperation problems allowing better explaining the origin of these problems. Based on the interpreted concepts, two models are proposed in order to draw attention to global view of relationships among these concepts and the relevance between concepts and cooperation processes. Due to the case studies in aeronautical industry, the results from the reference models are approach to real cooperation situations, showing that problems during cooperation may be induced by interrelated non-technical concepts such as trust, common understanding, willing to cooperate, balance of power and so on, which are not considered in other models for supply chain cooperation. In addition, the same concepts which are considered as positive points for cooperation in the customer's side are in opposite considered as negative facts from the sub-contractor side. This is a key point that impacts the cooperation in supply chain.

As perspectives in future work, we suggest that cooperation models could consider these interrelated concepts as the "input" or "data" in order to improve the cooperation from partnership rather than standard processes. A possible way to ameliorate the proposed models using ARIS is that "data" are classified according to its influence to the customer and the sub-contractor. For instance, concept "trust" acts as a "support data" in the models of the customer, in opposite, "trust" plays as a "constraint data" in the models of the sub-contractor. In that way, both the customer and the sub-contractor are legible about the conflicts and commons, furthermore to improve the cooperation between partners.

Fig. 1 .

 1 Fig. 1. Typical structure of a Supply Chain

3

 3

Corresponding author. E-mail: yue.ming@enit.fr


Aïcha Amrani-Zouggar

Jean-Christophe Deschamps
email: jean-christophe.deschamps@ims-bordeaux.fr

Jean-Paul Bourrières
email: jean-paul.bourrieres@ims-bordeaux.fr

Supply chain reactivity assessment regarding two negotiated commitments: Frozen horizon and flexibility rate

Keywords: Supply chain, Tactical production planning, supply contract commitments, simulation

The problem addressed in this paper is the supply chain reactivity assessment through numerical experimentations regarding specifically two negotiated commitments within supply contract: the frozen horizon and flexibility rate. Analysis of impact of these commitments on each partner will be depicted in term of storage costs, reliability and reactivity indicators. The decision making inside each partner is operated under rolling horizon planning and based on production linear programming model wherein different contractual commitments are included. To carry out experimental scenarios, simulation platform is developed from which expecting numerical results afford deciders to get more understanding about the commitments that should be contracted and the relevant dimensioning of them.

Introduction

In increasingly competitive context where the customer's requirements are still growing and the demand is highly volatile, many risks are threatening the order fulfilment process. One way to cope with these risks is to extend the partner's network that brings some stability to the network. The deciders are aware that collaborative approaches constitute a strong axis of reducing surrounding risks. However, if the network may constitutes a response to some risks, it generates other ones [START_REF] Christopher | Logistics and Supply Chains management[END_REF] therefore it becomes essential to achieve the challenging aim of ensuring whole supply chain performance. Our current work is based on collaborative relationships that are framed by supply contracts among the partners. Indeed, contractual agreement of supplying products from the suppliers if accurately designed may provide the required enhancement of performance. Negotiate specific clauses of collaboration with suppliers through contract commitments becomes an excellent coordination mechanism [START_REF] Mentzer | Supply chain collaboration: enablers, impediments, and benefits[END_REF] stabilizing the relationship over certain horizon of time and minimizing industrial risks (such as high inventory level, backorders, delay of deliveries, unsatisfying customer and rush orders).

In our previous works, we have shown in [START_REF] Amrani-Zouggar | Supply chain contracts design according to industrial risks[END_REF] the intrinsic relationship between risks and the negotiated clauses. Further, we have revealed through simulation an effective quantified sensitivity of buyer and supplier performance to different quantity commitments contracts [START_REF] Amrani-Zouggar | Supply chain planning under various quantity commitment contracts[END_REF]. In this paper, our proposition focuses on the analysis of supply chain reactivity regarding two negotiated commitments: Frozen horizon and flexibility rate. The purpose of this study is beyond the simple checking of sensitivity leading to show explicitly to which partner do the commitment benefit and how explain it? The remainder paper is organized as follows. The related work of supply contracts is presented in Section 2. In Section 3, description of tactical production planning model is provided with an overview of contractual agreements (frozen horizon and flexibility rate) subjected to the study. Section 4 is devoted to discussing the reactivity of supply chain regarding two evoked commitments. The analysis is done inside a buyersupplier relationship. In Section 6, further experimentations come to reinforce our contributions and conclusion comes to end this paper.

Literature review

Great attention is granted to collaborative approaches which are widely studied. Supply contracts constitute part of them and consist in agreements between buyer and supplier, that aim at protect their respective own and joint interests, describe the limits of risk, enounce terms and conditions of fulfilment. Once clauses clearly identified, monitoring of order fulfilment process becomes possible at the operational level. In literature, we distinguish for example [START_REF] Cachon | Supply chain coordination with contracts[END_REF], [START_REF] Bassok | Analysis of supply contracts with total minimum commitments[END_REF] where the authors aim through their research to get optimal purchasing policy. We notice that majority of works are optimization models under contractual context based on stochastic modelling [START_REF] Liston | Contract costing in outsourcing enterprises: Exploring the benefits of discrete-event simulation[END_REF] or continuous modelling [START_REF] Anupindi | Supply contracts with quantity commitments and stochastic demand[END_REF]. Our research is quite different in term of problem modelling and objective, in one hand we propose a discrete planning model (like [START_REF] Schneeweiss | The design of contracts to coordinate operational interdependencies within the supply chain[END_REF]) rather infrequently used in this field. In the other hand, the simulation that will be carried out is the basis of quantitative analysis to oversee simultaneous impact on performance of varying two commitments. The aim of our work is rather to check the impact of each commitment (frozen horizon and flexibility rate) on own and overall performance than to assess the numeric value of the optimisation.

Tactical Production planning model

Each actor of considered supply chain SC is assimilated to a DMU (Decision Making Unit) with carrying out the calculation of production, replenishment and delivery plans and the levels of necessary stocks to each period. The model concerns multiproduct (p), multi periods (t), with finished nominal capacity that accommodates adjustment by additional capacity represented here by the decision to resort to overtime (additional hours). Planning process is dynamically depicted according to the principle of rolling horizon planning. Any modification that occurs either on the demand or on operational execution can be taken into account at the next planning occurrence. We make the assumption that Demand is deterministic and known along the planning horizon. The production planning process developed is based on linear programming modelling with a criterion to maximize under a set of constraints.

Model

The table 1 summarizes various notations adopted to formalize the production planning process.

Table 1. Notation list

The objective function (1) tends to maximize the profit resulting from the difference between the sales and the various undergoing costs :

∑∑ - + == ⋅ - + + + - 1 1 . , , , , , ) . .
A h L l B b I i F f L PV ϕ ϕ ∑ = ⋅ + - m j t j j t j j R a I i 1 , ,
)) . (

Under the constraints

These constraints are valid

- + = - ∑ = - - + = n p t p j p t j t j t j F R I I 1 , , , 1 , , . γ t n p t p p A CAPN F + = ∑ ≤ 1 , . α CAPN CAPA CAPA At . % θ = ≤ n p ,..., 1 = ∀ ) 2 ( t p t p t p t p L D B B , , 1 , , - + = - n p ,..., 1 = ∀ ) 3 ( m j n p ,..., 1 , ,..., 1 = ∀ = ∀ n p ,.., 1 = ∀ n p ,..., 1 = ∀ ) 4 ( ) 5 ( ) 6 (
The equation ( 2) is a quantity conservation equation; it links the level of stocks and the produced quantity. The equation ( 3) links the level of shortages to the demand and deliveries. The equation ( 4) calculates the level of stocks of components according to the receptions, the production and bill of materials coefficients. The constraint [START_REF] Cachon | Supply chain coordination with contracts[END_REF] gives the limits of production quantities according to the normal capacity and additional capacity. The constraint (6) guarantees limitation of overtime in such way that additional capacity is equal to a certain percentage (θ%) of the normal capacity.

Contractual constraints

The specificity of this contribution is to check the potential impact on reactivity of partners when varying two commitments negotiated during the design of supply contract. In this section we introduce more deeply these clauses and formalize them in order to integrate them into the production planning process.

Frozen horizon (FH) & Flexibility rate (α%)

In fluctuant demand context, rolling horizon planning often comes to palliate the uncertainty impact giving the possibility to the deciders to update their planning process including new information (demand fluctuation, delivery disturbance…). However, the industrial reality shows the necessity to stabilize the activities during certain amount of time called "frozen horizon" (FH) in [START_REF] Millart | The impact of rolling horizon planning on the cost of industrial fishing activity[END_REF], or "freezing time". When a frozen horizon is negotiated through supply contract between two adjacent partners, the value of purchasing quantities over frozen horizon have a commitment values and could not be modified with next planning occurrence. Over a frozen horizon, a rate of flexibility (α %) is negotiated to enable the buyer to modify demand among two planning occurrences (Fig. 1). Flexibility rate concept has been studied in literature. These are some definitions founded: for [START_REF] Liston | Contract costing in outsourcing enterprises: Exploring the benefits of discrete-event simulation[END_REF], it is an upside and downside flexibility bounds of order quantity. Bassok & Anupindi in [START_REF] Anupindi | Supply contracts with quantity commitments and stochastic demand[END_REF] considers a model in which the amount of increase or reduction in the order for a given period is limited to a percentage of the current order for the period. We notice that these definitions converge to the same idea, flexibility rate (α%) consists in two bounds allowing adaptation to the uncertainty of the market. These commitments constitute a kind of constraints that each partner has to model, to formalize and take into account during each occurrence of the planning process. Our work consists on modelling these commitments and introduces them in a tactical planning model. Over seven periods of FH in (Fig. 1), the producer starts a certain production volume. Indeed, the necessary purchasing quantities from supplier for executing orders will have a commitment value. They could not be modified at next planning moments. Beyond the frozen horizon of the producer, we find the flexible horizon (FLH) which is by definition less rigid. On this horizon the producer is approved to vary his orders of over or under certain percentage (α%) at the next planning occurrence (example: α%=20% means from 100 units to 120 units). After planning period PP, additional decisions come to complete the length of horizon

t j i C ,

Fig.1. Frozen horizon and flexibility rate

We claim that it should be taken care that the quantity of purchasing orders (C j,t ), belongs to the intervals authorized by negotiated (α %). Constraints of this context may be written as follows:

To ensure the arrivals of (R j,t ) the purchasing quantity (C j,t ) have to be transmitted to supplier some periods (D liv ) in advance; it is expressed through equation [START_REF] Liston | Contract costing in outsourcing enterprises: Exploring the benefits of discrete-event simulation[END_REF]. Equations ( 8), ( 9), [START_REF] Millart | The impact of rolling horizon planning on the cost of industrial fishing activity[END_REF] express the report of the frozen decisions. For example, Produced quantities F i p,t at step (i) will be assigned the value of previous produced quantities F i-1 p,t of previous planning step as long as , the orders transmitted at planning step (i) C i j,t might vary within the interval plus or less (α %) from a previous order C i-1 j,t .

Experiments & analysis

The simulation platform dedicated to perform different scenarios has been detailed in our previous contribution [START_REF] Amrani-Zouggar | Supply chain planning under various quantity commitment contracts[END_REF]. In this experimental section, based on our simulation platform, we test different configurations of flexibility rate, and frozen horizon between a buyer OEM and supplier PRODU. The results will be expressed in terms of different performance indicators, as the profit (criterion to maximize), the costs of adaptation (including finished product inventory costs, delivered components inventory costs, backorders and additional hours costs); the reactivity is then expressed by the number of required periods by the partner to satisfy the entire demand and the reliability is calculated as the ratio of real delivery and expected delivery products. These indicators allow a better understanding of supply chain behaviour according to the point of view of decision maker. At first, buyer supplier view is analyzed in order to give off global trends. To depict accurately the impact of parameters on both partners, more focused analysis will be carried out. Demand disturbance would be tested at period t=11 with enhancement of 600 products.

) ( , , Dliv t j i t j i C R - = %) 1 .( %) 1 ( , 1 , . , 1 α α + ≤ ≤ - - - t j i t j i t j i C C C 1 ,..., - + = ∀ H t ϕ ϕ t p i t p i F F , 1 , - = 1 - = i i At At t j i t j i C C , 1 , - = ) 7 ( ) 1 ( ,.., - - + = ∀ PP FH t ϕ ϕ ) 8 ( ) 9 ( ) 1 ( ,.., - - + = ∀ PP FH t ϕ ϕ ) 10 ( ) 1 ( ,.., - - + = ∀ PP FH t ϕ ϕ 1 ,..., 1 - + - + = ∀ FLH FH t ϕ ϕ ) 11 (

Buyer supplier view: global trends

Global trend shows (Table 2.) that the supply chain behaves differently according to the adopted configuration of FH and α %. More the FH is high better it is for supplier (PRODU) but not to the buyer. More the flexibility rate increases, better it is for the buyer (OEM) but unfortunately not so benefit for supplier PRODU. Further, we achieve a detailed analysis on each partner to perceive the mechanism that leads the partner to record these performances.

Table 2. Buyer & supplier performance trend

According to these results, we may notice that these two clauses are antagonists. That's why it becomes important to relevantly negotiate them. Another interesting observation that simulation shows is that a compromise of performance (by regulating two parameters) could be obtained to achieve expected performance. It doesn't mean that maximum value of flexibility only achieve accepted performance. Configuration of (α =20%, FH=8) records less overall costs than configuration (α=35%, FH=7) it underlines the fact that the best configuration of commitments compromises can be obtained by simulation and the best configurations aren't particularly obviously expected.

Analysis of local performance per partner

What happens with varying frozen horizon, why is it benefiting for supplier?

We highlight the undertaken points to make our analysis; it consists on observing the costs of inventory levels, backorders levels and required additional hours. Let us consider the scenario where flexibility between two partners is equal to 13%; we focus on the differences of costs generated by two configurations of frozen horizon FH=6 and FH=7. (Fig. 2 The observation shows that for OEM more frozen horizon is high, more he will be constrained to freeze also his production planning according to the arriving components from suppliers, less periods remains for performing the smooth of the load so less production could be done. (FH=7) generates by this way more backorders, huge costs and smaller reactivity. FH seems not to be benefit to the buyer at all, it prevents him from smoothing and do not allows the transmission of the real demand changing, limited to only what supplier would like to perceive. Whereas for PRODU, more the frozen horizon is high (FH=7) better it is, the supplier hasn't ever to perceive the demand pick, he considers previously planned production and is not obliged to make high inventory of ended product (as it is the case for FH=6). Indeed, if frozen horizon decreases, (Fig. 2) shows the necessity to anticipate by preparing more inventory level generating high adaptation costs for supplier.

What happens with varying flexibility rate, why is it benefiting for buyer? Fig. 3. Profiles with varying α% at buyer (OEM) and supplier (PRODU)

We carry out an analysis in scenario with (α =13%, FH=6) and (α =20%, FH=6) configurations of commitments. The results enable us to show that increased α % granted by the supplier benefits to OEM and penalise PRODU. In (Fig. 3), we may notice with increasing α % that inventory level of components at OEM decreases. In deed, with increasing flexibility rate, more deliveries can be expected avoiding cumulating inventory stocks at the buyer OEM. Whereas at the supplier, more inventories of finished products becomes required to be reactive to

Periods of time

Quantity of product

Inventory level of finished products, alpha=13%

Inventory level of finished products, alpha=20% OEM PRODU α%=20% α%=13% α%=20% α%=13% buyer pick; therefore, we see that the smooth of inventory load becomes bigger in scenario α =20% configuration.

Perspectives & Conclusion

Starting from simulation study wherein we check for the impact of FH and α% commitments, we can release some interesting observations about their relevance and their usefulness at each partner of supply chain. More the flexibility is high, less inventory at the buyer are required enhancing by the way his performance. More the FH is high better it is for the supplier who avoids perceiving the demand variation and is not obliged to make high inventory level. In this paper, the supply chain is still reduced to its elementary network (producer and supplier). The simulation platform enables us to carry out other simulations extended to 3 partners in the network. These results are under finalizing and will be published in future work. Converging to adequate contract between SC partners still remains a delicate step hard to achieve in industrial reality. This study wishes to provide deciders with more visibility about the commitments able to protect them or on contrary threat their interests in order to guide them to thoroughly consider them during negotiation process.

1 :

 1 At planning step (i-1), we report decisions of (C i-1 j,t ) over periods 5,6,7. The constraints (11) expresses the flexibility commitment, as long as 1

Fig. 2 .

 2 Fig.2. Profiles with varying FH at producer (OEM) and supplier (PRODU)

  )

		FH= 6			FH = 7			FH = 8
	OEM	PRODU	Overall	OEM	PRODU	Overall	OEM	PRODU	Overall
	α=13%
	Profit ($)
	Costs ($)
	Reactivity (period)
	Reliability (%)


Jérôme Nika
email: jnika@ircam.fr

José Echeveste
email: echeveste@ircam.fr

Marc Chemillier
email: chemilli@ehess.fr

Jean-Louis Giavitto
email: giavitto@ircam.fr

Planning Human-Computer Improvisation

Improvisation intrinsically carries a dialectic between spontaneity/reactivity and long-term planning/organization. This paper transposes this dialectic to interactive human-computer improvisation where the computer has to interleave various generative processes. They require different levels of prior knowledge, and follow a coarser improvisation plan driven by real-time interactions with the musicians. We propose a time-aware extensible architecture allowing the temporal coordination of different improvisation strategies. It integrates various generative strategies capitalizing on the system Improtek into the high-level structure provided by the language associated to the score follower Antescofo. The resulting framework manages the musical events, the triggering of generative processes at different time scales and the declarative specification of improvisation plans driven by the occurrence of complex events.

INTRODUCTION

This article proposes a new framework to conciliate the need of spontaneity and reactivity with long-term planning and temporal organization in human-computer improvisation. This framework enables the temporal coordination of different improvisation strategies within an improvisation plan driven by the occurrence of complex musical and logical events.

Most improvisation styles rely on prior knowledge of the temporal evolution of the music to produce. This temporal organization can be an explicit sequence as standard themes in be-bop improvisations or given melodies in some traditional folk music. When it is not, the temporal structure can be specified as a sequential scenario describing a sequence of constraints that must be satisfied successively by the improvisation to be played. A standard example is the harmonic progression used in most current western musical styles such as rock, blues, jazz or pop music. Otherwise, the temporal organization may not take the form of a sequential structure. In this case it can be best described as responses to complex events implying both musical events and logical conditions, as for instance in soundpainting. These temporal structures exist concurrently at different time scale, for example: at short-term, the synchronization of the notes of a generated sequence with current tempo; generation of musical sequences satisfying global constraints in mid-term; and at a higher level, switching from an improvisation part to another, defined by different sets of prior knowledge, memory, mechanisms and rules (such as switching from lead to follow, from free to idiomatic, etc.). The coordination of these temporal sequences and reactions constitute complex improvisation plans or dynamic scores.

In [START_REF] Rowe | The aesthetics of interactive music systems[END_REF], Rowe outlines that designing interactive musical systems pushes up musical composition "to a meta-level captured in the processes executed by the computer". The framework proposed in this paper addresses this "metalevel" and is aimed at the definition and the implementation of the temporal structures used to guide or constrain music generation in reaction to an active listening of the live musical input. It couples two literatures, generative model with real-time recognition and reactive systems, usually considered separately but whose integration makes complete sense in interactive and improvised musical practices.

This architecture has been deployed with the development of an experimental prototype capitalizing on the Improtek [START_REF] Nika | ImproteK, integrating harmonic controls into improvisation in the filiation of OMax[END_REF] and the Antescofo [START_REF] Cont | On the creative use of score following and its impact on research[END_REF] systems. The former provides structured and guided musical generation from an ordered and indexed online or offline memory, while the latter provides musical synchronization and the possibility to specify reactions to unordered complex events.

After presenting some background in interactive improvisation systems and sequencers in section 2, this paper gradually describes how improvisation strategies with different degrees of indeterminism can be employed within the same plan. Section 3 focuses on fixed reactions to a planned input. Section 4 presents the generation of musical sequences satisfying long-term constraints and section 5 how reactivity can be injected into these generative processes through dynamic calls and parametrization with the musical context. Finally, section 6 sketches programing patterns for writing reactions to unordered complex events.

RELATED WORK

Interactive improvisation systems can be categorized by their hard-coded inherent strategy to drive the music generation process. A first category let to an operator-musician the guidance of the generation process: OMax [START_REF] Assayag | OMax brothers: a dynamic topology of agents for improvization learning[END_REF][START_REF] Lévy | OMaxist dialectics[END_REF] is controlled by a user steering the navigation through a representation extracted in real-time from the playing of a live musician. The user is also at the heart of Mimi4x [START_REF] Franc ¸ois | Mimi4x: an interactive audio-visual installation for high-level structural improvisation[END_REF] and is involved in the construction of the performance by choos-ing the musical corpus and modifying the generation parameters. Other systems are driven by an analysis of the live inputs: SoMax [START_REF] Bonnasse-Gahot | Online arrangement through augmented musical rendering[END_REF] translates the musical stream coming from an improviser into constraints, for example described in terms of harmonic background, to filter the possible paths in a corpus whose internal logic can also be followed. VirtualBand [START_REF] Moreira | Virtualband: Interacting with stylistically consistent agents[END_REF], emphasizes interaction and reactivity and extracts multimodal observations from the musician's playing to retrieve the most appropriate musical segment in a memory in accordance to previously learned associations. In the same line, Reflexive Looper [START_REF] Pachet | Reflexive loopers for solo musical improvisation[END_REF] uses in addition harmonic annotations in the search criteria. Finally, an upstream structure or description can run the generation process: PyOracle [START_REF] Surges | Feature selection and composition using PyOracle[END_REF] proposes to create behavior rules or scripts for controlling the generation parameters of an improvisation session. The concept of control improvisation in [START_REF] Donze | Control improvisation with application to music[END_REF] introduces a control structure to guide the improvisation by a reference sequence and satisfying given specifications. The generation process presented in section 4 also includes an inherent strategy based on longterm constraints. In the context of improvised mixed music, it needs to be integrated in an environment allowing the specification of temporal developments of musical processes in reaction to human performance or controls given to an operator-musician.

The system Antescofo is chosen for the high-level organization of the musician-computer interaction because it combines score following capacity with an expressive timed and reactive scripting language. In Max/MSP or PureData [START_REF] Puckette | Combining event and signal processing in the max graphical programming environment[END_REF] which are dataflow graphical languages and where control and signal processing are statically determined, it is easy to construct static behaviors, but much harder to organize and control changing behaviors according to a complex scenario. Antescofo, compiled as a Max or PureData object, is used in these cases to interact with the external environment. Other dynamic languages encounter some success in the interactive music community such as SuperCollider [START_REF] Mccartney | Supercollider: a new real-time synthesis language[END_REF] or Chuck [START_REF] Wang | The chuck audio programming language." a strongly-timed and on-the-fly environ/mentality[END_REF]. These are textual languages facilitating the programming of audio and algorithmic processes. Their real-time properties make them ideal tools for "Live Coding" practices, often improvised, where the time of composition (in the program) coincides with that of performance. However, the semantics of these languages does not allow the direct specification of the behavior of the external environment. Furthermore, their models of time is not directly linked with that of the performer.

Compared to traditional sequencers such as LogicPro, Pro-Tools or CuBase, Antescofo is dedicated to more dynamic situations. Ableton Live with Max4Live adds more possibilities of interaction compared to the sequencers cited above, but without providing a flexibility allowing to synchronize the electronic processes to the elastic time of the musician.

FIXED REACTION TO A PLANNED INPUT

An improvised music performance may refer to predefined melodies, scores, audio materials or more broadly sequences of actions with their own temporality. The synchroniza-tion with a musician's performance of heterogeneous electronic actions (playing an audio file, triggering of a synthesis sound, or the execution of some analysis processes, etc) is a common problem of interactive music systems. Many solutions have emerged to deal with this issue depending on musical purpose or available technologies, leading to the score following approach used in the environment described in this paper.

The most elementary solution is to launch a predefined electronic sequence recorded on a fixed support (magnetic band, classical sequencer). In this case, the musician's performance is totally constrained by the time of the concerned support. Another way to make the time of electronic actions progress is to use a cue-list logic. The electronic is here defined as a list of successive actions and a mechanism as a pedal controller activated by the musician at the right moment triggers corresponding actions to execute. This approach is more flexible than the previous one because the time of the performance is under the supervision of the musician. However it raises the issue of how to partition the electronic part of the score if it is continuous in the thought of the composer and during the performance. Furthermore, giving the control of the electronic time to the musician can hinder the expressivity during the performance.

Score following is defined as the real-time alignment of an audio stream played by one or more musicians into a symbolic musical score. It offers the possibility to automatically synchronize an accompaniment, and thus can be used for the association of an electronic part to a predefined instrumental in an improvised music context. Antescofo is a real-time system for interactive music authoring and performing. It focuses on high-level musical interaction between live musicians and a computer, where the temporal development of musical processes depends on active listening and complex synchronization strategies [START_REF] Cont | On the creative use of score following and its impact on research[END_REF]. In [START_REF] Cont | Antescofo: Anticipatory synchronization and control of interactive parameters in computer music[END_REF] a novel architecture has been proposed that relies on the strong coupling of artificial machine listening and a domain-specific real-time programming language for compositional and performative purposes. The user creates an augmented score whose language integrates both programmed actions and musical events, allowing a unique and flexible temporal organization. The augmented score includes both the instrumental part to recognize and the electronic parts and the instructions for their real-time coordination during a performance.

The syntax for writing the instrumental part allows the description (pitches and durations) of events such as notes, chords, trills, glissandi and improvisation boxes. Actions are divided into atomic actions, performing an elementary computation, and compound actions. The atomic actions can be: messages sent to the external environment (for instance to drive a synthesis module), a variable assignment, or another specific internal command. The group construction describes several actions logically within a same block that share common properties of tempo, synchronization and errors handling strategies in order to create polyphonic phrases. Other constructions such as loops for iterated actions or curve for continuous specification are also available.

During performance, the runtime system evaluates the augmented score and controls processes synchronously with the musical environment, thanks to data received from the machine listening. The reactive system dynamically considers the tempo fluctuations and the values of external variables for the interpretation of accompaniment actions. The possibility of dating the events and the actions relatively to the tempo, as in a classical score, is one of the possibility offered by Antescofo. Within the augmented score language, the user can thus decide to associate actions to certain events with delays, to group actions together, to define timing behaviors, to structure groups hierarchically and to allow groups act in parallel.

Delays and durations are arbitrary expressions and can be expressed in relative time (in beats) or in physical time (in seconds). Antescofo provides a predefined dynamic tempo variable through the system variable $RT TEMPO. This variable is extracted from the audio stream by the listening machine, relying on a cognitive model of the behavior of a musician [START_REF]A coupled duration-focused architecture for realtime music to score alignment[END_REF]. Programmers may introduce their own frames of reference by specifying a local tempo for a group using a dedicated attribute. All the temporal expressions used in the actions within this group are then computed depending on this frame of reference. As for other attributes, a local tempo is inherited if groups are nested. A local tempo is an arbitrary expression involving any expressions and variables. This expression is evaluated continuously in time for computing dynamically the associated delays and durations.

IMPROVISATION GUIDED BY A SEQUENTIAL SCENARIO

Memory and scenario

When the prior knowledge on the structure of the improvisation is not as explicit as classical score, a melody or a theme, it may consist in a sequence of formalized constraints for the generation of the improvisation to create.

Examples of such formalized structures can be a chord progression in blues, rock, or jazz improvisation; the harmonic progression given by the bass in the baroque basso continuo; or the precise description of the evolution of the improvisation in terms of melody, tempo or register in the indian raga. This section describes an improvisation model extending that of ImproteK [2] 1 , relying on such a sequence of constraints existing before the performance. This model follows on the work initiated in [START_REF] Dubnov | Universal classification applied to musical sequences[END_REF][START_REF] Assayag | Guessing the composer's mind: Applying universal prediction to musical style[END_REF] on the navigation through a cartography of a musician's live playing, partly capturing his musical logic. The application of these principles in a real-time improvisation system led to OMax [START_REF] Assayag | OMax brothers: a dynamic topology of agents for improvization learning[END_REF][START_REF] Lévy | OMaxist dialectics[END_REF], and long-term constraints and a priori knowledge were brought in the generation process with ImproteK by means of an abstract symbolism conveying different musical notions depending on the applications, like meter as regards rhythm or chord notation as regards 1 Links to video examples of live performances and work sessions can be found at http://repmus.ircam.fr/nika harmony [START_REF] Chemillier | L'improvisation musicale et l'ordinateur[END_REF], joining previous works on the use of chord charts in improvisation [START_REF]Improviser des séquences d'accords de jazz avec des grammaires formelles[END_REF][START_REF]Toward a formal study of jazz chord sequences generated by Steedman's grammar[END_REF].

The improvisation process is here modeled as the articulation between a scenario to follow and a structured and indexed memory in which musical fragments are retrieved, transformed and reordered to create new improvisations:

• the scenario is a symbolic sequence guiding the improvisation and defined over an appropriate alphabet for the musical context, • the memory is a sequence of contents labeled with a symbolic sequence defined over this same alphabet.

In this framework, "improvising" means going through the memory to concatenate some contiguous or disconnected blocks satisfying the sequence of temporal constraints given by the scenario. These blocks are chained in a way comparable to an improviser who is able to develop an improvisation by using motifs he eared or played himself in different contexts, described here with different scenarios. The improvisation process searches for the continuity of the musical discourse as well as the ability to grow apart from the original material. It relies on the indexation of some similar patterns in the scenario and the memory, and the self-similarities in both sequences.

Overview of the model

The scenario and the sequence describing the musical memory are represented as words defined over a same alphabet. This alphabet describes the equivalence classes chosen to compare the musical contents of the online or offline memory. After choosing a temporal unit for the segmentation, the letter at index T of the scenario S of length s is noted S[T ] and corresponds to the required equivalence class for the time T of the improvisation. In the same way, the letter M [P ] gives the equivalent class labeling the musical fragment corresponding to the date P in the memory M of length m. In what follows, each musical content in the memory will be assimilated to the letter M [P ] indexing it, and by extension the whole memory will be assimilated to the word M . The scenario gives access to a prior knowledge of the temporal structure of the improvisation to play. It enables to take into account the required classes for future dates T + 1, T + 2,... to generate improvisation at time T . The current scenario, noted S T , corresponds to the suffix of the original scenario beginning at the letter at index T : S[T ]...S[s -1]. At each time T , the improvisation goes on from the last state read in the memory at time T -1, searching to match the sequence of constraints given by the current scenario.

The proposed improvisation model undertakes successive navigation phases2 through the musical memory, which rely on searches of prefixes of the current scenario in the memory. The length of these prefixes is one of the control parameters of the process. Figure 1 illustrates two consecutive generation phases. 1. Search for a prefix providing a starting point in the memory (steps 1 or 3 in figure 1), detailed in 4.3, 2. Follow a linear or non-linear path matching the scenario (steps 2 or 4 in figure 1), detailed in 4.4.

They respectively take advantage of the prior knowledge on the structure of the scenario and the memory, and address the concerns of musical continuity and transformation of the original material. Each of these two steps described in the following part of this section introduces a parameter whose value influences the musical result: c f representing the continuity regarding the future of the scenario, and c p quantifying the continuity regarding the past of the memory.

Step 1: searching for a section of the current scenario in the memory

The first step when going through the memory to produce the improvisation is to search for a pattern matching a section of the current scenario in the memory, that is to say a

prefix M [i]...M [i ′ ] of S T =S[T ]...S[s -1] in M . The first element of this pattern, M [i],
gives a starting point for the navigation phase. The trivial solution is then to copy the whole pattern M [i]...M [i ′ ] (the other options are described in the following paragraph 4.4). The set SP (T ) of possible starting points for the generation of the improvisation from a date T is defined by:

SP (T ) = {i ∈ N | ∃c f ≥ 0, M [i]...M [i + c f ] ∈ Prefixes(S T )}
where c f measures the duration of the sequence in the memory starting at the chosen index i, matching a part of the current scenario S T , and which can be literally cloned.

The choice of an actual starting point among the elements in SP (T ) is made in accordance with the current state of the constraints imposed on it. For example, imposing the maximum value for c f will lead to a maximal length prefix and will provide a homogeneous and continuous musical result throughout its duration. Conversely, a small value will lead to extractions of short segments in potentially different zones of the memory. Depending on the musical situations, one can successively prefer a state providing the coherence of the musical discourse in the long term and very close to a section of a learned sequence, or a more fragmented musical result. Constraints on others parameters also influence the choice of an element in SP (T ), among them the location of the pattern in the memory or the preference for a segment offering the best progression regarding the end of the segment produced by the previous phase. The control on these parameters can be given to an operator-musician and/or integrated in a higher level of the improvisation planning (see 6.5).

The prefix indexing algorithm used to obtain the set SP (T ) (detailed in an upcoming paper) uses the "failure function" of the Morris and Pratt algorithm [START_REF] Morris | A linear pattern-matching algorithm[END_REF] to process selfsimilarities in S T in a preliminary analysis phase (as it is used in [START_REF] Crochemore | Algorithms on strings[END_REF] to get the tables of prefixes and borders). This result is then used in the search phase to index the prefixes of the current scenario S T in the memory M .

Step 2: following a non-linear path matching the current scenario

For each generation phase, the improvisation process starts from the chosen starting point and runs through the memory collecting a sequence of states whose labels match the scenario, and this mechanism goes on until the research of a new starting point is necessary. After a starting point is chosen in the memory at the indexing step (4.3), the first solution is to literally clone the prefix beginning by this state (step 2, figure 1). Yet, in particular when S T and M are very close, the set of possible paths has to offer more than a simple copy to create new material. The navigation process exploits therefore an analysis of the selfsimilarities in the structure of the memory to generate a continuous musical discourse while widening the scope.

The possible progressions matching the scenario from a given state M [k 0 ] is thus defined as the set of the states in the memory sharing a common past with M [k 0 ], and satisfying the next label S[T ] imposed by the scenario. The set P (T, k 0 ) of indexes k of the states in the memory matching the time T of S and being a candidate for the next progression from the previous state M [k 0 ] is defined by:

P (T , k 0 ) = {k ∈ N | ∃ c p ∈ [1, k], M [k -c p ]...M [k -1] ∈ Suffixes(M [0]...M [k 0 ]), and M [k] = S[T ]}
The similar pattern in M and S T can be linearly followed by choosing in P (T, k 0 ) the consecutive state in the memory M [k] = M [k 0 + 1]. Assuming that jumps between two segments in the memory sharing a common past preserve a certain musical homogeneity, non-linear paths are also considered, as in the step 4 (4a then 4b) in figure 1, to avoid a simple copy of the learnt sequence. Such jumps are authorized when the factors ending at the origin and at the destination of these jumps share a common suffix. The length of this common suffix c p measures the length of the shared musical past and therefore quantifies the "quality" of these jumps.

The automaton structure chosen to learn the musical memory is the Factor Oracle [START_REF] Allauzen | Factor oracle: A new structure for pattern matching[END_REF][START_REF] Lefebvre | Drastic improvements over repeats found with a factor oracle[END_REF]. The progression process of this second step of the generation extends the mechanism for improvisation, harmonization and arrangement proposed in [START_REF] Nika | ImproteK, integrating harmonic controls into improvisation in the filiation of OMax[END_REF] based on the navigation [START_REF] Assayag | Using factor oracles for machine improvisation[END_REF][START_REF] Assayag | Navigating the oracle: A heuristic approach[END_REF] in this automaton for musical applications. This automaton presents links locating repeated patterns within the sequence and providing the existence of a common suffix between the elements that they connect, giving then the successive sets P (T, k 0 ). The common suffix is seen as a common musical past in the context of this application. The postulate at the heart of the musical models using the Factor Oracle [START_REF] Assayag | OMax brothers: a dynamic topology of agents for improvization learning[END_REF][START_REF] Lévy | OMaxist dialectics[END_REF][START_REF] Bonnasse-Gahot | Online arrangement through augmented musical rendering[END_REF][START_REF] Surges | Feature selection and composition using PyOracle[END_REF][START_REF] Franc ¸ois | Mimi4x: an interactive audio-visual installation for high-level structural improvisation[END_REF][START_REF] Donze | Control improvisation with application to music[END_REF] is indeed that such non-linear paths in a musical memory thus mapped enable to create musical phrases proposing new evolutions while preserving the continuity of the musical discourse.

INTRODUCING REACTIVITY INTO THE IMPROVISATION MODEL

From static to dynamic generation

The improvisation model guided by a scenario can be used in live performance to generate autonomous sequences satisfying given specifications or in an offline process, for instance composition. This section introduces scheduling of dynamic calls to this model in order to bring reactivity and adapt to the generation process to the improvisation environment. This way, the generation can react to changes of control parameters (given to an operator-musician and/or mapped to the live musical input) or to dynamically modified scenarios while being coherent with the past and keeping its long-term horizon. Listening to a source of beats gives the current date T , and also the associated label S[T ] in the scenario used in different concurrent processes. The three main aspects of the integration of the improvisation model into a real-time environment are presented in figure 2: 1) learning the musical material from the musicians playing with the system, 2) generating and 3) playing the new improvised phrases synchronously with the running improvisation session. For this end, a buffer is added to the two main elements in the model (scenario and memory). It contains the short-term anticipated playing "intentions", which are refined over time.

Scheduling the navigation phases: anticipations and rewritings

The implementation of this architecture involves parallel processes listening and reacting to the environment, the elements produced by the model, and the instructions given by the operator or a higher scale improvisation plan. These processes correspond to the three blocks building the generic dynamic score given in algorithm 1. It contains the scheduling of the calls to the model described in 4, and the sequence triggering:

Algorithm 1. Scheduling the reactions to the environment

1. Listening to update of current date orchestrates labeling and learning of musical material, and playing of anticipated events stored in the buffer (lines 1-6 in algorithm 1).

2. When a new element generated by the model is received (lines 12-18 in algorithm 1), it is stored in the buffer or immediately played managing potential delays.

3. A query to generate a segment of improvisation starting at date T ′ ≥ T associated to suffix a S T ′ of the scenario can be sent if it is required. The model is called to generate the improvisation phase (see 4.2) after phase, anticipating the performance time. A query launching a new generation phase is thus sent if the minimum anticipation delay between the current time T and the first date with no element previously generated and stored in the buffer E is reached (lines 7-9 in algorithm 1). Figure 3 gives an overview of different processes running at a given time T of performance. In reaction to modification of a parameter or an update of scenario affecting a date T ′ ≥ T , a query launching a new generation phase is sent (lines 10-11 in algorithm 1). If this query overlaps with a previous one, the associated anticipated part of the improvisation is rewritten. This scheduling architecture combines anticipation and reactive controls. The short-term intentions stored in the buffer evolve and are refined as the performance goes. A trace records history of paths in the memory and constraints of last navigation phases so that coherence between successive phases associated to overlapping suffixes of the scenario is maintained. This way for example, constraints can be imposed in realtime, and short-term memory can immediately be injected while keeping up with the scenario. A "reaction" is not seen here as a spontaneous instant response, but as a revision of the short-term intentions matching the scenario in the light of new events from the environment.

CHAINING REACTIONS TO UNORDERED COMPLEX EVENTS

6.1 From scheduling to logical planning

The generative model introduced in section 4 was implemented as a Common Lisp library using the OpenMusic environment [START_REF] Bresson | OpenMusic: visual programming environment for music composition, analysis and research[END_REF]. The memory and the navigation methods are called in this interaction context through a producerconsumer system which involves parallel processes sharing accesses to the memory and the information received from the dynamic score (algorithm 1). This structure containing the scheduling of the calls to the model, the buffer, and the triggering of the playing of the computed sequences is implemented using Antescofo language. The corresponding program is generic enough to be independent of improvisation situations and of types of scenario. The improvisations generated by the model are then played in synchrony with the musical environment, following the fluctuation of the tempo. The synchronization strategies to manage the delays (lines 13-16 algorithm 1) associated to anticipation are used to maintain musical coherence despite real-time modifications of generation parameters.

Beyond scheduling aspects detailed in the previous paragraph, this section presents Antescofo features allowing specification of high-level temporal structures of this model and also more generally of different kind of processes that can be involved in an improvised interactive music performance. Recent developments of the language integrate handling of dynamic duration, complex events specification and dynamic processes. This generalizes the notion of score following beyond triggering of an action or recognition of causal events. The score is no longer subject to linear rigidity of classical scores. It can be seen more as an interactive system where events, actions, durations, tempi and all the temporal structures can change dynamically. Such features make it an adequate environment for the temporal coordination of the processes that can be involved in Human-Computer Improvisation.

The whenever statement

The whenever statement launches actions conditionally on the occurrence of a signal. predicate is an arbitrary expression. Each time the variables of predicate are updated, the expression is re-evaluated. The whenever statement is a way to reduce and simplify the specification of the score particularly when actions have to be executed each time an event is detected. It also escapes the sequential nature of traditional scores. Actions of a whenever statement are not statically associated to an event of the performer but to the dynamic satisfaction of some predicate. They can be triggered as a result of a complex calculation, launched by external events, or any combinations of the above.

Patterns

The whenever structure is relevant when the user wants to define a reaction conditionally to the occurrence of an event. A logical event is specified thanks to a combination of variables. Complex events corresponding to a combination of atomic events with particular temporal constraints are however tedious to specify. Antescofo patterns make the definition of this kind of events concise and easy. A pattern is made of punctual events (EVENT) and of events with some duration (STATE). The example below shows how to define the complex event pattern::P, matching the following configuration: the variable $x is greater than a threshold equal to 10 during 0.5s. Then the variable is updated to 1 before one second is elapsed. This pattern can then be used in the specification of a whenever condition to assign a reaction to this event.

@pattern_def pattern::P { STATE $x where($x>10) during 0.5s before 1s EVENT $y where($y=1) } whenever(pattern::P) { actions... }

Processes

Processes are groups of actions dynamically instantiated. Unlike the other actions, the runtime structure associated to a process is not created during the loading of the score but at the time of the call, in accordance with its definition. Then, all the expressions involved in the process (durations, command names, attributes, etc.) may depend on parameters of the performance. ::delay("C4", 2.) NOTE D3 1 ::delay("D3", 1)

In the previous example, the process ::delay repeats twice the note that triggered it during the duration of this note. Processes are first-class values: for example, a process can be passed as an argument to a function or an other process. It can be recursively defined and various instances of a same process can be executed in parallel. Processes are quite adapted to the context of improvised music, and can be used for example as a library of parametrized musical phrases that are instantiated following the musical context.

Writing improvisation plans

The set of tools presented in this section enables to write improvisation plans defining different kinds of interactions. The schematic example in figure 4 shows an generic example of such a plan. In this context, the score of the musician is not completely defined and the inputs of the reactive module are not only extracted from Antescofo listening machine but can also be provided by external modules. Each state corresponds to an interaction mode between the performer and the system. Satisfaction of temporal patterns p1, p2 or p3 allows to switch between the different states s0, s1, s2 and s3. These patterns can for example be defined as temporal evolutions of some audio descriptors. s0 is associated to a classical phase of interaction of a score following system with electronic actions adapting to a sequence of predefined events. Reaching the end of the sequence leads to the beginning of the next part (s1) where the musician improvises with the generation model guided by a scenario chosen as a given harmonic progression, and a musical memory initialized with a chosen corpus. The part corresponding to s2 continues with the same scenario using the memory learned from the musician's performance during s1. Finally, s3 is a combination of predefined interactive mechanisms associating electronic reactions to unordered events.

CONCLUSION

This paper sketches an environment allowing the temporal management of human-computer improvisation. In this approach, improvisation plans with different kinds of interactions at multiple time-scales were considered ranging from completely determined to unordered events and reactions. The proposed environment integrates a model of generation for the improvisation in the high-level structure provided by a language for the specification and coordination of electronic actions depending on defined events. This coupling of high-level dynamic language with an improvisation model (generative processes), which is at the core of the prototype presented in this paper, enhances the coupling between interactive computer music and improvised practices. Researches on those lines could address complex problems with simple and elegant solutions useful for both music planning and improvised live performance.

  Copyright: c 2014 Jérôme Nika et al. This is an open-access article distributed under the terms of the Creative Commons Attribution 3.0 Unported License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

  a b a b c a b c c b a c b ... c c a b a b c a b a c b a c a b c c b a ...

  B' C A" B" C" C'" B'" A'" ...

Figure 1 .

 1 Figure 1. Improvising by articulating an indexed memory and a scenario: two navigation phases (1-2 and 3-4).

Figure 2 .

 2 Figure 2. The generation process within a real-time architecture.

3 CurrentTimePlayed ← false 4 if 6 CurrentTimePlayed ← true 7 16 CurrentTimePlayed ← true 17 Buffer[Idx] ← Content 18 E

 3467161718 Initial state: Buffer (storing the musical elements to play) = ∅ E (index of the first empty position in the buffer) = 0 CurrentTimePlayed = false 1 Whenever T updated do 2 Learn inputs from [T-1,T[ labeled by S[T-1] in M Buffer[T] then 5 Play(Buffer[T]) Whenever E -T < minimum imposed anticipation do 8 T' ← max(T, E) 9 Generate(T', ST') 10 Whenever modif. of parameters or S affecting date T' ≥ T do 11 Generate(T', ST') 12 Whenever RecvdElem = (Idx,Content) received do 13 if (Idx = T) & (¬ CurrentTimePlayed) then 14 Delay ← Date(update T) -Date(RecvdElem) 15 Play(Content, Delay) ← max(Idx+1, E)

Figure 3 .

 3 Figure 3. Processes launched at time T of the performance, reaction to a modification affecting time T ′ ≥ T .

  @proc_def ::delay($pitch, $d) { $d/3 loop $d/

Figure 4 .

 4 Figure 4. Schematic example of an improvisation plan.

These navigation phases are successive steps in the algorithmic process producing the improvisation, but they do not correspond in general to distinct musical "phrases".

Acknowledgments

The authors would like to thank Jean Bresson, Arshia Cont and Gérard Assayag for fruitful discussions. This work is supported in part by ANR projects: IMPROTECH ANR-09-SSOC-068 and INEDIT ANR-2012-CORD-009-03.