基于资源约束的突发事件应急救援鲁棒性调度优化

突发事件应急救援的调度优化,对于救援活动的顺利实施及应急资源的有效使用具有至关重要的作用。本文研究资源约束下的突发事件应急救援鲁棒性调度优化问题,其中,鲁棒性定义为各活动的时间缓冲与其权重系数乘积的总和,目标是在资源可用量及救援期限的约束下,安排活动开始时间和执行模式以最大化应急救援计划的鲁棒性。作者构建了问题的0-1规划优化模型,针对其NP-hard属性,基于问题特征设计双环路禁忌搜索启发式算法。通过对一个算例的计算分析,得到如下结论:给定网络结构及时间参数,利用权重系数的定义可以将时间缓冲分配到重要活动上,由此提高应急救援计划的鲁棒性;随着资源可用量的增加,计划的鲁棒性呈上升趋势,而当救援期限延长时,计划的鲁棒性单调增加。本文研究可为突发事件应急救援基准计划的制定提供决策支持。     

集装箱码头泊位计划的鲁棒优化模型

针对集装箱码头作业中的不确定性因素,构建泊位计划的鲁棒优化模型与算法,目的是降低不确定性因素对集装箱码头作业系统的影响。首先,提出泊位计划鲁棒性度量指标,利用算例对各指标的效果进行分析。在此基础上,设计泊位计划鲁棒优化的两阶段优化算法。算法的第一阶段不考虑泊位计划的鲁棒性,以船舶总延误时间最小为目标;算法的第二阶段以所选择的鲁棒性指标最大为目标,以第一阶段获得的船舶总延误时间为约束条件,获得鲁棒调度方案。最后,研究作业资源(装卸桥数量)的变化对泊位计划鲁棒性的影响。算例分析表明,权重松弛量是有效的度量泊位计划鲁棒性的指标,两阶段算法可以有效解决泊位计划鲁棒优化问题。     

一种求解柔性资源约束前摄性项目调度问题的启发式算法

在不确定环境中,一个具有较高鲁棒性的进度计划可以保证项目的稳定实施。考虑到现实中资源可能具有多种技能,会对制定鲁棒性较高进度计划的过程产生影响,因此本文研究了柔性资源约束下前摄性项目调度优化问题。首先界定研究问题;然后从鲁棒性最大化的视角出发,构建了研究问题的优化模型,在对模型进行分析的基础上将其分解为经典鲁棒优化和资源技能分配两个子模型;随后设计了求解问题的基于削峰算法的启发式算法;最后用一个实际案例验证了算法有效性,并分析了关键参数对进度计划鲁棒性的影响,得到如下结论:项目进度计划鲁棒性随着项目工期的延长、资源可用量的增加或资源柔性的提高而增大。     

双目标突发事件应急救援前摄性调度优化

本文以救援时间最短化与计划鲁棒性最大化为目标,研究突发事件应急救援前摄性调度优化问题。作者首先对所研究问题进行界定,其中计划鲁棒性定义为各活动开始时间可调整时差的总和,任务是在应急预算和救援期限的约束下,确定活动执行模式与开始时间以实现上述两个目标。随后,构建问题的0-1规划优化模型,鉴于其强NP-hard属性,设计禁忌搜索启发式算法。最后用一个算例对研究进行说明,得到如下结论:救援时间随应急预算的增加而缩短,随救援期限的放宽而延长;计划鲁棒性随应急预算的增加或救援期限的放宽而提高;当权重分配系数增大时,应急救援时间先保持不变而后缩短,计划鲁棒性则呈减小趋势。本文研究可为突发事件应急救援的组织与协调提供决策支持。     

Probability distribution fitting of schedule overruns in construction projects

The probability of schedule overruns for construction and engineering projects can be ascertained using a ‘best fit’ probability distribution from an empirical distribution. The statistical characteristics of schedule overruns occurring in 276 Australian construction and engineering projects were analysed. Skewness and kurtosis values revealed that schedule overruns are non-Gaussian. Theoretical probability distributions were then fitted to the schedule overrun data; including the Kolmogorov–Smirnov, Anderson–Darling and Chi-Squared non-parametric tests to determine the ‘Goodness of Fit’. A Four Parameter Burr probability function best described the behaviour of schedule overruns, provided the best overall distribution fit and was used to calculate the probability of a schedule overrun being experienced. The statistical characteristics of contract size and schedule overruns were also analysed, and the Wakeby (<AU$1?m and AU$11–50?m), Three Parameter Log-logistic (AU$1–A$10?m) and Beta (AU$51–A$100?m and >AU$101?m) models provided the best distribution fits and were used to calculate schedule overrun probabilities by contract size.     

A genetic algorithm for robust schedules in a one-machine environment with ready times and due dates

Computing a schedule for a single machine problem is often difficult, but when the data are uncertain, the problem is much more complicated. In this paper, we modify a genetic algorithm to compute robust schedules when release dates are subject to small variations. Two types of robustness are distinguished: quality robustness or robustness in the objective function space and solution robustness or robustness in the solution space. We show that the modified genetic algorithm can find solutions that are robust with respect to both types of robustness. Moreover, the risk associated with a specific solution can be easily evaluated. The modified genetic algorithm is applied to a just-in-time scheduling problem, a common problem in many industries.     

项目鲁棒调度的资源分配启发式算法研究

合理的资源配置是提高项目调度鲁棒性一种有效的方法。本文针对项目鲁棒调度问题,提出了Max-PRUA资源分配启发式算法,以期通过生成鲁棒性高的资源分配方案来提高调度计划的鲁棒性。本算法设计了最大化利用优先关系和不可避免弧传递资源的资源分配两项策略来传递最大资源量,以减少由额外约束传递的资源量,降低对项目调度鲁棒性的影响。为寻优最优资源分配方案,配合局部搜索算法,本算法构建了动态活动组GRA,通过对组内活动顺序重排以生成多种资源分配方案,以利于从解空间中寻优出最佳的鲁棒性方案。最后通过大量的仿真实验验证和与其它算法进行比较,结果表明本算法对于不同规模和不同因素影响的项目均有较好的适应性,生成的资源分配方案对调度计划鲁棒性影响较小,是一种有效的算法。     

A shift sequence based approach for nurse scheduling and a new benchmark dataset

This paper investigates an adaptive constructive method for solving nurse rostering problems. The constraints considered in the problems are categorised into three classes: those that are sequence related, those that are nurse schedule related and those that are roster related. We propose a decomposition approach (to construct solutions) that consists of two stages: (1) to construct high quality sequences for nurses by only considering the sequence constraints, and (2) to iteratively construct schedules for nurses and the overall rosters, based on the sequences built and considering the schedule and roster constraints. In the second stage of the schedule construction, nurses are ordered and selected adaptively according to the quality of the schedules they were assigned to in the last iteration. Greedy local search is carried out during and after the roster construction, in order to improve the (partial) rosters built. We show that the local search heuristic during the roster construction can further improve the constructed solutions for the benchmark problems tested.     

A multi-objective genetic algorithm for robust flight scheduling using simulation

Traditional methods of developing flight schedules generally do not take into consideration disruptions that may arise during actual operations. Potential irregularities in airline operations such as equipment failure are not adequately considered during the planning stage of a flight schedule. As such, flight schedules cannot be met as planned and their performance is compromised, which may eventually lead to huge losses in revenue for airlines. In this paper, we seek to improve the robustness of a flight schedule by re-timing its departure times. The problem is modeled as a multi-objective optimization problem, and a multi-objective genetic algorithm (MOGA) is developed to solve the problem. To evaluate flight schedules, SIMAIR 2.0, a simulation model which simulates airline operations under operational irregularities, has been employed. The simulation results indicate that we are able to develop schedules with better operation costs and on-time performance through the application of MOGA.     

基于随机活动工期的多模式现金流均衡项目调度优化

承包商在项目执行过程中的现金流均衡是保证项目成功的关键因素。本文研究基于随机活动工期的多模式现金流均衡项目调度问题,旨是在项目工期及鲁棒性阈值约束下合理安排活动执行模式与开始时间,实现承包商现金流均衡。本文通过构建整数规划优化模型对研究问题进行刻画,随后设计模拟退火算法进行求解,最后进行案例分析。结果表明:鲁棒性阈值虽然可以保证基准进度的稳定性,但是提高鲁棒性阈值水平反而不利于承包商的现金流均衡,该值过高时甚至得不到可行解。本文研究可为随机活动工期背景下承包商的现金流控制提供定量化决策支持。     

An optimization-based model for maximizing the benefits of fast-track construction activities

Fast-track construction projects have become more popular in recent years in response to growing industry demand. By allowing downstream construction activities to start with incomplete information from upstream design activities, fast-tracking (through overlapping) allows for shorter project duration at the expense of potential rework. This leaves practitioners with the challenge of determining the optimal fast-tracking strategy to meet project schedule requirements while avoiding excessive amounts of rework. This paper presents an optimization-based model that serves as a decision support tool in scheduling fast-track construction activities. The model takes into consideration information exchange between upstream and downstream activities and uses the concepts of sensitivity and evolution to maximize the net benefits of fast-tracking. The model is illustrated on an ongoing construction project, which was analysed under various overlapping scenarios. The results indicate substantial time savings depending on the speed of evolution and sensitivity. The project schedule can be shortened by up to 50 days without causing excessive amounts of rework.     

基于贝叶斯网络的工程项目进度完工概率分析

针对传统计划评审技术(Program Evaluation and Review Technique,PERT)在计算完工概率时假设条件的局限性(假设条件与工程实际存在偏差,导致完工概率偏大),提出了基于贝叶斯网络的施工进度完工概率分析方法.首先,分析了贝叶斯网络与进度计划网络之间的相似性,将两者结合起来构建了贝叶斯进度网络;在此基础上,综合考虑贝叶斯网络在节点取值及概率计算方面的优越性,并结合工程项目的不确定性及复杂性特点,建立了基于贝叶斯网络的施工进度完工概率分析模型.最后,将该模型应用于具体工程进行实例分析,验证了模型的可行性与有效性.研究结果表明:基于贝叶斯网络的进度完工概率模型充分考虑了工程施工中的风险因素,其结果能更客观地反映工程实际,可为工程项目决策者提供可靠的依据.     

基于网络图时间参数UTM算法的施工项目资源优化

资源优化是建设工程项目施工计划的一个重要内容.当施工计划某一时段资源用量大于资源限量时,就需调整工作计划重新满足资源限量条件,并使工期不变或延长最少.提出的施工进度计划网络图时间参数的UTM算法和"资源有限、工期最短"的资源优化算法,实现了利用计算机快速计算进行优化,并通过算例验证了算法的有效性.     

Discrete optimization in public rail transport

Many problems arising in traffic planning can be modelled and solved using discrete optimization. We will focus on recent developments which were applied to large scale real world instances. Most railroad companies apply a hierarchically structured planning process. Starting with the definition of the underlying network used for transport one has to decide which infrastructural improvements are necessary. Usually, the rail system is periodically scheduled. A fundamental base of the schedule are the lines connecting several stations with a fixed frequency. Possible objectives for the construction of the line plan may be the minimization of the total cost or the maximization of the passengers’s comfort satisfying certain regulations. After the lines of the system are fixed, the train schedule can be determined. A criterion for the quality of a schedule is the total transit time of the passengers including the waiting time which should be minimized satisfying some operational constraints. For each trip of the schedule a train consisting of a locomotive and some carriages is needed for service. The assignment of rolling stock to schedule trips has to satisfy operational requirements. A comprehensible objective is to minimize the total cost. After all strategic and tactical planning the schedule has to be realized. Several external influences, for example delayed trains, force the dispatcher to recompute parts of the schedule on-line. A Web page with examples quoted in this survey can be found at http://www.math.tu-bs.de/mo/ismp.html.     

Application of Heuristic Techniques to the Cutting-Stock Problem for Worktops

This paper addresses a cutting-stock problem which arises in the manufacture of furniture. An heuristic has been developed to schedule the cutting of worktops of varying shapes and sizes from available raw material.The work was carried out for a local manufacturing company. Interface software written at that company allows the program to be integrated into their computer system in such a way that it can easily be run by the user.Details of the heuristic are given, together with results of some numerical experiments designed to test the robustness of the algorithm and to give some guidance as to the optimal batch size and dimensions of the raw material.Performance of the algorithm in situ supports the results of numerical experiments, the computer solution giving some improvements over the previously obtained manual solution with respect to trim loss without incurring an unacceptable build-up of offcuts.     

单一成本目标数据处理服务外包业务工艺规划研究

本文对数据处理服务外包业务工艺规划所涉及的要素——成品数据要求、工艺方法、工序排序和设备工具进行了分析,结合数据处理业务流程特点,采用数学规划方法建立了非线性优化模型。在综合比较各类求解非线性规划的方法的基础上,鉴于遗传算法具有编码容易、搜索速度快以及鲁棒性等优点,选择遗传算法求解单目标优化问题。通过选取实际企业数据,利用MATLAB编程求解,验证了本文结果的适用性。     

A large neighbourhood search heuristic for the aircraft and passenger recovery problem

This paper introduces a large neighbourhood search heuristic for an airline recovery problem combining fleet assignment, aircraft routing and passenger assignment. Given an initial schedule, a list of disruptions, and a recovery period, the problem consists in constructing aircraft routes and passenger itineraries for the recovery period that allow the resumption of regular operations and minimize operating costs and impacts on passengers. The heuristic alternates between construction, repair and improvement phases, which iteratively destroy and repair parts of the solution. The aim of the first two phases is to produce an initial solution that satisfies a set of operational and functional constraints. The third phase then attempts to identify an improved solution by considering large schedule changes while retaining feasibility. The whole process is iterated by including some randomness in the construction phase so as to diversify the search. This work was initiated in the context of the 2009 ROADEF Challenge, a competition organized jointly by the French Operational Research and Decision Analysis Society and the Spanish firm Amadeus S.A.S., in which our team won the first prize.     

Robust scheduling and robustness measures for the discrete time/cost trade-off problem

Projects are often subject to various sources of uncertainties that have a negative impact on activity durations and costs. Therefore, it is crucial to develop effective approaches to generate robust project schedules that are less vulnerable to disruptions caused by uncontrollable factors. In this paper, we investigate the robust discrete time/cost trade-off problem, which is a multi-mode project scheduling problem with important practical relevance. We introduce surrogate measures that aim at providing an accurate estimate of the schedule robustness. The pertinence of each proposed measure is assessed through computational experiments. Using the insights revealed by the computational study, we propose a two-stage robust scheduling algorithm. Finally, we provide evidence that the proposed approach can be extended to solve a complex robust problem with tardiness penalties and earliness revenues.     

Evaluation of confidence intervals for the kappa statistic when the assumption of marginal homogeneity is violated

This article studies the robustness of confidence interval construction for the intraclass kappa statistic based on a dichotomous response when the assumption of marginal homogeneity across two raters is violated. Two methods of construction are considered: the goodness-of-fit approach and the modified Wald method. Evaluation was done by exact calculation of the confidence interval coverage produced by these approaches. It was found that under mild departures from marginal homogeneity (differences in rater success rates of $<$ 10 %), the goodness- of-fit approach can be recommended. Moreover, under these same conditions, Cohen’s kappa tends to be less biased as a point estimator than the intraclass kappa statistic.     

不确定环境下基于时间、费用及鲁棒性权衡的多目标项目调度优化

项目调度中的时间和费用是两个重要的指标,而在不确定环境下进度计划的鲁棒性则是保证项目平稳实施的关键。本文研究不确定环境下的多目标项目调度优化问题,以优化项目的工期、鲁棒值和成本为目标安排各活动的开始时间。基于此,作者构建多目标项目调度优化模型,将模型分解为三个子模型分析目标间的权衡关系,然后设计非劣排序遗传算法进行求解,应用精英保留策略和基于子模型权衡关系的优化策略优化算法,进行算法测试和算例参数敏感性分析。最后,应用上述方法研究一个项目实例,计算得到非劣解集,实例的敏感性分析结果进一步验证了三个目标间的权衡关系,据此提出资源的有效利用策略。本文的研究可以为多目标项目调度制定进度计划提供定量化决策支持。