The analysis of a single base in an airlift operation

In this paper, some performance measures of a single base in an airlift operation are evaluated, assuming that the inter-arrival times of the aircraft at the base are exponentially distributed. The crews arriving with the aircraft rest at the base for a constant amount of time before being ready to fly from the base. A certain number of crews are placed at the base initially in order to reduce the waiting times of the aircraft at the base. Closed form expressions for the probability distribution functions of the waiting times of the aircraft and crews at the base and the number of aircraft and crews waiting are derived as functions of the mean inter-arrival times, the number of crews placed initially at the base and the duration of the rest period.     

A heuristic approach for an integrated fleet-assignment,aircraft-routing and crew-pairing problem

This paper deals with the fleet-assignment, aircraft-routing and crew-pairing problems of an airline flying between Canary Islands. There are two major airports (bases). The company is subdivided in three operators. There are no flight during the night. A crew route leaves from and returns to the same base. An aircraft route starts from one base and arrive to the other base due to maintenance requirements. Therefore some crews must change aircrafts, which is an undesired operation. This paper presents a mathematical formulation based on a binary variable for each potential crew and aircraft route, and describes a column-generation algorithm for obtaining heuristic solutions. Computational results on real-world instances are given and compared to manual solutions by the airline.     

基于优先级的进离港航班排序优化问题研究

研究机场终端区进离港航班排序优化问题,对于提高跑道利用率以及降低航班延误损失具有重要意义。本文首先考虑航班运行方式(降落和起飞)、飞机类型以及航班的重要程度(航程是否连续)的不同所造成延误损失的不同,设计三维优先级表反映调度优先等级,并将其转化为延误成本系数。其次,为实现调度的公平性和减轻管制人员的工作负荷,设置允许延误的航班架次约束、邻边约束以及最大限制位置约束。再次,以最小化航班总延误成本为目标建立模型,提出相应的改进蚁群算法(GJAC)进行求解。最后通过数值实验验证所提算法在考虑调度优先等级及上述约束条件的同时能有效减少进离港航班队列的总延误成本。     

Multi-depot vehicle scheduling problems with time windows and waiting costs

The multi-depot vehicle scheduling problem with time windows (MDVSPTW) consists of scheduling a fleet of vehicles to cover a set of tasks at minimum cost. Each task is restricted to begin within a prescribed time interval and vehicles are supplied by different depots. The problem is formulated as an integer nonlinear multi-commodity network flow model with time variables and is solved using a column generation approach embedded in a branch-and-bound framework. This paper breaks new ground by considering costs on exact waiting times between two consecutive tasks instead of minimal waiting times. This new and more realistic cost structure gives rise to a nonlinear objective function in the model. Optimal and heuristic versions of the algorithm have been extensively tested on randomly generated urban bus scheduling problem (UBSP) and freight transport scheduling problem (FTSP). The results show that such a general solution methodology outperforms specialized algorithms when minimal waiting costs are used, and can efficiently treat the case with exact waiting costs.     

单架飞机受干扰后飞机路径恢复多项式算法研究

飞机路径恢复是航班调整中保证航班能够运行的必要条件之一,而传统目标下的飞机路径优化问题是NP-hard的。本文针对单架飞机受到干扰后,基于最小最大目标的同机型飞机路径最优化问题,给出了一个新的多项式时间算法。首先基于航空公司调整航班的常用原则,提出把最大航班延误时间最小化作为问题的目标。然后根据问题的一些特点和目标形式,设计出解构造算法,得到飞机路径恢复问题的最优解,并分析出算法的复杂度为O(n²)。相对于一般的最小最大二分图匹配算法(复杂度为O(n³log(n))),该算法具有较小的时间复杂度。最后用实例验证了解构造算法的有效性。该研究结果将为航空公司减少航班延误提供理论和方法支持。     

Single machine scheduling problems with controllable processing times and total absolute differences penalties

In this paper, we consider single machine scheduling problem in which job processing times are controllable variables with linear costs. We concentrate on two goals separately, namely, minimizing a cost function containing total completion time, total absolute differences in completion times and total compression cost; minimizing a cost function containing total waiting time, total absolute differences in waiting times and total compression cost. The problem is modelled as an assignment problem, and thus can be solved with the well-known algorithms. For the case where all the jobs have a common difference between normal and crash processing time and an equal unit compression penalty, we present an O(n log n) algorithm to obtain the optimal solution.     

A model and computational tool for crew scheduling in train transportation of mine materials by using a local search strategy

This work introduces a model of the crew scheduling problem for the operation of trains in the mining industry in the North of Chile. The model possesses particular features due to specific regulations with which train operators in mine material transportation are required to comply: every week, a fixed set of trips must be made according to current demand for the transportation of mine products and supplies. In order to balance the loads of the crews in the long term, the proposed model generates an infinite horizon schedule by means of a rotative scheme in which each crew takes the place of the previous one at the beginning of the next week. This gives rise to a medium/large size 0–1 linear optimization problem, whose solution represents the optimal assignment of drivers to trips with the number of working hours per week distributed equally among crews. The model and algorithm have been implemented with a user interface suitable for the remote execution of real instances on a High Performance Computing platform. The transportation company regularly uses this computerized tool for planning crew schedules and generating efficient assignments for emerging and changing operational conditions.     

Scheduling programs with repetitive projects: A comparison of a simulated annealing,a genetic and a pair-wise swap algorithm

We address the problem of scheduling in programs involving the production of multiple units of the same product. Our study was motivated by a construction program for fast naval patrol boats. Other applications of this problem include procurement of multiple copies of aircraft, spacecraft, and weapon systems. In this problem we must decide how many units of the product to assign to each of a number of available crews (individuals, teams, subcontractors, etc.). These types of problems are characterized by two potentially conflicting considerations: 1) the need to complete each unit by its contractual due date, and 2) learning effects. Because of the first consideration, there is a tendency to use multiple crews for simultaneous production, so that meeting due dates is assured. However, the second consideration encourages assigning many units to a single crew so that learning effects are maximized. We study this scheduling problem with two different penalty cost structures and develop models for both versions. The models trade-off the penalty associated with late deliveries and the savings due to learning (and possibly incentive payments for early completion). We discuss different heuristic algorithms — simulated annealing, a genetic algorithm, and a pair-wise swap heuristic — as well as an exhaustive search to determine a baseline for comparisons. Our computational results show that the pair-wise swap algorithm is the most efficient solution procedure for these models.     

An evolutionary approach to rehabilitation patient scheduling: A case study

Focusing on real settings, this study aimed to develop an evolutionary approach based on genetic algorithm for solving the problem of rehabilitation patient scheduling to increase service quality by reducing patient waiting time and improve operation efficiency by increasing the therapy equipment utilization. Indeed, due to partial precedence constraints of rehabilitation therapies, the problem can be structured as a hybrid shop scheduling problem that has received little attention to date. In addition, a mixed integer programming model was also constructed as a benchmark to validate the solution quality with small problems. Based on empirical data from a Medical Center in Taiwan, several experiments were conducted to estimate the validity of the proposed algorithm. The results showed that the proposed algorithm can reduce patient waiting time and enhance resource utilization and thus demonstrated the practicality of the proposed algorithm. Indeed, a decision support system embedded with the developed algorithm has been implemented in this medical center.     

Optimising Waiting at Nodes in Time-Dependent Networks: Cost Functions and Applications

In this paper, the relationship between waiting at nodes and the path cost in a transport network is analysed. An exact solution algorithm for generating the shortest path with optimal waiting at the nodes is proposed. The general case is examined, considering a time-dependent network (time influences the cost). To develop a full application, the algorithm is applied in the case of a vehicle routing problem on a real network.     

A simplification of the double-sweep algorithm to solve the k-shortest path problem

In this paper, we define the k-shortest path problem, which will be used to model the problem of routing aircraft through a network of airfields. This problem finds the optimal alternative routes from one or more origins to one or more destinations. We solve this problem using the double-sweep algorithm. We present a simplification to the double-sweep algorithm, and show that this simplification reduces the computational complexity of the algorithm by a factor of k. We prove that the simplified double-sweep algorithm converges. Finally, we demonstrate this algorithm on a small airlift network.     

Continuous management of airlift and tanker resources: A constraint-based approach

Efficient allocation of aircraft and aircrews to transportation missions is an important priority at the USAF Air Mobility Command (AMC), where airlift demand must increasingly be met with less capacity and at lower cost. In addition to presenting a formidable optimization problem, the AMC resource management problem is complicated by the fact that it is situated in a continuously executing environment. Mission requests are received (and must be acted upon) incrementally, and, once allocation decisions have been communicated to the executing agents, subsequent opportunities for optimizing resource usage must be balanced against the cost of solution change. In this paper, we describe the technical approach taken to this problem in the AMC barrel allocator, a scheduling tool developed to address this problem and provide support for day-to-day allocation and management of AMC resources. The system utilizes incremental and configurable constraint-based search procedures to provide a range of automated and semi-automated scheduling capabilities. Most basically, the system provides an efficient solution to the fleet scheduling problem. More importantly to continuous operations, it also provides techniques for selectively reoptimizing to accommodate higher priority missions while minimizing disruption to most previously scheduled missions, and for selectively “merging” previously planned missions to minimize nonproductive flying time. In situations where all mission requirements cannot be met, the system can generate and compare alternative constraint relaxation options. The barrel allocator technology is currently transitioning into operational use within AMC's Tanker/Airlift Control Center (TACC). A version of the barrel allocator supporting airlift allocation was first incorporated as an experimental module of the AMC's Consolidated Air Mobility Planning System (CAMPS) in September 2000. In May 2003, a new tanker allocation module is scheduled for initial operational release to users as part of CAMPS Release 5.4.     

Parallel-machine scheduling with non-simultaneous machine available time

We consider a problem of scheduling n independent jobs on m parallel identical machines. The jobs are available at time zero, but the machines may not be available simultaneously at time zero. We concentrate on two goals separately, namely, minimizing a cost function containing total completion time and total absolute differences in completion times; minimizing a cost function containing total waiting time and total absolute differences in waiting times. In this paper, we present polynomial time algorithm to solve this problem.     

具有恶化效应和凸资源分配关系的单机排序问题

研究工件加工时间具有恶化效应和凸资源关系的单机排序问题,其中工件的实际加工时间是其正常的加工时间,工件开工时间(具有恶化效应)及消耗资源量的函数。目标为在最大完工时间(总完工时间、总等待时间、完工时间总绝对差与等待时间总绝对差)小于或等于给定常数的条件下找到工件的最优排序和最优的资源分配使工件的总资源消耗量最少。在单机状态下,证明了此问题是多项式时间可解的,并给出了求解该问题的算法和数值实例。     

Scheduling de-icing vehicles within airport logistics: a heuristic algorithm and performance evaluation

Most delays in the air transport occur at the airport. A particular reason is the complexity of managing the large number of supporting flows in airport logistics. We consider the optimisation problem of scheduling de-icing vehicles that is one of the key supporting logistic flows in the turn-around process of aircraft. The objective is to minimise the delay of flights due to de-icing, and the travel distance of the de-icing vehicles. We study the complexity of the problem, and develop a solution algorithm using greedy randomised adaptive search. A case study of real-life data from Stockholm Arlanda Airport shows that optimised schedule leads to significantly better performance in comparison to intuitive and simple scheduling strategies. The benefit of optimisation in reducing the waiting time for de-icing is further demonstrated via dynamic simulations.     

An advanced tabu search for solving the mixed payload airlift loading problem

This article describes a new, two-dimensional bin packing algorithm that feasibly loads a set of cargo items on a minimal set of airlift aircraft. The problem under consideration is called the Mixed Payload Airlift Loading Problem (MPALP). The heuristic algorithm, called the Mixed Payload Airlift Loading Problem Tabu Search (MPALPTS), surpasses previous research conducted in this area because, in addition to pure pallet cargo loads, MPALPTS can accommodate rolling stock cargo (ie tanks, trucks, HMMMVs, etc) while still maintaining feasibility. To demonstrate its effectiveness, the load plans generated by MPALPTS are directly compared to those generated by the Automated Air Load Planning Software (AALPS) for a given cargo set; AALPS is the load planning software currently mandated for use in all Department of Defense load planning. While more time consuming than AALPS, MPALPTS required the same or fewer aircraft than AALPS in all test scenarios.     

Airport noise modelling and aircraft scheduling so as to minimize community annoyance

A mathematical model of the annoyance created at an airport by aircraft operations is developed. The model incorporates population distribution considerations around an airport and the annoyance caused by aircraft noise. The objective function of this model corresponds to seeking to minimize total population annoyance created by all aircraft operations in a 24-hour period. Several factors are included in this model as constraint relationships. Aircraft operations by type and time period are upper bounded. Demand for flight services is incorporated by including lower bounds on the number of operations by type of aircraft, runway used and time period. Also upper bounds on the number of operations for each runway are included. The mathematical model as formulated is recognized as corresponding to a nonlinear integer mathematical programming problem.The solution technique selected makes use of a successive linear approximation optimization algorithm. An especially attractive feature of this solution algorithm is that it is capable of obtaining solutions to large problems. For example, it would be feasible to attempt the solution of problems involving several thousand variables and over 500 linear constraints. This suggested solution algorithm was implemented on a computer and computational results obtained for example problems.     

Composing medical crews with equity and efficiency

The quality of the health care is directly connected to the equity and to the efficiency of the service delivered. Usually, the health care is delivered by crews composed of individuals working together sharing knowledge, experiences and skills. We consider the problem of composing medical crews in such a way that the health care service provided follows the principles of equity and efficiency. We present a general mathematical programming model for this problem and a solution algorithm based on Tabu Search methodology. Computational analysis proves the effectiveness of the proposed algorithm.     

基于控制工序性质的LOB截止日期问题分析与算法

截止日期问题是重复性项目调度中研究最为广泛的问题之一,其旨在满足项目截止日期前提下求得一个工作队雇佣总量最小的调度方案。由于重复性项目往往为大型工程建设项目,一个准确的最优进度计划对于节约项目的资源和成本具有重要意义。在平衡线法(LOB)框架下,本文从控制工序的性质出发,研究并分析了控制工序工作队分配与项目总工期之间的关联,给出了截止日期问题的一些特殊性质。基于这些性质,一方面能够帮助项目管理人员判断一个调度方案是否可行且经济,另一方面能够得到一些有效的剪枝策略,从而设计出具有针对性的分支限界算法。最后,通过案例计算和仿真实验验证了本文提出的算法在计算效果和计算效率上的有效性。     

Minimizing the cycle time of multiple-product processing networks with a fixed operation sequence,setups, and time-window constraints

We solve a special case of the single-robot cyclic scheduling problem with a fixed robot operation sequence and time window constraints on processing times. It generalizes the known single-part fixed-sequence problems into the one to cover a processing network with multiple part types and setup time requirements between the processing steps for different parts at the shared stations. The objective is to minimize the cycle time. We prove that this problem is equivalent to the parametric critical path problem, and propose a strongly polynomial time solution algorithm which uses a new labeling procedure to identify all feasible parameter values. The proposed algorithm is based on an extension to the known Bellman–Ford algorithm.