The paper is devoted to the problem of scheduling for the linear section of a single-track railway: how to organize the ow in both directions in the most e cient way. In this paper, the authors propose an algorithm for scheduling with independent edges orientations, examine the properties of this algorithm and perform the computational experiments.
In this paper, we continue a consideration of the problem of scheduling for the
linear section of a single-track railway started in [
This problem with di erent modi cations is well-known (see [
In this work we use notations proposed in [
For each station vi we have a positive integer m(vi), being the number of auxiliary railway tracks at this station. These tracks are the only places where a train can stop. Each auxiliary track can hold only one train.
Therefore, if all auxiliary tracks of the station are occupied then a train cannot stop at this station.
By l(e) we denote the length of the track corresponding to edge e from E. Suppose all trains have equal speeds. It should be a nonnegative time interval between two trains moving in same direction. Also, there is an isolated station w 2 V such that every train passing this station is obliged to stay at it for a nonnegative time due to technical reasons (the change of locomotive crew, train inspection, etc.). Stations v1 and vn are sources and receivers of trains. Thus, there are two directions of movement: from v1 to vn and from vn to v1 (these directions are denoted by v1 7! vn and vn 7! v1, respectively). We can assume that each train does not change the direction and does not visit any vertex twice. For passing each other when moving in di erent directions, one of the trains waits another one on an auxiliary track.
Let = (V; E), m : V ! N0 and T | the whole time period. Since adding new stations without auxiliary tracks, we get the same problem, we can suppose that, without loss of generality, all edges have the same length 1: l(fvi; vi+1g) = 1: Also, we assume that trains pass one edge per the unit of time.
The section corresponds to a single-track railway. So for every moment of time trains can move on every edge only in one direction. Thus, if we have R | a schedule of trains movement on , then we can de ne map sR : T E ! f 1; 1g, where sR(t; e) = 1, if there is a movement with direction v1 7! vn, and sR(t; e) = 1 otherwise. Let R be a set of schedules such that there exist partition the whole time interval T onto disjoint half-intervals with similar length
T = [ik=0[ti; ti + ); where sR(ti; e) = sR(ti + 0; e) for all R 2 R, e 2 E and 0 0 < .
We need the following sets of schedules of trains movement. 1) Let A consists of all schedules R from R, such that for all t 2 T we have sR(t; e) = sR(t; e0) for all e; e0 2 E. Thus, for R in A there are no trains moving in opposite directions | in any moment of time trains move in xed direction or stop on auxiliary tracks. 2) Let B consists of all schedules R from R with property, that there exist functions m1 : V ! N0 and m2 : V ! N0 such that m1(vi) + m2(vi) = m(vi) and, for each station vi, there are m1(vi) auxiliary tracks for the direction v1 7! vn and m2(vi) auxiliary tracks for the direction vn 7! v1. Thus, we divide all the auxiliary tracks into two sets for both directions. Now, the trains can use auxiliary tracks corresponding to their directions and the whole task can be divided into two independent subtasks for each direction.
The problem is to construct and implement a scheduling algorithm to send as much as possible trains for period of time T in both directions (more speci cally we are interested in the schedule at which the minimum number of trains in both directions over a speci ed period of time is maximal, this number per time we call track capacity of the section with given schedule).
Properties of schedules from A and A\B were studied in [
In this section we suppose, that
= 0 and there are no isolated stations.
Proposition 1. The maximal track capacity for schedules from R doesn't exceed doubled maximal track capacity for schedules from A \ B.
Proposition 2. Let R is a schedule from B and for every edge of total time, when the edge is orientated in direction v1 7! vn equals time, when the edge is orientated in direction vn 7! v1. Then there exist schedule R0 from A \ B such that track capacity for schedule R0 doesn't exceed track capacity for R.
The following propositions were obtained earlier.
Proposition 3 ([
min 4 i
X
i j i+
m(vi):
Proposition 4 ([
Thus propositions 2, 3 and 4 make possible to determine a maximal track capacity for schedules from B in case, when for every edge of total time, when the edge is orientated in direction v1 7! vn equals time, when the edge is orientated in direction vn 7! v1. In common case, rough estimations can be obtained from proposition 1.
We suppose that the following conjectures are correct.
Conjecture 1. Track capacity for the section with schedule from B doesn't exceed of track capacity of the section with some schedule from A \ B. Conjecture 2. Track capacity for the section with schedule from R doesn't exceed of track capacity of the section with some schedule from A \ B. 3
Consider a mathematical model of linear section of a single-track railway with 65 stations and 2 of them are isolated with 1 = 80 and 2 = 135 (isolated station w with described in Introduction).
For t 2 T For from 60 to 720 minutes and for arbitrary independent edges orientation lets nd the maximal track capacity. Below we give verbal description and pseudocode of the algorithm.
Pseudocode of the algorithm
V_{i,t}:= [] V_{1,0}:= m_1(i,t) V_{n,0}:= m_2(i,t) for t in T { for i in (n..2) { if s_r(t, e_{i,i-1}) == -1 { while m_1(i,t) > 0 { }
} } while m_1(1, t+1) == 0 { } for i in (1..n-1) { create newTrain add newTrain to V_{1, t+1} if s_r(t, e_{i,i+1}) == 1 { while m_2(i,t) > 0 { train <- minNumberTrainOnStation(V_{i,t}) remove train from V_{i,t} add train to V_{i-1,t+1} train <- minNumberTrainOnStation(V{i,t}) remove train from V_{i,t} add train to V_{i+1,t+1} }
} } while m_2(n, t+1) == 0 { create newTrain add newTrain to V_{n, t+1} }
}
The algorithm was implemented in C++ (we used standard data structures,
see [
For our experiments we use jT j = 14400 (equal to 10 days), cluster with 6 nodes. A node con guration one can see in Table 1.
The algorthim uses class Generator, which produces xed distribution of movement direction for each edge with given time interval . All these distributions are processed independently, so we have linear growth of speedup. After the processing the algorithm chooses the best schedule.
Tasks for nodes are distributed with MPI in a way that all cores of the processor are used. Thus we create 24 threads with OpenMP for every node (2 processor with 12 cores per node).
We using Intel Xeon Phi with o oad mode and create 240 threads with OpenMP.
Execution times, speedup and e ciency of the program for di erent con gurations can be seen from Table 2 and Table 3. Table 2 describes speedup and e ciency of the program compared with 1 node with 12 threads. In this paper the speedup is the ratio of the execution time for 1 node with 12 threads to the value of the Table 2. The e ciency is a ratio of speedup to number of devices (number of nodes or number of Intel Xeon Phi). Number of nodes and number of thread per node Times (minutes) 1 node x 12 threads 296 2 node x 12 threads 168 6 node x 12 threads 61 1 node x 1 mic 249 1 node x 2 mic 133 2 node x 1 mic 149 2 node x 2 mic 71 Number of node and number of thread per node speedup e ciency 2 node x 12 threads 1.761 0.88 6 node x 12 threads 4.852 0.8 1 node x 2 mic 1.87 0.93 2 node x 1 mic 1.67 0.83 2 node x 2 mic 3.5 0.82 4
Estimations of track capacity from B were obtained. The software, which implements the algorithm using MPI and Intel Xeon Phi coprocessor, was created. The numerical experiments were performed on the supercomputer with Intel Xeon Phi. Thus we have obtained a numerical con rmation of Conjecture 1. In future we are going to continue our research and check the correctness of Conjecture 2.