Manar Qamhieh
email: manar.qamhieh@univ-paris-est.fr

Serge Midonnet
email: serge.midonnet@univ-paris-est.fr

An Experimental Analysis of DAG Scheduling Methods in Hard Real-time Multiprocessor Systems [Extended Abstract]

Keywords: Real-time scheduling, parallel tasks, Directed Acyclic Graphs, global preemptive scheduling, DM and EDF scheduling algorithms

The scheduling of real-time parallel tasks on multiprocessor systems is more complicated than the one of independent sequential tasks, specially for the Directed Acyclic Graph (DAG) parallel model. The complexity is due to the structure of the DAG tasks and the precedence constraints between their subtasks. The trivial DAG scheduling method is to apply directly common real-time scheduling algorithms despite their lack of compatibility with the parallel model. Another scheduling method called the stretching method is summarized as converting each parallel DAG task in the set into a collection of independent sequential threads that are easier to be scheduled.

In this paper, we are interested in analyzing global preemptive scheduling of DAGs using both methods by showing that both methods are not comparable in the case of using Deadline Monotonic (DM) and Earliest Deadline First (EDF) scheduling algorithms. Then we use extensive simulations to compare and analyze their performance.

INTRODUCTION

Increasing the performance of execution platforms has been done by increasing the speed of uniprocessor systems associated to the reduction of the size of chips leading to heating problems. Multiprocessor systems have been seen as one solution to overcome these physical limitations, by increasing execution capabilities with processor parallelism.

Many practical examples of shifting towards multiprocessors can be found, such as the Intel Xeon, ARM and Cavium processor families.

However, current real-time software APIs are not able to efficiently take advantage of multiprocessor platforms especially when parallelism is considered. In the industry, the majority of designed applications are targeting uniprocessor systems. But this is expected to change in the coming few years which will focus on parallel programming to take advantage of multiprocessor architectures. There are many models of parallel application, but in this work, we are interested in a particular family of parallelism called intersubtask parallelism, in which a parallel task consists of a collection of subtasks under precedence constraints and dependencies between subtasks. The most general model is the Directed Acyclic Graph (DAG) model, which we consider as our task model in this paper.

Real-time scheduling of DAG tasks in particular and parallel tasks in general is a challenging problem. In hard realtime systems, the correctness of a system does not only depend on the correctness of the results, but on the respect of tasks timing parameters. Real-time systems on both uniprocessor and multiprocessor systems have been studied in the last decade, and many researches and scheduling algorithms have been proposed for such platforms [START_REF] Davis | A survey of hard real-time scheduling algorithms and schedulability analysis techniques for multiprocessor systems[END_REF]. However, the extension of real-time scheduling w.r.t. parallel tasks with dependencies is not trivial. Later in this paper, we present two main DAG scheduling methods which are used in literature. We call the first method the parallel scheduling method, in which parallel tasks are scheduled directly using common scheduling algorithms. The other method is the stretching scheduling method which transforms DAG tasks into independent sequential tasks that execute on multiprocessor systems. The stretching method simplifies scheduling at the price of losing some of the characteristics of parallel tasks, as it removes subtasks dependencies such that classical scheduling algorithms can then be used.

Both scheduling methods are used independently in many researches. To the best of our knowledge, this is the first work which compares both methods and show that both methods are not comparable regarding schedulability in the case of global preemptive Deadline Monotonic (DM) and Earliest Deadline First (EDF) scheduling algorithms. Then we compare their performance by extensive simulation and experimental results.

The remainder of this paper is organized as follows. Section 2 presents related works w.r.t. to the problem of scheduling real-time tasks on multiprocessor systems especially for parallel DAG model. Then we present in Section 3 the con-sidered task model. In Section 4, we describe in details the two DAG scheduling methods and we prove their incomparability. Simulation results are provided in Section 5 to compare the performance of these scheduling methods. Finally, Section 6 concludes this work.

RELATED WORK

The scheduling of parallel real-time tasks of different models has been studied on both uniprocessor and multiprocessor systems. In the case of uniprocessor systems, a classical approach in the state-of-the-art is to transform a parallel task into a chain and to assign each subtask of the chain extra timing parameters used for their scheduling. For example, in [START_REF] Chetto | Dynamic scheduling of real-time tasks under precedence constraints[END_REF], the authors considered a hybrid taskset of periodic independent tasks and sporadic dependent graph tasks with a DAG model. They proposed an algorithm aiming at modifying the DAG timing parameters (by adding intermediate offsets and deadlines) in order to remove the dependencies between the tasks in the analysis.

In the case of multiprocessor systems, most research has been done regarding scheduling hard real-time tasks on homogeneous multiprocessor systems, especially for independent sequential tasks [START_REF] Davis | A survey of hard real-time scheduling algorithms and schedulability analysis techniques for multiprocessor systems[END_REF]. As mentioned above, there are mainly two methods for scheduling parallel DAGs in hard real-time systems. The parallel method schedules DAG tasks by using directly common scheduling algorithms and adapting the performance analysis and the scheduling conditions to take into consideration the particular characteristics of DAGs and parallel tasks in general. This technique is introduced in [START_REF] Baruah | A Generalized Parallel Task Model for Recurrent Real-time Processes[END_REF], which considers a taskset of a single sporadic DAG. They also provided polynomial and pseudopolynomial schedulability tests for EDF scheduling algorithm.

The problem of scheduling multiple DAG tasks on multiprocessors have been more studied in [START_REF] Bonifaci | Feasibility Analysis in the Sporadic DAG Task Model[END_REF][START_REF] Li | Analysis of Global EDF for Parallel Tasks[END_REF]. The authors considered general timing parameters of DAG tasks without taking into account their internal structure. In [START_REF] Qamhieh | Global edf scheduling of directed acyclic graphs on multiprocessor systems[END_REF], the internal structure and the dependencies between subtasks are considered in the analysis of global EDF scheduling of DAG tasks.

The stretching method for DAG scheduling is based on DAG transformation. Dependencies of inter-subtask parallelism are removed and a DAG task is transformed into a collection of independent sequential threads. A decomposition algorithm is provided in [START_REF] Saifullah | Parallel real-time scheduling of DAGs[END_REF] to distribute the slack time of the DAG task on its subtasks. The slack time is defined as the difference between the deadline of the graph and its minimum sequential execution time. The subtasks are assigned intermediate offsets and deadlines.

In [START_REF] Lakshmanan | Scheduling Parallel Real-Time Tasks on Multi-core Processors[END_REF], the authors considered fork-join model of parallel tasks and they proposed a stretching algorithm to execute them as sequentially as possible. A fork-join model is represented as an alternative sequence of sequential and parallel segment. All parallel segments of the same task have the same number of threads, and the threads of each segment have the same sequential execution length. The authors proposed to stretch a fork-join task into a master thread with utilization equal to 1, the remaining parallel threads are forced to execute in parallel with the master thread within a fixed activation interval. Hence, dependencies are no longer considered in the scheduling process. We consider a taskset τ of n periodic parallel real-time Directed Acyclic Graph (DAG) tasks run on a system of m identical processors. The taskset τ is represented by {τ1, ..., τn}. Each DAG task τi, where 1 ≤ i ≤ n, is a periodic implicit-deadline graph which consists of a set of subtasks under precedence constraints that determine their execution flow. A DAG task τi is characterized by (ni, {1 ≤ j ≤ ni|τi,j}, Gi, Di), where ni is the number of its subtasks, the second parameter represents the set of subtasks of τi, Gi is the set of directed relations between these subtasks and Di is τi's relative deadline. Since each DAG task has an implicit deadline, its period Ti (interval time between its successive jobs) is the same as its deadline Ti = Di.

TASK MODEL

Let τi,j denotes the j th subtask of the set of subtasks forming the DAG task τi, where 1 ≤ j ≤ ni. Each subtask τi,j is a single-threaded sequential task which is characterized by a WCET Ci,j. All subtasks of a DAG share the same deadline and period of the DAG. The total WCET Ci of DAG τi is defined as the sum of WCETs of its subtasks, where The directed relations Gi between the subtasks of DAG τi define their dependencies. A directed relation between subtasks τi,j and τ i,k means that τi,j is a predecessor of τ i,k , and the latter subtask have to wait for all of its predecessors to complete their execution before it can start its own. An example of a DAG task is shown in Figure 1, in which τ1 consists of 7 subtasks. Precedence constraints are represented by directed arrows between subtasks. A source subtask is a subtask with no predecessors such as τ1,1. Respectively, a sink subtask is the one without any successors such as τ1,7.

Based on the structure of DAG tasks, the critical path of DAG τi is defined as the longest sequential execution path in the DAG when it executes on a virtual platform composed of an infinite number of processors. Its length Li is the minimum response time of the DAG. A subtask that is part of the critical path is referred to as a critical subtask, while non-critical subtasks are executed in parallel with the critical ones.

A DAG task is said to be feasible if the subtasks of all of its jobs respect its deadline. A taskset τ is deemed unfeasible when scheduled using any scheduling algorithm on m unitspeed processors if, at least, one of the following conditions is false:

∀τi ∈ τ, Li ≤ Di U (τ ) = n i=1 Ui ≤ n i=1 Ci Ti ≤ m

DAG SCHEDULING METHODS: PARALLEL VS. STRETCHING

A real-time scheduling algorithm is responsible for distributing the executing jobs of the system on its available processors during the execution interval of the task set. At each time unit within this interval, the scheduling algorithm chooses particular jobs among the ready ones to execute on the system's processors using a particular priority assignment. A global real-time scheduler allows migration of any job in the system between the processors of the system during its execution, and a preemptive scheduler allows higher priority jobs to interrupt the execution of those of lower priority.

In this work, we consider two common real-time scheduling algorithms. The first is the Earliest Deadline First (EDF) algorithm which is an optimal 1 scheduling algorithm on uniprocessor systems and it performs well on multiprocessor systems despite the loss of its optimality. This algorithm assigns priorities to jobs based on their absolute deadlines where jobs with earlier absolute deadlines have higher priorities. Since jobs of the same real-time task might have different priorities, EDF is classified as a fixed job priority assignment algorithm. The second scheduling algorithm is the Deadline Monotonic (DM) algorithm from the fixed task priority assignment algorithms. In this algorithm, priorities assigned to tasks based on their relative deadline. Hence, all jobs of the same task have the same priority.

In the case of independent sequential real-time tasks, the scheduling algorithm can take decisions based on the timing parameters of tasks such as their deadline (absolute or relative), their period, their slack time, ... While, in parallel real-time tasks such as the DAG model, a single task consists of a collection of subtasks, each with a different activation time based on the structure of the DAG. According to the task model presented in Section 3, the timing parameters are assigned on a DAG level and not a subtask level, and subtasks are characterized by their worst-case execution time and their precedence relations only. The other timing parameters of subtasks necessary for the scheduling process are inherited from their original DAGs. Regular scheduling algorithms which are designed originally for the scheduling of sequential independent tasks can be used for the scheduling of such parallel tasks. However, it is harder for them to take accurate decisions for subtasks based on these given timing parameters.

We define a scheduling method of a parallel DAG task as the method which specifies the structure of subtasks in the DAG and how they execute w.r.t. their successor and prede- 1 Optimal scheduling algorithm is defined in Definition 1. cessor subtasks. A scheduling method is used combined with a scheduling algorithm in order to execute parallel DAGs on multiprocessor systems. There are two scheduling methods for DAG tasks on multiprocessor systems which uses common scheduling algorithms in real-time systems, which we call parallel and stretching scheduling methods. More details and examples regarding the two scheduling methods of DAGs are provided below.

Parallel Scheduling Method

We consider the parallel scheduling method as the first and default scheduling method for DAG tasks on multiprocessor systems. This method supports inter-subtask parallelism in DAGs in which all subtasks are assumed to execute in parallel whenever it is possible. For example, if there are two sibling subtasks (who share the same parent) and there is more than one available processor at their activation time, then both subtasks will execute in parallel, otherwise, the scheduling algorithm blocks the execution of one of them and they will execute sequentially as a result.

According to the parallel scheduling method, the subtasks of a DAG task execute as soon as possible based on the default structure of the DAG task. For each subtask, we consider its earliest activation time which is the result of execution blocking of its predecessors while executing on a system of infinite number of processors. This method is used in literature and many analyses are provided, such as in [1, 2, 9, 10]. We believe that the parallel scheduling method is better described using an example. Figure 2 shows the structure of subtasks of DAG task τ1 from Figure 1 when the parallel scheduling method is applied. We assume that DAG task τ1 has a deadline equal to 10 and it consists of 7 subtasks. As shown in Figure 1, the source subtasks {τ1,1, τ1,2, τ1,3, τ1,5} are activated at time t = 0 and they are assumed to execute in parallel. Subtask τ1,4 is a successor of subtasks τ1,1 & τ1,2 and it has to wait at for them both to finish execution before it starts its own. In this example, the earliest possible of τ1,4 is equal to 3. By following the same reasoning, we calculate the earliest activation and even the latest finish time of subtasks based on their precedence constraints. Based on these additional timing parameters, we define the maximum possible execution interval of each subtask in a DAG task, in which it executes either in parallel or sequentially with other subtasks in the system based on the decisions of the scheduling algorithm.

Stretching Scheduling Method

The problem of dependencies between subtasks of a single DAG is solved using the stretching scheduling method.

In this method, a DAG task is converted into independent sequential threads, one of them, at least, is fully stretched. According to the stretching method, the parallel structure of DAGs is avoided whenever it is possible, and some of the subtasks are forced to execute sequentially, while the rest are assigned intermediate offsets and deadlines so as to execute independently. The DAG stretching technique is inspired from the algorithm provided in [START_REF] Lakshmanan | Scheduling Parallel Real-Time Tasks on Multi-core Processors[END_REF] which targets a special parallel task model called the Fork-join model. Briefly, the critical path of a DAG task is filled by some of the noncritical subtasks until it is fully stretched up to its deadline. Based on this stretching, the remaining subtasks of the DAG are forced to execute in parallel with the stretched critical path. In order to maintain the original precedence constraints in the DAG, the subtasks are assigned intermediate offsets and deadlines which assure their independence. As a result, the scheduling problem is simplified into the common scheduling problem of independent sequential threads on multiprocessor systems. Figure 3 shows the structure of the DAG task from Figure 1 when the stretching scheduling method is applied. Let Si,j denote the j th segment of task τi. As shown in the figure, the critical path is transformed into a sequential thread of WCET equal to 10 which is the deadline of the DAG, while the remaining sibling subtasks execute in parallel. For more details about the stretching algorithm for parallel tasks, we invite the reader to refer to [START_REF] Lakshmanan | Scheduling Parallel Real-Time Tasks on Multi-core Processors[END_REF].

In-comparability of Scheduling Methods

In this section, we compare the parallel and stretching methods of DAG scheduling. We discuss the case of global preemptive scheduling in which two scheduling algorithms are used. The algorithms are the Deadline Monotonic (DM) from the fixed task priority assignment family and the Earliest Deadline First (EDF) from the fixed job family. Definition 1. A scheduling algorithm is said to be optimal if it is able to schedule all possible feasible task sets. Definition 2. Scheduling algorithm A dominates scheduling algorithm B if all task sets schedulable by algorithm B are also schedulable by algorithm A, but the opposite is not correct.

Using two examples, we show that both DAG scheduling methods presented in this paper are not optimal. This is not considered as a drawback of these approaches because in real-time multiprocessor scheduling, optimal scheduling algorithms are not practical due to huge overheads and execution costs of algorithms. Also, common uniprocessor scheduling algorithms cease to be optimal when they are used on multiprocessors. As a result, non-optimal scheduling algorithms are used for multiprocessor scheduling in practice.

Proving the in-comparability of both scheduling methods is important in order to show that both methods are acceptable for DAG scheduling and no one dominates the other from schedulability point of view. In order to do so, we provide two general examples showing the scheduling of a given DAG set on multiprocessor system using a global preemptive scheduling algorithm. In the first example, we show that the DAG set is schedulable when the stretching scheduling method is used, while the parallel scheduling method leads to a deadline miss. In the second example, we show oppositely that parallel scheduling method schedules successfully a DAG set while stretching method fails. The following examples are valid for global EDF and DM scheduling algorithms.

Usually, finding a single case of in-comparability is enough to deem the performance of a scheduling method or algorithm.

Example 1

Taskset: As shown in Figure 4, the DAG set of this example consists of two periodic implicit-deadline DAG tasks. DAG τ1 has a deadline equal to 6, and it consists of 5 subtasks. The worst-case execution time of each subtask and the precedence constraints between them are shown in Inset 1 of Figure 4(a). This inset represents also the structure of DAG τ1 when parallel scheduling method is used, which favored inter-subtask parallelism. Hence, subtasks of DAG τ1 execute as soon as possible by considering an infinite number of processors. Subtask τ1,1 is a source subtask which is activated by the activation of the DAG. Then, subtasks {τ1,2, τ1,3, τ1,4} execute in parallel. When they finish execution, the sink subtask τ1,5 executes. Inset 2 of Figure 4(a) shows the structure of DAG τ1 in the case of stretching scheduling method, in which its critical path ({τ1,1, τ1,2, τ1,5}) is filled with non-critical subtasks until its deadline. The result is a fully stretched thread (its worstcase execution time is equal to the deadline) and subtask τ1,3 which executes in parallel with it. Task τ2 is shown in Inset 3 of Figure 4(a) and it has a deadline equal to 7. It consists of a single subtask τ2,1 which has a worst-case execution time equal to 6. Since task τ2 is a sequential task, there is no difference between its parallel and stretching scheduling methods and the result is the same as shown in the inset.

Parallel method: Figure 4(b) shows the global preemptive scheduling of DAG set on a system consists of 3 homogeneous processors. This scheduling is done based on the parallel scheduling method of DAGs and for both scheduling algorithms, EDF and DM. According to DM algorithm, all jobs of DAG τ1 have higher priority than the jobs of DAG τ2. Also in the case of EDF, the first job of DAG τ1 has an earlier absolute deadline than the first job of DAG τ2 when synchronous activation of DAGs is considered. As shown in the figure, the first job of τ1 executes without being interrupted by the other task, and since we consider a parallel scheduling method, its parallel subtasks ({τ1,2, τ1,3, τ1,4}) occupy the processors of the system for 2 time units. As a result, the first job of τ2 is blocked during this time. Know- ing that DAG task τ2 has 1 time unit as a slack, a definite deadline miss occurs due to this blocking.

Stretching method: The same characteristics of the above scheduling are considered for the case of stretching scheduling method. Based on the structure of DAG task τ1 in Inset 2 of Figure 4(a), its jobs need a maximum of 2 processors in order to execute successfully at all times, because the stretching method forces subtask τ1,4 to execute sequentially within the critical path of the DAG. For any given scheduling algorithm, the DAG set is schedulable on a system of 3 processors, since DAG τ1 needs only 2 processors to execute and the remaining processor can be used by DAG task τ2.

Conclusion: In the case of global preemptive EDF and DM scheduling algorithms, stretching scheduling algorithm succeeds in scheduling the periodic implicit-deadline DAG set while the parallel method fails.

Example 2

Taskset: As shown in Figure 5, the DAG set of this example consists of two periodic implicit-deadline DAG tasks. DAG τ1 has a deadline equal to 6, and it consists of 4 segments of 8 subtasks. The worst-case execution time of each subtask and the precedence constraints between them are Parallel method -GEDF & GDM Stretching method -GEDF & GDM Stretching method -GEDF & GDM shown in Inset 1 of Figure 5(a). Since DAG τ1 has no slack time (its critical path length is equal to its deadline), applying the stretching scheduling method does not change the structure of the DAG from the parallel method, hence, Inset 1 of Figure 5(a) represents both scheduling methods. DAG task τ2 consists of 3 subtasks, in which subtask τ2,1 is the source subtask of the DAG and subtasks {τ2,2, τ2,3} are its successors. According to the parallel scheduling method, both subtasks τ2,2 and τ2,3 execute in parallel as shown in Inset 2 of Figure 5(a). We consider the critical path of the DAG τ2 to be subtasks {τ2,1, τ2,2} and its slack is equal to 1 time unit. Using the stretching scheduling method, all subtasks are forced to execute sequentially as shown in Inset 3 of Figure 5(a). In this method, subtask τ2,3 is forced to execute after subtask τ2,2 and all subtasks of DAG τ2 form a single sequential fully stretched thread.

Parallel method: In Figure 5(b), we show the global preemptive scheduling of DAG set on a system of 3 iden-tical processors using the parallel scheduling method. This example can be applied to EDF and DM scheduling algorithms as in Example 1. Based on DM, all jobs of DAG τ2 have higher priorities than the ones of DAG τ1, because relative deadline of τ2 is lower than the relative deadline of τ1 (3 < 6). In the case of EDF, which assigns priorities to jobs based on their absolute deadlines, the first job of DAG τ2 has the earliest absolute deadline, then it has the highest priority. However, the first job of DAG τ1 and the second job of DAG τ2 have the same absolute deadline, then we consider that the second job of τ2 has higher priority arbitrary. According to the parallel scheduling method, subtasks τ2,2 & τ2,3 can execute in parallel whenever there are processors available in the system. As shown in Figure 5(b), all subtasks of DAG τ2 execute in time interval [0,2) and [START_REF] Chandarli | YARTISS: A Tool to Visualize, Test, Compare and Evaluate Real-Time Scheduling Algorithms[END_REF][START_REF] Davis | Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems[END_REF] and they do not interrupt the execution of DAG τ1 despite the priority ordering. According to this scheduling, no deadline miss occurs.

Stretching method: According to the stretching scheduling method, subtasks of DAG τ2 are forced to execute sequentially as a single thread. Since it has higher priority according to DM and EDF, DAG task τ2 occupies a single processor by itself, which leads to a deadline miss for the first job of DAG τ1. This is a result of the blocking effect and the delay of subtask τ1,4 in time interval [START_REF] Bonifaci | Feasibility Analysis in the Sporadic DAG Task Model[END_REF][START_REF] Chandarli | YARTISS: A Tool to Visualize, Test, Compare and Evaluate Real-Time Scheduling Algorithms[END_REF].

Conclusion: In the case of global preemptive EDF and DM scheduling algorithms, parallel scheduling algorithm succeeds in scheduling the periodic implicit-deadline DAG set while the stretching method fails. What we conclude from both examples is that both scheduling methods are not comparable and no one dominates the other.

SIMULATION ANALYSIS

Due to the in-comparability of the parallel and stretching scheduling methods in the case of global preemptive DM and EDF on multiprocessor systems proved by the above examples, we use extensive simulation as an indication to the performance of both methods. Simulation is a good tool to give us indications about the performance of particular scheduling methods and algorithms and it is useful when we compare scheduling algorithms together.

Simulation Environment

The simulation process is based on an event-triggered scheduling. This means that at each event in the interval [0, H), where H denotes the hyper period of the scheduled taskset τ and defined as the least common multiple of periods, the scheduler is awakened and it decides which jobs have the highest priorities to execute on the available processors.

We used a simulation tool called YARTISS [START_REF] Chandarli | YARTISS: A Tool to Visualize, Test, Compare and Evaluate Real-Time Scheduling Algorithms[END_REF], which is a multiprocessor real-time scheduling simulator developed in Java. It contains many scheduling algorithms and task models (including parallel tasks), and it can be used easily for both hard and soft real-time systems.

For each system utilization from 1 to 8, we generated 50, 000 tasksets randomly. The number of parallel tasks within each taskset is varied from 2 to 10 tasks/taskset. This variation affects the structure of tasks because, for a fixed utilization, increasing the number of tasks will decrease their WCET in average and as a result, the number of parallel threads per task will be lowered. Based on this, we can control the percentage of parallelism within a taskset and it can help in analyzing the effect of parallelism on scheduling as we will see below.

Regarding the generation of parallel tasksets, our task generator is based on the Uunifast-Discard algorithm [START_REF] Davis | Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems[END_REF] for random generation of tasks. This algorithm is proposed by Davis and Burns to generate randomly a set of tasks of a certain total utilization on multiprocessor systems. The number of tasks and their utilization are inputs of this algorithm. The taskset generator is described briefly as follows:

• The algorithm takes two parameters n and U , where n is the number of parallel tasks in the set and U is the total utilization of the taskset (U > 0).

• The Uunifast-Discard algorithm distributes the total utilization on the taskset. A parallel task τi can have a utilization Ui greater than 1 which means that its threads cannot be stretched completely, and it has to execute in parallel.

• The number of threads and their WCET of each parallel tasks are generated randomly based on the utilization of the tasks. The maximum number of threads is predefined as 10 threads per parallel task.

• The number of parallel tasks per taskset is varied as well in the generation so as to vary the average utilization per task. Tasksets with low number of tasks tend to have high utilization per task (Hi), while tasksets with high number of tasks have lower task's utilization (Lo).

In order to limit the simulation interval and reduce the time needed to perform the simulation, which is based on the length of the hyper period of each taskset, we used the limitation method proposed in [START_REF] Goossens | Limitation of the Hyper-Period in Real-Time Periodic Task Set Generation[END_REF], which relays on using a considerate choice of periods of the tasks while generation so as to reduce their least common multiple. Using this method, we implemented our task generator to choose periods of tasks in the interval [START_REF] Baruah | A Generalized Parallel Task Model for Recurrent Real-time Processes[END_REF]25200].

Simulation Results

The performance of both scheduling methods varies significantly based on the used scheduling algorithm. This result is not clear using the scheduling analysis and it is possible to show it using simulation only. We compare the scheduling success rate of simulated tasksets while varying their utilization on a fixed number of processors in the system. Starting by Figure 6, we can notice that, in the case of global preemptive fixed task priority DM algorithm, the stretching scheduling method (in both taskset types, Hi and Lo) has better success rates than the parallel scheduling method. And almost 100% of task sets remained schedulable using stretching method while the schedulability of task sets using parallel scheduling started to decrease from utilization equal to 3. We can conclude that the stretching method is more adapted to fixed task priority assignment algorithm.

While in Figure 7, parallel scheduling method performs better in the case of global preemptive EDF scheduling algorithm, which means that this method is more adapted to the fixed job priority assignment scheduling algorithms. We can notice that the schedulability of stretched task sets with high utilization (str-hi) decreases sharply little before system's utilization become 3 to reach less than 10% of success rate, while the parallel scheduling method performs well in general.

Based on these results, we conclude that even if both scheduling methods are not comparable using scheduling analysis and there is no definite dominance of one on another, it is still interesting to use a more adapted scheduling method based on the chosen scheduling algorithm.

CONCLUSION

In this paper, we described two main scheduling methods for global preemptive parallel real-time DAG tasks on multiprocessor systems. The parallel scheduling method enforces inter-subtask parallelism and allows direct scheduling for parallel tasks. While stretching scheduling method transforms parallel tasks into sequential independent task model easier to be scheduled. Both scheduling methods have advantages and disadvantages, and we prove, using scheduling examples, that they are not comparable regarding scheduling and no one of them dominates the other. The comparability analysis is shown for two common scheduling algorithms, the Deadline Monotonic (DM) from the fixed task priority assignment family and the Earliest Deadline First (EDF) from the fixed job priority assignment family.

We conclude the paper by simulation results that show clearly that DM algorithm is more adapted to the stretching scheduling method while EDF performs better when DAG tasks execute using parallel method. In the future, we aim at better analyzing the behavior of such algorithms on the scheduling methods of DAG scheduling, and we aim at extending the analysis to consider other scheduling algorithms may be found in literature.

Figure 1 :

 1 Figure 1: An example of a DAG task τ1 which consists of 7 subtasks. The number on the upper right corner of each subtask represents its WCET and the arrows represent their precedence constraints.

  . Let Ui denote the utilization of τi where Ui = Ci Ti .

Figure 2 :

 2 Figure 2: An example of parallel scheduling method of DAG task from Figure 1

Figure 3 :

 3 Figure 3: Example of stretching scheduling method for DAGs.

XX

  Parallel method -GEDF & GDM 3. Parallel & Stretching methods of DAG Task 2 Stretching method -GEDF & GDM (a) Example 1: DAG set consists of two periodic implicitdeadline DAG tasks. (1) The structure of DAG τ1 when the parallel scheduling method is used. (2) The structure of DAG τ1 when the stretching scheduling method is used. (3) Both scheduling methods (parallel & stretching) of DAG τ2. Parallel method -GEDF & GDM Parallel & Stretching methods of DAG Task 2 Stretching method -GEDF & GDM (c) A successful global EDF & DM scheduling in the case of stretching method for DAG set.

Figure 4 :

 4 Figure 4: An example of scheduling method incomparability in favor of the stretching method.

2 3.

 2 Stretching method of DAG 2 (a) Example 2: DAG set consists of two periodic implicit-deadline DAG tasks. (1)Both scheduling methods (parallel & stretching) of DAG τ1. (2) The structure of DAG τ2 when the parallel scheduling method is used. (3) The structure of DAG τ2 when the stretching scheduling method is used. Parallel method -GEDF & GDM Parallel & Stretching methods of DAG Task

2

 2 Stretching method of DAG 2 (b) A successful global EDF & DM scheduling in the case of parallel method for DAG set.

2

 2 Stretching method of DAG 2 Type to enter text (c) Global EDF & DM scheduling showing a deadline miss when stretching method is used for DAG set.

Figure 5 :

 5 Figure 5: A scheduling example of a DAG set scheduled using parallel scheduling.

Figure 6 :

 6 Figure 6: Simulation results of global DAG fixed priority deadline monotonic scheduling.

Figure 7 :

 7 Figure 7: Simulation results of global DAG EDF scheduling.


Jesus Gonzalez-Feliu

Costs and benefits of railway urban logistics: a prospective social cost benefit analysis

Keywords: combined transport, urban logistics, evaluation, socio-economic cost benefit analysis, simulation

This paper presents a general framework to assess urban rail logistics suitability via a socioeconomic cost benefit analysis. Firstly, we propose an overview on the basic notions of CBA and SCBA. Secondly, we identify and present the main types of costs and benefits or railway urban logistics services and the related final delivery services using low emission road vehicles to serve customers where the rail systems cannot. Thirdly, as an example of application, we propose to assess a scenario of deployment of a freight tramway in Paris, in a possible configuration. The results show the potential of those approaches but also show that it is important to contextualize them and inform the different users about their real capacities.

Introduction

It is more than 20 years that urban logistics is a formal subject of research (Gonzalez-Feliu et al., 2014) and since [START_REF] Ruske | City-Logistics-Solutions for urban commercial transport by cooperative operations management[END_REF], several authors propose urban logistics solutions, which are of different nature and have different effects, exploring different possibilities from theory to practice [START_REF] Taniguchi | City Logistics. Network modelling and Intelligent Transport Systems[END_REF][START_REF] Taniguchi | Innovations in city logistics[END_REF]Macharis and Melo, 2011;[START_REF] Gonzalez-Feliu | Financing Urban Logistics Projects[END_REF]. Urban consolidation is one of the main subjects in conciliating research and practice issues, and several authors manifested the difficulties of making such solutions operational [START_REF] Allen | The role of urban consolidation centres in sustainable freight transport[END_REF][START_REF] Verlinde | How to consolidate urban flows of goods without setting up an urban consolidation centre?[END_REF][START_REF] Janjevic | Downscaling the consolidation of goods-state of the art and transferability of micro-consolidation initiatives[END_REF][START_REF] Morana | Urban Consolidation and Logistics Pooling[END_REF]. Multimodal urban logistics has been seen an interesting alternative solution since the beginning of the structured research on the field [START_REF] Taniguchi | City Logistics I[END_REF], but it remains mainly conceptual. Indeed, as highlighted by Ardvidsson and Browne (2013), most experiences of rail-road urban logistics are nowadays stopped, and to the best of our knowledge it seems that fluvial urban logistics remains marginal or few studied in literature.

Railway urban logistics is appointed as difficult since traveled distances by urban freight railway services remain short (and certainly extremely lower than the minimum distance of combined transport stated by Nierat, 1997), but this idea has been reexamined with the last advances on short rail services' research [START_REF] Marinov | Short haul rail freight services[END_REF]. However, since the principle of urban freight railway services are a declination of urban consolidation schemes (Gonzalez-Feliu, 2013), they seem difficulty viable without a financial and organizational support at the project construction phase. This support can be made by Cost-Benefit-Analyses (CBA), already used in infrastructure development projects [START_REF] Dg Regio | Guide to Cost Benefit Analysis of Investment Projects[END_REF]. Those analysis, and mainly those that relate monetary costs with both monetary and non-monetary benefits (called socio-economic CBA), are rare in urban logistics, which explicates partially the difficulty of such systems to be deployed and transferred (Gonzalez-Feliu et al., 2014b). For those reasons, it seems important to propose an analysis framework to clarify both researchers and practitioners and incite them to develop such practices (usage of SCBA in urban logistics strategic planning, particularly in railway urban logistics) in their project developments.

The aim of this paper is to propose a SCBA-based analysis framework for strategic scenario assessment in the context of railway logistics project development. First, the paper makes an overview on the basic notions of CBA and SCBA. Second, it identifies and presents the main types of costs and benefits or railway urban logistics services. Third, an example of application (that of the freight tramway in Paris, an ongoing project) allows to illustrate the SCBA framework and its application. Finally, the paper concludes on the capacities and targets of SCBA as well as further possible developments of the present work.

Bases of Social Cost Benefit Analysis

Assessing and evaluating the suitability of urban logistics solutions is a popular subject [START_REF] Russo | A classification of city logistics measures and connected impacts[END_REF][START_REF] Muñuzuri | How efficient is city logistics? Estimating ecological footprints for urban freight deliveries[END_REF][START_REF] Ambrosini | A design methodology for scenarioanalysis in urban freight modelling[END_REF]Gonzalez-Feliu et al., 2013). However, cost-benefit approaches are less spread than in other fields, like infrastructure development of public transport planning [START_REF] Hayashi | International comparison of background concept and methodology of transportation project appraisal[END_REF].

Since railway-based urban logistics includes a non-negligible infrastructural component, and can be implemented in synergy with public transport initiatives (tramway, metro, train services), it seems suitable for us to propose a cost-benefit analysis framework (CBA). However, since the main benefits (and some costs) are non-monetary ones, it is important to see it on the perspective of extended CBA, also called Social CBA (SCBA). In this section we present the methodological bases of SCBA and the main adaptation issues to our case (railway urban logistics).

Let's start by recalling the basis of a classic CBA. This method consists mainly on listing on one side all monetary costs (investment and operational), and on the other side all economic benefits; this is done year after year, for a given time horizon [START_REF] Gonzalez-Feliu | Financing Urban Logistics Projects[END_REF]. This time horizon is in general set to 10 years for infrastructure or public transport projects (DG REGIO, 2008). Then, benefits are confronted to costs year by year to obtain a ratio of gains/losses at the end of each year of the given horizon, and their difference is updated using an update rate in order to take into account the money updating year after year. Since the value of money is not the same year after year, it is important to define an updating rate a, which allows comparing two quantities of money at two different periods. Taking the value of a quantity of money V t at time t, and V n the value of this quantity at horizon n, they are related by the following equation

V t = V n /(1+a)n
In a classical CBA, given a year t, we can estimate the net benefit NB t in year t as follows:

NB t = B t -C t
where C t are the monetary costs of year t (both investment and operational) and B t the economic benefits (revenues) made at year t. After that, the discounted net benefit DNB t is calculated on the basis of update coefficient a, using the following relation:

NB t = NB t / (1+α) t
Where the update rate α is set to 4% [START_REF] Hayashi | International comparison of background concept and methodology of transportation project appraisal[END_REF].

Then, we estimate the Net Present Value (NPV t ):

NPV t = NPV t-1 + NB t
Finally, an Investment Return Rate (IRR) is calculated, in a 10-year horizon, using the following relation:

= ∑

In a SCBA approach, the considered costs and benefits are not only economic values but also non-monetary costs and benefits, as for example the reduction of environmental footprints, social benefits but also non-monetary costs which are not always easy to identify and quantify. In SCBA, economic, environmental and social costs and benefits need to be quantified then a monetary value is associated to them. Then the method to obtain savings is the same. At horizon n, we estimate a Socio-Economic Return Rate (SERR) in the same way IRR was calculated, but using extended costs (i.e. economic, environmental and social costs).

Socio-economic costs and benefits of railway urban logistics

The main investment costs are related to infrastructure investments. The most important investment costs are associated to two main categories of infrastructures: linear infrastructures, i.e., the railway line itself, and nodal infrastructures, mainly terminals and loading and unloading bays. In both case it is important to distinguish between the case where one or more new infrastructures are required and the case where all infrastructures are existing, so an adaptation of such infrastructures is envisaged.

Moreover, an urban railway service is in general arriving to the city, but since the urban space is rare and expensive, final destinations (customers) will not be able to be equipped with terminals, so the railway city freight stations need to be connected to retailers via a road transport. This implies also the creation of a specific fleet of vehicles used to link each train/tram stop to the final delivery locations, mainly small, electric vehicles [START_REF] Arvidsson | A review of the success and failure of tram systems to carry urban freight: the implications for a low emission intermodal solution using electric vehicles on trams[END_REF]. The costs of buying or renting such vehicles need also to be included into the investment costs list of the urban freight railway system.

The main operational costs are related to the addition of ruptures of charge. If urban consolidation centers imply one rupture of charge, rail logistics needs at least two: the first at the consolidation terminal, and the second at city, near destination. That means the need of two approach transport to rail terminals. The first is done in general by shippers, usually with existing vehicles, on a feeder perspective (Gonzalez-Feliu et al., 2013); the second is usually done by a specific fleet, as said before (Delaître and de Barbeyrac, 2012).

Concerning benefits, such systems ask in general a fee to customers using it, related to the number of parcels/pallets or to the quantity of freight transported. Since refight railway services do a limited number of stops, we can consider, as for public transport, a pricing system organized in categories of prize, directly related to the zones of origin and destination.

Other monetary benefits can be observed and related to potential savings of shippers or transport carriers using the system, as for example savings related to the part of transport nondone because using the system.

Concerning non-monetary costs, we can observe that although railways can present several advantages at medium and long term horizons, in the period of construction of the railway, also negative impacts to the environment can be observed. Such impacts are not only imputed to pollution and noise of railway works, but also to the decrease of potential customers for retailing and service activities around works.

Non-monetary benefits are in general associated to the potential savings, mainly at environmental and social, but also at an economic level. The main environmental and social benefits are imputed to greenhouse gas emission, pollution and noise savings, but we can define other benefits related to the improvement of the global quality of life of a city (for example related to congestion) at the only condition that such benefits would be quantified. Moreover, time savings can also be quantified, as opposing to private car transport, the impacts of delivery times on total transport cost are known and very important in transport management (Gonzalez-Feliu et al., 2013).

An example of application: the Paris freight tramway service

In this section we will try to illustrate the estimation of different costs and benefits for a given example: that of the freight tramway project in Paris (France). This project has been developed by APUR under the recommendations of the Ile-de-France Region who made an important part of its Urban Mobility Plan to goods transport (APUR, 2014). Moreover, the French Strategic Analysis Council stated on the interests for the collectivity (i.e. all inhabitants and stakeholders within a city or urban area) of using tramway infrastructures to bring goods into the city centers (Conseil d'Analyse Stratégique, 2012).

The initial project was based on experimentation consisting on making running a freight tramway on an existing line in order to identify the main benefits of using tram to bring freight to the city (APUR, 2014). Such experience resulted on interesting conclusions; the most important seems that of using the tramway not to capillary delivering points in the city center but to bring freight from periphery to the main city. For this reason, a project consisting on defining a new railway branch to link the far periphery of Paris metropolitan area to the existing tramway network was created. From this idea, we propose to quantify costs and benefits of making this project.

For infrastructure investment costs, we start by defining the unitary costs of building the linear infrastructure. According to [START_REF] Li | Coûts de transport en commun pour l'application numérique dans le modèle monocentrique[END_REF], several sources estimate this cost allowing to estimate range between 1.15 and 3.50 M€ per kilometer. Those costs include project, construction and testing costs (including human force, technical knowledge and materials, among others). Making an average between all references given by Li (2011), we established an average cost of 22.5 M€/km. Since this cost includes (for public transport) the eventual stop points, we could think that those costs would be lower. In a first time, for the purpose of this paper, we will set this value to 20 M€/km1 , and include in this cost the different crossdocking points (that can be called city multimodal points). Concerning consolidation terminals, we can take costs from multimodal construction literature (Janic, 2007, Genevois and d'Aubreby, 2012). In our case, the hypothesis made is that the space is available in an existing terminal and such costs will be related to a rental prize than a construction cost to pay once. We estimate this cost to 150 000 €/year for the considered terminal. Costs related to freight trams are extrapolated from Li (2011) with a confirmation by RATP (Paris urban public transport, managing classical tramway lines) 2 . They are estimated to 1,5 M€ per vehicle. For final delivery vehicles, we have asked to several manufacturers 3 . Finally, we can also consider other investment costs (related to software implementation, backoffice deployment or project management, among others) or non-monetary costs that have not been considered in this research. We synthesize all investment costs in Table 1. Concerning operational costs, we can observe five main categories. The first that of operational costs of the tramway service itself, that are extrapolated from classical tramway services. Those costs include driving manpower and vehicle maintenance, and are estimated in all the railway line used for goods. The given value has been obtained from Li (2011) with a confirmation by APUR. To those costs we have to add those of the final delivery service and those of cross-docking. Final delivery service operational costs include the corresponding cross-docking costs, whereas upstream cross-docking costs have to be detailed (in the third category: other manpower costs). Infrastructure management costs are considered only for the new railway branch, and not for existing infrastructures, since in this second case maintenance costs can be absorbed by the passenger tramway service. Finally, we can define other maintenance costs related to the system operations and the back-office functioning.

Those costs are synthesized in Table 2. Finally we can define the benefits of the system. The first is that of the fee requested to use the service. Then, non-monetary benefits can be associated to the system: time savings (related to the time a carrier will earn if it uses the service), environmental benefits (greenhouse gas emissions, pollution and noise) and congestion decrease. For a fee, it will be the object of the analysis (to define a suitable fee). Time savings are calculated as in Gonzalez-Feliu et al. (2014). Greenhouse gas emissions and pollution will be estimated using Gonzalez-Feliu et al.'s (2013a,b, 2014) considerations, whereas noise and congestion will not be used for the moment. A summary of such benefits can be seen in Table 3.

A first attempt of assessment

To assess the presented example, we need to summarize and complete the main hypotheses made. The project aims to construct 20 km of light railway to deliver peri-central zones in Paris to deploy a service of urban deliveries. Connected to this railway system, a final delivery service using commercial vehicles (less than 3.5T) of Gas-based vehicles is assumed.

We set the update rates to 4%, the time horizon to 10 years from the construction achievement and no hypotheses on how money is obtained (loans, etc.) are made. In other words, we assume that the money is available and has not to be refunded back to a bank or loan institution. The target of the assessment it to find a suitable fee and a minimum usage of the system.

We present below a set of results illustrating a possible assessment of the example presented above. An SCBA framework is applied to the given scenario and parameters are changed (mainly the asked fee) to obtain a suitable situation.

In the best configuration results, the IRR (only economic) remains negative (about -8%) with a realistic fee (5€/pallet4 ). Those results seem not suitable, since the economic equilibrium is not found. However, we obtain a SERR of 5%, i.e., adding non monetary costs and benefits, the system seems to achieve a solid equilibrium. This equilibrium is made with a service using 2 trams per day (making each 3 shuttle trips), 50 vehicles for final deliveries (each vehicle with a total weight of 5-7 tons, i.e. similar capacity to classical 3.5 tons but with electric and gas vehicles the total weight of the empty vehicle increases for technical reasons) and a needed fee of 5€/pallet as said before. We took the hypothesis that 90 eq.pallets/day are passing the system.

The main non-monetary savings are estimated to be about 3,5 M€/year related to CO 2 and pollution and about 8,1 M€/year related to congestion and time. This second set of savings, which is the most important of the two, is also the most easy to show to private stakeholders, since those savings, that do not have a real monetary significance to collectivities, are instead easily translated into monetary gains (fuel savings and manpower cost decrease, mainly) to transport carriers. Remains however to pursuit the analysis with the facitilators and limitators of the system (in an approach like that of Gonzalez-Feliu and Morana, 2011), to be carried out using a qualitative analysis of semi-directive interviews, and could be done in a near future.

Conclusion

This paper presented briefly the interests and possibilities of using SCBA in assessing the suitability of urban rail logistics systems, by presenting the main element of the SCBA methodology and an example of application based on a possible configuration of the Paris Freight Tram. Railway urban logistics seems an interesting alternative for city distribution but needs to be planned and consensued among stakeholders, and SCBA can be a tool to support decisions, mainly in a group decision making context.

The proposed example shows that it is not always possible or suitable for a public authority to compensate costs only with economic benefits, mainly if it is not possible to ensure a threshold quantity of goods entering the system, or during the transition phase needed to reach this threshold. Moreover, railway seems more adapted to bring goods to the city, but not to do capillary distribution within the city center, mainly due to competition with passenger rail services and the difficulty to reach all parts of the territory. It is then important to focus rail freight services on canalizing goods to the city centers and aggregate them, then plan other types of final delivery services using more adapted modes (as for example soft modes or small, low-polluting road vehicles. However, final deliveries with small vehicles imply too many costs that are not compensated by benefits, so a more general approach including nonmonetary costs and benefits is needed.

Results show that if those non-monetary costs and benefits are included in the assessment, the system can be justified, and stakeholders can be motivated to use it on the basis of quantifiable potential benefits for them. However, those methods need to be used to support the decision and negotiation process and not to justify or impose solutions without allowing discussion and consensus search. For those reasons, it is important to combine those approach with group decision methods and consensus search approaches (Gonzalez-Feliu et al., 2013c; Morana and Gonzalez-Feliu, 2014).

Remains to recall that the costs and benefits given here, as well as the assessment results, are examples using suitable data to make an example, and do not represent the real Paris Cargotram project in the configurations retained in the last meetings (those data are confidential). However, they represent a possible situation that need to be examined in-depth. Further developments are to define a more realistic scenario in collaboration with the Paris decision makers and to propose a set of possible situations to compare them. Moreover, the researches of facilitators and limitations, as well as of supporting the definition of a solid business model for such type of systems are objectives of possible further developments.

Table 1 .

 1 Synthesis of the main investment costs of building a new rail branch for a freight tramway

	Type of cost	Stakeholder involved Unitary cost
	Tramway construction cost (railway) Public administration	22.5 M€/km
	Consolidation terminal	Public administration	0.15M€/year
	City multimodal points	Public administration	Included in tram
			construction costs
	Freight tramway vehicles	Service manager	1,5 M€/vehicle
	Final delivery vehicles	Service manager	0.08 M€/vehicle
	Other investment costs	Varia	Not considered yet
	Non-monetary costs	Collectivity (city)	Not considered yet

Table 2 .

 2 Synthesis of the main investment costs of building a new rail branch for a freight tramway

	Type of cost	Stakeholder involved Unitary cost per year
	Tramway operational costs (including	Public administration	9.6 €/km
	maintenance)
	Final delivery service operational costs Service manager	3.5 €/km
	Other manpower costs	Service manager	0.03 M€/employee
	Infrastructure maintenance	Public administration	0.3 M€/km
	Other operational costs	Varia	0.2 M€

Table 3 .

 3 Synthesis of the main benefits of the system

Type of benefit Stakeholder involved Unitary benefit per year

	Fee	Service manager	Defined during the analysis
	Cost savings (distance + time)	Transport carrier	3.5 €/saved km
	Greenhouse gas emission savings Collectivity (city)	100 €/ton
	Pollution decrease	Collectivity (city)	150 €/ton
	Noise decrease	Collectivity (city)	Not considered yet
	Congestion decrease	Collectivity (city)	Not considered yet

Based on an experience feedback from the Paris Agency of Urbanistics (APUR) in January

[START_REF] Ambrosini | A design methodology for scenarioanalysis in urban freight modelling[END_REF] Confirmation made at SITL 2014, Paris, April.[START_REF] Apur | Le projet Tram Fret. Mise en place d'un transport de marchandises par le tramway, Note n° 69[END_REF] Four interviews made between July 2012 and December 2013.

According to Yves Guyon, president of City Logistics society, Lyon, 8€/ton is a suitable fee, and

5€ pallet is in general lower since in city logistics the main constraint for vehicles is volume and not weight.


Sandra Mallet

Jean-Pierre Bondue

COMMERCE ET TEMPS APPROCHE CHRONOTOPIQUE DU COMMERCE Auteurs

Photographie: Dépanneur à Montréal, ouvert 7j/7, 24h/24 (Sandra Mallet, 2011) La notion de temps est plurielle. Elle résulte d'une longue évolution historique, sociale et culturelle et les géographes ne peuvent se limiter à la considérer comme une donnée homogène, neutre et régulière, comme le font les physiciens. L'illusion de l'uniformité du temps a déjà été critiquée par les sociologues et les anthropologues. Le temps peut, en effet, être ressenti, vécu, perçu de façons diverses et les comportements face au temps varient selon les cultures et les différents groupes sociaux.

Schématiquement, et pour s'en tenir à une appréhension plus objectivée du temps, on peut considérer le commerce selon trois grands types de temporalités: les longues durées, les moments et les cycles, qui orientent respectivement l'analyse vers trois perspectives : -l'historicité. Cette histoire, comme le souligne René Sédillot (1964), comporte des temps forts (favorisés par le développement des transports et des échanges, le climat de sécurité et un contexte général d'ouverture) et des temps faibles (causés par les guerres, le repli dans des systèmes autarciques ou totalitaires); -l'instantanéité relative. Le commerce peut connaître des accidents (flambée des cours, krachs, ruptures de stock), créer des évènements (ventes flash, soldes, ventes aux enchères), susciter des achats d'impulsion;

-la périodicité. Les foires, marchés périodiques de détail, horaires d'ouverture quotidiens des magasins et les cadences du shopping (routines des approvisionnements courants) rythment le commerce. Un tel découpage permet de simplifier l'approche temporelle mais s'inscrit dans une vision structurelle et académique. Ces échelles ne sont pas seulement analysables et interprétables en elles-mêmes. Elles se déroulent en phase, en décalage ou à contre-courant d'autres temps, qu'ils soient individuels ou collectifs, issus du libre arbitre de chacun ou façonnés par des marqueurs socioculturels. Par cette entrée qui intègre les dynamiques globales de l'existence, l'analyse du commerce et du temps tend à s'éloigner de la sphère des sciences économiques et de gestion pour mieux s'ancrer dans le champ des sciences humaines et sociales.

Le paradigme à privilégier est désormais celui de l'articulation des temporalités quotidiennes des individus et des groupes sociaux avec les rythmes commerciaux: le géographe doit s'attacher à comprendre les synchronisations, les enchaînements, les stratégies, les attentes, les conflits. Les stratégies de gestion du temps consacré aux achats sont en rapport étroit avec les lieux, les formes et les formules de l'appareil commercial qu'elles influencent et qui les déterminent à leur tour. Dès lors, le géographe adoptera une vision chronotopique du commerce et de la consommation, analysant ces derniers dans une perspective tout autant spatiale que temporelle.

Le contexte actuel est marqué par des recompositions temporelles majeures et "c'est le temps qui, aujourd'hui, constitue le paramètre principal de l'usage de la ville par les consommateurs" (DESSE, 2001, p.24). Le modèle d'une ville en continu fonctionnant 24h/24, 7j/7, interroge, ce qui témoigne d'une mutation historique des modes de vie, influencés tout autant par un processus de globalisation que d'individualisation des sociétés. Les convenience stores, les automates, le e-commerce, les ouvertures des boutiques le dimanche ou en nocturne constituent des figures révélatrices des nouvelles dynamiques du commerce et du temps.

RECOMPOSITIONS DES TEMPS SOCIAUX

Nouvelles gestions du temps

Les temps du travail se sont transformés, réorganisant l'ensemble des temps de la vie quotidienne. La banalisation du travail salarié des femmes a engendré des problèmes d'ajustement entre temps professionnels, familiaux, domestiques. La flexibilité s'est imposée comme une norme répondant aux exigences économiques des entreprises. Les journées de travail courtes augmentent, de même que les journées longues, les horaires décalés et le travail de nuit. Les week-ends prolongés et le fractionnement des périodes de vacances se généralisent. Les horaires de travail, voire les lieux, sont de moins en moins standardisés. Une sorte de brouillage apparaît entre les périodes de travail et de non-travail, d'autant plus que des objets toujours plus nombreux, comme le téléphone portable ou l'ordinateur portable, favorisent l'enchevêtrement des temporalités. Les technologies induisent des temps de plus en plus artificialisés et recomposent les liens entre temps et espace. Les technologies de communication et de l'information favorisent le "temps-réel" et l'ubiquité. Les transports, toujours plus rapides, réduisent les distances entre les lieux qui se lisent désormais en terme de distance-temps. Les attentes, les comportements, les représentations du temps s'en trouvent bouleversés. La sensation d'un manque de temps semble devenue banale. La société est dite "chronophage", évoluant vers le "zapping", les "demandes à la carte". Autrement dit, les temporalités s'individualisent, se désynchronisent, alors que l'individu "branché" est devenu polychrone en effectuant couramment plusieurs tâches à la fois.

Temporalités de la consommation.

Ces mutations bouleversent les pratiques d'achat des consommateurs qui opèrent de nouveaux arbitrages dans leurs emplois du temps. Comment s'articule le temps des courses dans les stratégies de gestion des différents temps quotidiens? « L'homme est une création du désir, non pas une création du besoin » explique le philosophe Gaston Bachelard. Consommer, c'est d'abord désirer, se projeter, tenter de satisfaire un plaisir. Pourtant, seulement 15% des Français considèrent la consommation comme un plaisir et environ 84% la voient comme une nécessité1 . Faire les magasins n'est pas toujours jugé agréable et la consommation peut directement être assimilée à une perte de temps. La durée moyenne des courses ne cesse de diminuer. Les clients évitent l'attente aux caisses et les panels de choix trop larges qui peuvent « gaspiller » leur temps. En revanche, ils fréquentent davantage de magasins. Cela peut s'expliquer par le fait que, si grandes surfaces et hypermarchés restent malgré tout des lieux de destination privilégiés le samedi, ils sont de moins en moins le lieu d'une destination finale, au coeur des projets motifs mêmes du déplacement (Bellanger, 2001). Au contraire, les courses se font de plus en plus en chemin, les déplacements étant souvent considérés comme improductifs et les heures passées aux courses de shopping ne compensent pas cette perte de temps.

Les individus opèrent de nombreuses stratégies de décalages et d'évitement qui se ressentent sur façons de consommer, lieux d'achats, type de magasin fréquenté. Ils rationalisent leur emploi du temps, réduisant certaines tâches, pour mieux profiter d'autres activités; réduisant le "temps subi" pour privilégier le "temps plaisir". Le temps libre n'est plus un simple résidu du temps de travail, il s'est constitué en objet central de nos modes de vie, bouleversant les comportements. Et, depuis les années 1960, la marchandisation des loisirs n'a cessé de s'élargir. La hausse du pouvoir d'achat, la multiplication des types de loisir et des espaces qui leurs sont dédiés ouvrent des possibilités en matière de sport, de détente et de divertissement. Or, si nous disposons plus de temps libre, encore faut-il savoir l'utiliser et pouvoir en disposer de façon satisfaisante. L'individu cherche à en optimiser sa gestion afin de concilier ses diverses activités, quelles soient domestiques, familiales, liées aux loisirs ou à la consommation.

LE COMMERCE ENTRE LOISIRS ET TEMPS CONTRAINTS

Le temps est devenu l'un des points forts de l'attractivité commerciale et fait l'objet de recherches en marketing. Celui-ci est désormais prioritaire dans l'analyse des modes de consommation. Le commerce pouvant être associé, de façon paradoxale, aux loisirs d'un côté et à un temps contraint de l'autre, de quelles manières les acteurs du commerce tentent-ils de s'adapter aux évolutions temporelles des modes de vie ?

Nouvelles logiques de proximité

Réduire les temps contraignants: les nouveaux formats en centre-ville "2 enfants, 2 jobs à temps pleins, ont changé pour une banque compatible avec leurs agendas" : la réduction des pertes de temps est devenue un argument courant des slogans publicitaires, tels que celui-ci utilisé par Monabanq en 2007. Face aux transformations des emplois du temps des consommateurs, certains modèles s'essoufflent, comme celui de l'hypermarché, devenu trop chronophage. La perte de temps passé dans les transports pour s'y rendre, la durée d'attente aux caisses, celle passée à choisir parmi la multitude de produits dans les rayons, ne sont pas compensés par le gain de prix escompté. D'une façon générale, tandis que les grandes surfaces périphériques connaissent un ralentissement de leur fréquentation, les ventes des petites surfaces de centre-ville desservis par des transports en commun modernisés progressent, de même que les moyennes surfaces offrant des commodités de stationnement en milieu urbain. Le commerce de proximité pédestre ou automobile se situe donc dans une phase de dynamisme alors qu'il a été délaissé durant des années. Les modèles de la supérette et du hard-discount séduisent. 60% des personnes fréquenteraient les hard-discounts d'abord pour une question de temps et non de prix. Souvent situées dans des zones résidentielles denses, proposant surtout des articles de première nécessité avec peu de références pour chaque catégorie de produits, les courses y prendraient en moyenne 20 minutes, contre 45 dans un hypermarché. Les grands distributeurs renforcent leur offre de proximité avec des enseignes telles que Carrefour City, 8àhuit, Petit Casino. De "nouveaux formats de la proximité" se constituent ainsi (BELLANGER, 2001).

Les temps opportuns des lieux de transit

Le commerce tente aussi de devenir plus accessible, dans un contexte de complexification des mobilités. Les lieux de transit tels que les aéroports, gares, stations services, deviennent des emplacements commerciaux privilégiés. La mobilité tenant une part importante dans la vie quotidienne des individus, ceux-ci peuvent profiter de leurs déplacements pour faire des achats. Ainsi, la proximité ne veut pas seulement dire "s'installer là où vivent les gens" mais aussi "sur les cheminements des gens". Chaque voyageur devient alors un "un client ambulant potentiel, différent en cela du consommateur qui se rend à un endroit déterminé pour y satisfaire une demande particulière (magasins ou marchés, généralement fréquentés avec une intention précise). » (MONNET, 2006). Les gares et stations de métro canalisent des flux importants de voyageurs et les boutiques qui y sont implantées réalisent souvent des chiffres d'affaires largement supérieurs aux grandes surfaces de périphérie. En Allemagne, en Grande-Bretagne ou au Japon, certains espaces de transit constituent de véritables galeries marchandes. A l'occasion des déplacements quotidiens, les commerces et les services de ces espaces se substituent pour une part aux défaillances des commerces traditionnels de proximité des lieux résidentiels.

L'ubiquité du e-commerce

Le e-commerce facilite également l'accessibilité de l'offre. Il attire une clientèle qui souhaite faire ses achats à tout moment, rapidement et sans se déplacer, plutôt jeune et urbaine. Les transactions sont accélérées: en quelques clics, le client est relié au cybercommerçant et trouvera une variété et une disponibilité des offres inédites. Mais le temps de commande prend souvent 40 minutes, égalant le temps passé dans un supermarché et le délai de livraison s'ajoute à cela. La vente en ligne reste encore minoritaire, les individus privilégiant certains types d'achats, plutôt ponctuels (tels que les voyages, produits informatiques, livres et musique) mais progresse, et l'on peut imaginer qu'il deviendra un lieu d'achat ordinaire. Internet fait partie intégrante de notre quotidien : une part importante et croissante de foyers en est équipée, la ville multiplie ses points d'accès et Internet a pris place sur les téléphones mobiles. Le temps virtuel de la consommation peut ainsi prendre place à domicile, dans les temps de déplacement, de travail, de loisir, etc., autrement dit, partout et tout le temps.

La consommation comme loisir

Si la distribution, d'un côté, cherche à réduire les temps contraignants, elle tend, de l'autre, à valoriser et développer les offres fondées sur "l'achat plaisir", tendant à offrir des moments « de qualité » et prônant le plaisir dans l'effectuation des achats. Le principe d'une consommation-loisir est mis en avant par les investisseurs, avec une volonté de créer des lieux de distraction autant que de dépense. Né au Etats-Unis, le fun-shopping s'est importé en Europe dans les années 1990. Si les centres commerciaux outre-Atlantique deviennent parfois de véritables parcs d'attractions, le concept est plus modéré dans les pays européens où les enseignes commerciales se mélangent avec les espaces de loisir (d'abord des multiplexes et des restaurants, avant de s'ouvrir parfois à une diversité d'équipements tels que salle de spectacle, centre de remise en forme, bowling, karting ou discothèque). Les modèles américains des Urban Entertainment Centers et Festival Market Places sont transférés dans le vieux continent. Bercy Village, créé en 2001 à Paris sur une friche vinicole, en est un exemple. La combinaison des activités reposant sur les loisirs, la restauration, la culture et le commerce, de même que l'alimentation des imaginaires grâce à un passé riche en guinguettes et cafés en fait un espace novateur. Chaque visiteur passe en moyenne près de 2 heures (hors cinéma) à flâner, le plus souvent en famille, dans cet univers inhabituel de la vie parisienne et deux tiers d'entre eux sont considérés comme des clients potentiels2 .

VERS UNE VILLE EN CONTINU?

Les transformations des temps sociaux tendent donc à réorganiser les logiques de localisation, les formats, les activités associées au commerce. On est passé d'une notion étroite de proximité en tant que proximité spatiale au lieu de résidence à un système plus complexe, tenant compte des variables "temps", "espace" et "mobilité". Mais ces nouvelles formes du commerce posent des questions sociales car elles restent moins accessibles aux personnes peu inscrites dans les réseaux de mobilité. Qu'en est-il des horaires qui participent, eux aussi, directement à l'accessibilité des équipements?

Des horaires mal adaptés?

Face à la désynchronisation des rythmes sociaux, nombreux considèrent que les horaires et jours d'ouverture des commerces ne sont pas suffisamment adaptés aux modes de vie des populations. Pourtant, des analyses ont mis en évidence que la majorité des Français considère les temps du commerce bien adaptés, contrairement à ceux des services publics et administrations. Moins d'un tiers affirment manquer de temps pour leurs achats et une faible majorité est favorable à l'ouverture des établissements le dimanche3 . L'élargissement des horaires le soir et le week-end semble surtout le souhait de cadres et de jeunes. Se dégage alors l'hypothèse d'une génération porteuse de valeurs nouvelles, remettant en cause les temporalités traditionnelles. Par ailleurs, l'extension des horaires d'ouverture des magasins nécessite des travailleurs en horaires décalés. Or, seulement 39% des Français actifs se disent prêts à travailler régulièrement le dimanche. Les rythmes de travail des salariés du commerce sont déjà bien souvent "hors normes": près de la moitié travaillent au moins occasionnellement le dimanche, 9 sur 10 oeuvrent le week-end, 40% des femmes sont à temps partiel et les horaires varient souvent d'une semaine à l'autre4 . L'ensemble de ces résultats relativise les discours dénonçant l'inadaptation de l'amplitude horaire des magasins. Pourtant, les villes françaises apparaissent souvent "en retard", comparé à celles des Etats-Unis ou du Japon -où supermarchés, salles de sports, restaurants, librairies fonctionnent parfois jour et nuit.

Des horaires qui s'élargissent

En France, peu de boutiques restent ouvertes passé 19h. Même à Paris, rares sont les magasins ouverts après 22h. Cependant, les nuits de la capitale s'animent, sous l'effet d'une économie des loisirs mais aussi d'activités de type diurne. Fait révélateur: en 2003, seules deux supérettes y étaient ouvertes jusqu'à minuit; en 2010, une trentaine ferment entre 23h et 1h5 . D'une façon générale, les horaires s'étendent en soirée et le dimanche s'ouvre de plus en plus à l'activité dans de nombreux pays européens et au Canada, faisant l'objet de débats politiques, économiques, sociaux. Les lois s'assouplissent. Le gouvernement du Québec autorise ainsi le commerce de détail à ouvrir certains soirs de la semaine et le dimanche. Dans cette province, on compte à présent près de 6000 "dépanneurs" qui vont "du colosse des autoroutes au petit indépendant en passant par le spécialiste du ver à pêche des campagnes" (LUSSIER, 2010). Les dérégulations sont justifiées par les évolutions temporelles des sociétés et les contraintes croissantes supposées peser sur le temps du shopping.

La régulation des horaires a toujours existé mais les lois ont été renforcées dans les années 1930. Les objectifs sont de promouvoir une certaine qualité de vie, protéger le petit commerce et assurer un jour de repos pour tous, tout en garantissant l'accès aux biens essentiels. En France, il n'y a pas de limite d'ouverture des commerces, mais des restrictions existent au niveau du travail salarié, la nuit et le dimanche. Les économistes ont montré que les dérégulations ont des conséquences sur les rythmes de consommation et entraînent des disparités territoriales. En Allemagne, presque tous les hypermarchés et grands magasins ont prolongé leurs horaires d'ouverture entre 1996 (date de la dérégulation) et 1998. A l'inverse, nombreux sont les petits commerces individuels qui ont gardé leurs horaires habituels faute de pouvoir supporter la charge d'un salarié supplémentaire (KOSFELD, 2002). Les dérégulations bénéficient surtout à la grande distribution qui en profite pour augmenter ses prix [START_REF] Tanguay | Shopping Hours and Price Levels in the Retailing Industry: A Theoretical and Empirical Analysis[END_REF]. Au niveau des comportements des consommateurs, on observe aux Pays-Bas, depuis la dérégulation de 1996, une augmentation du temps passé dans les commerces, une plus grande fréquentation en soirée et le dimanche après-midi mais la plupart des personnes gardent leurs habitudes (KOOREMAN, JACOBSEN, 2004).

Une géographie contrastée

Les ouvertures plus tardives ne sont pas rentables pour les commerces qui ne jouissent pas d'une attractivité suffisante pour compenser les frais liés (emploi de salariés en particulier). La localisation du magasin constitue une variable importante: il faut un environnement attractif et des effets de publicité pour attirer suffisamment de clients durant les horaires atypiques, ce qui est surtout le cas des commerces de centre-ville et des zones périphériques qui possèdent une densité et une diversité commerciale conséquentes (KOSFELD, 2002). On observe ainsi des disparités géographiques remarquables et des effets d'entraînement. Ces effets s'observent aussi à proximité des zones où l'ouverture dominicale est autorisée: cela incite certaines boutiques à ouvrir le dimanche, même illégalement. A une autre échelle, autour des petites épiceries aux ouvertures tardives se forment parfois des micro-centralités aux temporalités spécifiques. On peut aussi penser à toute l'animation commerciale et festive qui se développait la nuit autour des halles centrales avant leur transfert sur des marchés de gros périphériques. Certains commerces ouvrent même leurs portes à des moments peu rentables pour des effets d'image ou afin de casser la situation de monopole que leurs concurrents auraient alors. D'une façon générale, au sein d'une même agglomération, des écarts persistent entre centre-ville et périphérie. A Avignon, seuls 20% des commerces intra-muros sont ouverts après 18h30 alors que 60% de ceux des grands pôles périphériques le sont (GENRE-GRANDPIERRE, 2007). De plus, seule la moitié des commerces du centre-ville est accessible entre 12h30 et 14h alors que la grande distribution a adopté la journée continue depuis longtemps. Mais les écarts se resserrent et les petits commerces centraux ont tendance à revoir leurs horaires.

De nouveaux territoires temporels apparaissent et une autre géographie du commerce, complexe et mouvante, se dessine. Les frontières temporelles traditionnelles s'effacent, un "front" progresse dans l'espace d'une manière discontinue, avec des points d'appui, des citadelles à temps continu (MELBIN, 1977) : quartiers de centre-ville, micro-centralités ponctuant régulièrement le paysage urbain, espaces des flux internationaux ou zones périphériques. De nouveaux chronotopes se forment avec une relation originale au temps et à l'espace. Le commerce constitue une activité essentielle dans l'organisation et le fonctionnement urbain et ses temps forts animent la ville, la rythment. Une continuité temporelle inédite se forme, qui doit nous interroger sur la place de la consommation dans les modes de vie ainsi que sur la place du commerce dans la ville. Cependant en France, d'un côté, les dimensions temporelles du commerce restent ignorées des schémas de cohérence territoriale et de développement commercial qui ne se déclinent encore qu'en termes de logiques spatiales. Si les analyses privilégient les questions de surface et de localisation, elles omettent aussi de fixer des échéances communes en matière d'évolution du commerce et de la ville. D'un autre côté, ni les urbanistes ni les acteurs des politiques temporelles n'ont véritablement été conviés aux débats sur l'ouverture des commerces le dimanche. Or, les transformations des rythmes urbains ont des conséquences sur l'accessibilité spatio-temporelle des commerces, le prix des produits, la compétitivité des établissements, leur localisation, leur format. Penser systématiquement l'aménagement urbain et la géographie du commerce et de la consommation à la fois dans l'espace et dans le temps constitue donc un défi à relever. GENRE-GRANDPIERRE, Cyrille (2007), "Inégalités dans l'accessibilité spatio-temporelle aux commerces dans l'aire de vie avignonnaise. Etat des lieux et perspectives de réduction", Espace Populations Sociétés , n° 2/3. KOOREMAN, Peter;JACOBSEN, Joyce P. (2004), "Timing Constraints and the Allocation of Time: The Effects of Changing Shopping Hours Regulations in the Netherlands", IZA Discussion, n° 1309. KOSFELD, Michael (2002), "Why shops close again: An evolutionary perspective on the deregulation of shopping hours", European Economic Review, n°46, pp. 51-72. LUSSIER, Judith (2010), Sacré dépanneur!, Héliotrope. MELBIN, Murray (1978), "Night as frontier", American Sociological Review, vol. 43, pp. 3-42. MONNET, Jérôme (2006), "L'ambulantage : Représentations du commerce ambulant ou informel et métropolisation", Cybergeo : European Journal of Geography. SEDILLOT, René (1964), Histoire des marchands et des marchés, Fayard.

BIBLIOGRAPHIE

  BELLANGER, François (2001), Escale(s). Temps et lieux de la consommation, Transit-City, Les Carnets. BONDUE, Jean-Pierre (dir.) (2004), Temps des courses, course des temps, Lille, USTL. DESSE René-Paul (2001), Le nouveau commerce urbain, Presses Universitaires de Rennes.

CREDOC (2008), L'ouverture des commerces le dimanche : opinion des français, simulation des effets, cahier de recherche n°

246, novembre 2008.

Cabinet ECCE (2002), Etude d'image et de clientèle pour le compte de la SCI Bercy Village.

CREDOC (2008), L'ouverture des commerces le dimanche : opinion des français, simulation des effets, cahier de recherche n° 246, novembre 2008.

INSEE (2011), "Travailler dans le commerce de détail ou l'artisanat commercial", INSEE première, n° 1358.

APUR (2010), "La nuit à Paris. Etat des lieux et tendances 2000-2010", Note de 8 pages, n°43.