Benders' partitioning scheme applied to a new formulation of the quadratic assignment problem

In this paper we present a new formulation of the quadratic assignment problem. This is done by transforming the quadratic objective function into a linear objective function by introducing a number of new variables and constraints. The resulting problem is a 0-1 linear integer program with a highly specialized structure. This permits the use of the partitioning scheme of Benders where only the original variables need be considered. The algorithm described thus iterates between two problems. The master problem is a pure 0-1 integer program, and the subproblem is a transportation problem whose optimal solution is shown to be readily available from the master problem in closed form. Computational experience on problems available in the literature is provided.     

反导作战指控系统信息流时延模型研究与应用

在现代反导作战中,如何规划反导作战指控系统从而缩短目标、指挥信息传输时间和提高指挥精度是很重要的问题。基于此展开讨论,首先设计规划了3种反导作战指控系统信息流时延模型并提出了应用原则,其次分别以一典型3 500 km TBM和不同射程TBM为例进行了时延模型仿真计算和分析,最后通过分析计算结果给出反导作战指控系统建设性结论。     

Minimizing mean absolute deviation of completion times about a common due date

We consider a single machine scheduling problem in which the objective is to minimize the mean absolute deviation of job completion times about a common due date. We present an algorithm for determining multiple optimal schedules under restrictive assumptions about the due date, and an implicit enumeration procedure when the assumptions do not hold. We also establish the similarity of this problem to the two parallel machines mean flow time problem.     

On a large sample test for the traffic intensity in GI|G|s queue

A large sample test based on normal approximation for the traffic intensity parameter ρ in the cases of single and multiple-server queues has been proposed. The test procedure is developed without imposing steady-state assumptions and is applicable to queueing systems with general interarrival and service-time distributions.     

Multiproduct dynamic lot-sizing model with coordinated replenishments

In this article we consider a multiproduct dynamic lot-sizing model. In addition to a separate setup cost for each product ordered, a joint setup cost is incurred when at least one product is ordered. We formulate the model as a concave minimization problem over a compact polyhedral set and present a finite branch and bound algorithm for finding an optimal ordering schedule. Superiority of the branch and bound algorithm to the existing exact procedures is demonstrated. We report computational experience with problems whose dimensions render the existing procedures computationally infeasible.     

Visibility probabilities on line segments in three-dimensional spaces subject to random poisson fields of obscuring spheres

The methodology of determining simultaneous visibility probabilities and points on line segments is extended to problems of three-dimensional spaces, with Poisson random fields of obscuring spheres. Required functions are derived analytically and a numerical example is given for a special case of a standard Poisson field, with uniform distribution of sphere diameters.     

A general age replacement model with minimal repair

A general age replacement is introduced which incorporates minimal repair, planned and unplanned replacements, and costs which depend on time. Finite and infinite horizon results are obtained. Various special cases are considered. Furthermore, a shock model with general cost structure is considered.     

Higher‐order Markov chain models for categorical data sequences*

In this paper we study higher‐order Markov chain models for analyzing categorical data sequences. We propose an efficient estimation method for the model parameters. Data sequences such as DNA and sales demand are used to illustrate the predicting power of our proposed models. In particular, we apply the developed higher‐order Markov chain model to the server logs data. The objective here is to model the users' behavior in accessing information and to predict their behavior in the future. Our tests are based on a realistic web log and our model shows an improvement in prediction. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

A single-machine problem with multiple criteria

The problem considered is that of finding the set of efficient sequences of jobs on a single machine with respect to the total flow time and the number of tardy jobs. We present some properties of an existing algorithm and the problem itself.