Detection and resolution of conflicting change operations in version management of process models

Version management of process models requires that different versions of process models are integrated by applying change operations. Conflict detection between individually applied change operations and conflict resolution support are integral parts of version management. For conflict detection it is utterly important to compute a precise set of conflicts, since the minimization of the number of detected conflicts also reduces the overhead for merging different process model versions. As not every syntactic conflict leads to a conflict when taking into account model semantics, a computation of conflicts solely on the syntax leads to an unnecessary high number of conflicts. Moreover, even the set of precisely computed conflicts can be extensive and their resolution means a significant workload for a user. As a consequence, adequate support is required that guides a user through the resolution process and suggests possible resolution strategies for individual conflicts. In this paper, we introduce the notion of syntactic and semantic conflicts for change operations of process models. We provide a method how to efficiently compute conflicts precisely, using a term formalization of process models and consider the subsequent resolution of the detected conflicts based on different strategies. Using this approach, we can significantly reduce the number of overall conflicts and reduce the amount of work for the user when resolving conflicts.     

A multi-camera image processing and visualization system for train safety assessment

In this paper we present a machine vision system to efficiently monitor, analyse and present visual data acquired from a railway overhead gantry equipped with multiple cameras. This solution aims to improve the safety of daily life railway transportation in a two-fold manner: (1) by estimating multiple safety requirements using image analysis algorithms that can process large imagery of trains (2) by helping train safety operators to detect any possible malfunction on a train. The system exploits high-rate visible and thermal cameras that observe a train passing under a railway overhead gantry. The machine vision system is composed of three principal modules: (1) an automatic wagon identification system, recognizing the wagon ID according to the UIC classification of railway coaches; (2) a system for the detection and localization of the pantograph of the train; (3) a temperature monitoring system. These three machine vision modules process batch trains sequences and their resulting analysis are presented to an operator using a multitouch user interface.     

列车运行网络抗毁性能的量化研究*

为尽可能减少由于自然灾害导致铁路运输受阻甚至中断情况下受影响的列车数,提出了对现有列车运行方案以抗毁性优化为目标的量化分析方法.首先基于当前列车运行方案建立列车运行网络模型,该模型以实际铁路站点为节点,以实际铁路线为边,以每条边开行的列车数量为边权重;随后提出了一个称之为度权效应的抗毁性评价指标,并以该评价指标为目标函数,使用改进粒子群算法对网络权重进行优化.仿真结果得出了优化前后列车运行网络的抗毁性评价值分别为0.8881和0.9063,表明可通过量化分析方法来刻画列车运行网络的抗毁性能.     

Dispatching and coordination in multi-area railway traffic management

This paper deals with the development of decision support systems for traffic management of large and busy railway networks in case of severe disturbances. Railway operators typically structure the control of complicated networks into the coordinated control of several local dispatching areas. A dispatcher takes rescheduling decisions on the trains running on its local area while a coordinator addresses global issues that may arise between areas. While several advanced train dispatching models and algorithms have been proposed to support the dispatchers' task, the coordination problem did not receive much attention in the literature on train scheduling. This paper presents new heuristic algorithms for both local dispatching and coordination and compares centralized and distributed procedures to support the task of dispatchers and coordinators. We adopt dispatching procedures driven by optimization algorithms and based on local or global information and decisions. Computational experiments on a Dutch railway network, actually controlled by ten dispatchers, assess the performance of the centralized and distributed procedures. Various traffic disturbances, including entrance delays and blocked tracks, are analyzed on various time horizons of traffic prediction. Results show that the new heuristics clearly improve the global performance of the network with respect to the state of the art.     

Modelling disruptions and resolving conflicts optimally in a railway schedule

Resolving disruptions, by dispatching and rescheduling conflicting trains is an NP-complete problem. Earlier literature classify railway operations as: (i) tactical scheduling, (ii) operational scheduling, and (iii) rescheduling. We distinguish the three based on operational criticality. Existing optimisation models do not distinguish precisely between scheduling and rescheduling based on constraints modelling; the only difference is in their objective function. Our model is the first of its kind to incorporate disruptions in an MILP model and to include conflicts-resolving constraints in the model itself. The major advantage of such a formulation is that only those trains which are disrupted are rescheduled and other non-conflicting trains retain their original schedules. Our model reschedules disrupted train movements on both directions of a single track layout with an objective to minimise total delay of all trains at their destinations. Using a small sized data it is proved that all possible conflicts out of a disruption are resolved. Apart from achieving optimal resolutions, we infer through experimental verification that a non-standard dispatch ordering is a requisite for global optimality, as cogitated by other authors.     

Emphasizing conflict resolution versus conflict avoidance during schedule generation

Classical planning systems attempt to solve a planning problem by avoiding possible conflicts before the actions are put on a timeline. This is computationally very expensive and the search for all possible future conflicts may be prohibitive. A conflict resolution approach can check for immediate conflicts and try conflict resolution strategies as each activity is put on a timeline without regard for possible future conflicts. A more practical approach is to use a combination of conflict avoidance and conflict resolution based upon heuristics which limit the amount of search required when either is used. Because humans are not good at solving problems which require complex lookahead, this combined approach, with emphasis on conflict resolution, is what human schedulers actually use when they develop schedules. A system which simulates this human approach to scheduling has been developed at NASA's Goddard Space Flight Center for scheduling satellite activities. This system, which includes the Planning And Resource Reasoning (PARR) shell, allows expert schedulers to specify conflict resolution strategies as well as conflict avoidance strategies to be used during the scheduling process. PARR has been used since May 1987 to schedule the Tracking and Data Relay Satellite System services for the Earth Radiation Budget Satellite. PARR will also be used to schedule platform resources on the Explorer Platform, scheduled for launch in early 1992. This paper describes the advantages of using a combined conflict avoidance and resolution approach in a satellite scheduling system.     

具有极大时间约束的轨道交通系统的周期分析

运用极大–加代数方法研究具有极大时间约束的轨道交通系统的周期运行规律.分别建立具有两个车站的双回路城际轨道交通系统和具有n个车站的单回路城市轨道交通系统的极大–加线性模型.对于前者,运用系统状态矩阵的周期性,证明各个车站第k次与第(k+2)次的发车时间间隔相同;对于后者,运用状态变量的线性替换,证明在任何初始状态下,系统经过一次循环便可进入周期稳态运行,即列车连续两次到达同一车站的时间间隔相同.周期时间分析有利于轨道交通系统列车时刻表的编排和周期运行方案的设计.为验证本文结果的实用性和有效性,给出周期时间分析在列车调度和线路规划中的应用例子.     

基于两阶段算法的列车调度问题

考虑突发铁路损坏对列车运行的影响, 在列车运行调度理论的基础上, 建立了单线铁路调度模型, 设计了一种带有突发事件处理能力的两阶段列车调度算法, 第1阶段对列车区间运行速度进行调整, 第2阶段对列车的停站时间进行调整. 将3种有效的搜索算子、一种自适应更新规则与粒子群算法相结合, 以列车延迟率作为优化目标, 求解单线铁路列车调度问题. 通过将所提算法与其他算法在相同实验条件下进行测试对比, 并进行突发事件测试, 验证了所提算法的有效性.     

A feasible timetable generator simulation modelling framework for train scheduling problem

An important problem in management of railway systems is the train scheduling/timetabling problem. This is the problem of determining a timetable for a set of trains that do not violate track capacities and satisfy some operational constraints. In this study, a feasible timetable generator framework for stochastic simulation modelling is developed. The objective is to obtain a feasible train timetable for all trains in the system. The feasible train timetable includes train arrival and departure times at all visited stations and calculated average train travel time. Although this study focuses on train scheduling/timetabling problem, the developed simulation framework can also be used for train rescheduling/dispatching problem if this framework can be fed by real time data. The developed simulation model includes stochastic events, and can easily cope with the disturbances that occur in the railway system.     

The periodicity and robustness in a single-track train scheduling problem

The most important operating problem in any railway industry is to produce robust train timetables with minimum delays. The train scheduling problem is defined as an application of job shop scheduling which is considered to be one of the most interesting research topics. This paper deals with scheduling different types of trains in a single railway track. The authors have focused on the robust and periodic aspects of produced timetables. This paper is also concerned with some applicable constraints, such as the acceleration and deceleration times, station capacity and headway constraints. The periodic timetable for railways is modeled based on the periodic event scheduling problem (PESP). Furthermore, a fuzzy approach is used to reach a tradeoff among the total train delays, the robustness of schedules, and the time interval between departures of trains from the same origins. To solve large-scale problems, a meta-heuristic algorithm based on simulated annealing (SA) is utilized and validated using some numerical examples on a periodic robust train scheduling problem. Finally, a robustness measure is defined in order to assure the effectiveness of the proposed SA to find robust solutions.     

Personnel scheduling in a complex logistic system: a railway application case

In complex logistic systems, such as transportation systems, dealing with personnel scheduling is a non-trivial task. Duties have to be created and assigned to workers in a way to optimize a certain objective function. In this paper, in particular, we consider the case of scheduling train drivers on a railway subnetwork. Train driver scheduling involves the construction of feasible duties from a set of trips to be carried out by a number of train drivers. Each duty consists of a sequence of trips to be carried out by a single train driver on a single day. The duties should be such that: each trip is covered by at least one duty, each duty satisfies feasibility constraints, additional constraints involving the complete schedule are satisfied, one or several objectives are met. In this paper we focus on minimizing the number of duties and on maximizing the robustness of the obtained schedule for outside disruptions. We present an implicit column generation solution approach. We describe a heuristic procedure to find an initial feasible solution together with a heuristic branch-and-price algorithm based on a dynamic programming algorithm for the pricing-out of columns. We tested our approach on the timetable of the Intercity train series 500, 700, 1600 and 1700 of NS Reizigers, the largest Dutch operator of passengers trains.     

STK/Scheduler在卫星数传调度中的应用研究

卫星数传调度问题是一类复杂的组合优化问题,即如何为卫星数传任务分配地面资源的问题,它是当前航天领域需要重点研究的问题之一.STK/Scheduler模块是STK工具包中的调度模块,对外提供了二次开发功能.针对卫星数传调度问题,研究了STK/Scheduler模块在该问题中的应用.首先在分析问题的基础上建立了卫星数传任务模型和调度模型,然后对基于STK/Scheduler的卫星数传调度系统进行了设计.最后利用AFIT基准数据进行了验证,结果表明在卫星数传任务规模不太大的情况下,TK/Scheduler为卫星数传调度问题的求解提供了一条捷径.     

An Advanced Real-Time Train Dispatching System for Minimizing the Propagation of Delays in a Dispatching Area Under Severe Disturbances

In highly utilized rail networks, as in the Netherlands, conflicts and subsequent train delays propagate considerably in time and space during operations. In order to realistically forecast and minimize delay propagation, there is a need to extend short-term traffic planning up to several hours. On the other hand, as the magnitude of the time horizon increases the problem becomes computationally intractable and hard to tackle. In this paper, we decompose a long time horizon into tractable intervals to be solved in cascade with the objective of improving punctuality. We use the ROMA dispatching system to pro-actively detect and globally solve conflicts on each time interval. The future evolution of railway traffic is predicted on the basis of the actual track occupation, the Dutch signaling system and dynamic train characteristics. Extensive computational tests are carried out on the railway dispatching area between Utrecht and Den Bosch.     

Optimizing Train Network Routing Using Deterministic Search

In this paper, we use walk search strategy to solve the optimization problem of train routing on railway network. The proposed approach is a local search algorithm which explores the railway network by walker’s navigating through the network. Using some selection rules, walker can dynamically determine the optimal route of trains. In order to analyze and evaluate the proposed approach, we present two computational studies in which the search algorithm is tested on a part of railway network. The results demonstrate that the proposed approach is an effective tool for optimizing the train routing problem on railway network. Moreover, it can be executed with shorter computation time.     

Optimizing railway crew schedules with fairness preferences

Railway crew scheduling deals with generating duties for train drivers to cover all train movements of a given timetable while taking into account a set of work regulations. The objective is to minimize the overall costs associated with a crew schedule, which includes workforce costs and hotel costs. A cost minimal schedule often contains duties that are unpopular to train drivers, and these unpopular duties are often unevenly distributed among crew depots. At the company that motivated our research, for example, train drivers dislike duties that start in the early morning hours. Currently, some crew depots operate large numbers of these unpopular duties, while others do not have any unpopular duties at all. The train drivers perceive this situation as unfair. They prefer schedules with fewer and more evenly distributed unpopular duties across crew depots. In this paper, we define and measure unpopularity and (un)fairness in a railway crew scheduling context. We integrate fairness conditions into a column generation-based solution algorithm and analyze the effect of increased fairness on cost. We also show how increased fairness affects the unpopularity of a schedule. Our method has been applied to test instances at a large European railway freight carrier. Compared to a standard approach that penalizes only the number of unpopular duties in a schedule, we were able to significantly improve schedule fairness with only marginal increases in schedule cost.     

QoS based resource scheduling by computational economy in computational grid

In this paper, we consider multiple QoS based grid resource scheduling. Each of grid task agent's diverse requirements is modeled as a quality of service (QoS) dimension, associated with each QoS dimension is a utility function that defines the benefit that is perceived by a user with respect to QoS choices in that dimension. The objective of multiple QoS based grid resource scheduling is to maximize the global utility of the scheduling system.     

A decomposition based hybrid heuristic algorithm for the joint passenger and freight train scheduling problem

We study the joint problem of scheduling passenger and freight trains for complex railway networks, where the objective is to minimize the tardiness of passenger trains at station stops and the delay of freight trains. We model the problem as a mixed integer program and propose a two-step decomposition heuristic to solve the problem. The heuristic first vertically decomposes the train schedules into a passenger train scheduling phase and then a freight train scheduling phase. In the freight train scheduling phase, we use a train-based decomposition to iteratively schedule each freight train. Experimental results show the efficiency and quality of the proposed heuristic algorithm on real world size problems.     

An optimal track maintenance scheduling model analysis taking the risk of accidents into consideration

This paper presents an optimal track maintenance scheduling model developed for maintaining adequate conditions of the railway tracks and accomplishing an efficient management of the railway service. Our model has been used in several major Japanese railway companies to develop optimal track maintenance schedules (OTMS). Since train accidents cause enormous losses (not only for the railway company but also for society), we propose to take into account the risk of train accidents while developing the OTMS. Thus, it is critically important to identify measures to quantitatively evaluate the risk of accidents to ensure safe and stable transportation. We propose a method to estimate track maintenance costs and the related costs associated with the risk of train derailment due to longitudinal level irregularities of the railway track. We attempt to show a desirable condition of railway tracks by applying the accident cost estimation method and the OTMS model to an actual railway section. We also demonstrate how to apply these models to actual railway networks in general by validating the estimation results using actual numerical data.     

A quality of service driven concurrency framework for object‐based middleware

Threads play a key role in object‐based middleware platforms. Implementers of such platforms can select either kernel or user‐level threads, but neither of these options are ideal. In this paper we introduce Application Scheduler Contexts (ASCs) which flexibly combine both types of thread and thereby attempt to exploit the advantages of each. Multiple ASCs can co‐exist, each with their own concurrency semantics and scheduling policy. ASCs also support quality of service (QoS) configurability, and define their own QoS schema. We show how ASCs can be efficiently implemented and how they can usefully be exploited in middleware environments. We also provide a quantitative evaluation that demonstrates the feasibility of the ASC concept in performance terms. Copyright © 2002 John Wiley & Sons, Ltd.     

Secure interoperation in a multidomain environment employing RBAC policies

Multidomain application environments where distributed multiple organizations interoperate with each other are becoming a reality as witnessed by emerging Internet-based enterprise applications. Composition of a global coherent security policy that governs information and resource accesses in such environments is a challenging problem. In this paper, we propose a policy integration framework for merging heterogeneous role-based access control (RBAC) policies of multiple domains into a global access control policy. A key challenge in composition of this policy is the resolution of conflicts that may arise among the RBAC policies of individual domains. We propose an integer programming (IP)-based approach for optimal resolution of such conflicts. The optimality criterion is to maximize interdomain role accesses without exceeding the autonomy losses beyond the acceptable limit.