Approximation methods for the analysis of a multicomponent,multiproduct assemble‐to‐order system

In this article, we consider the performance evaluation of a multicomponent, multiproduct assemble‐to‐order (ATO) system. Each component is managed independently using a base‐stock policy at a supply facility with limited production capacity and an infinite buffer. The arrivals of demands follow a multivariate Poisson process and unfilled demands are backlogged. Because exact analysis of the proposed system is not feasible, we propose two approximation methods which provide upper and lower bounds for various performance measures such as fill rate, average waiting time, and average number of backorders of the proposed system. Our computational experiments demonstrate the effectiveness of the two approximation methods under various system settings. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Cyclic scheduling in robotic flowshops with bounded work‐in‐process levels

This study addresses cyclic scheduling in robotic flowshops with bounded work‐in‐process (WIP) levels. The objective is to minimize the cycle time or, equivalently, to maximize the throughput, under the condition that the WIP level is bounded from above by a given integer number. We present several strongly polynomial algorithms for the 2‐cyclic robotic flowshop scheduling problems for various WIP levels. © 2010 Wiley Periodicals, Inc. Naval Research Logistics 58: 1–16, 2011     

C2组织的通信结构优化设计与分析

指挥控制(Command and Control,C2)组织的通信结构设计是解决网络中心战条件下指控信息高效交互的核心问题.围绕C2组织通信结构的延时、可靠性及成本进行建模,在虚拟全连通网络中采用路由随机搜索的方法避免路由及拓扑的局部搜索,并基于遗传算进行全局搜索求解.实验分析表明该方法可以实现优化目标和效果.     

过程挖掘算法

过程挖掘又称工作流挖掘,主要依据日志中记录的过程实例执行信息重构工作流过程模型,是工作流再设计与分析方法的一项关键技术。对目前主流的过程挖掘算法和相关工具进行了研究,把过程挖掘算法按照特性及解决问题分成了4类,对每类算法的优缺点进行比较研究。最后指出了目前过程挖掘研究中存在的问题。     

Parallel machine scheduling with job assignment restrictions

In the classical multiprocessor scheduling problem independent jobs must be assigned to parallel, identical machines with the objective of minimizing the makespan. This article explores the effect of assignment restrictions on the jobs for multiprocessor scheduling problems. This means that each job can only be processed on a specific subset of the machines. Particular attention is given to the case of processing times restricted to one of two values, 1 and λ, differing by at most 2. A matching based polynomial time ε‐approximation algorithm is developed that has a performance ratio tending to . This algorithm is shown to have the best possible performance, tending to 3/2, for processing times 1 and 2. For the special case of nested processing sets, i.e., when the sets of machines upon which individual jobs may be assigned are non‐overlapping, the behavior of list scheduling algorithms is explored. Finally, for assignment restrictions determined by just one characteristic of the machines, such as disc storage or memory constraint in the case of high performance computing, we contribute an algorithm that provides a 3/2 worst case bound and runs in time linear in the number of jobs. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

火炮射表数据处理方法评述

主要介绍火炮射表数据处理方法,对国内目前较为流行的两种射表逼近方法进行了全面、系统的分析与比较,指出了逐步回归射表逼近方法存在的缺陷和不足。对国外近几年采用的插值法文中也进行了比较详细的讨论,并指出了未来的研究问题。     

Minimizing makespan in a multimode multiprocessor shop scheduling problem

We study the problem of multimode scheduling tasks on dedicated processors, with the objective of minimizing the maximum completion time. Each task can be undertaken in one among a set of predefined alternative modes, where each mode specifies a required set of dedicated processors and a processing time. At any time each processor can be used by a single task at most. General precedence constraints exist among tasks, and task preemption is not allowed. The problem consists of assigning a mode and a starting time to each task, respecting processor and precedence constraints, to minimize the time required to complete all tasks. The problem is NP-hard in several particular cases. In previous works, we studied algorithms in which a solution was obtained by means of an iterative procedure that combines mode assignment and sequencing phases separately. In this paper, we present some new heuristics where the decision on the mode assignment is taken on the basis of a partial schedule. Then, for each task, the mode selection and the starting time are chosen simultaneously considering the current processor usage. Different lower bounds are derived from a mathematical formulation of the problem and from a graph representation of a particular relaxed version of the problem. Heuristic solutions and lower bounds are evaluated on randomly generated test problems. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 893–911, 1999     

Minimizing sums and products of linear fractional functions over a polytope

In this paper, we develop efficient deterministic algorithms for globally minimizing the sum and the product of several linear fractional functions over a polytope. We will show that an elaborate implementation of an outer approximation algorithm applied to the master problem generated by a parametric transformation of the objective function serves as an efficient method for calculating global minima of these nonconvex minimization problems if the number of linear fractional terms in the objective function is less than four or five. It will be shown that the Charnes–Cooper transformation plays an essential role in solving these problems. Also a simple bounding technique using linear multiplicative programming techniques has remarkable effects on structured problems. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 583–596, 1999     

Two exact algorithms for the vehicle routing problem on trees

This article describes a heuristic and two exact algorithms for several classes of vehicle routing problems defined on tree networks. These include capacitated and time‐constrained vehicle routing problems. One of the exact algorithms is based on the computation of bin packing lower bounds. The other uses column generation. The first algorithm performs better on problems containing small customer demands and in which all vehicles are identical. Otherwise, the second algorithm is more powerful and more versatile. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 75–89, 1999     

Aggregating courier deliveries

We consider the problem of efficiently scheduling deliveries by an uncapacitated courier from a central location under online arrivals. We consider both adversary‐controlled and Poisson arrival processes. In the adversarial setting we provide a randomized (3βΔ/2δ ? 1) ‐competitive algorithm, where β is the approximation ratio of the traveling salesman problem, δ is the minimum distance between the central location and any customer, and Δ is the length of the optimal traveling salesman tour overall customer locations and the central location. We provide instances showing that this analysis is tight. We also prove a 1 + 0.271Δ/δ lower‐bound on the competitive ratio of any algorithm in this setting. In the Poisson setting, we relax our assumption of deterministic travel times by assuming that travel times are distributed with a mean equal to the excursion length. We prove that optimal policies in this setting follow a threshold structure and describe this structure. For the half‐line metric space we bound the performance of the randomized algorithm in the Poisson setting, and show through numerical experiments that the performance of the algorithm is often much better than this bound.