Optimal assignment of high multiplicity flight plans to dispatchers

This paper addresses the problem of finding a feasible schedule of n jobs on m parallel machines, where each job has a deadline and some jobs are preassigned to some machine. This problem arises in the daily assignment of workload to a set of flight dispatchers, and it is strongly characterized by the fact that the job lengths may assume one out of k different values, for small k. We prove the problem to be NP‐complete for k = 2 and propose an effective implicit enumeration algorithm which allows efficiently solution a set of real‐life instances. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 359–376, 2000     

An optimal procedure for the coordinated replenishment dynamic lot‐sizing problem with quantity discounts

We consider in this paper the coordinated replenishment dynamic lot‐sizing problem when quantity discounts are offered. In addition to the coordination required due to the presence of major and minor setup costs, a separate element of coordination made possible by the offer of quantity discounts needs to be considered as well. The mathematical programming formulation for the incremental discount version of the extended problem and a tighter reformulation of the problem based on variable redefinition are provided. These then serve as the basis for the development of a primal‐dual based approach that yields a strong lower bound for our problem. This lower bound is then used in a branch and bound scheme to find an optimal solution to the problem. Computational results for this optimal solution procedure are reported in the paper. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 686–695, 2000     

A competitive genetic algorithm for resource-constrained project scheduling

In this paper we consider the resource-constrained project scheduling problem (RCPSP) with makespan minimization as objective. We propose a new genetic algorithm approach to solve this problem. Subsequently, we compare it to two genetic algorithm concepts from the literature. While our approach makes use of a permutation based genetic encoding that contains problem-specific knowledge, the other two procedures employ a priority value based and a priority rule based representation, respectively. Then we present the results of our thorough computational study for which standard sets of project instances have been used. The outcome reveals that our procedure is the most promising genetic algorithm to solve the RCPSP. Finally, we show that our genetic algorithm yields better results than several heuristic procedures presented in the literature. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 733–750, 1998     

Scheduling stochastic jobs with asymmetric earliness and tardiness penalties

We consider a stochastic counterpart of the well-known earliness-tardiness scheduling problem with a common due date, in which n stochastic jobs are to be processed on a single machine. The processing times of the jobs are independent and normally distributed random variables with known means and known variances that are proportional to the means. The due dates of the jobs are random variables following a common probability distribution. The objective is to minimize the expectation of a weighted combination of the earliness penalty, the tardiness penalty, and the flow-time penalty. One of our main results is that an optimal sequence for the problem must be V-shaped with respect to the mean processing times. Other characterizations of the optimal solution are also established. Two algorithms are proposed, which can generate optimal or near-optimal solutions in pseudopolynomial time. The proposed algorithms are also extended to problems where processing times do not satisfy the assumption in the model above, and are evaluated when processing times follow different probability distributions, including general normal (without the proportional relation between variances and means), uniform, Laplace, and exponential. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44, 531–557, 1997.     

槽头式野战管线水击波速计算方法研究

按照弹性水击理论,管线内发生水力瞬变时,其水击波速取决于管子的弹性、流体的可压缩性和管子受约束的情况。对于给定的输送介质,焊接式固定输油管线的水击波速是一个常数。而槽头式野战管线采用连接器连接,胶圈密封,这种特殊的连接方式改变了管子整体的弹性摸量,从而使水击波速的常规计算方法不再适用。本文研究了野战管线连接器连接方式时水击波速的影响,实验研究了在受到约束时,橡胶的弹性模量随所受压力的变化而变化的规律,推导出野战管线水击波速平均计算方法,推导的公式表明:与焊接式固定管线不同,野战管线的水击波速随管线内压力的增大而增大。     

长管水击最大水击压强的解析

从管道水击微分方程的特征分析入手,提出了水击特征方程的黎曼不变量和网格分析解,建立了管道水击问题的近似解析解,给出了长管水击最大水击压强的计算表达式。通过实际算例对解析解和数值解结果进行了比较。对水击微分方程的重力项也进行了讨论。     

含缺陷管道评价标准及方法研究

为提高含缺陷管道剩余寿命预测的精确程度,系统阐述了国内外含缺陷管道的评价标准及评价方法,介绍了AGA NG-18标准、ASME B31G标准以及缺陷的具体评价方法,分析了各自的特点,针对评价方法提出了以有限元分析为研究方向的结论。     

槽头式野战管线水击波速测量研究

液体管道的水击波速受流体压力、温度、分子结构、含气量及管线几何尺寸、管材等因素的影响,准确地确定管线的水击波速是一个相当困难的问题,通过实验测量水击波速是一个常用方法。管线水击波速的常用测量方法有波前法和周期法。综合运用波前法和周期法,设计了实验测量野战管线的水击波速,并将实验结果与笔者先前提出的水击波速计算公式的计算结果作了对比,验证了公式的有效性。     

Scheduling jobs and maintenance activities on parallel machines

Most machine scheduling models assume that the machines are available all of the time. However, in most realistic situations, machines need to be maintained and hence may become unavailable during certain periods. In this paper, we study the problem of processing a set of n jobs on m parallel machines where each machine must be maintained once during the planning horizon. Our objective is to schedule jobs and maintenance activities so that the total weighted completion time of jobs is minimized. Two cases are studied in this paper. In the first case, there are sufficient resources so that different machines can be maintained simultaneously if necessary. In the second case, only one machine can be maintained at any given time. In this paper, we first show that, even when all jobs have the same weight, both cases of the problem are NP-hard. We then propose branch and bound algorithms based on the column generation approach for solving both cases of the problem. Our algorithms are capable of optimally solving medium sized problems within a reasonable computational time. We note that the general problem where at most j machines, 1 ≤ j ≤ m, can be maintained simultaneously, can be solved similarly by the column generation approach proposed in this paper. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 145–165, 2000     

An exact branch‐and‐price algorithm for multitasking scheduling on unrelated parallel machines

We consider the multitasking scheduling problem on unrelated parallel machines to minimize the total weighted completion time. In this problem, each machine processes a set of jobs, while the processing of a selected job on a machine may be interrupted by other available jobs scheduled on the same machine but unfinished. To solve this problem, we propose an exact branch‐and‐price algorithm, where the master problem at each search node is solved by a novel column generation scheme, called in‐out column generation, to maintain the stability of the dual variables. We use a greedy heuristic to obtain a set of initial columns to start the in‐out column generation, and a hybrid strategy combining a genetic algorithm and an exact dynamic programming algorithm to solve the pricing subproblems approximately and exactly, respectively. Using randomly generated data, we conduct numerical studies to evaluate the performance of the proposed solution approach. We also examine the effects of multitasking on the scheduling outcomes, with which the decision maker can justify making investments to adopt or avoid multitasking.