Skip to article
AHFE AHFE Discoveries AHFE International Open Access Journal
AHFE OPEN ACCESS OPEN ACCESS CONFERENCE PROCEEDINGS PAPER

An exact solution approach for prioritised and nonprioritized trains scheduling problem

1 LaROMaD Laboratory, Faculty of Mathematics, University of Science and Technology Houari Boumediene (USTHB), BP 32, 16111 Bab Ezzouar, Algeria ↗
2 LIST Laboratory, Faculty of Technology, University of M’hamed Bougara of Boumerdes (UMBB), 35000 Boumerdes, Algeria ↗
Publication year
Digital Object Identifier10.54941/ahfe1004094

Abstract

We deal with a new decision problem, namely, the problem of scheduling prioritized trains and nonprioritised trains in a railway network. The difference between these two types of trains is the no-wait constraint, which should be satisfied by the prioritized trains. However, the nonprioritised trains may remain on the current section until a section on the routing becomes available. Our objective is to find a feasible scheduling that minimizes the total tardiness. It has been showed that this problem is NP−hard, and it can be considered as a job shop scheduling problem with blocking and no-wait constraints. A mathematical integer programming formulation is given, and numerical experiments are provided for evaluating the proposed approach. To the best of our knowledge, we are the first who deal this trains scheduling problem with total tardiness criterion, which is the main contribution in this paper.

INTRODUCTION

We have addressed the problem of scheduling prioritised trains and non- prioritised trains in a single-track railway, when the prioritised trains such as express trains should pass through network continuously without any interruption, this imposes a no-wait constraint. However, the nonpriori- tised trains are allowed to pass though the next section only if available, this implies the blocking constraints. The network railway consists of sta- tions, single rails or several parallel rails and sidings. Each train has its path and a duration for every part of its path, with an earliest departure time, and a desired arrival time. At any time, each train can occupy at most one single track, as far as no more than one train can occupy each single track.

The trains scheduling problem was treated in a large variety of papers and projects of the literature. Cai and Goh (1994) classified a simple form of a single-track trains scheduling problem to be NP-complete. They devel- oped a heuristic algorithm based on a local optimality criterion for the trains

© 2023. Published by AHFE Open Access. All rights reserved. 861

862 Lissioued and Ourari

scheduling in a single-track railway with the assumption that all trains mov- ing in the same direction must have the same speed and terminating siding. Szpigel (1973) was the first who identified the similarities the first who iden- tified the similarities between a job shop problem and the trains scheduling in a single-track railway. The former was solved in Szpigel (1973) using a branch and bound algorithm, the initial linear programming excluded the order constraints. Dorfman and Medanic (2004) used a discrete-event model to schedule the traffic on a railway network. Their model was computa- tionally efficient and generated near optimal schedules with respect to a number of criteria related to travel time. Zhou and Zhong (2004) dealt with a double-track trains scheduling problem with multiple objectives. A branch and bound algorithm with an effective dominance rule is developed to gener- ate Pareto solutions for the bicriteria scheduling problem, and a beam search algorithm with utility evaluation rules is used to construct nondominated solutions. Caprara et al. (2006) described the design of a train timetabling system that takes into account several constraints that arise in real world applications. Zhou and Zhong (2007) used a resource constrained project scheduling for a single-track timetabling problem. They developed a branch and bound algorithm in order to obtain a feasible trains timetable with a guaranteed level of the optimality. Carey and Crawford (2007) developed heuristic algorithms to assist in the task of finding and resolving the con- flicts in draft train schedules. Burdett and Kozan (2010) interpreted the trains scheduling in terms of a job-shop problem with parallel machines. A disjunc- tive graph model was used in several algorithms with a makespan objective. Liu and Kozan (2011) were the first who treated the trains scheduling prob- lems when prioritized trains and nonprioritized trains are simultaneously traversed in a single-track railway. A generic algorithm has been developed to construct a feasible trains timetable in terms of the given trains order. Several authors have been interested in particular aspects of the problem, such as the demand for passers and we cite: Ghoseiri et al. (2004); Niu and Zhou (2013); Niu et al. (2015); D’Ariano et al. (2008); Törnquist and Persson (2007), Veelenturf et al. (2015). Cordeau et al. (1998) and Lusby et al. (2011) provided an overview of different problem structures and with resolution approaches. Recently, Lange and Werner (2018) addressed the trains schedul- ing problem with blocking constraints, and showed that the problem of job shop with blocking can be used to solve the trains scheduling problem for the minimization of the total tardiness of trains. Several mixed integer program- ming formulations based on different transformation approaches with or without additional routing flexibility were considered by using distinct types of decision variables. Lange and Werner (2018) and Liu and Kozan (2011) mentioned as perspectives in their study the trains planning with blocking and no-wait constraints, a scheduling problem that we are dealing with in this paper.

In this paper, we propose an integer linear program based on the model of Lange and Werner (2018) to find exact solutions. The remainder of this paper is organized as follows. First, we define our problem and the notations associated to its formulation. After, we present the mathematical model and computational results. Finally, we discus some perspectives of our work.

An Exact Solution Approach for Prioritised and Nonprioritised Trains Scheduling Problem 863

PROBLEM DESCRIPTION The network considered consists of single tracks connecting the sations in the two directions. The capacity of a single track is one unit, whereas sidings and stations can be occupied by as many trains as they have parallel tracks. On the other hand, each train can only occupy one track section at a time. For each train a fixed route is predefined to travel on, and it is supposed that the train begins and ends its journey by sections of the extremity. Moreover, an earliest departure time at the origin and preferred arrival time at the destination are given for every train.

The order of trains is to be determined for every track, taking into consider- ation that prioritised and nonprioritised trains are simultaneously traversing on a single tracks network. Prioritised trains (such as express passenger trains) must pass from the departure to the terminal station without inter- ruption, while the nonprioritised trains are those whose can traverse the succeeding track only if it is available, otherwise they remain on the current section, and are blocked until to pass through the next section. The problem can be considered as a prioritised and nonprioritised trains scheduling prob- lem to determine the arrival time of each train, in order to minimize the total tardiness of trains.

It should be noted that we can observe the correspondence between this trains scheduling problem and the job shop scheduling problem with blocking and no-wait constraints as shown in Szpigel (1973), Kreuger et al. (1997), Oliveira and Smith (2000), D’Ariano et al. (2007), Liu and Kozan (2011), Gholami et al. (2013) and Lange and Werner (2018).

More precisely, let be a set of trains traveling through railway network having a bidirectional single tracks, stations and siding with different parallel tracks. Trains are represented as jobs J =

Mathematical equation reproduced from the original PDF
Equation reproduced from the original PDF.

Mathematical equation reproduced from the original PDF
Equation reproduced from the original PDF.
Mathematical equation reproduced from the original PDF
Equation reproduced from the original PDF.

which represent tracks. Referring to the literature:

  • Sections with parallel tracks can be considered as parallel machines, in other words each track represents one machine, and by the definition of a train path one of the parallel tracks has to be chosen.
  • The train path is considered as the technological order of the job.
  • The journey of the train along its track without interruption is considered as the job execution on machines without interruption.
  • The passage of the train on the track section is represented by an oper- ation Oij, which define the processing of the job by a machine without interruption.

  • Each job has an ordered set of ni operations Ji =

Oi1, . . . Oini

expressing the processing order on the different machines which is already established and known, this order translates the precedence constrains between the operations of the same job.

  • The processing times pij of the operations correspond to the travel time of trains on track sections. Moreover, the release time ri and the due date di of any jobs is given, which describe earliest time and desired leaving times of the trains.

864 Lissioued and Ourari

  • Jobs recirculation (recrs) has been included, provided that job can be processes more than one way for each machine.

We note that direction of each train is represented implicitly by the tech- nological order of the jobs on different machines, so we dispense with the direction data of trains. The scheduling of trains is defined by the determi- nation of the order of all jobs on machines and the starting time Sij for all operations. The blocking situation occurring in trains is interpreted as jobs blocking machines, when a job having completed processing on a machine, remains on the machine until the succeeding machine becomes available for processing. We kept the same representation of the blocking situation used by Lange and Werner (2018), by applying starting time variables and includ- ing blocking in additional constraints. For the no-wait constraint, a job must be processed from the start to the completion without interruption either on or between machines, in other words, two operations must be performed without any interruption.

Therefore, the difference between the completion time of the last operation of a job and the start time of its first operation is equal to the sum of processing times of all its operations. This constraint describes for example the case of trains carrying dangerous products that must pass without interruption, or the express passenger trains (speed trains).

The objective is to schedule all jobs in order to minimize the total tardiness of jobs. The tardiness Ti of each job is calculated as follows: Ti = max

0, Ci −di

when: Ci = Sini + pini. This problem can be classi- fied into the NWBPMJSS that means no-wait blocking parallel machines job nP shop scheduling, and denoted by: Jm|ri, di, block, recs, no −wait| Ti.

Mathematical equation reproduced from the original PDF
Equation reproduced from the original PDF.
  • Each operation can be executed by only one machine at a time.
  • Each machine can only process at most only one operation at a time.
  • The execution of a job on a machine cannot be interruption.
  • Each machine treats each job at most one times.

Disjunctive and Alternative Graph Model The disjunctive graph proposed by Roy and Sussman (1964), used for for- mulate the job shop scheduling problem is defined by G = (X, A ∪E) where:

  • X denotes a set of vertices corresponding to operations of jobs. This set contains two additional dummy vertices, which represent the start and the end of schedule.
  • A is a set of conjunctive arcs which represent the precedence constraints between two consecutive operations of the same job. We also add con- junctive arcs from one additional dummy vertex of the start and the first operation of each job, and from the last operation of every job to a second additional dummy vertex of the end

An Exact Solution Approach for Prioritised and Nonprioritised Trains Scheduling Problem 865

  • E disjunctive edges between every operations requiring the same machine. A disjunctive edge can be represented by two opposite directed arcs. These constraints are called disjunctive constraints. they forbid cycles in a clique corresponding to a machine.

The disjunctive graph disadvantage is that it does not take into consid- eration the intermediate buffer’s capacity between machines. A blocking situation that should be carefully taken into account. To integrate this con- straint, Mascis ans Pacciarelli (2007) have adopted the disjunctive graph to a more general graph called alternative graph machine. In the alternative graph, that considers the blocking situations, the pair (Oij →Ohl) and (Ohl →Oij) of disjunctives arcs (connecting operations requiring the same machine) is replaced by a pair of alternative arc (Os

ij →Ohl) and (Os

hl →Oij), where Os

hl is the successor vertex of Oij in the same job that will be processed imme- diately on different machine. Figures 1 and 2 show an example of the two different graphs.

Figure 1: Dijunctive graph for 3 jobs, 3 machines JSP without considering blocking constraint.
Original PDF Figure 1:
Figure 2: Alternative graph for 3 jobs, 3 machines JSP with blocking constraint.
Original PDF Figure 2:

MATHEMATICAL MODEL In this section, we present the integer linear program that we use to formulate the job shop scheduling problem with blocking and no-wait constraint. Based on the model of Lange and Werner (2018). We have proposed a mathematical model to resolve the job shop scheduling problem with blocking and no- wait constraints. The following notation is used for parameters and decision

866 Lissioued and Ourari

variables in the mathematical programming formulation for the NWBPMJSS problem.

Parameters and Indices

n: Total number of jobs (trains) m : Total number of machines (sections) ni : Total number of operations in the job Ji k: Index of machines k = 1 . . . m A: A large number I : Index of jobs i = 1 . . . n j: Index of operation order in job Oij: The jth operation of the job Ji W: Set of jobs subject to the no-wait constraint Opk: Set of operations executed by the machine k, k = 1 . . . m Oi: Set of operations of the same job Ji, Oi =

Oi1 . . . Oini Sij : The starting time of the operation Oij Cij : The completion time of the operation Oij pij: The processing time of the operation Oij di: The due date of the job Ji ri: The release time of the job Ji.

Decision Variable The job shop scheduling with blocking and no-wait constraints is modelled by the use of binary decision variables.

Mathematical equation reproduced from the original PDF
Equation reproduced from the original PDF.

1 if the operation Oij is executed before the operation Ohl on the machine Mk 0 otherwise

Constraints In the following, constraints (1) guaranteed that the starting time of each job Ji ∈J to be greater than or equals to its release time ri:

ri ≤si1 ∀i, Ji ∈J (1) Constraints (2) describe the operations precedence constraints between operations of the same job:

Sij + pij ≤Sij + 1 Oij ∈Oi, Oini ∀Ji ∈J\W (2) The no-wait constraints are the following: each operation from the jobs Ji ∈W must start its treatment immediately after the processing of the precedent operation.

Sij + pij = Sij + 1 Oij ∈Oi\Oini ∀i, Ji ∈W (3) The tardiness of a job is defined in Constraints (4) and (5):

Ti ≥Sini + pini −di ∀i, Ji ∈J\W (4) Ti ≥0 ∀i, Ji ∈J\W (5)

An Exact Solution Approach for Prioritised and Nonprioritised Trains Scheduling Problem 867

Constraints (6) are aimed at operations processed by the same machine. It imposes directly one of the two operations Oij or Ohl to be processed the first on the machine k: yij,hl,k + yhl,ij,k = 1 ∀Oij, Ohl ∈Opk avec i < h, Mk ∈M (6)

To ensure more the order expressed by constraints (6), the completion time (Cij = Sij + pij of the operation processed the first has to be less than or equal to the starting time of precedence operation, that’s ensured by the following constraint: Shl + A 1 −yij,hl,k ≥Sij + Pij ∀Oij, Ohl ∈Opk, Mk ∈M (7)

The blockage constraints are expressed by the following inequalities: 1 −yij,hl,k ≥Sij + 1 ∀Oij, Ohl ∈Opk, Mk ∈M (8) Shl + A

Finally, the constraints of integrity of variables: yij,hl,k ∈{0, 1} ∀Oij, Ohl ∈Opk, Mk ∈M (9)

Objective Function

nP

Minimizing the total tardiness: Min

Ti.

Mathematical equation reproduced from the original PDF
Equation reproduced from the original PDF.

OVERVIEW OF SOME PERTINENT LITERATURE RESULTS The computational complexity of different versions of job shop scheduling problem is considered as an important factor in the study. Since, the job shop scheduling problem with unlimited buffers is one of the most difficult NP-hard combinatorial optimization problems. The job shop scheduling with blocking (limited buffer capacity) and no-wait situations is strongly NP-hard, and limited number of research papers are dedicated for the NWBJSSP prob- lem. In the following paragraph, some pertinent works on the NWBJSSP are presented.

Brizuela et al. (2001), proposed a genetic algorithm to deal the NWBJSSP with makespan objective function. Decoding techniques that ensure no vio- lation of the no-wait and blocking conditions were proposed as the main contribution of their research. Van den Broek and Hurkens (2007) proposed a new heuristic and an integer programming formulation for the NWBJSSP with makespan objective function. The main contribution is that the pro- posed heuristic always finds feasible solution, and the tests prove that the found solutions have good quality. The authors reported that one of the dis- advantages is that the computation time is increased substantially especially if the size of the input increases.

Liu and Kozan (2011) deal with train-scheduling problems when the prioritised trains and nonprioritized trains are traversed simultaneously in a complex rail network. The problem is mathematically formulated by integer programming and analysed based on an alternative graph model.

868 Lissioued and Ourari

In the first time, authors proposed a constructive algorithm to construct the feasible train timetable, then a two-stage hybrid heuristic algorithm is developed by combining the constructive algorithm and the local-search heuristic. The computational experiments and real-life applications show that the proposed two stage hybrid algorithm is able to find the prefer- able order of trains thereby greatly reducing the makespan of the con- structed train timetable. Louaqad et al. (2018) addressed the problem of job shop scheduling with transportation, blocking and no-wait constraints. Since the makespan objective function is considered, they formulated the problem based on the model of Manne (2005) used for NWBJSSP. In Addition, they proposed two heuristics (HC1) (HC2). Experimental results showed that heuristic (HC2) is quite efficient in terms of obtaining feasi- ble solutions. In addition, the comparison with MILP showed that (HC2) heuristic found approximate solutions in reasonable times for very large instances.

COMPUTATIONAL EXPERIMENTS The evaluation of our mathematical model is carried out using a first set of instances (n, m) ∈(10, 11) used by Lange and Werner (2018), and the second set of instances (n, m) ∈(15, 11) , (20, 11) , we developed from the first set (n, m) ∈(10, 11)by duplicating some jobs with there data. Table 1 illustrates an example of instance (n, m) ∈(10, 11) . For more details, the reader to can refer to Lange and Werner (2018).

Table 1. Input data information.

Table available in the original PDF paper.

Ji ri di Tech. order Processing time J1 13 30 (M10, M9, M8, M6, M5, M6, M8, M9, M11) (2,1,1,1,4,1,1,1,2) J2 2 38 (M1, M3, M4, M6, M8, M9, M11) (4,4,12,2,2,2,4) J3 8 37 (M1, M3, M4, M3, M2) (4,4,8,4,4) J4 5 41 (M1, M3, M4, M6, M8, M9, M11) (4,4,12,2,2,2,4) J5 4 40 (M11, M9, M7, M6, M4, M3, M2) (4,2,2,2,12,4,4) J6 6 41 (M10, M9, M7, M6, M5, M3, M1) (4,2,2,2,12,4,4) J7 11 47 (M11, M9, M7, M6, M4, M3, M2) (4,2,2,2,12,4,4) J8 2 38 (M11, M8, M7, M6, M4, M3, M2) (4,2,2,2,12,4,4) J9 8 26 (M2, M3, M5, M6, M8, M9, M10) (2,2,6,1,1,1,2) L10 5 53 (M11, M9, M8, M6, M4, M3, M1) (8,4,4,4,4,8,8)

Table 2 shows numerical results for the NBJSSP obtained by by our ILP. These results are obtained used the CPLEX 12.6 as LP solver. The linear program using CPLEX 12.6 program were run on an Intel R Core(TM) i 3(2.30GHz) with 4 GB RAM. The set of instances com- prises 15 instances grouped into three subsets with respective sizes of (n, m) ∈(15, 11) , (20, 11) were n represents the number of jobs (trains) and mrepresents the number of machines (sections). As assumed by Lange and Werner (2018), the origin and the destination of the routing train are different from each other.

An Exact Solution Approach for Prioritised and Nonprioritised Trains Scheduling Problem 869

The number of jobs submitted to the no-wait constraint is different from instances to others as it’s shown in Table 2. The first five instances having 10 jobs and 11 machines are solved optimally in a very small computation time. The most instances of the second group of instances (n, m) ∈(15, 11) re even solved optimally in a considerable execution time. the 5thinstance in this group having 2 jobs no-wait remain unresolved for more than 2 hours.

As shown in Table 2, no more instance is solved in the third group of instances having (n, m) ∈(20, 11). We have interrupted the running in 2 hours.

Table 2. Numerical results obtained by mathematical formulation.

Table available in the original PDF paper.

Instance Nb_job_no-wait Nb_var Nb_con PTi Time (10,11)_1 3 505 1554 138* 5.24 S (10,11)_2 3 509 1765 249* 4.04 S (10,11)_3 2 512 1673 203* 1.42 S (10,11)_4 2 534 2031 252* 2.04 S (10,11)_5 1 571 1767 260* 6.16 S Mean 525.6 1504,6 3,742

(15,11)_1 3 1014 3928 322* 2546.17s (15,11)_2 4 1057 4607 460* 106.99s (15,11)_3 5 1119 3878 296* 24.49 S (15,11)_4 3 1121 4204 373* 953.77 S (15,11) 5 2 1262 4233 550 (9,94%) 2h Mean 1164,6 4286,4 (20,11)_1 3 2029 7996 674 (44,17%) 2h (20,11)_2 4 2108 1107 7758 (29,71%) 2h (20,11)_3 5 2035 7479 625 (27,02%) 2h (20,11)_4 8 2010 7277 373* 2921,28s (20,11)_5 7 2213 7921 554 (7,58%) 2h Mean 2079 6356

In following, we give the notation used in the numerical results table:

  • Number of variables: (Nbr-var), number of constraints: (Nbr-con)

nP

  • The total tardiness value

Ti, and the percentage gap between the i=1 best integer solution found and the lower bound (for the values without optimality)

  • Running time (CPU) necessary for the resolution Noted that, we limit the computational time on 2h. Since the computational results is made on hard instances with up to 20 jobs and 11 machines, it shows that there is a correlation relation between the size of the instance and the time of resolution, it is also remarkable effects of the blocking and no-wait constraints on the value of the optimal solutions.

870 Lissioued and Ourari

CONCLUSION

This work is the first that deals with the problem of scheduling prioritised trains and nonprioritised trains in a railway network with total tardiness cri- terion. In this study, we described our problem that corresponds to a job shop scheduling problem with no-wait and blocking constraints. We proposed a mathematical integer programming model on the basis of the one developed by Lange and Werne (2018). In our case, we have adapted the Lange and Werne’s model for the job shop scheduling with blocking constraints, by con- sidering both the blocking and no-wait constraints. The performance of this ILP has been evaluated through numerical experiments.

These experiments have shown that our ILP solves to optimally the instances with small and average sizes. For further researches, we intend to ameliorate the solutions obtained in this paper, especially for big size instances, by investigating Meta-heuristic methods.

REFERENCES

Brizuela, C. A, Zhao, Y and Sannomiya, N. No-wait and blocking job-shops: Challenging problems for Gas. International Conference on Systems, Man and Cybernetics. e-Systems and e-Man for Cybernetics in Cyberspace, Tucson, AZ, USA, 2349–2354 (2001). Burdett, B. and Kozan, E. A disjunctive graph model and framework for constructing

new train schedulies. European Journal of Operational Research. V. 200(5) 85–98 (2010). Cai, X. and Goh, C. A fast heuristic for the train scheduling problem. Computers and Operations Research., V.21(5) 499–510 (1994). Caprara, A., M. Monaci, P. Toth, P. L. Guida. GSingle-track train timetabling

with guaranteed optimality: branch and-bound algorithms with enhanced lower bounds. Discrete Appl. Math. 154(5) 738–753 (2006). Carey, M., I. Crawford. Scheduling trains on a network of busy complex stations.

Transportation Research Part B V. 41 159–178(2007). Cordeau, J. F., Toth, P., and Vigo, D. A survey of optimization models on train routing and scheduling. Transportation Science. V. 32(4) 380–404 (1998). D’Ariano, A, Pacciarelli, D and Pranzo, M. A branch and bound algorithm

for scheduling trains in a railway network. European Journal of Operational Research. V. 183(2) 643–657 (2007). D’Ariano, A., Corman, F., Pacciarelli, D., and Pranzo, M. Reordering and local rerouting Strategies to manage train traffic in real time. Transportation Science. V. 42(4) 405–419 (2008). Dorfman, M. and Medanic, J. J, Scheduling trains on a railway network using a

discrete event model of railway traffic. Transportation Research Part B., V. 38 81–98 (2004). Gholami, O, Sotskov, YN and Werner, F. Fast edge-orientation heuristics for job-shop scheduling problems with applications to train scheduling. International Journal of Operational Research. V.2 19–32 (2013). Ghoseiri, K., Szidarovszky, F., and Asgharpour, M. J. SA multiobjective train schedul-

ing model and solution. Transportation Research Part B: Methodological. V. 38(10) 927–952 (2004).

An Exact Solution Approach for Prioritised and Nonprioritised Trains Scheduling Problem 871

Kreuger, P, Carlsson, M, Olsson, J, Sjöland, T and Aström, E. Trip scheduling on single track networks the tuff train scheduler. Workshop on industrial constraint directed scheduling 1–12 (1997). Lange, J and Werner, F. Railway Approaches to Modeling Train Scheduling Problems

as Job Shops with Blocking Constraints. Journal of Scheduling. V. 21(2) 191–207 (2018). Liu, S. and Kozan, E. Scheduling trains with priorities: a no-wait blocking parallelmachine job shop scheduling model. Transportation Science, V. 45(2), (2011) 175–198. Louaqad, S, Kamach, O and Iguider, A. Scheduling for job shop problems with trans-

portation and blocking no-wait constraints. Journal of Theoretical and Applied Information Technology, V. 96(10), (2018). Lusby, R. M., Larsen, J., Ehrgott, M., and Ryan, D. track allocation: Models and methods. OR Spectrum. V. 33(4) 843–883 (2011). Manne, A. On the job shop scheduling problem Operations Research. V.1960(8)

219–22 (2005). Mascis, A and Pacciarelli D. Job-shop scheduling with blocking and no-wait constraints. European Journal of Operational Research. V. 143 498–517 (2002). Niu, H., and Zhou, X. Optimizing urban rail timetable under time dependent

demand and oversaturated conditions. Transportation Research Part C: Emerging Technologies 36 212–230 (2013). Niu, H., Zhou, X., and Gao, R. Train scheduling for minimizing passenger waiting time with time-dependent demand and skipstop patterns: Nonlinear integer programming models with linear constraints. Transportation Research Part B: Methodological V. 76 117–135 (2015). Oliveira, E and Smith B. M. A job-shop scheduling model for the single-track railway

scheduling problem. Research Report Series 21, School of Computing, University of Leeds (2000). Roy, B and Sussman, B. Les Probl‘em d’Ordonnancement avec Constraintes Disjonctives. Note DS No.9 bis, SEMA, Paris (1964). Szpigel, B. Optimal train scheduling on a single line railway. European Journal of

Operational Research. V. 72(3) 344–351 (1973). Törnquist, J., and Persson, J. A. ON-tracked railway traffic rescheduling during disturbances. Transportation Research Part B: Methodological V. 41(3) 342–362 (2007). Van den Broek, J and Hurkens, C. A new heuristic for job shops with no-wait and

blocking constraints. ARRIVAL-TR, V. 0112, (2007). Veelenturf, L. P., Kidd, M. P., Cacchiani, V., Kroon, L. G. and Toth, P. A railway timetable rescheduling approach for handling large-scale disruptions. Transporta- tion Science. V. 50(3) 841–862 (2015). Zhou, X. and Zhong, M. Distinguishing cartesian powers of graphs. Transportation

Research Part B. V. 21 320–341 (2007). Zhou, X., M. Zhong. Bicriteria train scheduling for high-speed passenger railway planning applications. Eur. J. Oper. Res. V.167 752–771 (2004).

Cover of the proceedings volume Human Interaction & Emerging Technologies (IHIET 2023): Artificial Intelligence & Future Applications

Explore the complete digital volume

Human Interaction & Emerging Technologies (IHIET 2023): Artificial Intelligence & Future Applications

Read this individual research paper free through the original publisher, or explore the full digital proceedings book.

ISBN 978-1-958651-87-2

Explore this ISBN in the AHFE Bookstore Listed in the July 2026 bookstore catalogue; search by ISBN to confirm current availability · Digital book purchase optional

Explore Related Research

Related research 8 matches

More papers from this volume

← Back to Research ExplorerBrowse the full library →