Javier Luis Cánovas
email: javier.canovas@inria.fr

Izquierdo Atlanmod

Jordi Cabot
email: jcabot@uoc.edu

Enabling the Definition and Enforcement of Governance Rules in Open Source Systems

Governance rules in software development projects help to prioritize and manage their development tasks, and contribute to the long-term sustainability of the project by clarifying how core and external contributors should collaborate in order to advance the project during its whole lifespan. Despite their importance, specially in Open Source Software (OSS) projects, these rules are usually implicit or scattered in the project documentation/tools (e.g., tracking-systems or forums), hampering the correct understanding of the development process. We propose to enable the explicit definition and enforcement of governance rules for OSS projects. We believe this brings several important benefits, including improvements in the transparency of the process, its traceability and the semi-automation of the governance itself. Our approach has been implemented on top of Mylyn, a project-management Eclipse plug-in supporting most popular tracking-systems.

I. INTRODUCTION

The development of large-scale software is a long-life process which has to cope with a huge number of development tasks consisting of either implementing new issues or fixing bugs [START_REF] Aranda | The Secret Life of Bugs: Going Past the Errors and Omissions in Software Repositories[END_REF]. Effective and precise prioritization of these tasks is key for the success of the project.

With this purpose, each project defines and applies its own set of governance rules, that is, a set of instructions which describe how to contribute to the project and how decisions regarding the acceptance/rejection of such contributions are going to be made. For instance, rules can be as simple as team leaders decide the tasks to do or more complex as the task to be done will be the one most voted by the developers participating in the project. Governance rules enable the coordination of developers in order to advance the project during its whole lifespan and, more importantly, their evolution allows the project to adopt societal changes on the way people want to collaborate, thus promoting the sustainability of the development process.

Despite their importance, in practice, governance rules are hardly ever explicitly defined, specially in the context of Open Source Systems (OSS), where it is hard to find an explicit system-level design, a project plan or list of deliverables [START_REF] Mockus | Two Case Studies of Open Source Software Development: Apache and Mozilla[END_REF], [START_REF] Shibuya | Understanding the Process of Participating in Open Source Communities[END_REF], [START_REF] Singh | Users of Open Source Software: How do They Get Help?[END_REF] (e.g., browsing issue and bug trackers for any project quickly uncovers "forgotten" requests from several years ago where new users periodically comment on trying to guess if that feature/bug has been implemented/fixed or not, if it will be, and how they can help to push it up on the priority list). Moreover, the support for enforcing such governance rules is even more limited. This hampers and can even scare away the participation of new users/developers who must invest some time understanding the "culture" of the project.

To alleviate this situation, mechanisms to facilitate the communication and assignment of work are considered crucial [START_REF] Mockus | A Case Study of Open Source Software Development: the Apache Server[END_REF], [START_REF] Bertram | Communication, Collaboration, and Bugs: the Social Nature of Issue Tracking in Small, Collocated Teams[END_REF]. Tracking systems (i.e., bug-tracking such as Bugzilla 1and issue-tracking systems such as Mantis2 ) are broadly used to manage the tasks to be performed. Other collaborative tools such as mailing-lists or forums are also used to coordinate the developers involved in the project. While these tools provide a convenient compartmentalization of work and effective means of communication, they fall short in providing adequate support for specifying and enforcing governance rules (e.g., automatically prioritizing tasks based on votes, easy tracking of decisions made in the project, etc.).

Therefore, we believe the explicit definition of governance rules along with the corresponding infrastructure to help developers follow them would have several benefits, including improvements in the transparency of the decision-making process (promoting the understanding of the project evolution), traceability (being able to track why a decision was made and who decided it) and the automation of the governance process (e.g., liberating developers from having to be aware and follow the rules manually, minimizing the risk of inconsistent behaviour in the evolution of the project).

This paper makes the following original contributions:

• We report on the results of a survey conducted to assess the importance of making explicit the governance rules. The survey revealed that, while contributing is usually easy, knowing how such contributions are going to the treated is hard. We confirmed that a proper definition of the project governance would help to understand how it evolves and therefore encourage people to contribute. • We propose a new Domain-Specific Language (DSL) to let project managers easily define the governance rules of their projects, thus promoting sustainability. The DSL is defined based on our analysis of the (implicit) rules used in the governance of a set of OSS development projects. • We provide a collaborative infrastructure to enforce those rules as part of the project evolution, thus promoting traceabiliy and automation of the process. Our approach has been implemented on top of Mylyn, a project management plugin for Eclipse with connectors for most popular tracking systems. Thanks to these connectors our approach can be used together with the existing tracking systems already in place in OSS projects. The rest of the paper is structured as follows. Section II reports on the results of a survey confirming the importance of making explicit the governance rules of OSS projects. Section III analyzes the governance rules used in several OSS projects. Our DSL to define governance rules is described in Section IV while the infrastructure needed to apply them is presented in Section V. Section VI presents an illustrative case study. Finally, Section VII shows the related work and Section VIII finalizes the paper.

II. MAKING THE GOVERNANCE RULES EXPLICIT

To assess the importance of having explicit governance rules in OSS projects we conducted a survey. Our aim is to answer the following research questions: (RQ1) How hard is it to contribute to OSS projects?, and (RQ2) is it feasible to make explicit the governance rules? if so, is it useful? To promote the participation, the survey was announced and distributed online, being freely accesible and targeting any developer willing to participate. To maximize the number of responses, we kept the number of questions as reduced as possible. The survey comprised questions on three different aspects:

QA User profile, including questions to characterize the survey participant according to his/her experience contributing to OSS projects, the role (i.e., project leader, contributor, end-user, no expertise or bad experience), and the number of projects contributed (if any). QB Understanding of the contribution process, which analyzes how difficult it is to understand how to contribute (e.g., providing source code, notifying bugs, proposing new features, etc.) to the project. This category comprised questions to assess the difficulty level (ranking from 1 -easy, to 5 -hard) of the main contribution activities (i.e., how difficult was to propose a change request, a bug or a patch) and understanding the governance rules applied in the process (i.e., how difficult was to know when a proposal was accepted or whether/when it will be included in the next release). QC Governance rule definition, with questions to analyze the opinion regarding the feasibility and usefulness of making governance rules explicit. The survey was promoted through social media (i.e., twitter, facebook, etc.) and in one of the author's blog 3 . It was available for one month and answered by 51 people that had the option to remain anonymous if they wished 4 . All participants answered the full set of questions. A summary of the results is shown in Figure 1.

3 http://modeling-languages.com/dont-contribute-open-source-projects 4 The results are available at http://goo.gl/tvzYz9 Figure 1a depicts the main results for the questions profiling the surveyed developers (i.e., QA questions). Note that respondents who tried but failed to contribute (i.e., QA1) sometimes considered their attempt as contribution (i.e., QA2), which will influence the remainder of the survey. As can be seen, the great majority of the respondents are contributors (see QA1 results) who have participated in 1 to 5 projects (see QA2 results).

Figure 1b shows the results regarding the difficulty of understanding the contribution process and addresses RQ1. The results reveal that in average contribution activities are easy to understand: proposing a change request receives an average value of 2.37 (see QB1 results), notifying a bug receives an average value of 1.80 (see QB2 results) and sending a patch receives an average value of 2.07 (see QB3 results). However, the results regarding the understanding of the application of governance rules get worse evaluations in average. Thus, knowing the status of a proposal (i.e., QB4) or its inclusion in the next release (i.e., QB5) receive an average value of 3.15 and 3.72, respectively.

Figure 1c shows the results with regard to the governance rule definition, thus answering RQ2. Respondants believe that most governance rules can be written down fully or partially (see QC1 results) and, in those cases where it is possible, they also acknowledged its positive impact to encourage new contributors to participate (see QC2 results) in the project. Furthermore, the results also show that a tool enforcing governance rules would be welcome in the context of OSS projects (see QC3 results), though with less support, which may indicate reluctance to (semi)automate the development process.

Our survey also included an open question to gather opinions about how to make the understanding of the governance easier. Among the answers, it is remarkable that a couple of developers noted that it is a common problem to make the effort of sending patches and then realize that they are delayed or ignored with no clear reason (e.g., one of the answers was I really wanted to work on a project and fixed few bugs. They answered immediately that they will use it, but it then took more than a year until they really did). There were also other answers commenting about the need of better mechanisms to facilitate the understanding of how the project is governed, such as better user interfaces (e.g., one for the end-user (simple, elegant, clear) and another for developers/maintainers with full information), delegating a person to specifically care about first-time contributions or ranking the projects according to their friendliness. These answers reveal that developers are willing to contribute but the effort to make is still too high for some of them.

Although the results of our survey may not represent the universe of all developers in OSS projects, we believe that they are illustrative enough to motivate the need of explicitly defining the governance rules behind OSS projects.

III. HOW OSS PROJECTS ARE GOVERNED

While the survey presented in the previous section shown the need of explicitly defining the governance rules in OSS projects, in this section we analyze eight well-known OSS projects in order to empirically study how existing projecs are governed. This information will help us to further confirm the survey results and to know better this domain in order to develop our solution as described in the next sections.

Most large OSS projects are organized in terms of tasks (either feature requests or bugs) that are solved by means of patches (implementing new features in response to the requests or correcting the bugs) which at some point can be selected to be part of the next software release. Figure 2 summarizes this workflow. The workflow includes three main decision points, namely: (1) task selection, (2) patch review and (3) release selection. Decisions at each point are taken based on the governance rules defined for the project. We have studied eight OSS projects where external contributions are welcome (i.e., Android5 , GNOME 6 , Apache web server 7 , Mozilla8 , Python9 , Moodle10 , EMF11 , MoDisco 12 ). Each project was analyzed according to nine dimensions targeting three main viewpoints, specifically: organizational viewpoint, which studies how developers are organized (mainly hierarchically or not) (organization dimension), the main communication means (coordination and tracking system dimensions) and who can participate (participation dimension); development process viewpoint, which assesses how the review process is done in each one of the three main decision points (task review, patch review and release decision dimensions); and governance rule definition viewpoint, which studies where the governance rules are usually defined and who is involved (Rules Def. / App. and Roles dimensions). We believe these dimensions cover all elements that are part of the governance of an OSS project. Table I shows a summary of the data we gathered. Next we describe the results in more detail.

• Organization. The organization followed by a project summarizes its main development philosophy. The vast majority of analyzed projects follow a hierarchical scheme, meaning that there exist several hierarchical levels of user groups collaborating in the development (e.g., leaders, contributors, users, etc.), where each group/role has different permissions and tasks. A good example is the Android project, where each role has assigned a particular function in the process (e.g., approvers approve tasks, verifiers review patches, etc.) supporting the project leader. On the other hand, Apache differs from the others by using a meritocracy organization where users can gain merits as they contribute to the project. • Communication mechanisms. This feature includes the main tools used to help users to collaborate during the development process. As can be seen, mailing-lists and forums are the most popular tools. Note that even though these tools are useful to keep in touch with the rest of developers, they are normally used to enforce some governance rules as well, which goes beyond their original purpose. This is the case of Apache, which uses a mailing-list to vote which feature requests/bugs should be implemented/fixed next. • Tracking system. The managament of tasks is performed by tracking systems, Bugzilla being the most popular one. Interestingly enough, tracking systems are also used as a forum to discuss possibles tasks which are not mature enough to be considered as real issues. For instance, in the GNOME project, some tasks 13 are used to openly discuss possible changes in the development strategy. • Participation. In general, in OSS, anyone is able to take part in the development, i.e., it is not necessary to be an official developer to inform new feature requests or bugs. • Task review. Once a task (i.e., feature request/bug) is notified, it can be reviewed to be accepted or rejected. Except for Python, where all the tasks are accepted and only reviewed if they include the corresponding patch, the rest of the projects have a decision process to accept or 13 http://felipec.wordpress.com/2011/09/23/no-gnome-doesnt-want-userfeedback-how-i-argued-in-favor-of-voting-in-bugzilla-and-got-banned-as-aresult reject the task proposal. In general, the decision process is made by either the leader (e.g., component leaders in Moodle) or by unanimous agreement if there are several leaders (e.g., in big Eclipse-based projects such as EMF).

• Patch review. Tasks may come with the corresponding patch implementing the improvement (if it is a feature request) or the fix (if it is a bug). Before incorporating the patch into the product, it is possible to perform a revision and test the quality of the patch. All the studied projects include a review process which analyzes the patch and eventually decides its acceptance or rejection. • Release Decision. As the tasks and the corresponding patches are accepted, new software product releases have to be published. In the analyzed projects, the decision of selecting when to perform the release and which tasks should be incorporated is normally taken by the product/component leader or by unanimous agreement when there are several leaders. The only exception is the decision process for Apache, where a ballot takes place. • Governance rule definition and application. This feature shows how governance rules are defined and applied.

In general, none of the projects explictly defines these rules, and to make things worse, the result of their application is scattered throughout the management systems (i.e., track systems or mailing-lists). • Roles. The group of users collaborating in the development are classified according to a set of roles. All the analyzed projects include both the role of developer (a.k.a. contributor/committer), who can commit changes into the source code repository of the software projecs, and the corresponding role for leaders (a.k.a owners/chairs). In summary, most projects are hierarchical where contributors are driven by a leader (or a set of leaders) who normally decides which tasks should be completed first. Patches are normally reviewed and tested by contributors while the product release is decided by a leader group as well. Thus, the resulting governance rules are mainly controlled by the group of leaders, who can decide how the software product should evolve. When there is a group of leaders, the decision is normally made by unanimous agreement and normally using collaboration tools (e.g., email, mailing-lists or forums).

The development of Apache web server is the main exception. The project is governed by a voting-based decision rule where all contributors can decide which tasks should be accepted and which ones should be included in the final release. It is important to note that although anyone can vote, only the votes from contributors are binding, the rest are helpful to see the general opinion of the community. The project also establishes how the voting process should be performed. Thus, if the task involves changes in the source code, the voting should result in an unanimous agreement in order to make the change and at least three votes must be casted. Otherwise, if the change does not involve code, a majority of positives votes (and at least three) are required. Moreover, any negative vote must include a rationale, which can therefore help to solve the disagreement.

Interestingly enough, in all the analyzed projects it was not trivial for us to discover the governance rules being applied since the available information was scarce and normally scattered among the documentation of the project. In fact, some projects such as GNOME recommend to be patient since it can take a long time to become a contributor. Potential contributors are therefore required to observe existing mailing lists, conversations on IRC, etc., to discover the way of working in the project. This evidence confirms the results gathered in the survey presented in the previous section.

Moreover, the result of the application of these rules is directly updated in the tracking systems, where normally there is no traceability information that helps to clarify later on why that decision was taken nor the possible discussion threads (maybe taken place outside the tracking systems, e.g., by chat or email as it is the case for smaller projects such as MoDisco) among the leaders that led to that decision.

Clearly, making explicit the governance rules followed in a project could help the developer community to understand and enforce those rules as part of their daily development activities. Next sections describe our proposal to define and enforce governance rules.

IV. DEFINITION OF GOVERNANCE RULES

In order to define the set of governance rules for development tasks, we propose to use a new Domain-Specific Language (DSL) providing specialized constructs that facilitate the specification of decision rules to be followed during the management of development tasks. Our goal is to provide a simple but precise language to make explicit such rules, thus promoting the understanding of how the project is developed and eventually encouraging developers to contribute. Based on our validation, the language is expressive enough to cover typical governance scenarios; nevertheless it could be tailored to cover more complex situations. Furthermore, this opens the door to automatically enforce those rules as discussed later on.

A DSL is defined by three main elements [START_REF] Kleppe | Software Language Engineering: Creating Domain-Specific Languages Using Metamodels[END_REF]: abstract syntax, concrete syntax and semantics. The abstract syntax defines the main concepts of the language and their relationships, and also includes well-formedness rules constraining how to use them. The concrete syntax defines the language notation (textual, graphical or hybrid) and a translational approach is normally used to provide semantics.

Our DSL has been defined in the context of Model-Driven Engineering, thus we use metamodelling techniques [START_REF] Brambilla | Model-Driven Software Engineering in Practice[END_REF] to define the abstract syntax. Similar to grammars, metamodels restrict the possible structure of valid models for a DSL. More specifically, we have defined a governance metamodel to represent the concepts and relationships needed to specify governance rules. Governance models conforming to this metamodel (i.e., models that can be expressed as valid instances of this metamodel) represent specific sets of governance rules of software projects. As concrete syntax, we have opted for a textual language following a typical block-based structure. Thus, each instance of a metaclass is textually represented by its keyword and a block that contains the name and value of its attributes. Containment references are represented as nested blocks while non-containment references use an identifier to refer to the referred element. Both abstract and concrete syntaxes have been implemented in our prototype tool [START_REF]Governance Tool[END_REF].

The abstract syntax metamodel of the language is shown in Figure 3. The concepts represented in the metamodel cover all the governance aspects identified in our study of OSS projects. In particular, a development project (Project metaclass) includes a group of roles of users (roles reference), rules (rules reference) and deadlines (deadlines reference). A role has an identifier (id attribute in Role metaclass) and represents a group of people in the development community who can vote. Decision rules are applied to a particular type of collaborations (appliedTo attribute) according to their nature in the tracking system (i.e., task, patch or comment) and at a specific moment (stage attribute) of the process (i.e., task review, patch review and release). The scope of the rule can also be defined (queryFilter attribute) (e.g., only those tagged as high priority).

We have predefined several types of decision rules (included in the hierarchy with root Rule), which cover the cases analyzed before:

• Majority Rule. Under this rule (Majority metaclass) only those collaborations which have received a support over 50% will be selected. The way of counting votes may differ depending on who voted during the lifespan of the rule. Since different terminology is used to refer the several types of majority rules (e.g., plurality or relative majority used in North America is called simple majority in Europe), we will use the neutral term majority range to determine exactly how the votes should be counted. Thus, if the range is present, the majority is based on the votes of those participants presented during the voting time. Otherwise, a qualified range is based on the votes of those participants qualified to vote (having voted or not, where abstention means disagreement). A majority rule can also require a minimum number of votes to be triggered (minVotes attribute). As an example, a majority rule to be applied only to tasks, voted by the committers if they are presently available, with no need of minimum votes and with a deadline of seven days from the task creation date would be specified with our textual concrete syntax as: A different percentage for the majority can also be set. In this case the rule will be called ratio majority (RatioMajority metaclass) and the ratio value must be specified. For instance, this type of rule would allow implementing well-known majorities such as three-fifths or two-thirds, which may be required for changes on fundamental laws. As example of ratio majority, the following definition modifies the rule presented before to be ratio-based with a ratio of acceptance of 75% and to be voted only by the project leaders. • Leader-Driven Rule. When the decision of accepting a collaboration relies on a user playing the role of leader (e.g., component or project leader), a leader-driven rule (LeaderDriven metaclass) is followed. Thus, this decision rule relies on the leader of a collaboration to decide its acceptance. Next section describes how the leader is represented. The leader must also define a default rule (default reference) where to delegate the decision in case the leader is not available (i.e., the leader doesn't vote before the deadline) An example of leader-driven rule to be applied only to tasks, with a majority default rule to be applied when the leader does not make the decision and with a deadline of seven days from the task creation date would be (note that the myMajorityRule rule defined before is reused as default behavior):

Project myProject { Roles: Committers Deadlines: myDeadline : 7 days Rules: myMajorityRule : Majority { ... } myLeaderDrivenRule : LeaderDriven { applied to Task when TaskReview default myMajorityRule deadline myDeadline } }

• Phased Rule. This is a composite rule which allows applying several rules in a chained way. The rules are defined and applied in an ordered way (phases reference). Thus, a set of collaborations are selected according to the first rule, the selected ones are then voted again and filtered according to the second rule, and so on. An example of phased rule composed of two phases where the first one applies a majority among the committers and with a deadline of seven days from the task creation date, and the second phase, which has a deadline of seven days after the first phase has been done, applies Regarding the deadlines that trigger a decision rule, we have currently defined three covering deadlines based on: (1) time (Timer metaclass), (2) an OCL 14 condition to be fulfilled in the collaboration (Condition metaclass) (e.g., the change of a tag in the collaboration model) and (3) a set of users have voted (WaitUserVote metaclass).

A. Rule Generator

To facilitate the use of the DSL beyond the textual syntax we also provide a form-based generator to define governance rules (i.e., our DSL instances). Figure 4 shows a snapshot of the tool 15 where developers can configure the governance rule for their development process and generate both the English text and the DSL instance describing such rule.

Additionally, the tool creates a permanent link to help referring the governance rule from any project (i.e., the link automatically shows the rule in English and the DSL instance). We envision that projects may define a governance.md file where governance rules can be specified along with the corresponding permanent links. To start with, we are already using this approach in the development of our research projects 16 .

B. DSL validation

In order to validate our DSL, we circulated the form-based generator among a group of developers who have participated in the development of OSS projects. The group was composed of 7 developers, with the following main roles: 3 leaders, 2 contributors, and 2 end-users. All of them were participating actively in the corresponding software project. After they tested the generator, we asked them several questions to assess their opinion on the expressiveness of the DSL. In particular, we were interested in learning whether they had been able to specify all the rules governing the projects they were working on with our DSL.

The participants reported a proper coverage for representing governance rules used in their projects but asked for an extended support for (1) roles and (2) deadlines. It turned out that both aspects where already supported by the DSL but were simplified in the implementation of our generator.

Regarding the support for roles, it was required to support the definition of custom roles. This issue appeared since the form-based generator included a fixed number of roles (the language abstract syntax actually allows for any type of roles, cf. Role concept). This has been now incorporated into the current version of the generator (the one shown in this paper).

With regard to the support for deadlines, the participants asked for the ability to define deadlines based on metadata (e.g., if the priority metadata is high, the deadline will be shorter). This issue was supported by the language (Condition element allows developers to define deadlines according to a OCL-based condition) but, for the sake of the simplicity, we decided not to over-complicate the form-based generator. Thus in those cases where it is necessary to define a more specific deadline, developers should edit the resulting DSL definition to include the OCL expression V. ENFORCEMENT OF GOVERNANCE RULES While the DSL enables developers to represent and understand how the project is governed, some projects may also want to use the specification of the rules to automatically manage the project itself. In order to do that we would need to: [START_REF] Aranda | The Secret Life of Bugs: Going Past the Errors and Omissions in Software Repositories[END_REF] provide support for recording all information regarding the community interactions (e.g., proposals, votes, etc.), and (2) implement a decision engine that can use this information and the governance rules to make the corresponding decisions and update the project status accordingly.

Thus, additionally to our DSL, we provide the needed infrastructure to "execute" the DSL specifications so that, beyond improving the understanding of the project internal organization, they can also be enforced to support and guide the collaboration among the project participants. decision point. Given a set of tasks to be discussed (i.e., to accept them, accept a patch for them or include them in a reusers can vote for/against them (step 1), then a decision engine analyzes the votes according to the governances rules defined (e.g., total agreement, simple majority, etc.) (step 2) and, as a result, the status of the tasks is changed based on the decisions taken by the engine (step 3).

To record the group interactions we use the metamodel shown in Figure 6. A particular collaboration (Collaboration metaclass) is represented by an identifier (id attribute) and a rationale explaining the collaboration (rationale attribute). There are three types of collaboration elements (type attribute in Collaboration metaclass): tasks, which represent a request for a feature request or a bug; patches, which represent the solution for a task; and comments, which represent comments and annotations that users can make as a follow up of other collaboration elements. A collaboration element can also have some metadata information (metadata reference) and has a proposing user (isProposed reference) and a leader (leader reference). During the collaboration, a user (User metaclass) is identified by an identifier (id attribute) and belongs to a one or more roles (roles reference). Note also that, both, collaboration elements and users are linked to the tracking system (see Tracking System component) to be able to link these interactions with the status of the corresponding elements in the official project tracking system. The metamodel also allows representing users' votes (Vote metaclass) to express their agreement/disagreement with a collaboration (agreement attribute). A vote has a timestamp (timeStamp attribute) and a rationale (rationale attribute) explaining the reason for the positive/negative vote.

When the deadline for a governance rule passes, the decision engine receives the collaboration model as input and follows the rule instructions to process the data and take a decision. This process generates a new decision (Decision metaclass) and trace it back to the affected collaboration elements (isDecided reference). A decision can accept/reject a collaboration element (accepted attribute), includes a timestamp of the moment when the decision was made (timeStamp attribute) and refers to the rule applied (rule reference). A collaboration element has usually only a decision element assigned except when a phased rule is used, in this case the decisions for each phase and the final decision are also stored in the model.

The decision engine is provided as part of our prototype tool [START_REF]Governance Tool[END_REF], which has been implemented as an Eclipse plug-in, and takes care of also updating the tracking system based on the changes performed on the collaboration model. The tool has been implemented on top of Mylyn 17 , a project management plugin for the Eclipse platform with connectors for most popular tracking systems.

VI. CASE STUDY: APACHE

We have used our approach to model the decision process followed in the Apache project (where the choice of Apache was motivated by the fact that it has a more complex governance process than other analyzed projects). Our goal is twofold: (1) illustrating the use of our approach and (2) checking that our DSL is able to represent complex governance processes.

We first represent the governance rules used to select tasks to complete. As described before, there are two types of voting procedures in Apache depending on whether the task to work on involves source code changes or not. The DSL excerpt defining these Apache governance rules would be: to facilitate the discovery of existing governance rules in a project to later represent and manage them using our approach.

Our DSL can be related to process description and workflow languages ( [START_REF] Omg | Business Process Model and Notation (BPMN) Version 2.0[END_REF], [START_REF] Wise | Using Little-JIL to Coordinate Agents in Software Engineering[END_REF] among others), where process and decision paths can be defined. However, our approach focuses on the decision rules used to make collaborative decisions, an aspect usually not included in these languages.

Concrete methodologies for collaboration strategies have also been proposed. For instance, [START_REF] Duque | Integration of Collaboration and Interaction Analysis Mechanisms in a Concern-based Architecture for Groupware Systems[END_REF] and [START_REF] Luther | Redistributing Leadership in Online Creative Collaboration[END_REF] present approaches to support collaborative processes in groupware systems and online creative projects, respectively. However, they do not provide mechanisms to define and enforce the governance rules to apply in each project.

Collaboration has also been the focus on two other DSLs. The approach presented in [START_REF] Gallardo | Modeling Collaboration Protocols for Collaborative Modeling Tools: Experiences and Applications[END_REF] describes a DSL to represent synchronous collaboration workflows in modeling tools (e.g., the steps needed to create a class diagram when several users are collaborating). In [START_REF] Cánovas Izquierdo | Enabling the Collaborative Definition of DSMLs[END_REF], authors presented a DSL-based tool to record the collaboration interactions taken place during the development of a DSLs. Again, these approaches do not provide any support for the definition nor enforcement of the rules controlling such collaborations.

VIII. CONCLUSION

In this paper we have presented an approach that enables the explicit and precise definition of governance rules for a development project and, if desired, also its automatic enforcement. Our approach comprises a new DSL for specifying the rules, a collaboration infrastructure to record the interactions (and trace them back when necessary) and a decision engine to automatically update the task status according to the rules. An implementation of the approach has been made available in [START_REF]Governance Tool[END_REF]. Although our approach mainly targets the OSS community, in particular, those projects where any developer can freely contribute, we believe it can also be adapted to in-house and commercial development processes.

As further work, we would like to study how to address the limitations previously identified, including as well usability aspects, e.g., regarding the enforcement of the rules and the their presentation (i.e. concrete syntax) to end-users. Also, we are interested in extending our language to be able to specify other kinds of complementary rules like the ones governing the team organization (e.g., how the project participants can be promoted between the different roles) or providing fallback behavior to deal with potential undecidable cases. Adding privacy concerns is also under evaluation (some projects may require anonymity in the voting phase, or keep private some discussions to all people with less privileges). Additionally, we would like to mine existing software repositories to infer and study their governance rules, e.g., to see if the extracted rules correspond to the perception of project participants. Preliminary results suggest that a clear rule definition could correlate with more successful (in terms of number of contributions) projects. We believe this is also worth investigating further. Finally, a more ambitious empirical validation of the mid/long term benefits for OSS adopting our approach is also needed.

Fig. 2 .

 2 Fig.2. Workflow followed by a task and main decision points.

Fig. 3 .

 3 Fig. 3. Abstract syntax metamodel of our DSL to represent governance rules.

Fig. 4 .

 4 Fig. 4. Form-based generator to define governance rules. a leader-driven rule among the project leaders would be (note that myMajorityRule and myRatioRule are reused): Project myProject { Roles: Committers, ProjectLeader Deadlines: myDeadline : 7 days Rules: myMajorityRule : Majority { ... } myRatioRule : Ratio { ... } myPhasedRule : Phased { phases { myMajorityRule myRatioRule } } }

Figure 5

 5 illustrates how the automatic enforcement of the DSL rules would change the group dynamics at a particular

Fig. 6 . 3 Fig. 5 .

 635 Fig. 6. Metamodel to represent collaborations.

  QA2. How many OSS projects have you contributed to?

					QA1. Have you ever contributed to OSS projects?
		16%	17%		Yes, as project leader
		12%				Yes, as contributor
		12%		43%		Yes, as end-user No, I don't think I can
						No, I tried but I failed
			14%
		21%				More than 5
						1 to 5
		12%		53%		Only one
						Zero
							(a)
	QB. How hard is it to understand...
			Avg.	Avg.		Avg.		Avg.		Avg.
	100%	2.37		1.80		2.07		3.15		3.72
		90%
		80%
		70%
		60%
		50%
		40%
		30%
		20%
		10%
			QB1.	QB2.		QB3.		QB4.		QB5.
		...how to propose	...how to	...how to	...knowing the	...knowing the
		a change	notify		provide	contribution	inclusion
		request?	bug?		patch?		status?		in release?
		5 -Very hard	4 -Hard	3 -Normal	2 -Easy	1 -Very easy
							(b)
	QC1. Would it be feasible to write down how the project is governed?
				Yes				Partially		No
	0%	10%	20%	30%	40%	50%	60%	70%	80%	90%	100%
	QC2. If feasible, would these "governance rules" encourage new contributors?
					Yes					No
	0%	10%	20%	30%	40%	50%	60%	70%	80%	90%	100%
	QC3. If a tool could enforce these rules, would you like OSS projects to adopt it?
					Yes					No
	0%	10%	20%	30%	40%	50%	60%	70%	80%	90%	100%
							(c)
					Fig. 1. Results of the survey.

TABLE I COMPARISON

 I OF HOW OSS SYSTEMS ARE GOVERNED.

	Project	Organization	Coordination	Tracking system Participation	Task Review	Patch Review	Release Decision	Rules Def. / App.	Roles
										Contributor
	Android	Hierarchy	Forum	Git Gerrit	Anyone	Yes (Approver)	Yes (Verifier)	Yes (Project Lead)	Documentation / Track system	Developer Verifier Approver
										Project Lead
	GNOME	Hierarchy	IRC mailing-list	Bugzilla	Anyone	Yes	Yes (Bug Squad)	Yes	Documentation / Track System	Contributor Mentor
										User
	Apache Web Server	Meritocracy	Mailing-list	Bugzilla	Anyone	Yes (Voting)	Yes (Voting)	Yes (Voting)	Documentation / Mailing-list	Developer Committer PMC Member
										PMC Chair
	Mozilla	Hierarchy	Forum Mailing-list IRC	Bugzilla	Anyone	Yes (Module Owner)	Yes (Module Owner & Super-reviewers)	Yes (Designated Group)	Documentation / Track System & Mailing-list	User Committer Module Owner Super-reviewer
	Python	Hierarchy	Mailing-list IRC Blogs	Mercurial Roundup	Anyone	No	Yes (Reviewer)	Yes (Core Developer)	Documentation / Track System	Contributor Reviewer Core Developer
										Users
	Moodle	Hierarchy	Forum	Moodle tracker	Anyone	Yes (Component leads)	Yes (Developers)	Yes (Component Leads)	Documentation / Track System	Developers Component Leads Integrators Testers
										Manteiners
										User
	EMF	Hierarchy	Forum	Bugzilla	Anyone	Yes (Committer)	Yes (Committer)	Yes (Project Leader)	Documentation / Track System	Contributor Committer
										Project Leader
										User
	MoDisco	Hierarchy	Forum	Bugzilla	Anyone	Yes (Committer)	Yes (Committer)	Yes (Committers)	Documentation / Track System	Contributor Committer
										Project Leader

http://www.bugzilla.org/

http://www.mantisbt.org/

http://www.android.com

https://www.gnome.org

https:/www.apache.org

https://www.mozilla.org

https://www.python.org

https://moodle.org

https://www.eclipse.org/emf

https://www.eclipse.org/modisco

http://www.omg.org/spec/OCL

Available at http://goo.gl/Fq79Wv

For instance, in http://goo.gl/H8MMSX

The example defines four roles and two rules called codeRule and noCodeRule. The former is a ratio majority rule which is applied to those tasks including the tag code (i.e., tasks involving changes in the code). All people belonging to the roles linked to the rule (see tag people) and presently available (see tag range) can vote. It is required a ratio of agreement of 100% (i.e., meaning that everybody has to agree) and at least three votes. Finally, the rule defines a deadline of two days, although the precise length is not specified in the project documentation. On the other hand, noCodeRule is a majority rule which is applied to those tasks not including the tag code. Like the previous rule, it is required at least three votes to make a positive decision and the deadline is two days after the creation of the task.

To illustrate the application of the previous rules, Figure 7 shows a possible collaboration model for a scenario where developers should take a decision about two task proposals with identifier task1 and task2. The former includes the tag code while the latter does not. For the sake of the clarity and conciseness, the rationale and timeStamp attributes have been removed in the Figure . As can be seen, after voting, although the first task has received more than three votes, it it is rejected because there is one negative vote. On the other hand, the second task is accepted because, although there is also a negative vote, the majority agrees with the change.

Note that instead of the current process (based on mail communications and manual counting of the votes) our approach (and tool support) could automatically take the decisions based on the rules and the interactions taking place between the developers. Moreover, both the collaboration and decisions are stored along with the element decided (i.e., the task status change), thus avoiding scattering information along the project management tools (i.e., the mailing-list in this case) and improving the sustainability and traceability of the process.

VII. RELATED WORK

The study of how people coordinate to develop a software system has been a research topic for a long time [START_REF] Herbsleb | Splitting the Organization and Integrating the Code: Conway's Law Revisited[END_REF], [START_REF] Kraut | Coordination in Software Development[END_REF], [START_REF] Parnas | On the Criteria to be Used in Decomposing Systems into Modules[END_REF], [START_REF] Crowston | Coordination of Free/Libre Open Source Software Development[END_REF], [START_REF] Markus | The Governance of Free/Open Source Software Projects: Monolithic, Multidimensional, or Configurational?[END_REF], including the broader topic of IT governance [START_REF] Chulani | Software Development Governance and Its Concerns[END_REF], [START_REF] Ramasubbu | Towards Governance Schemes for Distributed Software Development Projects[END_REF], [START_REF] Van Grembergen | Strategies for Information Technology Governance[END_REF], [START_REF] Webb | Attempting to Define IT Governance: Wisdom or Folly?[END_REF]. However, to the best of our knowledge, little attention has been paid to the precise definition and support for the governance rules in (OSS) projects.

The work presented in [START_REF] Rigby | Understanding Broadcast Based Peer Review on Open Source Software Projects[END_REF] analyzes how broadcast based peer review influences OSS development processes. Developer characteristics such as their expertise or behaviour are studied to analyze how they may impact in the development task selection and decision making. They report that such behavior can lead to frustration in newcomer contributions who do not understand the development process. Unlike this work, ours tries to explicitly define how decisions are made to help anyone to understand how the project is governed. Some works report on concrete case studies. For instance, [START_REF] Aranda | The Secret Life of Bugs: Going Past the Errors and Omissions in Software Repositories[END_REF] reports on the coordination activities performed to solve bugs (e.g., how bugs are detected and closed, means used to coordinate the work, etc.). In [START_REF] Guzzi | Communication in Open Source Software Development Mailing Lists[END_REF] authors present how developers use mailing lists during the development of FLOSS systems (e.g., which are the main topics discussed or the level or participation of the different user roles).

Other approaches focus on leveraging collaboration information obtained by mining software repositories to infer coordination relationships and structures. The work presented in [START_REF] Bird | Latent Social Structure in Open Source Projects Categories and Subject Descriptors[END_REF] describes an approach to discover potential social structures from the threads created in the mailing list of the project. In [START_REF] Heller | Visualizing Collaboration and Influence in the Open-Source Software Community[END_REF] visualization techniques are applied to easily discover communication patterns from Github repository metadata (e.g., the effect of geographic distance among developers, influence among cities, etc.). The tool called CrowdWeaver is presented in [START_REF] Kittur | CrowdWeaver: Visually Managing Complex Crowd Work[END_REF], which allows coping with the complexity of managing crowdsourced projects. These tools could be adapted


Olivier Cardin
email: olivier.cardin@irccyn.ec-nantes.fr

Nasser Mebarki

Guillaume Pinot

A study of the robustness of the group scheduling method using an emulation of a complex FMS

Keywords: Scheduling, Robustness, Flexibility, Group scheduling, Proactive-reactive scheduling

A study of the robustness of the group scheduling method using an emulation of a complex FMS

Introduction

The most classical scheduling situation is the static scheduling, also called predictive scheduling. In this contextthe variables, theconstraints, the environment, all the data are considered as known. Then, the scheduling problem can be solved using combinatorial optimization methods, either exact methods such as linear programming, branch and bound methods, or heuristic methods [START_REF] Pinedo | Scheduling: Theory, Algorithms, and Systems[END_REF].This phase is done off-line.

The problem is that manufacturing systems are not so deterministic. They present a lot of uncertainties and randomness, e.g., the breakdown of a machine, late material, new orders to proceed immediately, etc. During the execution of the schedule, it is frequently necessary to repair the schedule while preserving the solution's quality. This phase is done on-line and is called reactive scheduling or predictive-reactive scheduling since the reactive phase is based on a schedule computed during the predictive phase. When the schedule in progress can no longer be repaired, it is necessary to set a new predictive schedule.

Moreover, the model used to generate a schedule during the predictive phase can be more or less precise in regards with the real system (e.g. operating times considered as random, transfer times considered as negligible, etc.). [START_REF] Roy | Main sources of inacurratedetermination, uncertainty andimprecision in decisionmodels[END_REF] talks about "just about or ignorance areas that affect the modeling of a problem".

To cope with these drawbacks, one can use real-time control methods [START_REF] Chan | The State of the Art in Simulation Study on FMS Scheduling: A Comprehensive Survey[END_REF]. These kind of methods do not make any plan and builds the schedule dynamically. Generally, these methods use priority rules which determine for each resource of the shop the next operation to proceed among the waiting operations in the resource's queue. These methods consider the real-state of the shop, so hazardous phenomena can be effectively taken into account when they occur. As these methods deal with the real-state of the system, they are called reactive methods. The major drawback of the reactive methods is that their performance is generally poor.

Very few methods try to combine the advantages of both predictive and reactive methods. The proposed methods rely essentially on the introduction of slacks during the predictive phase in order to facilitate re-scheduling during the reactive phase. The idea is to introduce flexibility during the predictive phase in order to obtain a robust schedule, enabling to absorb the perturbations during its execution.This is called proactive scheduling (Herroelen and Leus, 2004;[START_REF] Van De Vonder | A classification of predictive-reactive project scheduling procedures[END_REF]. One of the most known proactivemethods in project scheduling is the critical chain method used in several project management pieces of software (Goldrath, 1997). The method relies on the introduction of slacks on the operations of the critical path in order to absorb the delays. Another proactive method is the Just In Case Scheduling method [START_REF] Swanson | Just-In-Case Scheduling[END_REF]. This method identifies the probable critical delays and for each of them an alternative scheduling is proposed.Other methods, using fuzzy logic, try to capture the uncertainties in the scheduling data. [START_REF] Caprihan | A fuzzy dispatching strategy fordue-date scheduling of FMSs with information delays[END_REF] have added fuzzy criteria on priority rules such as Work In Next Queue (WINQ) and Number In Next Queue (NINQ). Domingos and Polianto(2003) have proposed a procedure for on-line scheduling where decisions are based on fuzzy logic.

In this paper, we focus on the group scheduling method which is one of the most studied proactivereactive methods. This method is very interesting because it favors the cooperation between human and machine to address the uncertainties of both the system (i.e., randomness) and the model (i.e., lack of precision). This is done by defining a partial order of the operations on each machine, permitting the decision maker to complete the scheduling decisions according to his preferences and the real state of the shop. For this, the group scheduling method builds scheduling solutions that integrate sequential flexibility; moreover the method guarantees a minimal quality corresponding to the worst case. Thus, this method brings flexibility and enables to choose in real-time the operation (among a group of permutable operations) that fits best to the real state of the system However, group scheduling has a major drawback: when order groups are very large, the flexibility added to the schedule is bigger but the cycle times will be longer.

Group scheduling was first introduced in Erschler&Roubellat (1989). This method has been widely studied in the last twenty years, in particular in Erschler&Roubellat (1989), Billaut&Roubellat (1996), [START_REF] Wu | A graph-theoretic decomposition of the job shop scheduling problem to achieve scheduling robustness[END_REF] and [START_REF] Artigues | Maximization of solution flexibility for robust shop scheduling[END_REF].The flexibility added to the schedule should enable the method to be robust, i.e. the method should absorb uncertainties, randomness and lack of precision of the model. Only two precedent studies have tried to verify this supposed property of the group scheduling method. [START_REF] Wu | A graph-theoretic decomposition of the job shop scheduling problem to achieve scheduling robustness[END_REF] study the impact of disturbed processing times on the objective of weighted sum of tardiness in comparison with static and dynamic heuristics. [START_REF] Esswein | Un apport de flexibilité séquentielle pour l'ordonnancement robuste[END_REF] studies the impact of disturbed processing times, due dates and release dates on a one machine problem and compares its results with a static heuristic method.

Although these two studies show the capacity of group scheduling to be robust, they are made on simple and theoretical models with simplified assumptions.

This paper presents a new study to evaluate the capacity of group scheduling method to absorb uncertainties. Contrarily to previous studies done with the groupscheduling method, this study has been conducted on an emulation of a real flexible manufacturing system.As stated by Liu and MacCarthy(1996) a Flexible Manufacturing System (FMS) is an integrated system composed of automated workstations such as computer numerically controlled (CNC) machines with tool changing capability, a material handling and storage system such as automated guided vehicles or conveyors, and a computer control system which controls the operations of the whole system. It is frequently observed in the scheduling literature that transfer times are purely and simply ignored [START_REF] Pinot | Coopération homme-machine pour l'ordonnancement sous incertitudes[END_REF]. To evaluate the robustness of group scheduling in regards with uncertainties, we conducted experiments on a real FMS to test the effect of the non-consideration of transfer times in a predictive schedule. In order to have results on a large time horizon, experiments are made on an emulation of the real system and not directly on the real system.

The rest of the paper is organized as follows: first, the groupscheduling method is presented, second, the capacity of the group schedulingmethod to handle uncertainties are discussed, third, the different experiments made are presented, and finally the results, very promising, are discussed. [START_REF] Van De Vonder | A classification of predictive-reactive project scheduling procedures[END_REF]propose a classification of scheduling methods under uncertainties. Their classification relies on the way uncertainties are taken into account. From this, they identity three major categories: proactive methods, reactive methods and proactive-reactive methods.

Group scheduling

A proactive method is a method where flexibility is added in a predictive model in order to deal with the uncertainties when they occur. Its main advantage is that it permits the computation of an optimal solution of the schedule. The problem of this kind of methods is that it deals with a prediction of the system and not with the real state of the shop.

With reactive methods, decisions are taken considering the real events of the shop. So, these methods are really taking into account the uncertain nature of manufacturing systems. They are usually called dynamic methods because they build dynamically the schedule as one goes along the events in the system. Their main advantage is that they deal with the real-state of the shop but they may give poor solutions for the schedule.

Proactive-reactive methods deal with a static schedule computed by a predictive method during a first phase of the schedule called the predictive phase. Then, in a second phase re-schedulings are done in order to take into account the real-state of the shop. This second phase is called the reactive phase where the schedule is adjusted to the uncertainties which occur in the system. Thus, these kinds of approaches are very interesting because they try to use the benefits of both predictive and reactive methods. [START_REF] Bel | Approche simulatoire[END_REF] describe different proactive-reactive methods.

One the most powerful and studied proactive-reactive methods is the group scheduling method. It is also one of the only proactive-reactive methods to be implemented in an industrialscheduling software named ORDOSoftware [START_REF] Roubellat | Ordonnancement d'atelier en temps réel : d'ORABAID à ORDO[END_REF].

The group scheduling method was first introduced in [START_REF] Erschler | An approach for real time scheduling for activities with time and resource constraints[END_REF]. The goal of this method is to provide a sequential flexibility during the execution of the schedule and to guarantee a minimal quality corresponding to the worst case. This method has been developed in the last twenty years, in particular in [START_REF] Erschler | An approach for real time scheduling for activities with time and resource constraints[END_REF], [START_REF] Billaut | A new method for workshop real-time scheduling[END_REF], [START_REF] Wu | A graph-theoretic decomposition of the job shop scheduling problem to achieve scheduling robustness[END_REF], [START_REF] Artigues | Maximization of solution flexibility for robust shop scheduling[END_REF]. A full theoretical description of the method is available in [START_REF] Artigues | Maximization of solution flexibility for robust shop scheduling[END_REF]. Let us describe the method and for this introduce some notations: in the rest of this article, the index i will be used for the operations and the index l will be used for the resources.

A group of permutable operations is a set of operations to be performed on a given resource M l in an arbitrary order. It is named g l,k . The group containing the operation O i is denoted by g(i). The index k will be used for the sequence number of a group.

A group sequence is defined as a sequence of v l groups (of permutable operations) on each machine M l : g l,1 , …, g l,vl , performed in this particular order. On a given machine, the group after (resp. before)

g(i) is denoted by g + (i) (resp. g -(i)).
A group sequence is feasible if for each group, all the permutations among all the operations of the same group give a feasible schedule (i.e. a schedule which satisfies all the constraints of the problem). As a matter of fact, a group sequence describes a set of valid schedules, without enumerating them. The quality of a group sequence is expressed in the same way as that of a classical schedule. It is measured as the quality of the worst semi-active schedule found in the group sequence, as defined in [START_REF] Artigues | Maximization of solution flexibility for robust shop scheduling[END_REF], where a semi-active schedule is a feasible schedule in which no local left-shift of an operation leads to another feasible schedule.

To illustrate these definitions, let us study an example. Table 1. A jobshop problem Figure 1.A group sequence solving the problem described in Table 1.

Table 1 presents a job shop problem with three machines and three jobs, while Figure 1 presents a feasible group sequence solving this problem. This group sequence is made of seven groups: two groups of two operations and five groups of one operation. This group sequence describes four different semi-active schedules shown in Figure 1. Note that these schedules do not always have the same makespan: the best case quality is with Cmax = 10 and the worst case quality is with Cmax = 17. The execution of a group sequence consists in choosing a particular schedule among the different possibilities described by the group sequence. It can be seen as a sequence of decisions: each decision consists in choosing an operation to execute in a group when this group is composed of two or more operations. For instance, for the group sequence described on Figure 1, there are two decisions to be taken: on M 1 , at the beginning of the scheduling, either operation O 1 or O 8 has to be executed. Let us suppose the decision taken is to schedule O 1 first. On M 3 , after the execution of O 7 , there is another decision to be taken: scheduling operation O 3 or O 5 first. If the decision is to execute O 5 first, the first schedule of Figure 2 is realized.

Group scheduling has an interesting property: the quality of a group sequence in the worst case can be computed in polynomial time for minmax regular objective functions like makespan or maximum lateness (see (Artigueset al., 2005) for the description of the algorithm). Thus, it is possible to compute the worst case quality for large scheduling problems. Consequently, this method can be used to compute the worst case quality in real time during the execution of the schedule. Due to this property, it is possible to use group scheduling in a decision support system in real time during the execution of the scheduling process.

To improve the performance of the group scheduling method, [START_REF] Pinot | Coopération homme-machine pour l'ordonnancement sous incertitudes[END_REF]), Riezeboset al. (2010) propose a complete study of the best case quality in a group schedule. The best case evaluation of a group schedule can be used during the predictive phase as well as during the reactive phase. During the predictive phase, the best possible performance of the schedule along with its worst case evaluation give the range of all possible performances of the future schedule. During the reactive phase, it can be used to assess possible decisions: one can know the best quality obtained if an operation is executed first, thus it allows better performance for the execution of the overall schedule.

The group scheduling method enables the description of a set of schedules in an implicit manner (i.e.,without enumerating the schedules). Actually, as it proposes a group of permutable operations, one can choose, during the reactive phase, inside a group the operation that best fits the real state of the system. For that, [START_REF] Thomas | Aide à la décision pour l'ordonnancement d'atelier en temps réel[END_REF] proposes an indicator called the sequential free margin which is a free margin adapted to group scheduling. The sequential free margin of a given operation represents the maximum tardiness that can be tolerated to guarantee no late jobs in every schedule described by the group sequence. This margin gives the ability to monitor the group sequence in real time: if the sequential free margin becomes negative, then some schedules described by the group sequence have late jobs. Such a margin is a very useful tool to take proper decisions and monitor the quality of the group sequence.

Robustness and group scheduling

A robust schedule can generally be defined as a schedule where perturbations are easily absorbed [START_REF] Billaut | Introduction[END_REF]. Thus, there is an association between flexibility and robustness, adding flexibility to a model is the way to have a robust schedule.

The goal of group scheduling is to propose sequential flexibility during the reactive phase of scheduling. This flexibility should improve the robustness of the method. Two studies evaluate the robustness provided by group scheduling: [START_REF] Esswein | Un apport de flexibilité séquentielle pour l'ordonnancement robuste[END_REF] and [START_REF] Wu | A graph-theoretic decomposition of the job shop scheduling problem to achieve scheduling robustness[END_REF]. [START_REF] Esswein | Un apport de flexibilité séquentielle pour l'ordonnancement robuste[END_REF] formulates the predictive phase as a bi-objective problem: the first objective is the minimization of a regular objective (e.g., the makespan or the maximum lateness) in the worst case and the second is the maximization of the flexibility. The flexibility is expressed as a percentage according to the number of groups. A group sequence with a flexibility of 0% is a group sequence with one group per operation, and a group sequence with a flexibility of 100% is a group schedule with one group per machine. This flexibility represents the number of decisions to be effectively taken divided by the maximum number of decisions. [START_REF] Esswein | Un apport de flexibilité séquentielle pour l'ordonnancement robuste[END_REF] studies the robustness of group scheduling for one machine problems (1|r i , d i |f) with different objectives: Cmax (the makespan), Lmax (the maximum lateness), Tmax (the maximum tardiness) and ΣTi (the total tardiness). The study compares group scheduling with a static method. For the reactive phase, the free sequential margin proposed by [START_REF] Thomas | Aide à la décision pour l'ordonnancement d'atelier en temps réel[END_REF] is used to choose the operation in a group sequence. The static method is computed before the execution of the schedule using non disturbed data with the EDD priority rule.

Several types of uncertainties are studied: the increase of the release dates, the increase of the processing times and the decrease of the due dates. Several levels of perturbation are also tested. The results show that group scheduling is always better than the static method. In this study, adding flexibility at the expense of the worst case quality is generally profitable to the final quality of the schedule. [START_REF] Wu | A graph-theoretic decomposition of the job shop scheduling problem to achieve scheduling robustness[END_REF] uses group scheduling on a job shop with the minimization of the weighted total tardiness (J|| Σw i T i ). [START_REF] Wu | A graph-theoretic decomposition of the job shop scheduling problem to achieve scheduling robustness[END_REF] call the method PFSL, but [START_REF] Artigues | Maximization of solution flexibility for robust shop scheduling[END_REF] have shown that this method is equivalent to group scheduling. The reactive phase uses priority rules to make the last decisions. This scheduling method is compared with a static method and a reactive method based on the ATC priority rule. The uncertainties studied are the variation of the processing times. The proposed scheduling method exhibits better performances when the uncertainties are small to

moderated (p' i ∈ [0.9p i , 1.1p i ]).
This study shows that group scheduling can absorb uncertainties for small to moderated perturbed problems. This method does not use the free sequential margin, so group scheduling can be robust without this tool.

In both thestudies presented above, group scheduling exhibits better performance than static or dynamic methods when perturbations impact the execution of the schedule. At the end of hisstudy, [START_REF] Esswein | Un apport de flexibilité séquentielle pour l'ordonnancement robuste[END_REF] conclude that if the results obtained are promising, the context of the experiment is limited and simple and the perturbations are limited as well. The same remarks can be made for the study of [START_REF] Wu | A graph-theoretic decomposition of the job shop scheduling problem to achieve scheduling robustness[END_REF]. So, the question is "Do Group scheduling really absorbs uncertainties in a complex manufacturing system?" There is clearly a need for a detailed study to test the effectiveness of the robustness of the group scheduling method on a complexmanufacturing system.

According to [START_REF] Esswein | Un apport de flexibilité séquentielle pour l'ordonnancement robuste[END_REF], « uncertainties describe potential modifications of some of the scheduling problem data which may occur between the computation of the schedule and the end of its execution in the shop ». Then,an uncertainty can be defined as a difference between the execution of a schedule and the hypotheses made for the computation of the schedule. Based on the classification proposed byRoy ( 2005), examples such as those could be addressed: rounding a length of a conveyor, difference of parameters in the orders compared to previsions, breakdowns and failures, lack of raw materials or inaccuracies in speeds and durations.

In this paper, we propose to test the robustness of the group scheduling method on an emulation of a real manufacturing system described below. This is a flexible manufacturing system modeled as a job-shop model. Frequently on job-shop models, the transportation system is not taken into account or whenever it is modeled, it is partially: only the transfertimes are modeled not the transport resources and their limited capacity. This assumption is very frequent on job-shop scheduling problems but not so trivial.Here, our assumption is to consider that the group sequence method is the right scheduling method to deal with a complex flexible manufacturing system without having a precise and complex job-shop model. The group sequence method is a proactive-reactive scheduling method. It means that as a proactive method, it introduces flexibility in the predictive schedule (i.e., groups of permutable operations) that should permit to give very good results during the execution of the schedule even if the job-shop model is approximate.

Experiments

Our goal is to test the robustness of group scheduling with regards to uncertainties. In this study, the choice was made to choose, among all the possible uncertainties, thetransfer times. The main advantages of this choice are:

 It is possible to evaluate the exact impact of transfer time in the production, and thus find the optimal schedule using the same job-shop algorithm. This specificity is described later in this section when introducing the lower bound;

 It is possible to easily modify the impact of this uncertainty on the production by changing the speed of the transporters;

 This uncertainty is related to structural characteristics of the job-shop, which are thus static parameters of these experiments, therefore not chosen arbitrarily considering the scheduling problem.

In this section, we present in detail our experiments:

 To avoid the specificity of a single problem and thus biasing the results, 15 different scheduling problems were considered, each one with a 5 machines job shop and a various number of jobs., We have chosena set of benchmark instances called la01 to la15 from [START_REF] Lawrence | Resource constrainedprojectscheduling: an experimental investigation of heuristicscheduling techniques (supplement[END_REF], used extensively in the scheduling literature. This set of instances is doubly useful: first it is a benchmark in the scheduling literature and second as optimal solutions with an approximation of transfer times can be computed, they will be used as lower bounds.

 The routings and the operating times of this set of instances will be used as input data for the FMS used in our study.

 In order to control the experiments and to reduce experiment times, the execution of the schedules on the production system were made through discrete-event simulation on an emulation of the real manufacturing system.

 The quality of the schedule is measured on the makespan. This performance criterion which measures the productivity of the system is one of the most used in the literature to evaluate the performance of scheduling methods [START_REF] Buzacott | Flexible manufacturing systems: A review of analytical models[END_REF][START_REF] Chan | The State of the Art in Simulation Study on FMS Scheduling: A Comprehensive Survey[END_REF][START_REF] Pinedo | Scheduling: Theory, Algorithms, and Systems[END_REF]. As the group scheduling method is implemented in an industrial software (ORDOSoftware), it is already used on real manufacturing systems and the performance measures usually used with ORDOSoftware are the makespan (i.e.,Cmax) and the maximum lateness (i.e.,Lmax). The makespan being the time difference between the start and finish of a sequence ofjobs, in our experiments the sequences of jobs were fixed and the initial and final states of the production system were considered as empty, in order to properly compare the different experiments.

 The production system is deterministic.

 Each schedule was executed 100 times on the simulated system, each execution with a different transportation speed. This was only possible because experiments were made on an emulation of the FMS and not directly on the FMS.

 To solve all the job-shop problems presented in this paper, we used the branch and bound algorithm described in [START_REF] Brucker | A branch and bound algorithm for the job-shop scheduling problem[END_REF]. To generate the group sequences, we used a greedy algorithm (described in [START_REF] Pinot | Coopération homme-machine pour l'ordonnancement sous incertitudes[END_REF] and [START_REF] Esswein | Un apport de flexibilité séquentielle pour l'ordonnancement robuste[END_REF]) that merges two successive groups according different criteria until no group merging is possible without degrading the quality. This algorithm begins with a one-operation per group sequence from the schedule computed by the [START_REF] Brucker | A branch and bound algorithm for the job-shop scheduling problem[END_REF] algorithm used to solve the job-shop problems.

The next paragraphdescribes the construction of each schedule.

A lower bound, named LB, was computed. It is a solution of the classical job-shop scheduling problem with virtual machines added in order to model transportation times. This lower bound LB is compared to threedifferent schedules which are:

 NoTT (No Transfer Times): in this schedule, no transfer times are taken into account. By definition, this schedule will not allow any flexibility during the execution.

 OGSS (Optimal Group Sequence Schedule): in this schedule, the best case quality of the group sequence generated is equal to the worst case quality without any transfer times.

 DGSS (Degraded Group Sequence Schedule): in this schedule, the worst case quality for the scheduling problem without any transfer time is degraded. This group sequence offers more flexibility to choose operations during the execution of the schedule.

In order to conduct experiments on a large time horizon, we use an emulation [START_REF] Pinot | A study on the group scheduling method in regards with transportation in an industrial FMS[END_REF] of a Flexible Manufacturing System.The system under study (Fig. 3) is a Flexible Manufacturing System used as an experimental platform for research and teaching at the University of Nantes (France).

Figure 3.General overview of the system.

The system can be modeled as a six machines job shop, with automated transfers (Fig. 4). Each machine has a finite capacity upstream queue. Four of them are only FIFO queues, the two others enabling a free choice. Machine 6 is not considered in this study. Automated transfers between machines are performed by 42 unidirectional transporters, stored in a storehouse during the inactivity periods. They cannot handle more than one part at a time, but they also carry all data of the part updated in real-time (identification, routing, progress, etc.). The structure of the transport system is built around a central loop. Each transporter moves on the loop until it can enter the queue of a machine. To be more specific, when a transporter arrives at the entrance of any machine, a decision, based on the stock level, on the routing of the part and on the schedule of the machine, is made to allow (or not) the transporter to enter the queue of the machine. If not, the transporter goes ahead.

The emulation model allows us to simulate several scenarios, characterized by one parameter:the speed of the transporters (from zero to infinity).

Each transporter is assigned to a job at the exit of the storehouse, and is only freed when the job is completed. On the real system, these decisions are taken based on the data contained in the electronic tag of the transporter and the groups assigned to each station. Indeed, the schedules we suggest to work on can be implemented the same way, with the following specifications:

 each operation is assigned to a unique machine;

 for OGSS and DGSS, operations are stored in list of groups in each machine;

 forNoTT, each group has a single operation, thus there is no decision during the execution of the schedule.

As stated before, transportation times were chosen as the uncertainties considered in the model. Indeed, OGSS, DGSS and NoTT algorithms do not take into account the transportation times, and thus it is a disturbance in the execution of the schedule on the real system.As a matter of fact, changing the speed of the transporters enables to change the level of the uncertainties: the highest the speed of the transporters is, the less the uncertainties are.

Thus, to simplify the data analysis, we propose to use a parameter called the uncertainty degree and noted U°:

𝑈°= 𝑝 𝑖 𝑙 𝑖,𝑗
With𝑝 𝑖 the average processing time of an operation i and𝑙 𝑖,𝑗 the average transportation time between two operations i and j.

As a consequence, U°= 1 means that processing times and transportation times are equal in average; U°= 10 means that transportation times are 10 times bigger than processing times in average; and U°= 0.1 means that processing times are 10 times bigger than transportation times in average.

The model of the workshop was programmed with a discrete-event simulation tool, namely Arena. Its role is to exhibit the behavior of the real system (full of uncertainties) in response to a given schedule (not taking into account these uncertainties). A schedule is defined here as the output of the application of a scheduling algorithm to a scheduling problem. For each level of uncertainties, the transportation times evolve, and thus the problem is different.

For each schedule denoted Ψ, Ψ ∈ {LB, NoTT, DGSS, OGSS}, performance P Ψ is measured as the total makespan of the execution of the production.

For each Lawrence's instance, the following happened:

1) 100 entry files E1 to E100 for the scheduler are generated introducing transfer times between each operation. Each file is different of the other because the speed is different, and thus the transfer times. 2) E1 to E100 are computed by the job-shop scheduler. The results represent the values of P LB .

3) An entry file E101 is generated, only considering the data from Lawrence's instance (thus no transfer times). 4) The job-shop scheduler delivers a schedule S101 from E101. 5) 100 simulations are executed considering the schedule S101, each simulation with a different speed of the transporters. The results represent P NoTT . 6) The branch and bound algorithm delivers two schedules S102 and S103 from E101, S102 allowing a lower flexibility. 7) 100 simulations are executed considering the schedule S102, each simulation with a different speed of the transporters. The results represent P OGSS . 8) 100 simulations are executed considering the schedule S103, each simulation with a different speed of the transporters. The results represent P DGSS .

As stated before, the emulation model was made deterministic, i.e. not considering any other disruptions than the transportation times. As a matter of fact, two consecutive simulations of the same schedule give the exact same result, which explain why no stochastic replications are made.

Results

P Ψ can be considered as a function of the uncertainty degree U°, U°∈]0,+ ∞ [. Obviously, when U° increases, every P Ψ tends to increase in the same way. Therefore, in order to be able to compare the results of each schedule, it was chosen to normalize the results in regards with the value of the Lower Bound (LB). This was made possible because LB was computedtaking into account the transfertimes.

In the following, the function obtained will be called the Degradation Function, as it measures the percentage of performance lost because of a non-optimal schedule. The degradation is computed as follows:

𝐷 𝜓 𝑈° = 𝑃 𝜓 𝑈° 𝑃 𝐿𝐵 𝑈° -1
A couple of remarkable properties of D can be noted. By definition, we have:

∀𝑈°∈]0; +∞[, 𝐷 𝐿𝐵 𝑈° = 0
As LB is a lower bound, we have:

∀𝑈°∈]0; +∞[, 𝑃 𝜓 𝑈° ≥ 𝑃 𝐿𝐵 𝑈°
Thus, from the above relations, it comes:

∀𝑈°∈]0; +∞[, 𝐷 𝜓 𝑈° ≥ 0
The experiments are conducted on 15 different scheduling problems, the Lawrence's instances.

Comparing the performance degradations of each schedule for the 15 problems is rather difficult.So, we have chosen to first present the performance measures on a single Lawrence's benchmark instance named la15. This instancewas chosen because it is one of the largest problems we tested. Thus, the results are clear enough for a graphical presentation.

Figure 5 introduces the evolution of performance degradation of each schedule, along the evolution of U°.

Figure 5.Performance degradation of each of the three schedules.

When we look carefully at the general evolution of the performances three distinct areas appear:

(1) for U°< 0.8, an area with low uncertainties;

(2) for 0.8 < U°< 1.4, an intermediate area;

(3) for U°> 1.4, low speeds therefore long transportation time, and high uncertainties.

For each area, degradations are clearly distributed among the schedules.

a. Area with low uncertainties (U°< 0.8) for instance la15

In terms of pure degradation, NoTT is the best for very low uncertainties (about 0.1<U°<0.25). This was expected, as NoTT is supposed to be the best schedule with U°=0.Very close to NoTT performance, OGSS gives very satisfying results relatively to the lower bound. Even if it is slightly less accurate for very low uncertainties, it tends to become the most effective in the whole area as soon as uncertainties become perceptible. This was also expected as OGSS is close to NoTT but offers a little more flexibility to absorb growing uncertainties.

The case of DGSS is quite different. Its results at very low uncertainties underperformNoTT and OGSS, although not so far from LB (less than 20% and in average 10%). This statement is no more valid when the uncertainties increase degradesNoTT. There, the flexibility of DGSS enables this schedule to overcome NoTT, but it isalways worse (with a constant degradation) than OGSS. This is due to the higher amount of flexibility introduced in DGSS, which makes the system taking more bad decisions in DGSS than in OGSS. When uncertainties are low, it is preferable to follow the schedule made during the predictive phase. Yet, the more flexibility is introduced and the more probable the schedule in the reactive phase will deviate from the schedule of the predictive phase.

To conclude, it is important to highlight the stability of the performances. Indeed, OGSS and at the beginning NoTT are very stable, whereas DGSS ismore chaotic. This can be explained by two factors: first, the higher flexibility of DGSS enables to make decisions locally but the local optimum may not be the global optimum. Second, the complex nature of the transportation system makes the performance of NoTT unstable when uncertainties are present.

To provisionally conclude with low uncertainties, one can say that flexibility is needed but it is needed at the good level: only little flexibility is required to absorb low uncertainties.

b. Intermediate area (0.8 < U°< 1.4) for instance la15

In this area, performances are all almost equivalent. The only one which is clearly worst is NoTT, especially at the end of this area. However, OGSS is always a little more performing than DGSS. This is an area where flexibility brings a real added value.

c. Area with high uncertainties (U°> 1.4) for instance la15

With the increase of uncertainties, the flexibility, as expected, outperformsstatic schedules. Furthermore, looking at Table 2, one can see that performance degradations evolve not very much between U°=5 and U°=50. This tends to prove that, when a certain level of uncertainties is reached, degradation of performances relatively to the lower bound is quite constant (considering the chaotic nature of the measures).

Table 2.Behavior of degradations at extrema of uncertainty degree.

Below, we present the same type of analysis, aggregating the results of all the 15 instances.

Looking carefully at the general evolution of the performances, it is possible to identify three distinct study areas as presented above. However, the boundaries are not always located at U°=0.8 and U°=1.4. There are some slight fluctuations, from U°=0.65 to U°=0.8 for the lowest bound and from U°=1 to U°=1.4 for the highest bound. These fluctuations are in accordance with the instances' complexity, a complex instance having an intermediate interval higher than a simpler instance. In order to involve all the cases in this generalization, in the following, the areas are defined as:

(1) U°< 0.65, an area with low uncertainties;

(2) 0.65< U°< 1.4, called intermediate area;

(3) U°> 1.4, i.e. very low speeds therefore very long transportation time, and very high uncertainties.

d. Area with low uncertainties for all instances

Considering very low uncertainties, NoTT and OGSS are always reaching the Lower Bound (i.e. no degradation). This was expected, as these two schedules are optimized for minimizing the Cmax when no transportation times are taken into account.

DGSS show degradations between 0 and 10%,with an optimal performance in 40% of the instances. These instances correspond to the case where, the decisions, taken during the reactive phase, happen to be optimal if there are taken, by chance, on the critical chain.

When the uncertainties increase, the performances of NoTT and OGSS decrease, as shown with la15.

It is interesting to note that given all the instances, the performances of OGSS arevery close toNoTT, sometimes better, more and more frequently as uncertainties increase.

Finally, the chaotic aspect previously shown on the la15 instance is confirmed for DGSS for each instance. On the other side, the stability of NoTT and OGSS is confirmed.

e. Area with high uncertainties for all instances

In that case, the ranking is always the same for all the instances, from the more to the less reactive, i.e.,DGSS performs the best, then OGSS then NoTT.More precisely, DGSS is better than NoTT from 30 to 60% according to the instances. Yet, OGSS is not so far from DGSS, with a performance lower from 10 to 30%.

Discussion

First of all, it is important to explain the chaotic nature of some measures. It can be observed that the more flexible is the schedule (DGSS is the more flexible, then OGSS and then NoTT which has no flexibility), the more chaotic are the measures. It can be explained by the fact that adding flexibility requires that more decisions will be taken in the reactive phase and thus there will be a greater risk of dispersion of the performances. This phenomenon can particularly be observed for instances with more jobs. Once again, the more jobs in an instance, the more decisions are to be taken in the reactive phase, and a greater risk of fluctuations of the performances.

A second point (that is the main contribution of this paper) is that flexibility brings a real added value to absorb uncertainties. We can assess that the more flexible is the schedule, the more robust it appears to absorb uncertainties. It was not so obvious that it seems to be, especially for that kind of uncertainties and that kind of manufacturing system.

For low uncertainties, OGSS is better than NoTT and DGSS. For higher uncertainties DGSS is better than NoTT and OGSS. In all cases, OGSS performs better or at least as well than NoTT. For the record, OGSS is a schedule where the best case quality of the group sequence generated is equal to the worst case quality without any transfer times. Therefore, it means that the flexibility added without degradation of the worst case quality (without any transfer times) seems very promising. With low uncertainties, the better the quality of the schedule in the worst case, the better the final quality is. This observation is easily explained by the fact that with low uncertainties, it is preferable to stay close to the predictive phase (but with some flexibility), so the better will be the predictive phase, the better will be the reactive phase. And this is confirmed comparing OGSS and DGSS. With low uncertainties, adding flexibility at the price of degrading the worst case quality is not interesting.

As a conclusion, group scheduling without degradation of the worst case quality is always better than a static schedule (i.e., without any flexibility). This assertion is relevant with the conclusions of the previous studies on group scheduling from [START_REF] Wu | A graph-theoretic decomposition of the job shop scheduling problem to achieve scheduling robustness[END_REF] and [START_REF] Esswein | Un apport de flexibilité séquentielle pour l'ordonnancement robuste[END_REF].

Finally, our study shows that group scheduling is particularly efficientto absorb uncertainties caused by the omission of transportation times in the scheduling model.

Conclusion

In the field of predictive-reactive scheduling methods, group scheduling is reputed to be robust (in terms of uncertainties absorption) thanks to the flexibility it adds on the sequence of operations. However, this reputation was based on evaluations made on simple theoretical examples.

The aim of this paper is to carry on experimentations on a complex flexible manufacturing system in order to determine whether this flexibility really absorbs uncertainties. The transportation times of the parts between the machines was chosen as the uncertainty to be studied. This choice was lead by the possibility to schedule the FMS with and without taking into account this parameter, which is totally deterministic.

Thus, simulation studies were lead in order to evaluate the relationship between flexibility and ability to absorb uncertainties. The results enable comparing group scheduling of the system with various flexibility levels not taking into account uncertainties, classical scheduling without uncertainties and classical scheduling taking into account the uncertainties. This last schedule is called the lower bound, as it is the best schedule possible.

The results show that the flexibility added in group scheduling is efficient to absorb uncertainties, especially when the level of uncertainties is high. Furthermore, when the level is low, group scheduling shows a good performance, really close to the lower bound. When considering manufacturing systems with a level of uncertainties evolving along time, group scheduling shows good characteristics and performances.

Future works will try to evaluate the performance of group scheduling versus different types of uncertainties (predictive or corrective maintenance for example) or with performance measures related to the due dates such as total tardiness or maximum lateness. As lower bounds are computed off-line in a simplified model which does not take into account the transfer system, the procedure remains the same. [START_REF] Pinot | Coopération homme-machine pour l'ordonnancement sous incertitudes[END_REF] proposes a branch and bound algorithm which computes the bestcase quality for group sequencing for any regular criteria such as the makespan, the total tardiness or the maximum lateness.

Figure 2 .

 2 Figure 2.Semi-active schedules described in Figure 1.

Figure 4 .

 4 Figure 4.Job-shop model of the studied FMS.