Abdallah Ben Othman

Jean-Marc Nicod

Laurent Philippe

Veronika Rehn-Sonigo

Abdallah Benothman

Optimal Energy Consumption and Throughput for Workflow Applications on Distributed Architectures

Keywords: Scheduling, workflow applications, energy minimization, fault tolerance, throughput maximization, polynomial complexity

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

In this paper we focus on workflow applications described as Directed Acyclic Graphs (DAGs). An application is mapped on a set of distributed machines and a flow of instances has to be processed. This is the case of systems that continuously input raw data to which several processing stages or tasks must be applied to obtain a final result [START_REF] Subhlok | Optimal mapping of sequences of data parallel tasks[END_REF]. Another example are configurable production systems [START_REF] Tanaka | Development of desktop machining microfactory[END_REF][START_REF] Descourvières | Towards automatic control for microfactories[END_REF]. The system is designed as a collaborative platform of distributed machines. Each machine collaborates with others by performing all the instances of at least one task of the DAG. Illustrations of these contexts are a flow of images generated by a camera that must be processed in several stages or a production flow with several succeeding tasks. The considered tasks are of different types that represent the different processing procedures (e.g., filters, analysis, assembly and so on). When the data processing in the application is substantial, several computers or production cells must be used to be able to process the entire input flow and the problem of scheduling the tasks on the resources becomes complex due to the heterogeneity of the processing times on the resources [START_REF] Rehn-Sonigo | Multi-criteria Mapping and Scheduling of Workflow Applications onto Heterogeneous Platforms[END_REF]. The complexity of the problem may be lowered by considering that each machine only executes one task type thus avoiding costly context changes and cases where a machine executes parts of several tasks [START_REF] Diakité | Assessing new approaches to schedule a batch of identical intree-shaped workflows on a heterogeneous platform[END_REF]. Then the initial problem becomes a mapping problem where task types must be mapped onto machines and the objective function is to find the best possible throughput, i.e., to maximize the number of instances processed per time unit [START_REF] Benoit | Mapping workflow applications with types on heterogeneous specialized platforms[END_REF]. Note that the objective function used in this paper is the period minimizationthe time between two consecutive outputs. The period is the inverse of the throughput, which amounts to the same but is more widely used in workflow system optimization.

This paper adresses the problem of using a dedicated system that continuously executes the same DAG of tasks onto different instances with transient failures that sometimes destroy one instance. In this context the objective is to provide the lowest period for the system output. Application flow execution as image processing may be very energy consuming for large images. In the workflow all execution steps however do not have the same execution cost. Lowering the execution speed of the less loaded resources can substantially reduce the global energy consumption. We thus propose two polynomial algorithms based on a greedy approach that either reach the objective of period minimization for a fixed energy consumption or reach the objective of energy minimization for a fixed period. Furthermore we prove the optimality of both the two approaches. For cases where one of the constraints is not compliant with the optimal solution, we propose an adaptation of our algorithms that provides the Pareto front which links the two optimal solutions -the lowest energy consumption with an optimal period and the lowest period with the optimal energy consumption.

The paper is organized as follows: Section 2 discusses related work. In Section 3 we give a formal definition of the problem. In Section 4 we present and prove several lemmas that are used in Section 5 to define the proposed algorithms. Then, in Section 6, we present the result of the algorithm implementation, in the shape of a Pareto front, for cases where the constraints do not allow to reach the optimal solutions. We conclude the article in Section 7.

Related Work

Nowadays more and more attention is payed to energy consumption for financial and environmental reasons. This tendency has also reached the distributed computing domain [START_REF] Costa | The green-net framework: Energy efficiency in large scale distributed systems[END_REF][START_REF] Niemi | Improving energy-efficiency of grid computing clusters[END_REF][START_REF] Benoit | Performance and energy optimization of concurrent pipelined applications[END_REF]. In the case of flow applications where the global throughput is directed by the lower throughput of the graph, it is not always necessary that all machines run at maximum speed [START_REF] Benoit | Energy-aware mappings of series-parallel workflows onto chip multiprocessors[END_REF]. Several papers define an energy model based on power consumption modes where the processing ca-pabilities depend on the supplied voltage [START_REF] Aydin | Energy-aware partitioning for multiprocessor real-time systems[END_REF][START_REF] Chen | Multiprocessor energy-efficient scheduling for real-time tasks with different power characteristics[END_REF]. Then voltage scaling is used to slow down some of the machines -and as a consequence energy sparedwithout affecting the global throughput [START_REF] Benoit | Power-aware replica placement and update strategies in tree networks[END_REF]. It is thus worth to find the lowest possible speed for each machine for a given throughput or, on the opposite, the best reachable throughput for a given energy consumption.

On the other hand in distributed environments such as GRIDs or microfactories, the risk of task failures cannot be ignored, in particular for long running and communication intensive applications like flow applications. The failures may append for numerous reasons such as network or computing errors, network contention, task complexity and so on. Numerous works on reliability and energy focus on the problem of Dynamic Voltage and Frequency Scaling (DVFS) which leads to more errors when the frequency is scaled down [START_REF] Degalahal | Soft errors issues in low-power caches[END_REF]. This assumption however only lays on the assumption that with low voltage the processor becomes more likely to be pone to errors. Defining a global error model for an entire distributed system however is not so simple as these systems are composed of so many elements, each with their own failure model. For instance, [START_REF] Zhang | Optimal speed scaling algorithms under speed change constraints[END_REF] uses a model where the reliability of the processor is directly related to the number and span of speed changes. Increasing the speed of computations or/and the processing load can also lead to less reliable systems as it is shown on real HPC in-production systems [START_REF] Schroeder | A large-scale study of failures in high-performance computing systems, Dependable and Secure Computing[END_REF], or to DRAM errors [START_REF] Schroeder | Dram errors in the wild: a large-scale field study[END_REF]. [START_REF] Nightingale | Cycles, cells and platters: an empirical analysisof hardware failures on a million consumer pcs[END_REF], analyzing a large database of failure in PC systems, suggests that "one can minimize the likelihood of failure over a given time period by operating at the slowest CPU speed sufficient to achieve desired performance". Based on this observation, we assume in this paper that optimizing the energy consumption of the system by decreasing its speed leads to decrease the fault rate in addition to period minimization. In this context we propose two algorithms that minimize either the energy consumption for an optimal period or find the lowest period for a minimal energy consumption. Note that the antagonism between reliability and machine speed induces the complexity of the problem and, in particular, the properties set in section 4.

Framework

In this section we formally define the application, platform and energy models and our optimization objective.

Application Model

We consider a workflow application that is running during infinite or long time. The application is modeled as a directed acyclic graph (DAG) G(T, D), with T = {T 1 , . . . , T n } the tasks of the application and D ⊂ T × T the dependencies between the tasks (see Figure 1). Data sets enter the graph at the source task and traverse the graph from one task to another before producing a final result at the sink task. A weight w i is associated to each task T i that corresponds to the amount of work to be done to perform the task.

Platform and Execution Model

The platform is modeled as a set M = {M 1 , . . . , M p } of p machines fully interconnected. Each machine has input and output communication buffers to store temporary data. We assume that the communication times are shorter than the computation times so that, thanks to the data buffering, the former are covered by computations and thus can be neglected.

The tasks are statically allocated to machines according to an allocation function a such that a(i) = u, i.e., all data instances that enter task T i are performed by machine M u . Note that in this work we assume that the mapping is already defined thanks to mapping algorithms as defined in [START_REF] Benoit | Mapping workflow applications with types on heterogeneous specialized platforms[END_REF] and we concentrate on period and energy optimization of a given mapping.

A machine M u runs at different speed levels l u (l u ∈ {0, 1, 2, . . . , max(l u )}) with an associated slow down factor α lu u ∈ [1, +∞). Note that M u runs at its highest speed, noted s u , for level l u = 0. The system configuration L is given by vector L = (l 1 , l 2 , . . . , l u , . . . , l p ) that describes the speed level of each machine.

Tasks are subject to transient failures. In case of failure, the current data is lost and the task starts to process the next data. The failure rate is defined for each task as the percentage of failures. For a task T i , allocated to machine M u , we assume that the failure rate f lu i depends on the task and on the machine speed level l u . We also assume that the failure rate increases with the machine speed:

f lu i < f l ′ u i with l u > l ′ u .
It comes that if machine M u performs x lu i input data sets with task T i , it outputs (1-f lu i )x lu i data sets due to failures. Considering L, the configuration of the platform, it is possible to compute x lu i backwards for each data output of the application. If task T i has only one outgoing edge (T i , T j ) within the DAG, x lu i =

x lu j 1-f lu i (see Figure 2 for an example). If the task T i has several outgoing edges (T i , T j ) within the DAG, x lu i = (Ti,Tj )∈D

x lu j 1-f lu i .
Thus x lu i is the average number of data sets that machine M u has to perform with task T i so as to output at least one result data set out of the system.

Example of the Platform and Execution Model

To clarify the above stated platform and execution model, we consider the application given in Figure 2. To keep the example simple, we suppose that task T i is mapped onto machine M u with i = u and that each machine runs at is lowest speed level. Hence task T 1 is mapped onto machine M 1 which is running at a level l 1 . The failure rate of task T 1 accordingly depends on l 1 and we have f l1 1 = 1/6. The same holds for the other tasks. Figure 3: The acceleration of machine M 2 implies a higher number of input data sets at the application entry.

We suppose to have the failure rates indicated in Figure 2. We can now compute the necessary amount of data sets that each task needs as input to be able to produce at least one result out of the system (x out = 1). As indicated earlier, the computation is done backwards and we get

x l4 4 = 1 1-f l 4 4
x out = 1.5.

We now suppose that machine M 2 has two possible speed levels l 2 and l ′ 2 , where l ′ 2 is the accelerated level (l ′ 2 < l 2 ). The associated failure rate for level

l ′ 2 is f l ′ 2 2 = 2/5. If machine M 2 switches to level l ′ 2
, the x lu i values have to be recomputed in consequence and you can see the new configuration in Figure 3.

Throughput/Period Model

We define the platform throughput as the number of data outputs per time unit. We define the period of the platform as the inverse of the throughput: the period defines the maximum duration between the output of two consecutive data outputs. As we already know both the number of tasks that have to be performed to output at least one data set and the mapping of tasks to machines, we can compute the period of each machine of the platform. The task period p lu i is the time to perform x lu i instances of each task T i mapped onto machine M u :

p lu i = x lu i × wi×α lu u su
. Then the machine period p lu u on M u is:

p lu u = Ti|a(i)=u p lu i = Ti|a(i)=u x lu i × w i × α lu u s u
The application period on the platform is the longest period over all machines in configuration L:

P (L) = max Mu∈M (p lu u )
We define the critical machine M c as the machine with the longest period that determines the application period, i.e., P (L) = p lc c . We denote M c (L) one critical machine of the configuration L.

Energy Model

The energy consumption E(L) of the platform in configuration L is the sum of the energy consumption E L (u) of each machine M u that performs at least one task of the graph. The energy

E L (u) = E L stat (u) + E L dyn (u) is the sum of E L stat (u)
, the static part of energy consumed when machine M u is in service, and E L dyn (u), the dynamic part of energy consumed when the machine performs its tasks [START_REF] Benoit | Performance and energy optimization of concurrent pipelined applications[END_REF].

E L stat (u) only depends on the duration of the platform usage. The static energy needed to output one data out of the system is thus E L stat (u) = ε u ×P (L) where ε u is the static energy consumption per time unit, P (L) is the period of the application (or the duration between two consecutive outputs) and L is the configuration of the system.

On the other hand, the dynamic part of the energy depends on the machine speed when it performs tasks. Several models are defined in the literature for the dynamic energy consumption of a machine. It is usually represented by a polynomial of at least second degree as in [START_REF] Ishihara | Voltage scheduling problem for dynamically variable voltage processors[END_REF][START_REF] Bansal | Speed scaling to manage energy and temperature[END_REF] or a more general strictly convex and increasing function g of the machine speed as in [START_REF] Aydin | Energy-aware partitioning for multiprocessor real-time systems[END_REF] and [START_REF] Zhang | Optimal speed scaling algorithms under speed change constraints[END_REF]. As in [START_REF] Bansal | Speed scaling to manage energy and temperature[END_REF] we assume here that the energy consumed on machine M u at speed s depends on C en × s βu where β u > 1 and C en > 0. As the speed of machine M u is su α lu u the dynamic energy consumed during one period by machine M u is the sum of the energy consumed to perform all the tasks needed for that period is given by equation 1.

E L dyn (u) = Ti|u=a(i) C en × s u α lu u βu × p lu i (1)

Optimization Objectives

In this paper, we are interested in two objectives. First, we aim at minimizing the period and minimizing the energy consumption for the optimal period. Second, we optimize the energy consumption of our platform while minimizing the period for the optimal energy consumption.

System Properties

In this section we state some important properties for the changing of the system configuration L and we first exhibit the relation between two system configurations L and L ′ . The period of a machine M u in system configuration L ′ can be expressed through the task periods in system configuration L. Based on the platform model, we know that a machine period is the sum of all its task periods, and we can deduce the following relation:

p l ′ u u = Ti|a(i)=u x l ′ u i × w i α l ′ u u s u = Ti|a(i)=u x l ′ u i α l ′ u u x lu i α lu u × p lu i (2)
We now consider the influence of slowing down or accelerating machines.

Lemma 1. When a group of machines is accelerated, the amount of work to output one data set increases.

Proof. Let L and L ′ be two system configurations with l ′ u l u for each machine M u ∈ M , i.e., L ′ has some accelerated machines in comparison to configuration L. We aim at proving that ∀T i ∈ T, x lu i x l ′ u i with a(i) = u. That means the amount of input data sets for task T i is more important in configuration L ′ .

Let M u ∈ M be an accelerated machine whose configuration is set to l ′ u . As l ′ u < l u , by definition of our model,

f lu i < f l ′ u i for all tasks T i ∈ T with a(i) = u and so 1 1 -f lu i < 1 1 -f l ′ u i
. From the definition of the computation of

x lu i , the previous expression implies that the value of x l ′ u i increases on M u . Moreover since these values are computed backwards (Cf. Figure 2 in Section 3.3), this incrementation recursively modifies the x lv j by backwards following the dependency constraints in the group of machines. The global workload of each machine M v , where a(j) = v, thus increases.

Lemma 2. When a group of machines is accelerated, it cannot decrease the period of the other machines.

Proof. Let L and L ′ be two system configurations with l ′ v l v , ∀M v ∈ M , i.e., L ′ has some accelerated machines compared to L. Let M u be a machine with l u = l ′ u . We aim at proving that p lu u p l ′ u u . First, with Lemma 1, we know that for all tasks the amount of work is more important in L ′ than in L:

x lu i x l ′ u i , ∀t i ∈ T . Next, we know that if l u = l ′
u , the acceleration coefficient α is also the same:

α lu u = α l ′ u
u . Hence we have:

∀t i ∈ T s.t. u = a(i) : α lu u x lu i α l ′ u u x l ′ u i
and we get:

∀t i ∈ T s.t. u = a(i) : p lu i α l ′ u u x lu i α lu u x lu i × p lu i
This holds true for all task periods and we can deduce the machine period by summing up over all task periods of a machine M u and with Eq. 2, we prove that the machine period of M u is smaller in configuration L than in L ′ :

p lu u = Ti∈T |a(i)=u p lu i Ti∈T |a(i)=u α l ′ u u x l ′ u i α lu u x lu i × p lu i = p l ′ u u
Corollary 1. The acceleration of another machine than the critical machine cannot decrease the application period.

Proof. Let L and L ′ be two system configurations with l ′ v l v , ∀M v ∈ M , i.e., L ′ has some accelerated machines. Let M c be the critical machine such that p lc c = P (L) and l c = l ′ c . With Lemma 2, we know that the machine period of machine M c is lower (or equal) in L than in L ′ : p lc c p l ′ c c . By definition, we deduce that the period of configuration L is lower than the maximum period in L ′ :

P (L) p l ′ c c = max Mu∈M (p l ′ u u ) = P (L ′ )

Algorithm OptPer

The algorithm OptP er(L) (see Algorithm 1) returns the optimal system configuration resulting from a given system configuration, i.e., the system configuration with the optimal period and the minimal energy consumption for the optimal period. The algorithm starts from an initial configuration L where each machine is set at its maximal slow down level. Then, at each step, the algorithm speeds up the machine M c (L) by reducing its level l c by one. The new configuration is noted L. If the new system configuration period P ( L) is better than the current best period, it is stored in L as the new best system configuration. Then a new critical machine M c ( L) is identified and the algorithm passes to the next step.

Otherwise or if the slow down level of M c ( L) is null ( l c = 0) the algorithm finishes. The number of steps needed to finish this algorithm takes polynomial time. Indeed, in the worst case, the algorithm iterates p × LM AX times, with LM AX = max u (max(l u )) a constant which does not depend on the problem size. At each step, the computation of the necessary amount of the data sets for all of the tasks takes O(n) operations and the complexity of algorithm 1 is

O(p × n).
Algorithm 1: OptP er(L) To prove the optimality of the period returned by this algorithm we first set Lemma 5 and its corollary 2. For that we first define A(L) as the set of system configurations resulting from all possible machine accelerations from the system configuration L. Let L and L ′ be two system configurations.

Mc ← critical machine of L 1 L ← L 2 lc ← lc -1 3 Mc ← critical machine of L

∀L, L

′ : L ′ ∈ A(L) ⇔ ∀u : l ′ u l u (3)
For example, if L = (2, 1):

A(L) = {(2, 1)
, (1, 1), (0, 1), (2, 0), (1, 0), (0, 0)}

We recall that M c (L) is one of the critical machines of the configuration L, i.e., one of the slowest machines of the configuration L. Lemma 5. Let us consider a configuration L and a subset of system configurations L ′ in A(L) where l ′ c = l c with M c a critical machine of the configuration L. Then the period P (L) is smaller than any period P (L ′ ):

∀L ′ ∈ A(L) | l c = l ′ c ⇒ P (L) P (L ′ ) (4)
Proof. From the definition of function A(L) in equation 3 we know that:

∀L ′ ∈ A(L) ⇒ l ′ u l u
And from Corollary 1 we know that if the critical machine is not accelerated, the period cannot decrease. By association we get that for all system configurations L ′ in A(L) with l ′ c = l c the period of configuration L ′ is higher or equal than the period of the configuration L.

As a consequence of Lemma 5, only the configurations in A(L) that increase the speed level of a critical machine M c ( L) can provide a better period for the system. We formalize this property in the following corollary:

Corollary 2. The only configuration that is able to decrease the period of the system from a configuration L is to accelerate a critical machine.

Note that speeding up the critical machine by one level does not always lead to a better period for two reasons. First because speeding up a critical machine does not always lead to improve its own period. This acceleration is however an imposed condition to improve the application period in some cases. Second because there may be several critical machines at the same time, i.e., machines that have the same period, and we must speed up all of them before improving the application period.

Theorem 1. OptP er(L) finds the optimal system configuration L * with the optimal period in A(L), i.e.:

L * = OptP er(L), ∀L ′ ∈ A(L) ⇒ P (L * ) P (L ′ ).
Proof. First we note that, based on the definition of the system period P (L) given in Section 3, the order in which the machines are accelerated to reach a configuration L ′ from a configuration L does not impact P (L ′ ). The period P (L ′ ) only depends on the configuration L ′ , so on the (l ′ 1 , l ′ 2 , . . . , l ′ p ) values. Now we consider a sequence of configurations S = L 1 , L 2 , . . . , L k with k = |A(L)| such that L 1 = L is the initial configuration of the algorithm where all the machines are set to their lowest speed level and L 2 , . . . , L k ∈ A(L 1 ). The optimal configuration L * can be defined as:

L * = argmin L f ∈S (P (L f ))
Let L a and L b two system configurations such that the configuration L a is obtained by speeding up one machine from the configuration L b . From Lemma 5 we know that having P (L a ) < P (L b ) implies that the critical machine M c (L b ) has necessarily been speeded up to obtain L a .

As the order in which each machine is accelerated to reach a given configuration L f from the initial configuration L does not impact the period value P (L f ), we can reorder the sequence S in a new sequence S ′ . S ′ is reorganized such that L 1 = L is the first configuration of the sequence and then each configuration L x is obtained from configuration L x-1 by accelerating one of its critical machines M c (L x-1 ) is placed just after L x . All other configurations are placed after. This reordering of the sequence does not change the optimal value L * . ∀u : l ′′ u l * u . By using Lemma 3 we deduce that the energy consumed by each configuration L ′′ with P (L * ) = P (L ′′ ) is at least as high as the consumption E * = E(L * ) E(L ′′ ) and then that E(OptP er(L)) = E(L * ) is optimal.

Algorithm OptEner

From the previous algorithm, it is possible to define another greedy algorithm, OptEner(L) (see Algorithm 2), based on the same approach that finds a configuration L * with an optimal (lowest) energy consumption and with a minimal period for this energy consumption. Note that the energy consumption, as defined in the framework model, is composed of a static part and a dynamic part. In some cases where the period is too large, the speed of the machines is thus so low that the static part of the energy consumption becomes predominant. It is then possible to increase the speed of the machine while decreasing the energy consumption. On the other hand, if we increase too much the speed of the machines, above the optimal value, the energy starts increasing. Then the OptEner(L) algorithm finds a system configuration whose energy consumption is optimal. As the speed of the machines is increased accordingly, OptEner(L) is also a configuration with the minimal associated period. Note that this algorithm also works to compute the minimal energy consumption for a given period. We assume that the complexity of Algorithm 2 is O(p × n) considering the same arguments used to compute the complexity of Algorithm 1.

Algorithm 2: OptEner(L)

Mc ← critical machine 1 L ← L 2 lc ← lc -1 3 Mc ← critical machine 4 while ( lc > 0) do 5 if E( L) < E(L) ∨ 6 (E( L) = E(L)) ∧ (P ( L) P (L)) then 7 L ← L 8 Mc ← Mc 9 lc ← lc -1 10 Mc ← critical machine of L 11 return L 12
The algorithm starts from L, the initial configuration where each machine is set at its lowest speed level. Step by step, the algorithm looks for configurations where the energy is decreased compared to the current configuration or if the energy is not decreased at least the period is. The algorithm iterates until the critical machine cannot be accelerated anymore, i.e., when the critical machine has reached its highest speed level.

To prove the optimality of the algorithm we prove first that OptEner(L) finds the system configuration with the optimal energy consumption and then we prove that OptEner(L) finds the minimal period. Before these proofs, we set Lemma 6: Lemma 6. Let L ′ be a configuration in A(L) and M c be a critical machine of configuration L such that the slowdown level for M c is the same in L as in L ′ , then the energy consumption of L is lower than the energy consumption of L ′ :

∀L ′ ∈ A(L) : l ′ c = l c ⇒ E(L) E(L ′ )
Proof. We know, from the definition of function A(L), that each machine slowdown level l u of a machine M u in L is higher or equal than in L ′ with L ′ ∈ A(L).

And, considering Corollary 1, we know that the application period with the system configuration L is lower or equal than any other system configuration

L ′ in A(L) where l ′ c = l c (M c = M c (L))
. Thus, by association, we show:

∀L ′ ∈ A(L) : M c = M c (L) and l ′ c = l c ⇒ P (L) P (L ′ )
Moreover, from Lemma 4, if the slowest machine is not accelerated then the energy consumption of the system cannot decrease:

∀L, L ′ : (∀u s.t. 1 u p, l ′ u l u ∧ P (L) P (L ′ )) ⇒ E(L) E(L ′ )
Thus we find that the energy consumption in L is lower than in every system configuration L ′ in A(L) when l ′ c = l c .

Theorem 3. OptEner(L) finds the system configuration L * with the optimal energy consumption E * = E(L * ) in A(L):

L * = OptEner(L), ∀L ′ ∈ A(L) ⇒ E(L * ) E(L ′ )
Proof. Let L be a system configuration and let M c be a critical machine of configuration L. By using Lemma 6 we assess that the only way to lower the energy consumption is to accelerate the critical machine. The remainder of the proof is very similar to the proof of the OptP er(L) optimality. First we state that the order in which the machines are accelerated to reach a configuration L ′ from a configuration L does not impact the energy value. Indeed the energy consumed by a machine M u only depends on energy constants (C en and β u ), on its speed level (α lu u ) and its period (p lu i ). Then we consider the sequence of configurations S = L 1 , L 2 , . . . , L k such that k = |A(L)| and L = L 1 is the initial configuration where each machine configuration is set at its maximal slowdown level. We can thus assume that L 2 , . . . , L k ∈ A(L 1 ). We sort these configurations in a new sequence S ′ where critical machines are accelerated first. S ′ is reorganized as mentioned before, i.e., L 1 = L is the first configuration of the sequence and then each configuration L x is obtained from configuration L x-1 by accelerating one of its critical machines. All other configurations are placed after. L 1 , . . . , L a is the sequence obtained by OptEner(L) step by step. As L a is the last configuration where a critical machine can be accelerated, we have l c = 0 in L a . Obviously all configurations that are ordered after L a are configurations where the critical machines have not been accelerated and these machines cannot have a better period. From Lemma 4 we deduce that these configurations are more energy consuming than configuration L a : ∀f, a < f k :

E(L a ) E(L f )
We recall that the configuration sequence L 1 , . . . , L a is explored by the OptEner algorithm. Thanks to the condition on line 6 the algorithm only records the best of the covered configurations and thus finds the configuration with the lowest optimal energy consumption.

Theorem 4. OptEner finds the system configuration with the minimal period for the optimal energy consumption.

Proof. We have already shown, in the proof of Theorem 1, that the order in which we consider the machine accelerations does not impact the period value of a given configuration. We also know, from Lemma 3, that a machine acceleration can only decrease the energy consumption of the application if its period is lowered. Let E * be the optimal energy consumption.

As for Theorem 2, we consider the sequence S ′ where the configurations that accelerate critical machines come first in the same order as explored by the algorithm (until l c = 0). The other configurations are placed at the end of the sequence. The shape of the sequence is:

S ′ = L 1 , . . . , L * , . . . , L a , . . . , L k
From the previous proof (Theorem 3) we know that the optimal energy consumption is reached in this sequence at first for L * and that configurations after L a do not have an optimal energy consumption. Then we just have to consider the cases between L * and L a . These cases are examined by the algorithm OptEner step by step. The algorithm does not finish when it finds the optimal energy consumption with L * but continues until it reaches the maximum speed level for a critical machine for the first time. This case occurs with L a . Thanks to the condition on line 6 of Algorithm 2 we guarantee that, in this interval, if a period improvement is possible then it returns this best configuration.

Sub-optimal cases tied by constraints

In some cases the period or the energy may be constrained by external factors, as a limited output throughput or as limited available energy in embedded systems for example. In these cases, the optimal values computed by our algorithms are not reachable and a multi-criteria computation must be done to find either the best corresponding energy or period values. In this case the proposed algorithms can be easily adapted by introducing a new condition in the "if condition" of the algorithms. This condition allows to change the L configuration only if the new configuration L does not violate the constraint. It is then interesting to explore different constraints to get the pareto front that gives the best solutions for each configuration between the two optimal solutions.

For illustration we have computed the pareto front for a specific configuration given in Table 1. The platform configuration (see Table 1a) is composed of five machines M u (1 u 5) with the same initial speed s u (in computing units per second) and 10 speed levels l u so that the slowdown factor α lu u ranges between 1 and 2. The value of β u is either set to 2 or 3. The considered application has five tasks. The associated weight w i (in computing units) and failure rate f lu i are given in Table 1b. The failure rate ranges between 0.01% and 10% and depends on l u . In Figure 4 we plot the period obtained under energy constraints. About forty values of energy are taken between the optimal energy value (2881.26 W h) and the energy corresponding to the lowest -optimal -period (3417.62 W h). Note that the computed results are so close that they shape thick lines. Each line corresponds to the optimal configuration for the critical machine considering a range of energy values. The solid line gives the Pareto front obtained for this platform and this application. The Pareto front contains only 11 solutions. Each of them corresponds to a configuration given by our algorithm to guarantee the lowest period for a given energy level that has not to be exceeded to perform one output out of the system (see Table 2). Note that two Pareto solutions -(32.4637, 3304.99) and (32.4642, 3235.26) -are very close but the corresponding lines do not overlap as Figure 4 gives the impression. Figure 5 gives the details of this area.

Conclusion

In this paper we tackle the problem of energy saving in the case of DAG shaped workflow applications executed on distributed unreliable platforms. We assume that the energy consumption and the fault rate decreases when the machines are slowed down. Given an initial mapping of the tasks onto the machines 4 we propose two algorithms and prove their optimality. The first algorithm minimizes the application period and finds the lowest global energy for that period. The second algorithm optimizes the energy consumption of the system and finds the lowest period for that energy consumption.

In practical systems the energy consumption and the execution period are however often opposed criteria and reducing one of them usually leads to increase the other one. For this reason there is a need to find configurations that balance these criteria. For that we have modified the algorithms and introduced constraints values for both the energy and the period.

In the current work the failure rate of the tasks is a consequence of the speed of the machines. As lowering the task period leads to more faults there is a need to improve the reliability of the system. Improving the system quality implies to find a trade-off between energy, speed and faults. As future work we will consider the problem of optimizing the three criteria of energy, failures and throughput to identify the best configurations of the system given different objectives of improving the reliability, maximizing the speed and lowering the energy consumption. We plan to use multi-criteria techniques and explore different fault models to find good configurations. Due to the complexity of the tri-criteria problem we plan to develop heuristics that give efficient results for each of the three objectives in practical cases.

Figure 1 :

 1 Figure 1: Illustrating task graph

Figure 2 :

 2 Figure 2: Example for the backward computation of the necessary amount of data sets for each task in a linear application, taking into account the failure rates.

4 while ( lc > 0) do 5 if 6 L ← L 7 Mc ← Mc 8 lc ← lc - 1 9Mc ← critical machine of L 10 return L 11

 4567811011 P ( L) < P (L) then

Figure 4 :

 4 Figure 4: Example of a Pareto front for sub-optimal platform configurations

Table 1 :

 1 Illustrated configuration parameters

	Machine Mu su	lu	α lu u	βu	Task Ti wi	fi
		0	3	[1,9] [1,2]	3		0	69 [0.13%,9.24%]
		1	3	[1,9] [1,2]	2		1	31	[0.4%,9.26%]
		2	3	[1,9] [1,2]	3		2	19 [0.51%,7.23%]
		3	3	[1,9] [1,2]	3		3	80 [0.29%,8.91%]
		4	3	[1,9] [1,2]	2		4	54 [0.54%,9.85%]
		(a) Platform configuration		(b) Application
		3500
								pareto front
						period under energy constraint
		3400
	energy consumption in Wh	3000 3100 3200 3300
		2900
		2800
		30	32	34		36	38	40	42	44
					period in seconds

Table 2 :

 2 Figure 5: Zoom in the Pareto front for periods in the interval of 32.463 s and 32.465 s period (s) 31.6122 32.4637 32.4642 32.9058 34.1930 35.9612 energy (Wh) 3417.62 3304.99 3235.26 3101.17 3058.26 3020.72 period (s) 36.5210 38.7897 41.2347 43.3722 43.6949 energy (Wh) 2950.99 2908.08 2902.72 2897.35 2881.26 List of the 11 points belonging to the Pareto front presented in Figure

		3450
					pareto front
				period under energy constraint
	energy consumption in Wh	3250 3300 3350 3400
		3200
		32.463	32.4635	32.464	32.4645	32.465
				period in seconds

Lemma 3. The acceleration of a machine cannot decrease the dynamic energy of any machine.

Proof. Let L and L ′ be two system configurations with l ′ u l u , ∀M u ∈ M , i.e., L ′ has some accelerated machines. We aim at proving that for all machines the dynamic energy is smaller in L than in L ′ : ∀M u ∈ M, E L dyn (u) E L ′ dyn (u). By definition we have 1 α l ′ u u α lu u and β u > 1 so ∀T i ∈ T we can write:

) βu-1 By using the three positive constants C en , w i and s u and by using Lemma 1,

With Equation 1we have E L dyn (u) E L ′ dyn (u). Lemma 4. If the application period does not decrease, machine acceleration always increases the energy consumption of the application.

Proof. Let L and L ′ be two system configurations with l ′ v l v , ∀M v ∈ M , i.e., L ′ has some accelerated machines. Let M u be a machine with l ′ u < l u . Thus P (L) P (L ′ ) and the following inequality on the static energy of the two system configurations holds: ∀M u ∈ M : ε u ×P (L) ε u ×P (L ′ ). Moreover with Lemma 3 we know that for all machines the sum of the task energy consumption is smaller in L than in L ′ :

Thus we deduce that the total energy consumption of a machine M u behaves the same way as both the static and the dynamic part hold the inequality:

Hence we conclude that E(L) E(L ′ ).

Algorithms

In this section, we present two algorithms. The first algorithm OptP er(L) finds a system configuration with the optimal period and the minimal energyconsumption for this period. The second one, OptEner(L), finds a system configuration with the optimal energy-consumption and the minimal period for this consumption.

Let L a be the last configuration of the sequence S ′ that is obtained by accelerating a critical machine. Then:

Indeed only non critical machines are accelerated after step a and from Lemma 2 we know that this will not decrease the system period.

Here L 1 , . . . , L a is the sequence obtained by OptP er(L) step by step. Thanks to the condition on line 6 in Algorithm 1, OptP er(L) takes the best configuration from this sequence. As a consequence:

Then, from Equations 5 and 6, we deduce:

Additionally to the optimal period algorithm OptP er(L) also finds the configuration that is the less energy consuming.

Theorem 2. OptP er(L) finds the system configuration with the minimal energyconsumption E * for the optimal period.

Proof. First we can remark that the static energy consumption of the machines only depends on the system configuration period P (L) and thus is the same as long as the system keeps the same period. This is in particular true for the optimal period L * so that the proof can be limited to the study of the optimality of dynamic energy consumption.

Then, as for the period computation, we can note that the energy consumption definition does not depend on the order in which the configurations are used to reach a target configuration. We can arrange the configuration sequence in any order.

We consider again the sequence S ′ of configurations where the configurations are ordered in such a way that we accelerate critical machines first until L * and then we put the other configurations after. As defined within the proof of the previous theorem, let L a be the last configuration of the sequence S ′ that is obtained by accelerating a critical machine. We have S ′ = L 1 , . . . , L a , . . . , L k with k = |A(L)| and L = L 1 the initial configuration where each machine configuration is set at its maximal slowdown level. Now each configuration in the sub-sequence L a+1 , . . . , L k is a sub-optimal configuration so it is not considered in the following as we are only concerned by configurations which are potentially optimal. In L 1 , . . . , L * we also have sub-optimal configurations that are not considered either. As a result we just have to look at configurations L ′′ in L * , . . . , L a whose period is minimal (P (L * ) = P (L ′′ )).

By definition L * is the first configuration that reaches an optimal period in S ′ so that an other configuration L ′′ in S ′ with an optimal period is such that


S Deleplanque

A L M Fernandes

L Bernardes Real

R Saraiva De Camargo

A Quilliot

THE MINIMIZATION OF THE NUMBER OF STOPS PROBLEM

Keywords: Autonomous Vehicle, Vehicle Scheduling, ILP, Reliability

In this paper two optimum models to study the transport of passengers and goods through the VIPA (Automatic Individual Public Vehicle) are proposed. The objective is to minimize the number of times the vehicles stop. Since those are autonomous vehicles (they have no driver), the operations of deceleration, acceleration, stopping, opening and closing doors and going out of the circuit to go to the station implies a loss of reliability. Therefore, minimizing the number of times the vehicles stop is crucial to ensure their fleet works efficiently. Moreover, doing this we will achieve less energy expense, the minimization of the total time and the maximization of the number of served clients.

Introduction

Nowadays, studying a way of improving the transportation system is very important. For this reason, automated guided vehicles (AVGs) have been constantly developed. AVGs are able to perform their task without any intervention of a human operator. One of those types of cars, the VIPA (Automatic Individual Public Vehicle), was developed by the Institut Pascal research laboratory (Clermont-Ferrand, France), the design office APOJEE, and the car manufacturer Ligier in Clermont Ferrand, France. The partnership's goal was to develop a fully automatic vehicle, capable of moving over short distances (from 0.5 to 3.0 km) without any requirement for changes in infrastructure. The purpose is to allow the transport of persons or goods in a limited area, such as hospitals, airports and industrial sites. Although the VIPA is functional, its functions are limited. The vehicles do not overtake one another and the reliability's constraints require an evolution of the fleet on the circuit. The model must be ready to be used for fleet management problems of the VIPA in the next ten years. This study's objective is to minimize the fleet's operating costs of a VIPA that is implemented to carry passengers or goods in an industrial site or in a limited area. Here, the focus is on minimizing the number of times that each vehicle stops. Several benefits might be obtained: the spending of less energy, a faster route, the minimization of the total time and the maximization of the number of served clients. However, it is important to remark that the problem might be applied to other types of technology. One example is the Private Rapid Transit which operates at London's Heathrow Airport for passengers' transport. Moreover, the problem might be used in any system that has a long service time, and that is not proportional to the size of the charge, or even in some production systems.

In this problem, it is crucial to provide power management and to optimize the consumption, predicting the vehicle's return to the depot. With energy management, with a faster course and with a larger number of clients served, a reliable transportation system might be achieved. In a first moment, it is assumed that the transport requests will be known in advance. Thus, the costs must be minimized, taking into account these demands, passenger safety and the reliability of transportation. In this problem, the AGV routes are assumed to be predefined regardless of the demands, hence are not subject to optimization. So we are interested in minimization of the number of the vehicle stops. Furthermore, indirectly, it also minimizes the number of vehicles requested in the fleet.

The vehicles can be requested either by the stations at the terminals or directly by the passenger' cellphones. The passengers specify the departure station and the arrival station. It is considered that the network through which the vehicle passes is fixed, and at a first time, it is a loop circuit. These networks have deviations that allow a vehicle to get out of the circuit to post a client, to get a new client or to return to the depot. These deviations, the load/unload area, are composed by stations that can be of the type "users" or "garage". The first type represents the stations in which users will be taken or left. The second shows the stations that will work as a depot where the vehicles are kept or reloaded. The profile of the speed of a vehicle in the neighborhood of a load/unload area may be represented as in Figure 1. The vehicles decelerate to make these operations outside the common track. Therefore, the more the vehicles stop, the more they lose time.

To achieve the objective of minimizing the number of times that each vehicle stops, once the fleet of the VIPA is already running, it must call a real-time algorithm to allocate a given group of clients to a group of vehicles. In other words, this algorithm must say which one is the best way to distribute a set of The structure of the paper is as follows. In Section 1, we provide a literature review. Section 2 presents the definitions and formulations of two exact models developed to reduce the number of stops in a circuit. In Section 3, the results obtained for each model are compared. Section 4 concludes and discusses future work.

Bibliographical Review

A serious research has been made about the subject. This is the first work that propose a minimization of the number of stops. Therefore, in the bibliographical review, a focus was done for the problems which aim at the task allocation, the path planning and the scheduling.

Having the correct AGVs to perform the tasks in the right places and times is seen as the mean problem in AVG's planning and scheduling. An approach for integrating task allocation, path planning and collision avoidance is presented. The metaheuristic algorithms of the simulated annealing and of the ant colony and an auction algorithm are investigated and applied [START_REF] Liu | Simultaneous planning and scheduling for multiautonomous vehicles[END_REF].

There are some others studies that focus on the task allocation. In these cases, a rule is established to select a vehicle to perform a task. The rule can be, for example, the random vehicle rule, the nearest vehicle rule or the least utilized vehicle rule. In [START_REF] Egbelu | Characterization of automatic guided vehicle dispatching rules[END_REF], some heuristic rules for dispatching AGVs in a job shop environment are presented. In [START_REF] Yamashita | Analysis of Dispatching Rules of AGV Systems with Multiple Vehicles[END_REF], two empty vehicle dispatching policies are proposed. The first one is 'the nearest vehicle in time' whereas the second one is 'the nearest vehicle in distance' which dispatches the vehicle in the nearest position to the earliest arriving item even if this vehicle is not available before any other vehicle in the system as long as the increase of the waiting time of the item is less than a certain value.

Another part of the problem is the path planning, which is the selection of the path for the AVGs after that the tasks have been assigned and before that the movements starts. In [START_REF] Horn | Efficient modeling of travel in networks with timevarying link speeds[END_REF], exact and approximate methods are investigated for estimating the minimization of vehicular movements in road network models where link speeds vary over time. A condition of FIFO is assumed and several adaptations of Dijkstra's algorithm are used for path-finding purposes. In [START_REF] Baker | A genetic algorithm for the vehicle routing problem[END_REF] a genetic algorithm (GA) is applied to the basic vehicle routing problem (VRP). In this problem, the known demands are supplied by a single depot, vehicles are subject to a weight capacity and, in some cases, to a limit on the distance that they can travel. A GA is also proposed in [START_REF] Ulusoy | A genetic algorithm approach to the simultaneous scheduling of machines and automated guided vehicles[END_REF]. This study treats the problem of simultaneous scheduling of machines and of AGVs in a flexible manufacturing system aiming at minimizing the makespan. Zhan and Noon evaluate 15 shortest path algorithms using a variety of real road networks [START_REF] Zhan | Shortest Path Algorithms: An Evaluation using Real Road[END_REF].

Another point that has been studied in AVGs systems is the scheduling, which determines arrival and departure times of the vehicles at each path segment, station and intersection. The simulation methodology is used to compare the performance of three AGV configurations under a variety of experimental conditions in flexible manufacturing systems aiming to reduce congestion [START_REF] Farling | Analysis of automated guided vehicle configurations in flexible manufacturing systems[END_REF]. The objective of [START_REF] Moorthy | Deadlock prediction and avoidance in an AGV system[END_REF] is to develop an efficient deadlock prediction and avoidance algorithm for AVGs systems. An algorithm is developed to predict the occurrence of cyclic deadlock and the other kinds of deadlocks are avoided by using control logic.

Definitions and Formulation

To solve the problem two models were developed. The first one considers that the stations are disposed in a horizontal line. In contrast, the second one considers that the stations are disposed in a circular circuit, which allows the vehicles to make several cycles to meet the requests. Nevertheless, both models are utilized in transportation systems disposing of a circular circuit.

Model in a line circuit

In this model, the circuit by which the vehicle moves has been stretched and it can be traversed only once after optimization. That means we have a new node each time the vehicle passes through a station. Then, if the circuit has N stations, after stretching, it will have 2N -1 nodes. A circuit with four stations can be represented by the figure 2 We also defined the variable x k i ∈ {0, 1} which assumes the value 1 if the vehicle k stops in the node i; the variable y k d ∈ {0, 1} which assumes 1 if the vehicle k serves the request d; and the variable z k i that represents the charge of the vehicle k when it leaves the node i.

s.t. k∈K y k d = 1 ∀ d ∈ D (2)
y k d ≤ x k o(d) ∀ d ∈ D, k ∈ K (3)
y k d ≤ x k e(d) ∀ d ∈ D, k ∈ K (4)
z k i = z k i-1 + d∈D: o(d)=i w d y k d - d∈D: e(d)=i w d y k d ∀ i = 1..2N -1 k ∈ K (5)
z k i ≤ γ ∀ i = 1..2N -1, k ∈ K ( 6
)
The objective is to minimize the number of times the vehicles stops. Constraints (2) assure that every request is served. Constraints (3) ensure that if the vehicle k serves the request d, whose origin is i, then the vehicle k stops at the node i. Constraints (4) ensure that if the vehicle k serves the request d, whose destination is i, then the vehicle k stops at the node i. Constraints (5) make the mass balance. The charge of a vehicle when it leaves a node i is always its charge when it left the node before i, plus the charge that it picked up in i, less the charge that it left in i. Finally, constraints [START_REF] Moorthy | Deadlock prediction and avoidance in an AGV system[END_REF] assure that the capacity of each vehicle is always respected.

As in this model the vehicles do not have the possibility of doing several cycles in only one optimization, they cannot always satisfy all the requests. In the case where the aggregated capacity of all vehicles is not enough to answer all the set of requests this problem will be infeasible. Thereby, aiming to construct a model which will always be feasible, the next model was developed.

Model with the circle circuit

In this new model, in order to meet all the requests, each vehicle can make a maximum of C cycles, where C = ⌈ d∈D w d /Kγ⌉ + 1. We can assume that this number of cycles will always be enough for a certain number of vehicles and for a certain set of requests, each one with a different charge. Now, we shall consider a circle in which N stations are arranged. The others parameters still being the same.

We defined the variable x k ic ∈ {0, 1} which assumes the value 1 if the vehicle k stops in the node i in the cycle c; the variable y k dc ∈ {0, 1} which assumes 1 if the vehicle k serves the request d in the cycle c; and the variable z k ic that represents the charge of the vehicle k when it leaves the node i in the cycle c.

The problem formulation is presented below.

min k∈K N i=1 C c=1 (1 + c/C)x k i,c (7)
s.t. k∈K C c=1 y k d,c = 1 ∀ d ∈ D (8) k∈K y k d,C = 0 ∀ d ∈ D : e(d) < o(d) (9)
z k 1,1 = d∈D:o(d)=1 w d y k d,1 ∀k ∈ K (13) z k i,1 = z k i-1,1 + d∈D: o(d)=i w d y k d,1 - d∈D: e(d)=i, e(d)>o(d) w d y k d,1 ∀ i = 2..N, k ∈ K (14) z k 1,c = z k N,c-1 + d∈D: o(d)=1 w d y k d,c - d∈D: e(d)=1, e(d)<o(d) w d y k d,c-1 ∀ c = 2..C, k ∈ K (15) z k i,c = z k i-1,c + d∈D: o(d)=i
w d y k d,c-1 ∀ i = 2..N, c = 2..C, k ∈ K (16) z k i,c ≤ γ ∀ i = 1..N, c = 1..C, k ∈ K ( 17
)
The objective is to minimize the number of times the vehicles stop. In order to guarantee that the requests will be answered as soon as possible, we multiply x k i,c by c. Constraints (8) assure that every request must be served exactly once. Constraints [START_REF] Zhan | Shortest Path Algorithms: An Evaluation using Real Road[END_REF] do not allow a request to be served in the last cycle if e(d) < o(d), because otherwise this request would not be delivered, once this kind of request is always served in a cycle c and delivered in a cycle c + 1. Constraints ( 3), ( 11) and ( 12 13), ( 14), ( 15) and ( 16) make the mass balance. The charge of a vehicle when it leaves a node i is always its charge when it leaved the node before i, plus the charge that it picked in i, less the charge that it left in i. Finally, constraint (17) assures that the capacity of each vehicle is always respected.

Aiming to find a lower bound to the problem, the constraint (18) was added to it. We can infer that the number of stops made in a station will be at least the maximum between the biggest integer of the division of the number of persons, who have this station as origin by the capacity of the vehicles and the biggest integer of the division of the number of the persons, who have this station as destination by the capacity of the vehicles.

w d /γ⌉)∀ i = 1..N (18)

Computational Analysis

We present here the tests performed and their results, in relation to the two models, on an Intel I5, 2.5GHz and with 6Gb of RAM. Since there has been no previous test for this problem, we ran experiments on our own data, generated as realistically as possible. Sixteen scenarios were tested. For each scenario, five different instances were randomly generated. The difference from one instance to another is the origin and the destination of its requests. A program in C++ was created which takes as input the number of stations and the number of requests, to randomly generate the origins and destinations for each instance. The number of vehicles K ranged between 2 and 4 and their capacities assumed values 3, 4 and 6. The number of stations N was either 5 or 10. The number of requests |D| was either 20, 30 or 40. All requests were considered to have one as their load. To perform these tests, the exact models were developed in AMPL and tested in CPLEX.

The table 1 compares the results obtained for each model and the computational time spent. S line is the number of stops obtained by CPLEX on the model in a line circuit, cpu line and cpu circuit denote the execution times which where necessary for solving each problem, f is the objective function [START_REF] Ulusoy | A genetic algorithm approach to the simultaneous scheduling of machines and automated guided vehicles[END_REF] and Cycles is the number of cycles which was necessary to satisfy all the requests. The values below are an average of the instances of each scenario. For the second model, the objective function and the number of cycles utilized were also noted. This is due to the fact that the calculation of the objective function is different for the two models and that the second model allows the vehicles to do more than just one cycle. What matters here is the number of total vehicle stops. As stated earlier, the second model developed obtains presents feasible solutions even for instances for which the first model finds no answer. This happens because while the second model allows the vehicle to make a number of cycles that makes possible the fulfillment of all demands, the first model allows each vehicle to make just one cycle.

Another issue to note is that in some situations the second model finds a better solution than the first one. It can be understood by this example: if we have 2 vehicles with capacity 1, and 2 requests (one wants to go from the station 1 to the station 4 and the other wants to go from the station 2 to station 1). The first model finds the solution in which we utilize the two vehicles and each vehicle stops twice. Then, we have a total of four stops. If we utilize the second model, just one car is enough to answer the two requests and we have a total of three stops (the vehicle will first answer the second request, and subsequently the first one).

For scenarios 15 and 16, the second model spent a long time to solve some of the instances. Therefore, we stipulated a maximum time of 20 minutes to allow the model to function. The limited time was determined because we assumed that more than 20 minutes is not viable to await a solution. Then, the averages for these two scenarios shown above contemplate some solutions that are not the optimal ones. We accounted the solutions the model found after 20 minutes running. It is crucial to emphasize that the first model found the best solution for all the five instances of scenario 15. We can notice that when the first model finds viable solutions, it spends much less time than the second model.

Finally, analyzing the results, we can conclude that the number of stations in the circuit is more important to determine the number of vehicle stops than the number of requests.

Conclusion and future work

The VIPA is an important new technology to improve the transportation systems in cities and in industrial cities. Increasing its reliability is crucial, given its constraints due to the fact it is an autonomous vehicle. Therefore two exact models were developed aiming to minimize the number of times the fleet stops. The first model is faster than the second one, however it does not always find a feasible solution, because it limits to just one the number of cycles a vehicle can make. On the other hand, the second model allows the vehicles to make as many cycles as necessary, always finding a viable solution. Nevertheless, this last model can take too much time to find the best solution for larger instances such as those with 40 requests and 10 stations. Hence, a future work will implement a heuristic method to solve the problem in as little time as possible. This heuristic might be an insertion method (the demands are considered one after the other) or a successive matching method (the origin nodes are scanned and the related demands are distributed among the vehicles).

Another model for the variant of the problem involving time windows has to be implemented. The use of the time windows allows us to deal with real service times, which have influence on the duration of the tours which are performed by the vehicles. It requires dealing with another decisional variable.

Figure 1 .

 1 Figure 1. Speed Profile

  . We consider a line in which 2N -1 stations are arranged, a set D of requests d and a set of K homogeneous vehicles whose capacity is γ. Each request d consists of a 3-tuple o(d), e(d) and w(d) where o() and e() are the origin and the destination of d, respectively, and w() is the number of persons in the request d or its charge.

Figure 2 .

 2 Figure 2. Linear circuit after been stretched

∀

  d ∈ D, c = 1..C, k ∈ K (10) y k d,c ≤ x k e(d),c ∀ d ∈ D : e(d) > o(d), c = 1..C, k ∈ K (11) y k d,c ≤ x k e(d),c+1 ∀ d ∈ D : e(d) < o(d), c = 1..C -1, k ∈ K (12)

  ) guarantee that the vehicle k stops in the node i in the cycle c in the cases where: i is the origin of the request d and k serves d in the cycle c; i is the destination of d, with e(d) > o(d), and k serves d in the cycle c; i is the destination of d, with e(d) < o(d), and k serves d in the cycle c -1. Constraints (

  ≥ max(⌈ d∈D:o(d)=i w d /γ⌉, ⌈ d∈D:e(d)=i

Table 1 .

 1 CPLEX results for both linear programs Inst. K N |D| γ S line cpu line S circuit f

	Cycles cpu circuit

Acknowledgments

We wish to thank the Conseil Regional d'Auvergne, the FEDER of the European Union.