A multiagent framework for collaborative airlift planning using commercial air assets

Future operations by the U.S. military services will require greater collaboration within the government and with the private sector. Commercial enterprises that normally compete with one another will have to cooperate to satisfy the goals of the operation. For example, the military uses commercial airlift assets to support the movement of soldiers and cargo to the theater. Ideally, the military would like to receive adequate commercial airlift capacity at a reasonable cost, while the commercial air carriers would like to balance their workload and minimize the disruption to their daily operations. We present a distributed optimization approach that uses software agents—representing the interests of the military and commercial carriers—to collaboratively plan the airlift. By auctioning the missions and allowing carriers to swap missions when mutually beneficial, this approach cuts the controllable operating costs and schedule disruption costs by more than half compared with a centralized planning approach currently used.     

基于关键资源优先的三级装卸搬运分区协调策略

研究基于关键资源优先的单元化“装卸、搬运、装卸”三级作业链调度问题。已知关键资源调度方案,将两非关键作业级的调度问题分别转化为最小单位流问题求解。在数学模型基础之上提出三级装卸搬运的分区协调策略。对关键装卸级作业区进行合理分区和设备分配,从而合理设置已知参数;提出非关键级装卸作业区的分区协调策略,以扩大计算规模。以码头三级装卸搬运作业链为例,参照宁波港码头数据,设计面向集装箱码头的仿真算例,通过较大规模算例验证分区策略对于计算大规模非关键装卸级调度问题的可行性和快捷性。     

Complexity Results for Flow-Shop and Open-Shop Scheduling Problems with Transportation Delays

We consider shop problems with transportation delays where not only the jobs on the machines have to be scheduled, but also transportation of the jobs between the machines has to be taken into account. Jobs consisting of a given number of operations have to be processed on machines in such a way that each machine processes at most one operation at a time and a job is not processed by more than one machine simultaneously. Transportation delays occur if a job changes from one machine to another. The objective is to find a feasible schedule which minimizes some objective function. A survey of known complexity results for flow-shop and open-shop environments is given and some new complexity results are derived.     

Development of a novel family of military campaign simulation models

Dstl has sponsored the development and use of a family of campaign level models of military operations. The models are required to provide an insight into force structure assessment, procurement decisions and doctrinal developments. The family comprises CLARION (land/air war-fighting), COMAND (maritime/air war-fighting) and DIAMOND (non-war-fighting). The two key features of the family are the core role played by the representation of C3I (command, control, communications and information) and the classification of combat units by their interactions with one another at an aggregated level rather than by treating them as a collection of specific combat platforms.     

Queueing analysis of a discrete closed-loop conveyor with service facilities

We consider a discrete closed-loop conveyor system consisting of a loading station, an unloading station, and a number of carriers which move with constant speed along a closed track. At the loading station units arrive in batches while the arrival of batches is governed by a Poisson process. The units queue at the loading station and await there the arrival of an empty carrier. Each unit requires some amount of service which is provided while the unit is on a carrier. After completion of service a unit leaves the system as soon as it reaches the unloading station. Our interest focuses on the steady-state queue length at the loading station. We obtain explicit results for the case where units leave their carriers on passing the unloading station for the second time. We were motivated to study this case by a slotted ring protocol for local area networks.     

The ‘invisible science’: operational research for the British Armed Forces after 1945

This paper presents an original account of the contribution of operational research (OR) to the formulation of tactics and strategy on behalf of the British Armed Forces in the four decades after 1945. The main focus is on the Cold War in the European theatre, where OR analysts devoted considerable time and effort to the modelling of warfare on behalf of the British Army of the Rhine. In the absence of combat data for nuclear weapons, OR analysts devised a sequence of war games which evolved in conformity with the development of NATO strategy in relation to the Warsaw Pact. Again in the context of the Cold War, the paper analyses the role of OR in relation to the early V bomber force and the introduction of ‘global war studies’ on behalf of the Royal Navy. The paper also comments on the organisational structure of British military OR following on the creation of a centralised OR facility within the Ministry of Defence in 1965. In conclusion, the paper notes the sea-change in military OR following the end of the Cold War in 1990 and the onset of a period of sustained ‘asymmetric’ military operations in the former Yugoslavia, the Middle East and Afghanistan.     

Integral resource capacity planning for inpatient care services based on bed census predictions by hour

The design and operations of inpatient care facilities are typically largely historically shaped. A better match with the changing environment is often possible, and even inevitable due to the pressure on hospital budgets. Effectively organizing inpatient care requires simultaneous consideration of several interrelated planning issues. Also, coordination with upstream departments like the operating theatre and the emergency department is much-needed. We present a generic analytical approach to predict bed census on nursing wards by hour, as a function of the Master Surgical Schedule and arrival patterns of emergency patients. Along these predictions, insight is gained on the impact of strategic (ie, case mix, care unit size, care unit partitioning), tactical (ie, allocation of operating room time, misplacement rules), and operational decisions (ie, time of admission/discharge). The method is used in the Academic Medical Center Amsterdam as a decision-support tool in a complete redesign of the inpatient care operations.     

Improved Bounds for Acyclic Job Shop Scheduling

In acyclic job shop scheduling problems there are n jobs and m machines. Each job is composed of a sequence of operations to be performed on different machines. A legal schedule is one in which within each job, operations are carried out in order, and each machine performs at most one operation in any unit of time. If D denotes the length of the longest job, and C denotes the number of time units requested by all jobs on the most loaded machine, then clearly lb = max[C,D] is a lower bound on the length of the shortest legal schedule. A celebrated result of Leighton, Maggs, and Rao shows that if all operations are of unit length, then there always is a legal schedule of length O(lb), independent of n and m. For the case that operations may have different lengths, Shmoys, Stein and Wein showed that there always is a legal schedule of length , where the notation is used to suppress terms. We improve the upper bound to . We also show that our new upper bound is essentially best possible, by proving the existence of instances of acyclic job shop scheduling for which the shortest legal schedule is of length . This resolves (negatively) a known open problem of whether the linear upper bound of Leighton, Maggs, and Rao applies to arbitrary job shop scheduling instances (without the restriction to acyclicity and unit length operations). Received June 30, 1998 RID="*" ID="*" Incumbent of the Joseph and Celia Reskin Career Development Chair RID="†" ID="†" Research was done while staying at the Weizmann Institute, supported by a scholarship from the Minerva foundation.     

Modelling and Optimal Receding-horizon Control of Maritime Container Terminals

The main objective of this paper consists in modelling, optimizing, and controlling container transfer operations inside intermodal terminals. More specifically, maritime container terminals are here considered, involving three kinds of transportation modes, i.e., maritime, rail, and road transport. Generally speaking, an intermodal port terminal can be seen as a system of container flows with two interfaces, towards the hinterland and towards the sea, respectively. Moreover, inside a terminal, unloading operations of inbound containers, container storage, and loading operations of outbound containers are carried out. A simple model for maritime container terminals is proposed in this paper. In the model, a system of queues represents the standing of containers and their movements inside the terminal. The dynamic evolutions of these queues are described by discrete-time equations, where the state variables represent the queue lengths and the control variables take into account the utilization of terminal resources such as load/unload handling rates. On the basis of the proposed model, an optimization problem is defined that consists in minimizing the transfer delays of containers in the terminal. The problem is stated as an optimal control problem whose solution is sought by adopting a receding-horizon strategy.      

Solving the Unit Commitment Problem by a Unit Decommitment Method

In this paper, we present a unified decommitment method to solve the unit commitment problem. This method starts with a solution having all available units online at all hours in the planning horizon and determines an optimal strategy for decommitting units one at a time. We show that the proposed method may be viewed as an approximate implementation of the Lagrangian relaxation approach and that the number of iterations is bounded by the number of units. Numerical tests suggest that the proposed method is a reliable, efficient, and robust approach for solving the unit commitment problem.     

More on spatial oligopoly as a noncooperative game

This paper presents and solves another case of a problem posed byBeckmann [1973]. It considers a duopoly game of c.i.f. pricers selling to a population distributed on an interval. While Beckmann assumed equal transportation costs to sellers and consumers, we assume prohibitive ones to consumers. We also arrive at a mixed strategy solution, one that is somewhat more complicated. A brief extension ton-players oligopoly is carried out at the end.     

A review of strategic mobility models supporting the defense transportation system

The complexity of military logistics and force deployment modeling requires the use of advanced computer models for analysis. The last 20 years have not only seen a concerted effort to improve the fidelity of these models, but development to improve their interconnectivity. The area of strategic mobility has received greater interest in the last decade as the U.S. Military has become more reliant on a force projection posture rather than prepositioning its forces outside the continental United States. Strategic mobility describes how forces within the continental U.S. are deployed in support missions outside the continental U.S. This posture combined with the ever shrinking military budget and force size has placed increased emphasis on the capability to efficiently deploy personnel, equipment, and support materiel. Mobility modeling is conducted at various levels of the mobility planning process. The result is a myriad of models addressing different aspects of the process. Current models addressing strategic mobility use aggregate network flow models, one-pass greedy approaches, and simple bounding techniques. This paper presents an overview of these models, their operating characteristics, and their advantages and disadvantages for mobility modeling applications.     

Analytical solution of closed-loop conveyor systems with discrete and deterministic material flow

We consider a closed-loop conveyor system having a single loading and multiple unloading stations. Units to be transported on the conveyor systems are of the same type and have the same length and are placed on the conveyor along their length. Interarrival times of products to the conveyor system as well as service times of the servers at the unloading stations are all known and deterministic. An arriving unit at the loading station of the conveyor system is blocked when it interferes with the recirculating units of that conveyor system. An analytical solution is provided to measure effects of the recirculation times of units, and other parameters of the system such as the ratios between unit length and conveyor lengths, and arrival/service rates on the performance of the system.     

煤炭码头卸车调度问题多目标优化模型及算法

本文针对煤炭码头卸车调度问题,提出了相应的多约束多目标优化模型,并设计了采用仿真推演策略解码的遗传算法求解。首先,本文考虑列车、煤种、场存、设备、翻堆线和卸车作业过程等约束条件,以卸车效率最大和列车在港时间最短为目标,构建了煤炭码头卸车调度问题多目标数学模型。然后,综合运筹学、遗传算法以及仿真技术,给出了煤炭码头卸车调度问题遗传算法详细设计,包括组合式编码和仿真推演解码方法,染色体生成算法,适应度函数设计,以及采用多种策略的遗传操作及修正等,并列出了算法步骤。实例测试表明,本算法的执行效率高而且优化效果好,结果适用。     

Cost-benefit analysis of one-server n-unit adaptive system with slow switch

This paper considers a shared parallel system consisting of n-units supported by single service facility to carry out both installation and repair of a unit. Initially, all the n units share the total load equally and when one or more units fail, they go for repair while the other surviving units share the entire load equally till the failed units are ready for operation after installation. The installation time (switchover time) of a repaired unit is assumed to be non-negligible and random. The system will be down when all the units are non-operative , Assuming that the failure rates are different when the units function under varying loads, the system characteristics, namely, (1) the expected up-time of the system during (0, t], (2) the expected repair time of the units which failed due to varying failure rates during (0, t] and (3) the expected time spent by the units in the installation state during the period (0, t], are obtained by identifying the system at suitable regeneration epochs. The repair time and the switchover time of the units are arbitrarily distributed. The failure rate of unit is assumed to be constant. It depends on the number of surviving units at any instant. The cost-benefit analysis is also carried out using these system characteristics     

Complexity of flow shop scheduling problems with transportation constraints

In most manufacturing and distribution systems, semi-finished jobs are transferred from one processing facility to another by transporters such as Automated Guided Vehicles, robots and conveyors, and finished jobs are delivered to warehouses or customers by vehicles such as trucks.This paper investigates two-machine flow shop scheduling problems taking transportation into account. The finished jobs are transferred from the processing facility and delivered to customers by truck. Both transportation capacity and transportation times are explicitly taken into account in these models. We study the class of flow shop problems by analysing their complexity. For the makespan objective function, we prove that this problem is strongly NP-hard when the capacity of a truck is limited to two or three parts with an unlimited buffer at the output of the each machine. This problem with additional constraints, such as blocking, is also proven to be strongly NP-hard.     

金属矿山企业生产计划优化方法

针对金属矿山企业的单位开采与运输成本大、优化求解结果偏差大问题, 首先, 依据金属矿山企业编制开采计划的基本原则, 以矿石开采与运输成本最小化为优化目标, 利用整数规划方法, 构建了金属矿山企业生产计划数学模型, 其次, 为了精准快速求解金属矿山企业生产计划模型, 提出了改进的量子粒子群优化算法, 采用进化速度和聚集度因子对算法中的惯性权重进行动态调整, 并设计了双层可行域搜索策略, 提高了算法的局部和全局搜索能力。最后, 以某大型金属矿山企业采运生产作业为案例, 通过与矿山实际生产指标、非线性规划结果以及粒子群优化结果进行比较分析。结果表明:在相同经济指标和参数环境下, 本文算法优于其它两种优化方法, 且每吨矿石的开采和运输成本减少了0.05元左右, 降低了金属矿山企业的开采运输成本, 提高了企业的整体经济效益。     

Optimal search strategies using simultaneous generalized hill climbing algorithms

Optimal search strategies for conducting reconnaissance, surveillance or search and rescue operations with limited assets are of significant interest to military decision makers. Multiple search platforms with varying capabilities can be deployed individually or simultaneously for these operations (e.g., helicopters, fixed wing or satellite). Due to the timeliness required in these operations, efficient use of available search platforms is critical to the success of such missions. Designing optimal search strategies over multiple search platforms can be modeled and solved as a multiple traveling salesman problem (MTSP). This paper demonstrates how simultaneous generalized hill climbing algorithms (SGHC) can be used to determine optimal search strategies over multiple search platforms for the MTSP. Computational results with SGHC algorithms applied to the MTSP are reported. These results demonstrate that when limited computing budgets are available, optimal/near-optimal search strategies over multiple search platforms can be obtained more efficiently using SGHC algorithms compared to other generalized hill climbing algorithms. Applications and extensions of this research to other military applications are also discussed.     

选择性维护决策的研究进展与挑战

在工业生产和军事领域中,生产设备或技术装备往往要求连续执行多个任务,并且在任务间隔期内需要对系统中老化或失效的部件进行维护以确保完成后续任务.然而,由于受有限的成本、时间、设备及人员等维护资源的限制,在任务间隔期内难以修复系统中的所有组成部件,决策者只能有策略地选择部分部件进行维护,从而最大程度地确保完成后续任务,这类维护决策问题被称为选择性维护.现主要介绍选择性维护决策的基本模型和特点,并从系统建模、维护程度、资源约束与资源消耗、任务特性与应用环境、优化算法五个方面综述国内外关于选择性维护决策的研究进展和发展动态,并讨论其发展趋势和挑战.