A two stage heuristic algorithm for the integrated aircraft and crew schedule recovery problems

Airline disruptions incurred huge cost for airlines and serious inconvenience for travelers. In this paper, we study the integrated aircraft and crew schedule recovery problem. A two stage heuristic algorithm for the integrated recovery problem is proposed. In the first stage, the integrated aircraft recovery and flight-rescheduling model with partial crew consideration is built. This model is based on the traditional multi-commodity network model for the aircraft schedule recovery problem. The objective of this model also includes minimization of the original crew connection disruption. In the second stage, the integrated crew schedule recovery and flight re-scheduling model with partial aircraft consideration is built. We proposed a new multi-commodity model for the crew schedule recovery. The main advantage of such model is that it is much more efficient to integrate the flight-scheduling and aircraft consideration. New constraints are incorporated to guarantee that the aircraft connections generated in the stage 1 are still feasible. Two stages are run iteratively until no improvement can be achieved. Experimental results show that our method can provide better recovery solutions compared with the benchmark algorithms.     

基于损益云模型的制造车间重调度决策方法

针对制造车间重调度触发机制问题,建立了制造车间重调度损益函数,揭示了生产车间重调度过程损失及增益的变化规律.引入云理论测度重调度损益的不确定性,使用逆向云算法计算重调度增益云和损失云的数字特征,根据云形态预测重调度损益变化趋势.提出一种基于损益云模型的重调度决策方法以判断是否需要重调度,并利用最佳损益比甄选预调度方案以兼顾生产系统的稳定性和有效性.最后,通过实例验证了该方法的合理性和实用性.     

DS-OBS网络中的调度算法

首先介绍了支持区分业务的光突发交换（DS-OBS）网络,然后在现有算法LAUC_VF的基础上提出了一种新的调度算法,它的主要思想是：对新来的数据突发首先运用LAUC_VF算法进行数据信道调度;如果调度不成功就采用重调度的机制,该重调度算法命名为：LAUC_VF RESCHEDULE算法;当重调度不成功时,为了实现业务的区分就采用抢占机制,该抢占算法命名为：LAUC_VF_QIANGZHAN算法;仿真结果表明在大多数情况下该调度算法相对于LAUC_VF算法对网络性能的改善是比较大的.     

A multi-agent architecture for dynamic scheduling of steel hot rolling

Steel production is a complex process and finding coherent and effective schedules for the wide variety of production steps, in a dynamic environment, is a challenging task. In this paper, we propose a multi-agent architecture for integrated dynamic scheduling of the hot strip mill (HSM) and the continuous caster. The scheduling systems of these processes have very different objectives and constraints, and operate in an environment where there is a substantial quantity of real-time information concerning production failures and customer requests. Each process is assigned to an agent which independently, seeks an optimal dynamic schedule at a local level taking into account local objectives, real-time information and information received from other agents. Each agent can react to real-time events in order to fix any problems that occur. We focus here, particularly, on the HSM agent which uses a tabu search heuristic to create good predictive–reactive schedules quickly. The other agents simulate the production of the coil orders and the real-time events, which occur during the scheduling process. When real-time events occur on the HSM, the HSM agent might decide whether to repair the current schedule or reschedule from scratch. To address this problem, a range of schedule repair and complete rescheduling strategies are investigated and their performance is assessed with respect to measures of utility, stability and robustness, using an experimental simulation framework.     

Match-up approaches to a dynamic rescheduling problem

This article considers the problem of inserting arriving jobs into an existing schedule of a real world manufacturer. A number of match-up strategies, which collect the idle time on machines of a current schedule for the insertion of new jobs, are proposed. Their aim is to obtain new schedules with a good performance which are at the same time highly stable, meaning that they resemble as closely as possible the initial schedule. Basic rescheduling strategies such as ‘total rescheduling’, ‘right shift’ and ‘insertion in the end’ deliver either good performance or stability, but not both. Contrarily, our experimentation and statistical analysis reveal that the proposed match-up strategies deliver high performing schedules with a high stability. An analysis of the problem parameters that determine the behaviour of the proposed match-up algorithms is included in this article.     

A Constraint-Based Interactive Train Rescheduling Tool

In this paper, we report the design and implementation of a constraint-based interactive train rescheduling tool, a project in collaboration with the International Institute for Software Technology, United Nations University (UNU/IIST), Macau. We formulate train rescheduling as constraint satisfaction and describe a constraint propagation approach for tackling the problem. Algorithms for timetable verification and train rescheduling are designed under a coherent framework. Formal correctness properties of the rescheduling algorithm are established. We define two optimality criteria for rescheduling that correspond to minimizing the number of station visits affected and passenger delay respectively. Two heuristics are then proposed to speed up and direct the search towards optimal solutions. The feasibility of our proposed algorithms and heuristics are confirmed with experimentation using real-life data.     

Predictive, Stochastic and Dynamic Extensions to Aversion Dynamics Scheduling

Schedulers' decisions in real factories deal with perceived risks and impacts. They proactively anticipate and reactively mitigate risky events by altering what would be considered a normal schedule to minimize associated impacts. These risk mitigation concepts are called aversion dynamics (AD). Aversion dynamics describes the aversion that jobs exhibit to impacts resulting from risky events in dynamic and unstable production environments. The aversion manifests itself in either advancing or delaying the work to avoid the risky period. This paper extends the first AD heuristic, Averse-1, to capture additional real-world dynamics and to make the heuristic predictive (proactive) as to when the perceived risky event may happen. In particular, predictive and stochastic elements are incorporated within a dynamic job arrival framework to create an extended heuristic called Averse-2.     

考虑恶劣天气的班轮多阶段重调度方法

受恶劣天气影响的船舶调度是一个非常复杂的优化问题,也是班轮公司重点关注的问题之一。为此,针对某航运网络上的一家班轮公司的所有营运船舶,以获知设计的多阶段重调度机制时段内最新预报的天气信息和这些船舶的实时位置为前提,重点考虑班轮船期表的限制并兼顾港口间航速变化和船舶容量等现实约束,构建了以固定计划期内所有船舶的航运总成本最小为优化目标的非线性数学模型,并设计了嵌入基因修复算子的改进遗传算法用于求解该模型。由此,可以给出集成租船直运、跨航线调船、反挂和货物中转等解决策略的最佳多阶段重调度方案。通过对大、中、小规模的算例进行实验,实验结果表明,可知与传统等待办法相比,多阶段重调度节约了总航运成本的15%以上,验证了所提模型和方案的有效性;与Cplex相比,改进遗传算法的运算效率大大提高,且偏差值均在5%以内,而与蚁群优化（ACO）算法、禁忌搜索（TS）算法、量子差分进化（QDE）算法相比,改进遗传算法能在有效时间内降低10%左右的成本,验证了算法的科学性。所提方法可为班轮公司的实际船舶调度提供参考。     

资源动态组织支持的网格依赖任务重调度机制

针对网格依赖任务重调度所面临的效率低与触发频繁的问题,提出资源动态组织支持的网格依赖任务调度机制.该机制以资源的动态组织为核心,基于资源动态性度量结果对资源进行性能聚类分析,并过滤性能相似资源中的强动态性资源,以在减少资源数量的同时提高重调度备选资源的稳定性.实验表明基于该机制的重调度算法保持了静态调度策略在动态网格环境下相对于动态调度策略的性能优势,从而验证了该机制解决网格依赖任务重调度所面临问题的有效性.     

半导体制造重调度研究

以半导体制造重调度为研究对象，构建了半导体制造重调度体系结构，在此体系结构下，分析了引发半导体制造重调度的因素，提出了相应的重调度策略（何时引发重调度以及引发何种重调度），进一步探讨了重调度方法中的全局修正式重调度方法，给出了基于群体智能的半导体制造重调度模型，建立了用于重调度性能评价的短期性能指标体系。