1,721,051 research outputs found
The effectiveness of static implications in real-time railway traffic management
No full textWe study a real-time railway traffic management problem. It consists in adjusting train timetables in order to restore feasibility when unforeseen events in the network make unfeasible the off-line generated timetable. The problem can be formulated as a huge job-shop problem with blocking constraints, which has to be solved within strict time limits due to real-time constraints. Unfortunately, even finding a feasible solution is an NP-complete problem. To this aim, implication rules are a powerful tool to design fast and effective solution algorithms. In this paper we present a new simple static implication rule for the blocking job-shop problem, and its application to the real-time railway traffic management problem. A computational experience, based on a real railway infrastructure, shows the effectiveness of the implication rule to speed up a heuristic solution algorithm.Transport and PlanningCivil Engineering and Geoscience
Assigning jobs to time frames on a single machine to minimizetotal tardiness
No full textThis paper deals with a sequencing problem arising in the management of paced flowlines, that is production lines where jobs are released at constant time intervals. The problem is to sequence jobs to minimize total tardiness. The problem can be formulated as an assignment problem with a number of knapsack constraints. We prove the strong NP-hardness of the problem and give a number of lower bounds which are used in a branch-and-bound algorithm. Computational results in realistic settings confirm the eff ectiveness of the procedure developed. The results are particularly interesting with reference to mixed-model assembly lines in which several jobs of few diff erent types are produced periodically
Flexible timetables for real-time train rescheduling
No full textA common strategy for railway traffic management consists in the off-line development of a detailed timetable, and operating in real time with strict adherence to it. In real time, unforeseen events may require to partially modify the planned timetable. A recent trend in railway companies is for managing congested areas by planning less in the off-line phase, and solving train conflicts in real time. In this paper we investigate the concept of flexible timetable, and the relations between flexibility and delay minimization. We use a detailed model for conflict resolution, based on the alternative graph formulation, and a branch and bound algorithm for solving the problem at optimality. We compare optimal solutions computed when varying timetable flexibility. An extensive computational study on a small and complicated rail network has been carried out, based on a bottleneck area of the Dutch railway network
A branch and bound algorithm for scheduling trains in a rail network
No full textThe paper studies a train scheduling problem faced by railway infrastructure managers during real-time traffic control. When train operations are perturbed, a new conflict-free timetable of feasible arrival and departure times needs to be re-computed, such that the deviation from the original one is minimized. The problem can be viewed as a huge job shop scheduling problem with no-store constraints. We make use of a careful estimation of time separation among trains, and model the scheduling problem with an alternative graph formulation. We develop a branch and bound algorithm which includes implication rules enabling to speed up the computation. An experimental study, based on a bottleneck area of the Dutch rail network, shows that a truncated version of the algorithm provides proven optimal or near optimal solutions within short time limits
Reordering and Local Rerouting Strategies to Manage Train Traffic in Real Time
No full textTraffic controllers regulate railway traffic by sequencing train movements and setting routes with the aim of ensuring smooth train behaviour and limiting, as much as possible, train delays. In this paper, we describe the implementation of a real-time traffic management system, called ROMA (Railway traffic Optimization by Means of Alternative graphs), to support controllers in the everyday task of managing disturbances. We make use of a branch-and-bound algorithm for sequencing train movements, while a local search algorithm is developed for rerouting optimization purposes. The compound problem of routing and sequencing trains is approached iteratively, computing an optimal train sequencing for given train routes and then improving this solution by locally rerouting some trains. An extensive computational study is carried out, based on a dispatching area of the Dutch railway network. We study practical size instances, and include in the model important operational constraints, including rolling stock and passenger connections. Different types of disturbances are analysed, including train delays and blocked tracks. Comparison with common dispatching practice shows the high potential of the system as an effective support tool to improve punctuality
A rollout metaheuristic for job-shop scheduling problems
No full textIn this paper we deal with solution algorithms for a general formulation of the job shop problem, called alternative graph. We study in particular the job shop scheduling problem with blocking and/or no-wait constraints. Most of the key properties developed for solving the job shop problem with infinite capacity buffer do not hold in the more general alternative graph model. In this paper we report on an extensive study on the applicability of a metaheuristic approach, called rollout or pilot method. Its basic idea is a look-ahead strategy, guided by one or more subheuristics, called pilot heuristics. Our results indicate that this method is competitive and very promising for solving complex scheduling problems
Multi-agent single machine scheduling
Full text linkWe consider the scheduling problems arising when several agents, each owning a set of nonpreemptive jobs, compete to perform their respective jobs on one shared processing resource. Each agent wants to minimize a certain cost function, which depends on the completion times of its jobs only. The cost functions we consider in this paper are maximum of regular functions (associated with each job), number of late jobs and total weighted completion time. The different combinations of the cost functions of each agent lead to various problems, whose computational complexity is analysed in this paper. In particular, we investigate the problem of finding schedules whose cost for each agent does not exceed a given bound for each agent
- …
