Lamia Zouhaier

Yousra Bendaly Hlaoui

Leila Jemni

Ben Ayed

Methodology for the Development of Accessible User Interfaces Based on Meta-model Transformations: the Case of Blind Users

We propose a generic approach for the adaptation of user interfaces to the accessibility context. This approach is based on the Model-Driven Engineering MDE. Thus, we adapt any kind of UI to the accessibility context based on a generic adaptation process. We are based on meta-model transformations parametrized with the context of accessibility. The proposed approach generates modality-based UI adapted to each disability. We have developed an accessibility context related to the type of disability, the used platform, the user identity and his/her situation, the surrounded environment and modelled into ontology. The metamodel transformations were based on mapping rules implemented by the Kermeta language.

Introduction

The intelligent devices have enhanced the life of the humanity targeting all categories of users. These platforms vary considerably in their properties as the screen size, the resolution and the interaction devices [START_REF] Mitrovic | A Review of User Interface Description Languages for Mobile Applications[END_REF]. That is why adapting a user interface (UI) for various user devices is still one of the most interesting topics. In addition, adapting an UI to the user's disability remains the most interesting problem of the accessibility of interactive systems. Users with disabilities usually experience barriers when they interact with UIs which are not adequately adapted to their needs [START_REF] Minon | Integrating adaptation rules for people with special needs in model-based UI development process[END_REF][START_REF] Zouhaier | A Model Driven Approach for Improving the Generation of Accessible User Interfaces[END_REF] .

Unfortunately, no effective solution has been proposed considering the context of accessibility related to people with disabilities. This context is defined as a combination of the disability profile of the user, the physical environment of the used computing platform and the user mobility situation. Therefore, we have developed an accessibility context related to the user disability profile, the used platform, the user identity, his/her mobility situation and his/her surrounded environment [START_REF] Zouhaier | Automatic Generation of UIs for Disabled Users Using Context-Aware Techniques and Reasoning[END_REF].

In this paper, we present a generic approach for the adaptation of any type of UI to the user context of accessibility [START_REF] Zouhaier | A Model Driven Approach for Improving the Generation of Accessible User Interfaces[END_REF]. This solution has to be generic in order to allow the re-usability and to consider all kind of disability. Furthermore, instead of building an adaptation process for each given UI model, we develop a unique adaptation process getting as input the UI meta-model. To ensure this genericity, we are based on the Model Driven Engineering(MDE ) [START_REF] Omg | Model Driven Architecture (MDA)[END_REF].

Therefore and based on the MDE principals, our approach is defined of a series of meta-model transformations between different UI models. Thus, we propose a PIM(Platform Independent Model) to PIM transformation representing the abstract adaptation process which adapts any kind of UI model to the disability profile of current user. This transformation provides as output an adapted UI model to the user disability profile. To ensure the genericity of this process, we define all categories of user disability profiles with an ontology. As ontologies [START_REF] Benaboud | User's preferences and experiences based web services discovery using ontologies[END_REF] [23] are used to specify and manipulate any kind of knowledge [START_REF] Zouhaier | Automatic Generation of UIs for Disabled Users Using Context-Aware Techniques and Reasoning[END_REF]. Hence, the proposed transformation are defined by a set of mapping rules between non adapted UI metamodel and adapted UI metamodel using the user accessibility profile ontology as a parameter. That is why, we have considered these mapping rules as adaptation rules.

Once the adapted UI is provided, we perform a PIM to PSM(Platform Specific Model) transformation. This transformation consists of a specific adaptation process of the user disability profile adapted UI model to provide an adapted UI model to the execution platform. This output is not only adapted to the given user disability profile but also is adapted to the interaction modalities of the used execution platform [START_REF] Zouhaier | Generating Accessible Multimodal User Interfaces Using MDA-Based Adaptation Approach[END_REF]. The interaction modalities (vocal, graphic, multimodal(vocal and graphic), tactile, gestural) depend on the kind of the user disability. This dependence is specified in our approach by a relationship between the user disability profile ontology and the technical context ontology. This relationship allows in the PIM to PSM transformation the right selection of the convenient and the effective mode of the interaction between the user with disabilities and their execution platform. In the PIM to PSM transformation, we have respected the accessibility norms such as the norm WCAG2.0 [START_REF] Henry | Web Content Accessibility Guidelines (WCAG) Overview[END_REF][START_REF]Information technology, W3C Web Content Accessibility Guidelines (WCAG) 2.0[END_REF] and the norm ISO 9241-171 [START_REF]Ergonomics of human-system interaction, Part 171: Guidance on software accessibility[END_REF] using their directives in our mapping rules [START_REF] Zouhaier | A MDA-based Approach for Enabling Accessibility Adaptation of User Interface for Disabled People[END_REF].

The remainder of the paper is organized as follows. In section 2, we provide an overview of some related works dealing with accessibility of UI. The third section is a description of the proposed approach. Section four is dedicated to focus on the adaptation process and the specific transformation. The fifth section is an illustration of the proposed approach and sixth one represents an evaluation of this approach. Finally, in the conclusion section, we present some concluding remarks and future work.

Related works

Several MDE approaches [START_REF] Brossard | Taking context into account in conceptual models using a Model Driven Engineering approach[END_REF][START_REF] Bouchelliga | An MDE approach for user interface adaptation to the context of use[END_REF][START_REF] Oliveira | Transportation ontology definition and application for the content personalization of user interfaces[END_REF][START_REF] Paterno | Model-based Design of Multi-Device Interactive Applications based on Web Services[END_REF][START_REF] Thevenin | Adaptation en interaction homme-machine: Le cas de la plasticit[END_REF] have been proposed in the adaptation of the UIs. They have considered, in their adaptation process, only the user preferences and the platform technical context without considering the user accessibility context. Some of UI context adaptation approaches [START_REF] Abascal | A modular approach to user interface adaptation for people with disabilities in ubiquitous environments[END_REF][START_REF] Gajos | Automatically generating personalized user interfaces with Supple[END_REF] have considered the accessibility problem in their adaptation process. However, they have only addressed a limited number of disabilities. SUPPLE [START_REF] Gajos | Automatically generating personalized user interfaces with Supple[END_REF] have proposed an automatic personalization of UIs suitable for people with motor and vision impairments. They have adapted the UIs to person's abilities, devices, preferences, and tasks.

EGOKI [START_REF] Abascal | A modular approach to user interface adaptation for people with disabilities in ubiquitous environments[END_REF] is an automatic generator of accessible UIs allowing people with disabilities to access supportive ubiquitous services. EGOKI follows a modelbased approach and selects suitable interaction resources and modalities depending on users? capabilities. The major limitation of these automated approaches is that they have applied the personalisation of UIs on specific prototypes. However, in our approach we adapt any kind of UI to any kind of user disability considering the execution platform modalities.

The Adaptation Approach of UIs to the Accessibility Context

We propose a Generic Model-Driven Adaptation Approach based on the Context of Accessibility. Hence, we adapt any kind of UI to the developed context of accessibility based on a series of parameterized meta-model transformations.

The approach focuses on the use of modality-transformation as a key solution to suit the capacities of users with special needs. In fact, the employability of the multi-modality facilitates, firstly, the interaction of the disabled user with the UI and secondly with the platform capacities considering the accessibility context. Furthermore, we have fixed adaptation strategies for each type of disability in order to develop the target meta-models. In this paper, we will be limited only to the case of blindness disability which will be presented afterwards.

The proposed approach includes four principals phases:

Abstract modelling of the non adapted-UI using a Reverse Engineering technique: In this phase, we abstract the executed non-adapted UI from the implementation and the modality details by providing tan abstract UI non adapted model. This model( PIM-model) represents different abstract and structural elements composing the UI and their relationships.

This phase is based on two steps:

-Step 1 is the extraction of the different elements and their relationships from the executable non adapted UI to build a UI-tree using YED tool [START_REF][END_REF].

The UI-tree is a graph of the structuredUI-elements which facilitates the development of the non adapted PIM-model. This metamodel has to describe any type of UIs. It includes the information about the employed modalities (input, output) defined at the high level of abstraction.

Development of an ontology describing the context of accessibility:

We have developed an ontology representing knowledge about all accessibility concepts such as the user disability profile, the user situations, the user profile, the technical context and the environment context. This ontology will serves as input for the adaptation process and the specific transformation of the approach. The ontology instances represent the captured real values of the current accessibility context.

Adaptation process of the non adapted-UI according to an instance of the accessibility context ontology: It represents the kernel of the approach. It ensures the adaptation of any type of UIs to any accessibility context. The adaptation process transforms the Non Adapted UI Meta-model to an UI-Disability-meta-model using a given accessibility context ontology instance. It provides an adapted UI model. It is a parametrized transformation.

Specific transformation of the adapted UI-PIM to a specific platform of execution:

In this phase, we transforms the adapted UI-PIM provided from the adaptation process to a PSM model (Modality-PSM ) depending on the modalities of the execution platforms.

This phase includes two steps:

-Step 1 is an exogenous transformation which represents the PIM to PSM transformation depending on the modality -Step 2 is an endogenous transformation which is the PSM to PSM transformation depending on the target platform web, desktop or mobile.

Table 1 recapitulates different intervening source and target meta-models during the PIM to PIM and PIM to PSM transformations represented in figure 1. In this figure, we have only focused on the PSM to PSM transformation for the web platform.

In this paper, we have considered only sensory impairments. We have been limited to blindness, low vision and deafness impairments. For each category, we have defined the corresponding target metamodel namely, BlindnessAdapt-edPIM, LowVisionAdaptedPIM, DeafnessAdaptedPIM and HardDeafnessAdapt-edPIM (Cf. table1)

The metamodel transformation

The meta-model transformation is based on a set of rules according to the set of the given disability values. These rules are divided into two types: -Mapping rules: are used to match an element from the source meta-model to its correspondent of the target meta-model. -Adaptation rules: are used to structure the adapted UI model. In fact, during the adaptation process, these rules provide the UI framework of the correspondent element provided by the mapping rule. The UI framework is defined accordingly to the user disability context.

The specification of transformation rules is defined as follow:

For each Element E of Source Metamodel, match an element E from Target Metamodel based on an instance of the ontology representing a given accessibility context Instance(OO).

To introduce the syntax of mapping rules, we defined the adaptation function A which is described as follows:

A : M M nonadapted × OO → M M adapted (M U Inonadapted , I OO ) → M U I adapted

Modality Transformation

This step focuses on adapting the input (I) and output (O) modalities of the UI in an appropriate manner of the user disability. In the case of a blind user, we have defined two principal rules R B1 and R B2 which are defined as follows:

RB1 : A(InputM odality, Blindness) = V ocalM odality RB2 : A(OutputM odality, Blindness) = V ocalM odality
In fact, whatever the input or the output modality, for a blindness, the modality is vocal.

Transformation PIM2PIM: Case of Blindness disability

In this transformation, we use three strategies:

-Strategy 1: Since the problem of blind users is related to graphical elements of the UI and in order to offer perceptible elements for the her/him, we will adopt the vocal mode to represent the different type of elements of the adapted UI. Hence, each graphical element will be transformed to a vocal one. This will be done through mapping rules. -Strategy 2: The use of vocal modality into a UI causes a disruption of the user's concentration and his attention. This problem occurs when the user is faced to fill out a form. For this purpose, we will minimize the number of input elements (InputInteractor )per grouping unit (GroupingUnit). Therefore, we propose to put only one InputInteractor in each grouping unit of type GroupingUnit. Each presentation unit (PresentationUnit) should contain only one GroupingUnit. This gives result to new generated UIs, each one contains a single InputInteractor element. This strategy will be based on adaptation rules. -Strategy 3: Based on the result of the strategy 2, we obtain several Pre-sentationUNIT s of the adapted UI that are logically linked. This requires a strategy to ensure the dialogue between these different PresentationUNIT s.

For this reason, we will add some additional elements for navigation Navi-gationInteractor named next and previous allowing navigation between the different PresentationUNIT s.

Using these strategies, we have obtained the Blindness-PIM-Metamodel for blindness disability represented in Fig. 2.

Case Study: Blind user

In this case study, we focus only on the adaptation process of an UI of an hotel reservation application for a blind user using his laptop. Figure 3a depicts the UI hotel reservation and its corresponding PIM model represented by the Ecore [START_REF] Omg | EcoreTools -Graphical Modeling for Ecore[END_REF].

To start, we determined the type of the UI (desktop), its domain (tourism) and the input and output interaction modalities (graphical). As shown in Fig. 3a, the PIM model of the UI contains only one PresentationUnit that includes two main GroupingUnits Formulaire and Date and validation. The distribution of the elements within each GroupingUnit is as follows:

Evaluation, Results and Interpretation

To asses the results produced by our methodology, we have conducted an empirical study to improve the satisfaction of users with disabilities towards the proposed strategies and the interaction modalities. Users must express their real feeling and their comfort when interacting with adapted UIs. For that end, we have based on the interface UI-1 (see Fig. 3a). As apparatus, we have used a PC model ASU SN 56 with a screen size 15, 4" set to 1920 by 1080 pixels resolution, with a 64bit color palette. The apparatus is equipped with a loud speaker that will be used for voice output and a microphone for voice input. To evaluate the usability of the approach, 42 participants are selected carefully to achieve the desired results where 12 participants are blind, 14 are visually impaired and 16 are deaf. The picked subjects have different skills (low, medium, high) on using computing platforms. Two instrument were the basis of this empirical study:

-System Usability Scale (SUS): we have based on the standardized SUS questionnaire [START_REF] Lewis | The Factor Structure of the System Usability Scale[END_REF][START_REF] Sauro | Measuring usability with the System Usability Scale (SUS)[END_REF] to be filled by subjects. SUS is a reliable low cost usability scale used for global assessment of system's usability aiming to determine the level of user's satisfaction of the given system. It consists of 10 items [START_REF] Sauro | Measuring usability with the System Usability Scale (SUS)[END_REF] measuring two factors: the usability and the learnability [START_REF] Lewis | The Factor Structure of the System Usability Scale[END_REF]. The usability is described through 8 items which are Q1, Q2, Q3, Q5, Q6, Q7, Q8 and Q9. While the learnability is defined by the 2 items Q4 and Q10. Participants are asked to provide a 5 -point scales numbered from 1 anchored with "Strongly Disagree" to 5 anchored with "Strongly Agree". -Test Level Satisfaction: This metric measures the relative satisfaction and preference among the adapted UI-1 and the adapted interaction modalities that match better each disability. Each participant is asked to evaluate its satisfaction by providing a 7 -point scales numbered from 1 anchored with "Very Bad " to 7 anchored with "Excellent".

To estimate the reliability of the SUS questionnaire, we have used the coefficient Cronbach's Alpha [START_REF] Carricano | Analyse de données avec SPSS[END_REF] where the threshold of acceptability is 0.7. The results recapitulated in table 2 show that the SUS score = 73.92 which represents a good SUS score result. On the other hand, the value of the Alpha α = 0.839 > 0.8 which represents good internal consistency among the items. Besides, considering the two factors usability and learnability, it represents a reasonable and acceptable reability in term of usability factor (α = 0.781) however, it considered a questionable scale for learnability factor (α = 0.592). Figure 4 represents the result of test level satisfaction performed by all participant considering their experience with computing platforms.

These results indicate that all users find that it is usable to use the system but it is difficult to learn rapidly how to interact with the UIs using the different interaction modalities. It should be noted that this problem is remarkable for blind users using vocal modality whereas those who are deaf and visually impaired encounter fewer difficulties using the graphic modality. The rate of satisfaction is high when users are experienced with the use of computing platform specifically deaf and visually impaired users.

Conclusion

In this paper, we have presented an MDE approach for the generation of adaptable UIs considering the context of accessibility. The approach is based on metamodel transformations. Thus, we have defined a set of transformation rules (mapping and adaptation rules) for the different transformations. One case study has been described showing how this approach can support the adaptation process in the case of blind users. An empirical study has been conducted to evaluate the usability of the approach and the efficiency of the different developed meta-model transformations and their associated transformation rules. As future work, we would like to develop a graphical tool using the Eclipse Graphical Modeling Framework (GMF) [START_REF]IBM, Eclipse Graphical Modeling Framework (GMF)[END_REF] in order to easily draw UI models conforming to the proposed meta-models. We aims to make an automatic process of the whole approach.

-

  Step 2 is the development of the abstract UI model from the UI-tree. It transforms the UI-tree to an UML class diagram model. Each class of this model represents a tree-node which is an UI-element. The associations of the class diagram model describe the relationships existing between UI-elements represented as edges in the UI-tree. The resulted model is conformed to the non adapted UI meta-model.

MFig. 1 :

 1 Fig. 1: Diagram of activity of the whole approach process from the adaptation process to the specific transformation cibling the web platform

1 .

 1 The element GroupingUnit Formulaire contains three input elements of type TextInput and three associated elements of type TextOutput: called Name, Telephone, Email and a GroupingUnit called Region and hotel including a selection element SelectionInput called Hotel , an output element TextOutput called Select Hotel, a selection element SelectionInput region and an output element TextOutput called Select region. 2. The element GroupingUnit named Date and validation contains three selection elements SelectionInput called as follows: Day of Arrival , Month of Arrival and Year of Arrival to introduce the date of arrival. Each one is associated to an output element TextOutput. It includes, also, three others SelectionInput Day of departure, Month of Departure, Year of Departure associated to their correspondent TextOutput. It contains also, two activator elements ActivatorInteractor : Reserve and Cancel.

Fig. 2 :

 2 Fig. 2: Blindness-PIM-Metamodel specific to blindness disability

Fig. 3 :

 3 Fig. 3: The adaptation of a partial from the Reservation Hotel UI (a) based on the metamodel transformation for blind users for generating several Presentation UNIT (b)UI-1, (c) UI-2 ,(d) UI-3, and others.

Fig. 4 :

 4 Fig. 4: Test Level Satisfaction

Table 1 :

 1 Source and target Meta-models intervening during the PIM2PIM and PIM2PSM transformation

	Transformation Type	Source Metamodel	Target Metamodel
			BlindnessAdaptedMetamodel
	Transformation PIM2PIM Non-AdaptedPIM-Metamodel	DeafnessAdaptedMetamodel
			LowVisionAdaptedMetamodel
			HardDeafnessAdaptedMetamodel
		BlindnessAdaptedMetamodel	VocalPSM-Metamodel
	Transformation PIM2PSM	DeafnessAdaptedMetamodel	GraphicalPSM-Metamodel
		LowVisionAdaptedMetamodel	MultimodalPSM-Metamodel
		HardDeafnessAdaptedMetamodel

Table 2 :

 2 Reliability StatisticsN of items Alpha's Cronbach SUS score Std.dev

	Usability	8	0.781	64.78	7.79
	Learnability 2	0.592	9.14	4.14
	Total	10	0.839	73.92


Lukasz Gadomer
email: l.gadomer@pb.edu.pl

M Skoczylas
email: m.skoczylas@pb.edu.pl

Gesture recognition in 3D space using dimensionally reduced set of features

Keywords: gesture recognition, features, dimensionality reduction, singular value decomposition

In this study authors present a solution to track and recognize arbitrary gestures of hands in three dimensional space and review the recognition accuracy. The idea of this novel gesture recognition system is described and results of research made on a recorded gesture data set are presented. Gesture instances were defined by user standing in different distances from the controller, in different placements of their field of vision and with different speeds, making recognition velocity and position invariant. Authors' goal was to find the minimal number of features that give satisfying gesture classification result in order to achieve a compromise between accuracy and computation time. In this publication progress of the research on gesture recognition problem is described and a comparative study is presented.

Introduction

This paper presents a solution which allows tracking hand gestures in three dimensional space that can be inserted into a CAVE3D (Automatic Virtual Environment, see Figure 1).

System consists of two main parts: a gesture recognition tool and a graphical environment. The gesture recognition tool allows user to create gestures database, learn it using one of selected classifiers and then recognize gestures performed by the user in real time. Implemented solution allows recognition of gestures recorded with varied velocity and with different user placement relating to the controller, so it is velocity and position invariant. It also contains build-in features that test recognition accuracy which are helpful during research and tests of the quality of this solution.

The whole system allows real-time position and velocity invariant gesture recognition: preparation of user's own set of gestures, classifiers learning, and then recognition of gestures in real-time using selected classifiers, it is a novel and innovative solution. The main purpose of the work described in this paper is to reduce size of the data set and computation time of gesture recognition while maintaining the highest possible classification accuracy. To achieve this, number of attributes was reduced by extracting features from a prepared data set, performing dimensionality reduction and checking what is the minimal number of features needed to achieve satisfying accuracy. This goal was achieved, and the important issues concerning this work are described in the following paragraphs.

This work is the continuation of researches presented in [START_REF] Gadomer | Real time gesture recognition using selected classifiers[END_REF] and [START_REF] Gadomer | Towards gesture recognition in three-dimensional space[END_REF].

Related work

The problem of gesture recognition is a challenging and popular issue. Many researchers tried to resolve it in their own way. Diversity of approaches is, inter alia, a consequence of different possible ways of gesture representation. Very often gesture is represented as a movement of single body's part, usually a hand. This approach is the same that was described in the following gesture definition: gestures are ,,movements of the arms and hands which are closely synchronized with the flow of speech" [START_REF] Mcneill | Gesture and Thought[END_REF]. In [START_REF] Xu | Mems accelerometer based nonspecific-user hand gesture recognition[END_REF] authors studied possibility of gesture recognition using accelerometer MEMS (Microelectromechanical System). This device was controlled by user's hand and its movement in three dimensions was observed. Authors performed their research on seven simple gestures. The same device was used in [START_REF] Akl | A novel accelerometer-based gesture recognition system[END_REF] to resolve similar problem. In that work, the gesture classification was realized using Dynamic Time Warping (DTW) algorithm. A database consisting of 3780 instances of gestures, grouped into 18 different decision classes was used. Another solution which is based on the accelerometer device and the same classification algorithm is described in [START_REF] Hussain | User independent hand gesture recognition by accelerated dtw[END_REF]. In this publication authors tested classification accuracy in two cases: user-relevant and user-irrelevant. Their research database contained 3200 instances, each of them represented one of eight different gestures. In this case every single instance of gesture took the same time (3,40 seconds). In all these solutions gestures were treated the same way as presented in following paragraphs -as a movement of one single point, which represents user's palm in three dimensional space.

Another example of tracking hand's movement was described in [START_REF] Zhou | Adaptive template adjustment for personalized gesture recognition based on a finger-worn device[END_REF]. In this case to track gestures authors used a finger-worn device which was similar to a ring -it was called Magic Ring (MR). They presented personalized gesture recognition using a method of adaptive template adjustment. Another exemplary gesture recognition solution is called 1$ [START_REF] Wobbrock | Gestures without libraries, toolkits or training: A $1 recognizer for user interface prototypes[END_REF]. This name was given to symbolize algorithm's low cost and simplicity -it's implementation took only about a hundred lines of code. According to authors' description it works satisfyingly even there is only one training instance of each gesture. This work was an inspiration for the authors of [START_REF] Boyali | A robust gesture recognition algorithm based on sparse representation, random projections and compressed sensing[END_REF]. They designed a solution based on the algorithm described in [START_REF] Wobbrock | Gestures without libraries, toolkits or training: A $1 recognizer for user interface prototypes[END_REF] which used Sparse Representation (SR) and Compressed Sensing (CS) methods.

Gesture data collecting and processing

In this section authors describe issues connected with gesture data collection and processing. That was described in details in [START_REF] Gadomer | Real time gesture recognition using selected classifiers[END_REF] and [START_REF] Gadomer | Towards gesture recognition in three-dimensional space[END_REF], however let's outline briefly here: first, user has to prepare his own data set. He stands before the controller and performs gestures, signaling beginning and end of the gesture 1Then he can save created data set and use it for two purposes:

1. Learn selected classifier and use it to perform gesture recognition in real time, 2. Use selected data set for classifier's parameters optimization and measure the recognition accuracy to evaluate solution quality.

The first issue was described widely in [START_REF] Gadomer | Real time gesture recognition using selected classifiers[END_REF]. In this publication authors would like to concentrate on the progress which concerns the second one.

The issues connected with position and speed invariance was widely described in [START_REF] Gadomer | Real time gesture recognition using selected classifiers[END_REF] and [START_REF] Gadomer | Towards gesture recognition in three-dimensional space[END_REF]. For this reason, we do not concentrate about them in this paper.

Gesture dataset

Gesture database included 12 different gestures shown in Table 1, recorded as values in relative data format. Each gesture type (a decision class) was recorded 80 times which in total sums up to a gesture database consisting of 960 gestures. All of gestures were performed by four different users -each user recorded 20 gestures. What is more, they were asked to perform gestures in a different way and change their positions a bit between every gesture. As a result, every recorded instance was a bit different than others. Gestures were recorded with different velocities, users were standing in different distances to the controller and they were placed in a different parts of detecting range. Such way of performing gestures provided research data that allows test of position and velocity invariance in a real scenario. In addition, recordings that were not perfect were also included into the dataset (but recordings were not repeated), making the data set even more difficult to analyze. The only limitation in recording instances was assumption that every gesture should be performed in the same direction. It means that, for instance, every horizontal line is performed from left side to right side.

As it is shown in Table 1, all gestures are two-dimensional by their defintion (for example, brackets are designed to be two-dimensional, etc.). However they are captured in three-dimensional space. Device captured depth, that was recorded and written to the dataset the same way as width and height. It means that it was also important if the data collecting participants were performing movements in depth dimension. We have chosen such gestures, but there would be no problem to choose, for examples, "push" and "pull" ones -whichever selected gestures would be, the algorithm should work the same way.

All of recorded gestures were shuffled and written into a single dataset. The information about gesture performer was not saved. It means that gesture recognition is fully user-independent.

Gesture shape Starting point ( Top ) Top < Top > Top ∧ Left \ Top / Top | Top - Right ∼ Left O Top 8
Top Table 1. Gestures dataset

Feature data representation

Number of attributes in a data set depends on the length of gesture. Authors assumed that all gestures have 40 samples, three dimensions each, which makes 120 attributes. Recording 40 samples using Kinect controller takes a bit more than one second. It does not mean that user has to perform the gesture in exactly one second -it can take any amount of time. This assumed number is just a final length of the gesture after scaling.

To resolve this problem authors decided to extract features from the gesture instances. The advantage of this solution is the fact that it is possible to extract a given number of features independently from the gesture length. It means, no matter how long the gesture is, the number of features is always the same. This allows reduction or extension of dimension to the same number of dimensions, allowing to have unlimited length of gestures.

To extract data features authors decided to transform the prepared data set following way: from a relative hand position absolute values were computed, but always starting from point (0, 0, 0). That means gesture's samples values were translated to the beginning of the coordinate system. Authors performed this operation to express real movements of the hand -representation used in [START_REF] Gadomer | Real time gesture recognition using selected classifiers[END_REF] was a proper one for direct recognition, but in authors' opinion it needs above transformation to achieve features that express the given problem best way.

Table 2 shows features extracted from the prepared dataset. Popular statistical and signal features were selected. As it is presented, most of these features were computed independently for each axis and for all of the axes together. Axis to axis features were computed between the cartesian of axes. In total 49 features were extracted. In the Table 2 n is the number of samples k and l are the sample pair of axes and a is the sample.

Dimensionality reduction

One of the main objective in this publication is to check whether the minimal number of features exists that allows to achieve rewarding gesture classification accuracy. As it was mentioned in section 3.2, 49 features were extracted. This is the maximal number of dimensions proposed in our computations. The next step is the dimensionality reduction, which objective is to reduce number of features. To achieve this a Singular Value Decomposition (SVD) algorithm was used, but considering only real numbers (which is a right assumption for the purposes of our gesture recognition problems, where numbers cannot be complex).

The singular value decomposition of m × n matrix M is a M = U ΣV * factorization, where:

-U is a m × m unitary matrix, -Σ is a m × n rectangular diagonal matrix with non-negative real numbers on the diagonal, -V * is a n × n unitary matrix, which is a transposition of V .

Values that are placed on the diagonal of Σ are called singular values of matrix M . The m columns of U are known as left-singular vectors of M and the n columns of V are called right-singular vectors of M .

First, the SVD algorithm is performed on all set of n features. Then, to reduce this data set to k dimensions, all elements of k + 1 to n columns of Σ

Standard deviation

Measure that is used to quantify amount of dispersion of a set of samples

1 n n ∑ i=1 (ai -ā) 2
Each axis, all of the axes Variance Measure that expresses how far a set of samples is spread out

1 n n ∑ i=1 (ai -ā)
∑ i=1 kl -kl n ∑ i=1 (ki -k) 2 n ∑ i=1 (li -l) 2
Each pair of axes Skewness Measure of asymmetry of set of samples

√ n n ∑ i=1 (ai -ā) 3 n ∑ i=1 (ai -ā) 2 3
Each axis, all of the axes Kurtosis Measure of tailedness of set of samples

n n ∑ i=1 (ai -ā) 4 n ∑ i=1 (ai -ā) 2 4
Each axis, all of the axes Signal magnitude area Measure of magnitude of set of samples Each axis, all of the axes Table 2. Extracted features and V matrices and rows of U matrices are set to zeroes. Then a new M ′ matrix is computed according to the procedure presented before. As a result, its first k columns are different from 0 -these columns form a new, dimensionally reduced set of features.

Research description

For accuracy testing purposes and to achieve best results in gestures recognition problem, authors performed several experiments with collected gesture data. Aim of this study was to check the classifiers, primarily to identify accuracy in different gestures recognition, as well as speed of calculations.

Parameters optimization

The basic issue connected with classification using many classifiers, expecially SVM, is a parameter optimization. This process is essential due to the fact that classification accuracy highly depends on parameters of the classifier. Parameters have to fit the character of data. It is a serious problem because there is no simple way of selecting proper parameters. A popular method to obtain kernel parameters is a grid search. Note, that it is also possible that selected parameters do not fit to the testing set. All these facts mean that parameter optimization does not have a perfect solution -choosing good parameters is rather a compromise than a sure answer.

To minimize risk of data fitting authors decided to perform parameter optimization, use a single random data set division (but the same each time) and the 5-fold cross-validation. This division assumes that in every one of the five parts there are the same number of each gesture class instances. For each parameter combination the dataset was randomly divided into five parts, but taking into account that described assumption. Classifier is then learned using four of these parts and tested using the fifth, out-of-bag (OOB) part. This process is repeated five times (each time the other part is OOB part) and then the result is averaged. The same actions are performed for each of parameters combination and the best one is selected.

Because of long time of computations, the parameter optimization procedure was performed in a parallel way. The parallelisation ratio was computed on a single personal computer with Intel i7 processor (8 cores, 16 threads).

Classification

After selection of best classifiers' parameters (and kernel function parameters for the SVM classifier) authors performed data classification using the obtained parameters set. Similarly to parameter optimization, 5-fold crossvalidation was used, but the classification with 100 different random divisions was performed, not only the single one. The whole classification process was the same that it was in the case of parameters optimization -the difference is that research results were averaged over all these 100 divisions, and that value was recorded as a final classification accuracy.

Research parts -two experiments

Authors performed two main parts of the research and recognition accuracy evaluation.

The first experiment concerns analysis how tested classifiers deal with gesture classification problem. Evaluation of all four classifiers in two cases was performed: with and without the normalization. Additionally, for SVM classifier, five kernel functions were tested independently. Such research gave a large number of results, and they are summarized and presented in section 6.

For the latter, a Singular Value Decomposition was used to find the minimal number of features that give satisfying gesture classification results in order to obtain a compromise between the accuracy and computation time. To achieve this, gesture classification accuracy with the increase of number of dimensions was compared. In addition, best results using full data representation to feature data representation were compared, in order to check if new way of expressing data does not cause the severe drop of the classification accuracy.

One of the main purpose of second experiment was to check how many features are enough to achieve satisfactory classification accuracy. To accomplish this, dimensionality of data set was reduced, so that each example with 49 features was reduced iteratively into 48 new data sets that consisted from 1 to 48 features. Each of these data sets was tested using method described above. This allowed us to judge how an addition of a single dimension to a data set affects the classification accuracy.

All the results obtained are presented and discussed in section 6.

Results and discussion

First experiment

First experiment was performed using relative data representation. For each classifier one configuration was selected that achieved best results based on recognition accuracy comparison, and then these were compared with other classifiers' best configurations. Summarized results are presented in Table 3. On the basis of these observations, authors conclude that for the given problem of classification of gestures the best results are obtained using the SVM classifier. SVM performed best in the shortest possible time and was characterized by a low diversity of the results achieved in subsequent repetitions.

Classifier
The results of SVM kernels comparison are shown in Table 4. As we can see, in all the cases accuracy obtained using normalization is better than without using it. The best result was produced using wavelet kernel, but the difference between this kernel and the others was not large. It is important to note that without normalization Wavelet kernel generally gives much worse results. Authors have chosen best possible parameters and final results were good, but without cross validation it would be really hard to choose because most of parameters without normalization yielded bad results with the Wavelet kernel.

Considering results of presented research it is also worth to note what are the reasons of recognition mistakes. Figure 2 shows classification errors for opening bracket gesture. The most problematic were gestures similar to less-than sign and often they were incorrectly recognized as a vertical line. It is vital to note visual similarity between these gestures. When the user marks the curve too 4. Results of measurements obtained using selected SVM kernels sharply while performing opening bracket gesture, it makes similar to less-than sign. When user marks this curve not sharply enough, gesture starts to look like a vertical line gesture. This explains reasons of classification errors. Analysis of incorrectly classified instances of other gestures confirmed that observation.

Second experiment

The first tested approach was a check difference between classification accuracy using relative data representation, achieved in the first experiment, and the proposed feature representation using 49 or less proposed features. This was checked for each of five proposed kernel functions. The results are presented in Table 5. As it is shown in section 5, for four of five kernels the difference was about 1.5%-3% (it was bigger for sigmoid kernel). It is a noticeable drop of classification accuracy, which confirms that feature extraction causes loss of some information. The other reason can be not perfect choice of features that were extracted -this can be checked in further research. On the other hand, by performing feature extraction we reduced the number of dimensions more than twice (from 120 to 49), as a result we also reduced the classification time. We judge the 1.5%-3% difference is a price worth to pay for more than twice reduction of computation time.

The main part of our research dealt with classification accuracy using data sets that consisted of different number of dimensions. Authors checked 49 data sets having number of dimensions from 1 to 49 (with a step of 1). The results are presented in Figure 3. First of all, addition of each dimension is significantly increasing the classification accuracy for each kernel, but this tendency stops after 7-12 dimensions. At this point classification gains stable and satisfactory results. Best results most kernels (instead of sigmoid) started to achieve at 16th dimension. The further increase of dimensions from 16 to 31 does not result in significant classification accuracy growth, which means next features do not provide any more important information about data. After 31th dimension in three of five kernels classification accuracy drops, that means some information is excessive and is bringing unnecessary noise to the data set for these kernel functions.

The best results in 16-31 dimensions were comparable for each kernel function, but not sigmoid. Slightly better in this range is a wavelet function. In the larger number of dimensions the best classification accuracy was achieved by linear and polynomial kernel functions, and they achieved best results in the whole research. Sigmoid functions, comparing to the other ones, gave unsatisfactional results. We were unable to select a correct set of parameters for this function to achieve results comparable to other ones.

In Figure 4 the best results achieved during the parameters optimization process are shown. Figure 5 shows differences between classification accuracy achieved during optimization of parameters. In almost all of the cases results achieved using parameters optimization were better than during the research. Differences are the result of data overfitting. For four of five kernels (instead of the wavelet one) the differences were oscilating about 0%-3% all the time. For wavelet kernel the differences were much larger. For 0 to 30 dimensions they did not exceed 10%. For the larger number of dimensions (above 30) it was oscilating between 15% and 30%. It means this kernel function is the most sensitive to selection of parameters.

Conclusion

The method and algorithm of real-time gestures recognition described in this paper can be inserted into the CAVE3D system. Gestures can be successfully recognized using classifiers. Selection of appropriate classifier to solve the problem of gestures recognition is crucial. Based on studies presented in this paper it can be concluded that the decision should fall on the SVM classifier. It should be emphasized however, that results could be slightly different for different sets of gestures or other selected classifiers parameters, but taking into account specific nature of the problem and carefully conducted study by authors, the result of them can be considered as representative for a given research problem.

Also, according to the research presented in this paper, only 16 features are enough to achieve results that are about 1.5%-3% worse than using full data representation. This means that it is possible to reduce data set size about 7-8 times for slightly lower and probably unnoticeable cost of the classification accuracy.

Authors tested selected classifiers and found the best one that fits gesture recognition problem. Then, using this classifier, authors proved that it is possible to reduce the number of data set dimension using different feature data representation. The minimal number of features which gives satisfying result was also found for the data set used in this research.

Fig. 1 .

 1 Fig. 1. Cave3D experimental setup consists of 3 screens with 3D projectors that are surrounding the user.

ai

  Each axis, all of the axes

Fig. 2 .

 2 Fig. 2. Incorrect recognition of opening bracket gesture as different decision classes

Fig. 3 .

 3 Fig. 3. Classification accuracy referring to the number of dimensions

Fig. 4 .Fig. 5 .

 45 Fig. 4. Classification accuracy referring to the number of dimensions -parameter optimization

Table 3 .

 3 Results of measurements obtained using selected classifiers

		SVM	NN	RBF LMT
	Average classification accuracy	95.85 92.74 92.16 90.04
	Mean standard deviation of the accuracy 3.74	5.60	6.00	6.11
	Calculations Time	207.41 21819.19 201.23 5630.90

Table 5 .

 5 Comparison of relative data representation and feature data representation classification accuracy

	Kernel Function Relative data [%] Features [%]
	Linear	95.01	94.15
	Polynomial	95.36	94.15
	Sigmoid	95.46	77.90
	RBF	95.69	92.85
	Wavelet	95.85	93.11

It can be done by clicking ,,start recognition" and ,,end recognition" in our software. It can be done, for example, with a help of the operator, who can decide when are start and finish moments and that method was used in the data collecting process.

Acknowledgment

This work was supported by the grant S/WI/1/2013 from Bialystok University of Technology founded by Ministry of Science and Higher Education.


Ezzeddine Fatnassi

Hadhami Kaabi

A multi-agent system model for the Personal Rapid Transit system

Keywords: Multi-agent system modeling, On demand transportation system, Pubic Transportation, Simulation

This research concerns a routing and dispatching problem in the context of the on-demand Personal Rapid Transit transportation system. The objective of the problem is to efficiently optimize the total empty movement related to the vehicles as well as the waiting time of passengers in a dynamic settings. To achieve this, a multi-agent model is developed to manage efficiently the Personal Rapid Transit system. The proposed model involves three types of agent as well as the implementation of an efficient decentralized management strategy in order to handle demand of the passengers. Tests are made on a realistic use'case and results reveal the viability of the proposed model and strategy.

Introduction

Personal Rapid transit (PRT) is an on-demand urban transit transportation system. It is generally organized in a fully connected network' shape that covers some parts of a large urban area, or a multi-terminal airport. The network is composed by a set of PRT'stations and dedicated guideways.

The system is fully automated. In fact, the PRT uses a set of driverless electric vehicles (i.e. system controlled) that move along a set of dedicated elevated guideways. This feature allows the separation of the PRT traffic from the conventional urban traffic. PRT vehicles could carry an individual passenger or a small group of individuals up to 6 persons. PRT offers a personalized transportation service as the users of such a system determine on their own the departure time, the departure and the destination of their trip freely. The control system determines based on the current demand the vehicle that should satisfies the demand of users as well as its route and movements within the PRT' network.

The PRT control system needs also to determine the set of empty moves of vehicles within the system. In fact, as the demand from a PRT station does not equal to the demand to this specific PRT station, the PRT control system would need to balance the flow of empty available vehicles in order to meet perfectly the demand of its users while minimizing their waiting time as well as the total energy consumption of the system. This problem is known in the literature by the empty vehicle redistribution problem. The reader should refer to [START_REF] Lees-Miller | Empty vehicle redistribution for personal rapid transit[END_REF] for more details about this problem.

In the literature, many algorithms have been developed for the empty vehicle management of PRT' vehicles which focused mainly on the optimal reallocation of the empty vehicles within the system. In fact, this strategy could significantly reduce the waiting time of passengers within the PRT system by increasing the set of empty vehicles displacement. Generally, reallocation algorithms to manage empty moves of PRT vehicles are based on the available historical data related to the incoming of passengers as well as the estimation and prediction of future demands. These approaches use a form of a centralized data base containing past demand and historical data. Due to the central repository, these algorithms are implemented in a centralized manner which they mainly refer to the empty vehicle reallocation. Consequently, these algorithms are hard to be developed in a distributed decentralized way.

Based on this context, implementing simulation tools could be useful in order to analyze and implement effective empty vehicles strategies for PRT system. In fact, simulation could be seen as an abstraction of a complex system in order to study its behavior. In the literature, there exists several simulation approaches such as discrete event simulation, dynamic system and agent-based simulation approach (ABS).

Recently, an increasing interest on using multi-agent systems for innovation transportation applications have been proposed in the literature. In fact, Multi agent systems is a very convenient way to model complex urban transportation system composed of a large number of homogenous and heterogeneous individuals interacting within each other and with their environment. Generally, in this kind of system vehicles are modeled as an autonomous agents which aim to find a sequence of moves in order to optimize their operational cost. However, there are only few works in the literature that proposed efficient algorithms for computing approximate solutions in order to optimize transportation system.

The ABS presents the advantage of being able to study various complex system from the perspective of individual point of view. In the literature, ABS have been implemented and applied to model many logistics and transportation systems [START_REF] Moyaux | Supply chain management and multiagent systems: an overview[END_REF] [START_REF] Wen | Containment of higher-order multi-leader multi-agent systems: a dynamic output approach[END_REF]. Consequently, it would be interesting to implement an ABS based on the context of PRT in order to reduce its empty vehicles movement and waiting time of passengers.

In the literature, several simulation model and dynamic strategies have been implemented for the PRT context. One could note [START_REF] Lees-Miller | Empty vehicle redistribution for personal rapid transit[END_REF] where authors studied to minimize waiting time of passengers. However, these latter works does not consider battery issues related to the electric PRT vehicles.

One could note also [START_REF] Mueller | Simulation-based analysis of personal rapid transit systems: service and energy performance assessment of the masdar city prt case[END_REF]where authors proposed a discrete event simulation approach to model the PRT system. ABS have been proposed within the PRT context in [START_REF] Chebbi | Modeling on-demand transit transportation system using an agent-based approach[END_REF] [5] [START_REF] Daszczuk | Distributed algorithm for empty vehicles management in personal rapid transit (prt) network[END_REF]. However, in [START_REF] Chebbi | Modeling on-demand transit transportation system using an agent-based approach[END_REF] [5] authors focused on the activities related to vehicles rather than the stations and in [START_REF] Daszczuk | Distributed algorithm for empty vehicles management in personal rapid transit (prt) network[END_REF] authors does not consider battery issues related to PRT vehicles.

Based on these gaps in the literature, we propose in this paper a distributed management algorithm and ABS for PRT systems. The novelty of our approach resides on the fact that we model stations in PRT as an independent actors (i.e. Agents) that are capable of making decisions and ask for empty PRT vehicles. In fact, we give a special focus on implementing a decentralized management algorithm where the set of decisions is distributed on the stations rather than the vehicles. This feature offers several advantages:

-Eliminating the need for a central control system as the decisions are made autonomously by the stations. -A high flexibility for the PRT system as it would be able to cope with uncertain and unusual demand and traffic condition.

Consequently, the contributions of this paper is threefold:

-We propose an ABS where stations acts as an independent and autonomous actors in the PRT system. -We propose a decentralized management strategy for minimizing waiting time of passengers and the set of empty moves in the system. -We test our approach based on a realistic case study of Corby in the United Kingdom.

The structure of this paper is as follows. In Section 2, the problem definition is presented. Section 3 explains the proposed ABS as well as the implemented decentralized strategy. The computational results and analysis of our simulation model are presented in Section 4. Finally, Section 5 concludes and gives directions for future research.

Problem Definition

In this section, we present the formal problem definition related to PRT. The proposed problem considers to have a PRT network N with a set of finite PRT stations denoted M . Groups or individual PRT'users come at the different PRT stations to ask a specific transportation service from their current location to a specific PRT'station. We suppose that passengers arrives based on a specific poisson process of rate λ. The transportation requests should be served immediately. Rejection of transportation demand is not allowed in the system. The PRT system has a set of electric driverless vehicles that the system would use to satisfy the transportation demand. The PRT'vehicles are constrained by its limited battery capacity B. This limited battery capacity would allow the vehicle to travel for a limited distance before returning to the charging location to recharge their batteries.

We consider also to have a predefined matrix distance that determine the cost of moving between each pair of stations. The vehicles are initially located at the charging location. The vehicles in the PRT system are driverless that move without any human intervention. Our problem consider to find a set of dispatching decisions in order to satisfy the transportation demand. We should note that dispatching decisions refer to the assignment of a vehicle to a specific transportation request. As soon as the system receives transportation demand, dispatching decisions need to be made as soon as possible in order to reduce the waiting time of passengers and to increase the efficiency of the system. The dispatching decisions within a PRT system should be made while knowing the current state of the network. That is why effective strategies should be made while evaluating several possibilities in order to optimize the current state of the system.

Our problem is a dynamic one. In fact, the information related to the coming of the transportation requests is known gradually as the PRT system serves its passengers. This characteristic represents an important feature to our problem as the driverless vehicles could not serve all the transportation requests at the same time due to the limited battery capacity and fleet size.

The objective of our problem is to find the set of dispatching decisions related to PRT system that would minimize the total energy consumption and the waiting time of passengers. These two objectives are of a high interest as they would increase the efficiency and the appealing of such a transportation system.

The simulation model

In this section, we present the proposed ABS model to tackle the proposed problem related to PRT. For this purpose, we present the multi-agent system modeling of PRT. Then, we present the proposed decentralized strategy.

The multi-agent system modeling of PRT

Generally, coordination in on-demand transportation systems (i.e. PRT) could be in two distinctive forms: i) Centralized in which the central control system tends to improve the performance of the global system by exploring all the different alternatives related to the current situation related to the transportation network by the use of coordination and information sharing. ii) Decentralized in which coordination could be found at an inter-urban zone only, which could causes conflicting practices that need to be managed.

As a result of the high level of transportation service that the PRT aims to offer to its users, PRT could be modeled as a decentralized system in which independent agents could take their own decisions. This feature would ensures a highly reactive system to the upcoming demand of passengers. Consequently, the PRT could be modeled by using multi-agent system modeling approach. Multiagent system modeling approach consists of a set of different agents interacting with each other's in order to solve a specific problem, compete for a finite set of shared resources (i.e. the PRT vehicles) or coordinating with each other in order to avoid conflicts.

In the literature [START_REF] Avci | A multi-agent system model for supply chains with lateral preventive transshipments: Application in a multi-national automotive supply chain[END_REF], the term agent defines a software or a hardware based computer system that has specific characteristics such as reactivity and proactivity, autonomy, and social ability. Muti-agents systems offer the advantage of being simple to implement and understand [START_REF] Wen | Containment of higher-order multi-leader multi-agent systems: a dynamic output approach[END_REF]. Also when the problem and the modeled systems is itself distributed, multi-agent system models offer more flexibility in term of dealing with the different constraints of the simulated system.

As complex systems such the PRT are generally a decentralized and distributed ones with many interactions between its different components, it is rather difficult to model and analyze each possible interaction at the earlier design process of a multi-agent model. In fact, multi-agent systems modeling approach handles this complexity by decomposing the system into smaller and rather simple autonomous agents. Consequently and based on this feature, there is no need to define all the possible control reaction and interaction in the simulated system. Therefore, an autonomous agent in a multi-agent system would act and update its state according to its own environment and interaction with the other different agents. Based on this feature, the complexity of the whole simulated system is reduced [START_REF] Jennings | On agent-based software engineering[END_REF].

In the literature, PRT is considered as a complex and distributed system [START_REF] Chebbi | Reducing the wasted transportation capacity of personal rapid transit systems: An integrated model and multi-objective optimization approach[END_REF]. PRT is composed by different interacting actors and a network of complex subsystems that together provide a high level of transportation service. Thus, PRT can be modeled as a network of agents. Agents in PRT would try to maximize their own gain rather than the whole system gain. Each agents would act autonomously by being able to interact with its dynamic environment and taking pro-active and reactive decisions [START_REF] Moyaux | Supply chain management and multiagent systems: an overview[END_REF]. In this sense, it exists numerous studies that proposed to tackle on-demand transportation systems modeling by the use of a multi-agent system modeling approach.

In [START_REF] Chebbi | Modeling on-demand transit transportation system using an agent-based approach[END_REF] [5], authors proposed to model PRT using multi-agents based approach where vehicles act as an independent agents. In [START_REF] Daszczuk | Distributed algorithm for empty vehicles management in personal rapid transit (prt) network[END_REF], authors proposed to use multi-agent simulation approach for the PRT context where stations act as independent agent but without tackling many hard constraints related to PRT such as the limited distance constraints. Other works on PRT includes discrete event simulation [START_REF] Fatnassi | Evaluation of different vehicle management strategies for the personal rapid transit system[END_REF][9], static energy consumption minimization [START_REF] Fatnassi | Discrete honeybee mating optimization algorithm for the routing of battery-operated automated guidance electric vehicles in personal rapid transit systems[END_REF][10], fleet sizing [START_REF] Chebbi | Optimal fleet sizing of personal rapid transit system[END_REF], network design [START_REF] Zheng | Network design for personal rapid transit under transitoriented development[END_REF], and so on. The novelty on our approach is to consider stations as independent agents while taking into account various constraints and limitation related to the PRT vehicles.

The proposed modeling approach

As we proposed to use Multi-agents simulation approach for our PRT system, one could argue that the driverless vehicles would be used as the only agent types in our model. However, we used in our model three type of agents: i) Vehicles, ii) Passengers, iii) Stations.

This different agents would communicate with each other and their own environment. The passengers agents arrive at specific PRT station and ask to be transported to another PRT station. Consequently, the passengers agents send a transportation request to its current departure station. The transportation request is represented by a triplet: i) Departure station ii) Arrival station iii) Departure time This transportation request would be treated by the specific agent that represents the departure station. In fact, the station agent and based on the transportation demand characteristic would select the best available vehicle agent available at the departure station based on the total traveled distance and the available electric battery charge. Consequently, we could consider that the environment in our simulated system represents all the information available at the different nodes of the network.

In the following subsections, the role of each type of agent is explained.

Vehicle agent

The vehicle agents in our model has four different functions:

-They transport passenger' agents in order to satisfy their transportation requests. -They interact with the station agents in order to know what passengers request they could satisfy. -They interact with the specific charging station agent in order to perform charging operation. -They gather different statistics in order to evaluate the performance of the whole system.

Every vehicle can be in four principal states: waiting empty, moving empty, moving with passengers, charging state.

Passenger agent

The passenger agent is composed of a set of passengers or an individual one with the same departure and destination stations, and whose number does not exceed the capacity of the PRT vehicle in term of number of passengers (e.g. six passengers). This agent interacts with the station agent in order to inform it about its related transportation request. Then, after a vehicle agent pick up the passenger agent it sends a message to the station agent in order to inform it about its waiting time which would be needed to gather statistics related to the system.

Station agent

In our simulation model, the station agents are the most important ones. In fact, the dispatching decisions related to the PRT system are implemented as an integral part of the station agents. Thus, the station agents would receive all the different passengers arriving at their locations. Each station agent would evaluate the available transportation requests. Based on the current situation of the system, the station agent would interact with the vehicles agent available at its location in order to perform the transportation request. The station agent would choose from the available empty vehicle the best one able to perform the transportation request. This decision is based on the traveled distance related to the transportation request as well as the available electric energy in the different vehicles. If no empty vehicles are available, the station agent would communicate with the other station agents in order to ask for a specific number of vehicles. For example, if a station agent has four waiting transportation requests that could not be satisfied by the available vehicle agent in the station, it would ask all the other stations agents to send four different empty PRT vehicles. The different other station agents would evaluate the demand and would accept or reject the demand in empty vehicles. In the case of acceptance a conflict could arise if more than one station would satisfy the need of empty vehicles of a specific station agent. In this case, the station agent asking for empty vehicle would accept only the vehicles coming from the closest distance possible. Finally, we should note that periodically the station agent would evaluate the available empty vehicle agent available at its location. If a vehicle has waited empty for too long, it would be sent to the charging location.

Details about PRT station agents are shown in Algorithm 1. We should note that station agents treat the transportation demand based on the principle of first come first serve in order to minimize the total waiting time. Finally, we should note from Algorithm 1 that a proactive behavior is implemented as a part of the general behavior of the station agent. In fact, we propose that each station should have a fixed number of empty vehicle waiting for passengers to come in order to reduce the total waiting time of passengers. Periodically and after serving the different waiting passengers, the station agent would look for the number of empty waiting vehicles in its current location and ask other station agents to send empty vehicles if the station is at a deficit of empty vehicles (e.g. number of empty vehicles is less than the reserve value).

Algorithm 1 Station Agent Algorithm()

Computational Results

The proposed simulation model was written in C++ language with the intention of analyzing the proposed decentralized strategy. The written computer program was written with the intention to predict the service level for the system using several statistics related to the waiting time of passenger, consumed energy, etc.

In this section, we present the computational results related to our multiagent model for the PRT system. For the testing bed, we choose the one from the literature [START_REF] Fatnassi | Two strategies for real time empty vehicle redistribution for the personal rapid transit system[END_REF]. The testing bed is based on the Corby real use case which represents a realistic PRT network. The network is composed of 15 stations and 4 depots. As we are treating the case of a single depot topology, we proposed to generate four different networks where each one of them contain only one different depot.

As for the simulated scenarios related to the PRT transportation requests, we used scenarios adapted from the literature [START_REF] Chebbi | Reducing the wasted transportation capacity of personal rapid transit systems: An integrated model and multi-objective optimization approach[END_REF]. More specifically, the generated scenarios are based on the data available in the ATS/CityMobil software1 . The ATS/CityMobil presents the rates λ ij of a poisson process for traveling from any station i to any other station j in the Corby network. We should note that λ ij ∈ [0.789, 17.902]. We used in this paper 5 different scenarios. Also, we supposed that the total number of fleet is equal to 200 vehicles. The reserve value related to the number of empty vehicles that should be present in each station is equal to 2 vehicles. We should note that we supposed that the battery would make the vehicles run for 40 minutes before to be needed to recharge it [START_REF] Chebbi | Reducing the wasted transportation capacity of personal rapid transit systems: An integrated model and multi-objective optimization approach[END_REF]. Results are presented in Table 1. Table 1 presents the percentage of empty movements as well as the full movement (movement of a vehicles with passengers) of the total movement of vehicles in the system. We also present the mean waiting time of passengers for each scenario in minutes (Min). We should note that the waiting time of a passengers is the difference between the arrival time of the passengers to their arrival station and the time of the fulfillment of their demand.

Results shows the good performance of our decentralized strategy as we found a mean waiting time of 3.847 minutes and a mean empty movement of 47.677 % which means that the vehicles move in 47.677 % empty without taking passengers.

Conclusions

In this study, a multi-agent system model is proposed for the PRT system. Unlike the majority of the previous studies, a decentralized management strategy with complex relationships between the different agents is proposed. This study differs from the previous studies for PRT in that it considers stations as an autonomous agent as well as battery issues within a multi agent simulation model. The validity and reliability of the proposed model are evaluated through simulation experiments by using a real world application related to an urban use case from the United Kingdom. The next step of this study is to integrate the proposed model within a decision support system related to PRT in order to evaluate the best strategy among many others for the system. In future studies, the effect of other external factors on the performance of the different agents could be studied Finally, the development of learning algorithms for the stations and vehicles agents could be a promising field of study.

Table 1 :

 1 Results of the proposed strategyNetwork Scenario waiting Time in Min Empty Movement in % Full Movement in %

	1	1	2.552	37.634	62.366
	1	2	2.920	38.725	61.275
	1	3	3.145	40.158	59.842
	1	4	2.931	41.787	58.213
	1	5	2.827	40.840	59.160
	2	1	3.286	43.977	56.023
	2	2	3.891	44.474	55.526
	2	3	3.610	43.713	56.287
	2	4	3.981	47.605	52.395
	2	5	3.816	46.748	53.252
	3	1	4.338	54.576	45.424
	3	2	4.599	52.304	47.696
	3	3	4.039	51.145	48.855
	3	4	4.478	52.770	47.230
	3	5	4.750	55.088	44.912
	4	1	4.143	51.331	48.669
	4	2	4.770	51.513	48.487
	4	3	4.634	53.284	46.716
	4	4	4.295	53.729	46.271
	4	5	3.936	52.134	47.866
	Average		3.847	47.677	52.323

ATS/CityMobil PRT source: http://www.ultraprt.com/prt/implementation/simulation/


Tadeusz Nowicki
email: tadeusz.nowicki@wat.edu.pl

Robert Waszkowski
email: robert.waszkowski@wat.edu.pl

Productivity oriented cooperative approach to scheduling IT project tasks

Keywords: IT project management, scheduling, linear programming

Task execution duration depends on the employee who performs the task. Specifically in IT projects, an experienced employee can perform assigned tasks several times faster than a novice worker can. Preparing the schedule, project manager should take into account individuals' productivity determined by analyzing historical data of tasks implementation. Consequently, measured productivity is used in preparing the schedule in an optimal manner (minimizing the time needed to complete project tasks by a team of workers with different skills). As an extension of previous studies the authors formulate a linear programming problem including the possible cooperation of employees with tasks execution. The result of the conducted research is a complete package supporting project managers in determining productivity and scheduling.

Introduction

One of the most important task for project managers is to prepare the schedule. To arrange an optimal schedule the manager must have knowledge of tasks structure and their workload. Tasks structure is based on the execution order, determining predecessors and successors of each task. Workload is defined as the standard time needed to complete each task [START_REF] Brucker | Scheduling algorithms[END_REF][START_REF] El-Rewini | Task Scheduling in Parallel and Distributed Systems[END_REF][START_REF] Janiak | Scheduling in computer and manufacturing systems[END_REF][START_REF] Nowicki | Stochastic bi-objective Scheduling Problem in a Multiprocessor Computer System[END_REF][START_REF] Pinedo | Scheduling. Theory, algorithms and Systems[END_REF][START_REF] Pinedo | Scheduling. Planning and scheduling In manufacturing and services[END_REF][START_REF] Pochet | Production planning by mixed integer programming[END_REF][START_REF] Simchi-Levi | The Logic of Logistics[END_REF][START_REF] Sinnen | Task scheduling for parallel systems[END_REF]. In many works the authors consider the situation where co-operators are allowed [START_REF] Chen | Supply Chain Scheduling: Conflict and Cooperation in Assembly Systems[END_REF][START_REF] Calleja | Job scheduling, cooperation, and control[END_REF][START_REF] Chryssis | Work-Competitive Scheduling for Cooperative Computing with Dynamic Groups[END_REF]. However, it is not assumed that co-operation is not additive. In addition, co-operation does not reduce the costs, but shorten the execution time of a set of tasks. In this paper is considered exactly such a problem.

In fact, duration of the task execution depends on the employee who performs the task. In many situations, experience and skills of workers can result in significant differences in the execution time of tasks. According to the conducted research, an experienced employee can perform assigned tasks several times faster than a novice worker.

The manager usually has a team composed of both experienced and novice staff. Therefore, it is crucial which worker will perform a given task. The correct assignment of the task performers can result in a significant shortening duration of the overall project.

In practice, the knowledge about the productivity of each team member increases with the development time. If the manager is able to measure productivity, he can reschedule next stages of the project in a way to achieve optimal results. Therefore, the toolkit of a project manager must be equipped with computer-aided tools, allowing him/her to prepare the schedule as a result of a defined optimization problem. Preparing the schedule project manager should take into account individuals' productivity determined by analyzing historical data of tasks implementation. Consequently, measured productivity is used in preparing the schedule in an optimal manner (minimizing the time needed to complete project tasks by a team of workers with different skills).

In the article we assume scheduling of the project on the understanding that employees can cooperate and divide daily working time between tasks. It means that a task can be performed by more than one worker at the same time and a worker can perform more than one task at a time.

MATHEMATICL MODEL

The problem formulation

We assume that: 𝑅 = {1,2,3, … , 𝑟, … , 𝑅} -is a set of numbers of the project task types 𝑍 = {1,2,3, … , 𝑧, … , 𝑍} -is a set of numbers of project tasks The types of project tasks, that have to be performed, can be described by the vector:

𝑅 𝑍 = (𝑟 1 , 𝑟 2 , … , 𝑟 𝑧 , … , 𝑟 𝑍 )

where 𝑟 𝑧 -is the number of the type of the z-th task, 𝑟 𝑧 ∈ 𝑅, 𝑧 ∈ 𝑍 The task performance time is defined as an average time needed to perform the task by a worker without special skills. This time is called the reference time. The reference time is used to determine the task performance time of more qualified worker. The reference times for project tasks can be described by the vector:

𝐶 𝑤 = (𝑐 1 𝑤 , 𝑐 2 𝑤 , … , 𝑐 𝑧 𝑤 , … , 𝑐 𝑍 𝑤 ), 𝑧 ∈ 𝑍
The project tasks can include information about the need to perform other tasks before you started current task. Predecessors can be described by a matrix:

𝐷 = [𝑑 𝑖𝑗 ] 𝑧×𝑧
zz d       𝑧 1 , 𝑧 1 ∈ 𝑍
For the description of workers we assume that 𝑃 = {1,2,3, … , 𝑝, … , 𝑃}set of number of employees, to be taken into account in the tasks execution. The suitability for performance of specific types of tasks can be defined for each employee. Let it be described by following matrix 𝑈 = [𝑢 𝑝𝑟 ] 𝑃×𝑅 where 1 -when the p employee is able to accomplish the task of type r 0 -otherwise

pr th u       𝑝 ∈ 𝑃, 𝑟 ∈ 𝑅
The productivity of individual employees is different during the performance of different types of tasks. The difference in productivity of a given employee at a particular type of task is defined by a coefficient 𝛽, that represents how many standard time units assigned to perform a particular task the worker performs in one unit of his working time. Thus, the effectiveness of workers in the tasks of different types is defined by vector

𝛽 𝑝 = (𝛽 𝑝1 , 𝛽 𝑝2 , … , 𝛽 𝑝𝑟 , … , 𝛽 𝑝𝑅 ), 𝑝 ∈ 𝑃
Of course, if the p-th employee is not suitable for the task of r-type, which is defined in the matrix 𝑈: 𝑢 𝑝𝑟 = 0, then there is also equality 𝛽 𝑝𝑟 = 0.

Taking into account the productivity of the employee, the time for the task by the p-th worker (provided that the employee p suited to this type of task, namely 𝛽 𝑝𝑟 > 0, 𝑢 𝑝𝑟 = 1) is:

𝑐 𝑝𝑧 = 𝑐 𝑧 𝑤 𝛽 𝑝𝑟 𝑧 where 𝑝 ∈ 𝑃, 𝑧 ∈ 𝑍, 𝑟 𝑧 ∈ 𝑅 𝑧 , 𝑐 𝑧 𝑤 ∈ 𝐶 𝑤

Decision variables

The decision relating to the project schedule is described by matrix-vector: CC: task precedence must be taken into account The condition that the task 𝑧′′ must precede task 𝑧′ can be written as follows:

(𝑋,
𝜏 𝑧 ′ ≥ 𝑑 𝑧 ′ 𝑧 ′′ • ( 𝜏 𝑧 ′′ + ∑ 𝑥 𝑝𝑧 ′′ • 𝑐 𝑧 ′′ 𝑤 𝛽 𝑝𝑟 𝑧 ′′ 𝑃 𝑝=1 𝑢 𝑝𝑟 𝑧 ′′ ≠0 ) (CC)
for 𝑧 ′ , 𝑧 ′′ ∈ 𝑍, 𝑧 ′ ≠ 𝑧 ′′ CD: the worker cannot work more than 𝒍 𝒑 (i.e. 8) hours per day To check the condition that the employee does not work more than eight hours a day, for each of the individual tasks, check for all tasks occurring at the time of its initiation, if the amount of time spent per day on their implementation does not exceed eight hours.

To select tasks that are performed at the start time of another task it should be noted that the task 𝑧′ continues at the start time of the task𝑧′′ if each of the following inequalities is true:

{ 𝜏 𝑧′ ≤ 𝜏 𝑧′′ 𝜏 𝑧′ + 𝑐 𝑧′ ≥ 𝜏 𝑧′′ , 𝑧 ′ , 𝑧 ′′ ∈ 𝑍 (𝐶𝐷𝐴) (CDB)
Where inequality (CDA) means that the task 𝑧′ begins earlier than the task 𝑧′′ and inequality (CDB) means that the task 𝑧′′ begins at the time the task 𝑧′ lasts. The way to check if the inequality ∑ 𝑎 𝑗 𝑥 𝑗 ≤ 𝑏 𝑗 is satisfied in [START_REF] Waszkowski | Methods and tools for productivity evaluation in IT projects[END_REF]. Inequality 𝜏 𝑧′ ≤ 𝜏 𝑧′′ is equal to 𝜏 𝑧′ -𝜏 𝑧′′ ≤ 0, and the inequality (CDA) becomes:

{ 𝜏 𝑧′ -𝜏 𝑧′′ + 𝑀 ⋅ 𝑒 𝑧′𝑧′′ 1 ≤ 𝑀 + 0 𝜏 𝑧′ -𝜏 𝑧′′ -(𝑚 -𝜀) ⋅ 𝑒 𝑧 ′ 𝑧 ′′ 1 ≥ 0 + 𝜀 , 𝑧 ′ , 𝑧 ′′ ∈ 𝑍 (𝐶𝐷𝐴1) (CDA2)
where 𝑚 and 𝑀 are, respectively, the lower and upper bound of the expression (𝜏 𝑧′ -𝜏 𝑧′′ ) and 𝜀 is a small number that causes the failure of inequality.

If the set of all possible occurrences of the expression (𝜏 𝑧′ -𝜏 𝑧′′ ) is defined as:

𝑊 = {(𝜏 𝑧 ′ -𝜏 𝑧 ′′ ): 𝑧 ′ , 𝑧 ′′ ∈ 𝑍}
then the lower and upper bound should be considered as such values of 𝑚 and 𝑀, that satisfy the inequalities:

{ 𝑚 ≤ 𝑦 𝑀 ≥ 𝑦 , 𝑦 ∈ 𝑊
After applying these transformations indicator variable 𝑒 𝑧′𝑧′′ 1 = 1, when the inequality. (𝐶𝐷𝐴) is satisfied. The way to check if the inequality ∑ 𝑎 𝑗 𝑥 𝑗 ≥ 𝑏 𝑗 is satisfied in [START_REF] Waszkowski | Methods and tools for productivity evaluation in IT projects[END_REF]. Inequality 𝜏 𝑧′ + 𝑐 𝑧′ ≥ 𝜏 𝑧 ′′ can also be written as 𝜏 𝑧′ -𝜏 𝑧′′ + 𝑐 𝑧′ ≥ 0. It should be noted that the sum is over all 𝑧, also for the case where 𝑧 ′ = 𝑧′′. It is a non-linear inequality. Linearization method for such inequalities is described in [START_REF] Waszkowski | Methods and tools for productivity evaluation in IT projects[END_REF]. Let 𝑦́𝑝 𝑧′𝑧′′𝑙 = 𝑒 𝑧′𝑧′′ 1 ⋅ 𝑒 𝑧′𝑧′′ 2 ⋅ 𝑥́𝑝 𝑧′𝑙 . We then have:

∑ ∑ 𝑦́𝑝 𝑧′𝑧′′𝑙 𝑙 𝑝 𝑙=1 𝑍 𝑧 ′ =1 ≤ 𝑙 𝑝 , 𝑝 ∈ 𝑃, 𝑧 ′′ ∈ 𝑍 (CDC)
With additional constraints defined as:

{ 𝑒 𝑧 ′ 𝑧 ′′ 1 + 𝑒 𝑧 ′ 𝑧 ′′ 2 + 𝑥́𝑝 𝑧 ′ 𝑙 -𝑦́𝑝 𝑧 ′ 𝑧 ′′ 𝑙 ≤ 2 𝑒 𝑧 ′ 𝑧 ′′ 1 + 𝑒 𝑧 ′ 𝑧 ′′ 2 + 𝑥́𝑝 𝑧 ′ 𝑙 -3𝑦́𝑝 𝑧 ′ 𝑧 ′′ 𝑙 ≥ 0 (𝐶𝐷𝐷1) (CDD2) 𝑝 ∈ 𝑃, 𝑧 ′ , 𝑧 ′′ ∈ 𝑍, 𝑙 ∈ 𝐿
After this transformation, we obtain the linear inequalities.

2.4

Objective function

We have the objective function: , 𝑧 ∈ 𝑍 (CX)

𝐹(𝑋,

Optimization problem

Accordingly, the full optimization problem is as follows: min 𝑋,𝑇,𝑋 ́𝑔 subject to

∑ 𝑢 𝑝𝑟 𝑧 𝑥 𝑝𝑧 = 1, 𝑧 ∈ 𝑍 𝑃 𝑝=1 (CA) ∑ 𝑢 𝑝𝑟 𝑧 𝑥 𝑝𝑧 ≥ 1, 𝑝 ∈ 𝑃 𝑍 𝑧=1
(CB)

𝜏 𝑧 ′ ≥ 𝑑 𝑧 ′ 𝑧 ′′ • (𝜏 𝑧 ′′ + ∑ 𝑥 𝑝𝑧 ′′ • 𝑐 𝑧 ′′ 𝑤 𝛽 𝑝𝑟 𝑧 ′′ 𝑃 𝑝=1 𝑢 𝑝𝑟 𝑧 ′′ ≠0 ) (CC), 𝑧 ′ , 𝑧 ′′ ∈ 𝑍, 𝑧 ′ ≠ 𝑧 ′′ { 𝜏 𝑧 ′ -𝜏 𝑧 ′′ + 𝑀 ⋅ 𝑒 𝑧 ′ 𝑧 ′′ 1 ≤ 𝑀 + 0 𝜏 𝑧 ′ -𝜏 𝑧 ′′ -(𝑚 -𝜀) ⋅ 𝑒 𝑧 ′ 𝑧 ′′ 1 ≥ 0 + 𝜀 (𝐶𝐷𝐴1) (𝐶𝐷𝐴2) , 𝑧 ′ , 𝑧 ′′ ∈ 𝑍 { 𝜏 𝑧 ′ -𝜏 𝑧 ′′ + ∑ 𝑐 𝑧 ′ 𝑤 𝛽 𝑝𝑟 𝑧 ′ ⋅ 𝑥 𝑝𝑧 ′ 𝑃 𝑝=1 𝛽 𝑝𝑟 𝑧 ′ ≠0 + 𝑚 ⋅ 𝑒 𝑧 ′ 𝑧 ′′ 2 ≥ 𝑚 + 𝑏 𝜏 𝑧 ′ -𝜏 𝑧 ′′ + ∑ 𝑐 𝑧 ′ 𝑤 𝛽 𝑝𝑟 𝑧 ′ ⋅ 𝑥 𝑝𝑧 ′ 𝑃 𝑝=1 𝛽 𝑝𝑟 𝑧 ′ ≠0 -(𝑀 + 𝜀)𝑒 𝑧 ′ 𝑧 ′′ 2 ≤ 𝑏 -𝜀 (𝐶𝐷𝐵1) (𝐶𝐷𝐵2) , 𝑧 ′ , 𝑧 ′′ ∈ 𝑍 ∑ ∑ 𝑦́𝑝 𝑧′𝑧′′𝑙 𝑙 𝑝 𝑙=1 𝑍 𝑧 ′ =1 ≤ 𝑙 𝑝 , 𝑝 ∈ 𝑃, 𝑧 ′′ ∈ 𝑍 (CDC) { 𝑒 𝑧 ′ 𝑧 ′′ 1 + 𝑒 𝑧 ′ 𝑧 ′′ 2 + 𝑥́𝑝 𝑧 ′ 𝑙 -𝑦́𝑝 𝑧 ′ 𝑧 ′′ 𝑙 ≤ 2 𝑒 𝑧 ′ 𝑧 ′′ 1 + 𝑒 𝑧 ′ 𝑧 ′′ 2 + 𝑥́𝑝 𝑧 ′ 𝑙 -3𝑦́𝑝 𝑧 ′ 𝑧 ′′ 𝑙 ≥ 0 (𝐶𝐷𝐷1) (𝐶𝐷𝐷2) , 𝑝 ∈ 𝑃, 𝑧 ′ , 𝑧 ′′ ∈ 𝑍, 𝑙 ∈ 𝐿 𝒈 ≥ 𝝉 𝒛 + 𝒄 𝒛 𝒘 ∑ 𝜷 𝒑𝒓 𝒛 ⋅ 𝒙 𝒑𝒛 ⋅ 𝒙 ̅ 𝒑𝒛 𝒍 𝒑 𝑷 𝒑=𝟏 𝛃 𝐩𝐫 𝐳 ≠𝟎 , 𝒛 ∈ 𝒁 (𝐂𝐗) 3

Comparison of scheduling and without scheduling cooperation

Below provides results of sample solutions of the task of determining the schedule for versions with and without the cooperation of employees [START_REF] Brucker | Scheduling algorithms[END_REF][START_REF] El-Rewini | Task Scheduling in Parallel and Distributed Systems[END_REF][START_REF] Janiak | Scheduling in computer and manufacturing systems[END_REF][START_REF] Nowicki | Stochastic bi-objective Scheduling Problem in a Multiprocessor Computer System[END_REF][START_REF] Pinedo | Scheduling. Theory, algorithms and Systems[END_REF][START_REF] Pinedo | Scheduling. Planning and scheduling In manufacturing and services[END_REF][START_REF] Pochet | Production planning by mixed integer programming[END_REF][START_REF] Simchi-Levi | The Logic of Logistics[END_REF][START_REF] Sinnen | Task scheduling for parallel systems[END_REF]. The solution of the same problem in two versions gives you the opportunity to direct comparison of results.

The problem with no cooperation is described in detail in [START_REF] Nowicki | The method for solving productivity oriented scheduling problem[END_REF]. Let us compare the scheduling results concerning cooperation possibility described in the current article with the results based on the scheduling model described in [START_REF] Nowicki | The method for solving productivity oriented scheduling problem[END_REF].

For evaluation of the method for determining the optimal allocation of workers to the tasks let us consider the following case. Let 3 equally complex design tasks will be performed by 2 employees of equal productivity. Individual tasks do not depend on each other, and so they can be performed at the same time and in any order. The workload for each task is 8 hours, and the productivity of each worker is 1.

Case #1. Scheduling with no cooperation

Let us consider the case where the cooperation of employees in carrying out the task is not allowed. The results of the calculations for such case is shown in the following table and is described in the Gantt chart and resource load chart. On the resource load chart, it is shown the usage of the two employees labeled with different colors. The upper course of the graph for the selected worker means that the worker is working on a task, the lower -means that an employee at a given time is not used for the implementation of any task.

Case #2. Scheduling with cooperation

Let us consider the case where the cooperation of employees in carrying out the task is allowed.

The results of the calculations for such case is shown in the following table and is described in the Gantt chart and resource load chart. Just like before, on the resource load chart, it is shown the usage of the two employees labeled with different colors. The upper course of the graph for the selected worker means that the worker is working on a task, the lower -means that an employee at a given time is not used for the implementation of any task.

Assuming the cooperation opportunities of workers in the implementation of the design tasks, significant reduction of the overall duration time and a better use of resources is achieved. Employees are equally loaded throughout the duration of the project.

Conclusion

The mathematical model followed by formulation of optimization problems has been developed for the purpose of a schedule creation. Productivity of project team members is taken into account in the model. The authors designed and built software that formulates a linear programming problem based on a mathematical model. The problem is then solved using numerical methods. The result of the conducted research is a complete IT solution package supporting project managers in determining productivity and scheduling. As for the further research it is worth to examine the possibility to prepare models for other variants of the problem, as far as to rebuild the model in a way that could use the estimation of the future productivity. Furthermore, the impact of differentiation of the software development processes on the productivity is also worth researching.

2 = 1 ,

 21 when the inequality (CDB) is satisfied. If 𝑙 𝑝 is the number of allowable hours of work per day for a p-th worker, then: 𝑝 , 𝑝 ∈ 𝑃, 𝑧′′ ∈ 𝑍In the further considerations it is necessary to use binary variables. Thus 𝑥́𝑝 𝑧 can be written as: , 𝑝 ∈ 𝑃, 𝑧′′ ∈ 𝑍( * )

Fig. 1 .Fig. 2 .

 12 Fig. 1. Gantt Chart for case #1no cooperation

Fig. 3 .Fig. 4 .

 34 Fig. 3. . Gantt Chart for case #2cooperation

  𝑥́𝑝 𝑧 can also be represented using binary variables 𝑥́𝑝 𝑧𝑙 , and then becomes:

			𝑝 ∈ 𝑃, 𝑧 ∈ 𝑍,
	𝑇 = (𝜏 1 , 𝜏 2 , … , 𝜏 𝑧 , … , 𝜏 𝑍 ),
	𝜏 𝑧 -start time (number of an hour) of the z-th task,
	and
								pz PxZ Xx    
	x	 1, 2,..., means amount of hours during a day,  when p-th worker perfoms z-th task 1 than pz p t l    -if x pz pz t      pz
		  	0 -if x	pz		0
								𝑙 𝑝
								𝑥́𝑝 𝑧 = ∑ 𝑥́𝑝 𝑧′𝑙
								𝑙=1
	2.3	Problem constraints
	CA: each task must be completed by exactly one worker
								𝑃
								∑ 𝑢 𝑝𝑟 𝑧 𝑥 𝑝𝑧 = 1, 𝑧 ∈ 𝑍	(𝐶𝐴)
								𝑝=1
	CB: each worker has to perform at least one task
								𝑍
								∑ 𝑢 𝑝𝑟 𝑧 𝑥 𝑝𝑧 ≥ 1, 𝑝 ∈ 𝑃	(𝐶𝐵)
								𝑧=1
								𝑇, 𝑋 ́)
	where:
								𝑋 = [𝑥 𝑝𝑧 ] 𝑃×𝑍
	and
			x	pz	1 -if the p 0 -otherwise th     	worker will perform z		th	task

Table 1 .

 1 Results for case #1no cooperation

	Task	Workload	[h]	Prede-cessor	Employee assigned	Produc-	tivity	Start time	Duration	[h]	End time
	1	8		1	1	0	8	8
	2	8		2	1	0	8	8
	3	8		1	1	8	8	16

Table 2 .

 2 Results for case #2cooperation

	Task	Workload	[h]	Prede-	cessor	Employee	assigned	Productivi-	ty	Start time	Duration [h]	End time
	1	8			1	1	0	8	8
	2	8			2	1	0	8	8
	3	8			1, 2	1, 1	8	4	12