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     

Solving a selected class of location problems by exploiting problem structure: A decomposition approach

For many combinatorial optimization problems that are NP-hard, a number of special cases exist that can be solved in polynomial time. This paper addresses the issue of solving one such problem, the well-known m-median problem with mutual communication (MMMC), by exploiting polynomially solvable special cases of the problem. For MMMC, a dependency graph is defined that characterizes the structure of the interactions between decision variables. A Lagrangian decomposition scheme is proposed that partitions the problem into two or more subproblems, each having the same structure as the original problem, but with simpler dependency graphs. The dual problems are solved using subgradient or multiplier adjustment methods. An efficient method of adjusting the multiplier values is given. Computational results are reported that show the method to be quite effective. In addition, applications of the approach to other difficult location problems is discussed. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 791–815, 1998     

Scheduling to minimize the total compression and late costs

We consider a single-machine scheduling model in which the job processing times are controllable variables with linear costs. The objective is to minimize the sum of the cost incurred in compressing job processing times and the cost associated with the number of late jobs. The problem is shown to be NP-hard even when the due dates of all jobs are identical. We present a dynamic programming solution algorithm and a fully polynomial approximation scheme for the problem. Several efficient heuristics are proposed for solving the problem. Computational experiments demonstrate that the heuristics are capable of producing near-optimal solutions quickly. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 67–82, 1998     

Benders decomposition with alternative multiple cuts for a multi‐product closed‐loop supply chain network design model

In this article, we consider a multi‐product closed‐loop supply chain network design problem where we locate collection centers and remanufacturing facilities while coordinating the forward and reverse flows in the network so as to minimize the processing, transportation, and fixed location costs. The problem of interest is motivated by the practice of an original equipment manufacturer in the automotive industry that provides service parts for vehicle maintenance and repair. We provide an effective problem formulation that is amenable to efficient Benders reformulation and an exact solution approach. More specifically, we develop an efficient dual solution approach to generate strong Benders cuts, and, in addition to the classical single Benders cut approach, we propose three different approaches for adding multiple Benders cuts. These cuts are obtained via dual problem disaggregation based either on the forward and reverse flows, or the products, or both. We present computational results which illustrate the superior performance of the proposed solution methodology with multiple Benders cuts in comparison to the branch‐and‐cut approach as well as the traditional Benders decomposition approach with a single cut. In particular, we observe that the use of multiple Benders cuts generates stronger lower bounds and promotes faster convergence to optimality. We also observe that if the model parameters are such that the different costs are not balanced, but, rather, are biased towards one of the major cost categories (processing, transportation or fixed location costs), the time required to obtain the optimal solution decreases considerably when using the proposed solution methodology as well as the branch‐and‐cut approach. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

A single-period,multi-echelon stochastic model under a mix of assemble to order and assemble in advance policies

This article presents a stochastic model for a single-period production system composed of several assembly/processing and storage facilities in series. The production system operates under a composite strategy of the assemble to order and assemble in advance policies. The developed mathematical model is simpler and more compact than the ones provided in earlier articles. Moreover, the formulation allows the optimal inventory levels at the start of the period to be determined from the solution to the well-known newsboy problem. We also analyze the problem under the free distribution approach which only assumes the knowledge of the first two moments of the demand distribution. The robustness of this approach is tested by carrying an extensive experimental comparison using different demand distributions. Finally, the composite model is extended by considering the effects of some budgetary constraints. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 599–614, 1998     

On some sequencing problems

The (mxn) sequencing problem may be characterized as follows: There are m machines which can produce a piece consisting of n parts. Each part has a determined order in which it is processed through the machines. It is assumed that each machine cannot deal with more than one part at a time and that the processing required for each part can be accomplished only on one machine. That is, the machines are all specialized so that alternate machines for the same processing on a part is not possible. The problem is to find the best production plan consisting in sequencing the different parts so as to make the whole amount of time from the beginning of work till the piece is completed the shortest possible. Such a plan is called an optimum one. In the first 4 sections of this paper, the problem (2xn) is solved for the (2xn) case in which the order in which parts come on the machine is not constrained by further assumptions. The remainder of the paper then takes up: 1) the (3xn) problem of Bellman-Johnson (viz. the technological processing order through the machine is the same for all parts) for several new special cases; 2) the 2xn problem of sequencing when delay times must also be considered; and, 3) some properties of an approximating method for solving (mxn) problems, including a delineation of cases when the approximating method will yield optimal solutions.     

考虑战损件回收再造的战场军需备件供应优化研究

在考虑军需备件需求和战损件修复不确定性的条件下,研究了战场上军需备件供应优化问题,建立了优化问题的数学模型,证明了模型的凸函数特性,给出了模型的最优解析解计算方法.     

Volume discount decisions: Wealth maximization or EOQ approach?

A recent paper finds that when volume discounts are available, in some cases, reliance on the Economic Order Quantity (EOQ) model can induce purchasers to make wealth reducing decisions, and the Present Value (PV) approach should be preferred. While this finding is theoretically correct, the magnitudes of wealth reductions suggested by the paper's numerical examples seem to be questionable. Furthermore, the paper also finds that, in some other cases, a purchaser using the EOQ approach realizes a net increase in current wealth compared to a purchaser using the PV approach. Logic suggests that such a finding cannot be correct, since by its very definition, it is the PV approach that seeks to maximize the current wealth. We offer an alternative frame of comparison and a modified model to show that, under the paper's assumptions, the EOQ approach can never realize a net increase in current wealth compared to the current wealth generated by the PV approach. On the other hand, we also show that when typical values of the relevant parameters prevail, the additional costs imposed by the EOQ approach are not significant. Finally, we suggest that insofar as the PV approach requires greater administrative costs to implement, it may even be counterproductive to the goal of wealth maximization. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 377–389, 1998     

复杂结构的轴类零件弯曲刚度 CAD

内锥孔、外锥台同时存在的轴在航空机械中得到广泛地应用 ,但机械设计手册上未对这一情况给出具体地解决方法。本文讨论了用计算机对轴类零件进行弯曲刚度计算时应解决的问题 ,给出了内锥孔、外锥台同时存在的轴刚度计算的解决方法 ,并用ADS开发工具在AutoCAD开发环境下付诸实践。     

Heuristics for multicomponent joint replacement: Applications to aircraft engine maintenance

This paper considers the maintenance of aircraft engine components where economies exist for joint replacement because (a) the aircraft must be pulled from service for maintenance and (b) repair of some components requires removal and disassembly of the engine. It is well known that the joint replacement problem is difficult to solve exactly, because the optimal solution does not have a simple structured form. Therefore, we formulate three easy-to-implement heuristics and test their performance against a lower bound for various numerical examples. One of our heuristics, the base interval approach, in which replacement cycles for all components are restricted to be multiples of a specified interval, is shown to be robustly accurate. Moreover, this heuristic is consistent with maintenance policies used by commercial airlines in which periodic maintenance checks are made at regular intervals. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 435–458, 1998     

A nonparametric approach to accelerated life testing under multiple stresses

Accelerated life testing (ALT) is concerned with subjecting items to a series of stresses at several levels higher than those experienced under normal conditions so as to obtain the lifetime distribution of items under normal levels. A parametric approach to this problem requires two assumptions. First, the lifetime of an item is assumed to have the same distribution under all stress levels, that is, a change of stress level does not change the shape of the life distribution but changes only its scale. Second, a functional relationship is assumed between the parameters of the life distribution and the accelerating stresses. A nonparametric approach, on the other hand, assumes a functional relationship between the life distribution functions at the accelerated and nonaccelerated stress levels without making any assumptions on the forms of the distribution functions. In this paper, we treat the problem nonparametrically. In particular, we extend the methods of Shaked, Zimmer, and Ball [7] and Strelec and Viertl [8] and develop a nonparametric estimation procedure for a version of the generalized Arrhenius model with two stress variables assuming a linear acceleration function. We obtain consistent estimates as well as confidence intervals of the parameters of the life distribution under normal stress level and compare our nonparametric method with parametric methods assuming exponential, Weibull and lognormal life distributions using both real life and simulated data. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 629–644, 1998     

Multi-item service constrained (s,S) policies for spare parts logistics systems

Many organizations providing service support for products or families of products must allocate inventory investment among the parts (or, identically, items) that make up those products or families. The allocation decision is crucial in today's competitive environment in which rapid response and low levels of inventory are both required for providing competitive levels of customer service in marketing a firm's products. This is particularly important in high-tech industries, such as computers, military equipment, and consumer appliances. Such rapid response typically implies regional and local distribution points for final products and for spare parts for repairs. In this article we fix attention on a given product or product family at a single location. This single-location problem is the basic building block of multi-echelon inventory systems based on level-by-level decomposition, and our modeling approach is developed with this application in mind. The product consists of field-replaceable units (i.e., parts), which are to be stocked as spares for field service repair. We assume that each part will be stocked at each location according to an (s, S) stocking policy. Moreover, we distinguish two classes of demand at each location: customer (or emergency) demand and normal replenishment demand from lower levels in the multiechelon system. The basic problem of interest is to determine the appropriate policies (s_i S_i) for each part i in the product under consideration. We formulate an approximate cost function and service level constraint, and we present a greedy heuristic algorithm for solving the resulting approximate constrained optimization problem. We present experimental results showing that the heuristics developed have good cost performance relative to optimal. We also discuss extensions to the multiproduct component commonality problem.     

军事通信中ad hoc网络路由协议性能分析

移动ad hoc组网灵活,抗毁性很强,将在未来的军事通信中发挥重要作用。因此,对于移动ad hoc网络研究中的首要的路由问题作了探讨,先简要介绍了两种典型的路由协议OLSR(Optimized Link State Routing)和AODV(Ad hoc On-Demand Distance Vector Routing),接着利用网络仿真工具OPNET分析了AODV的协议特点,最后比较了两种路由协议的性能。仿真结果表明AODV路由开销小,但时延大,节点移动过快时存在路由稳定性的问题;OLSR路由开销很大,但时延相对较小。因此在搭建军用adhoc网时,应根据实际使用情形做出选择。     

Minimizing weighted mean absolute deviation of flow times in single machine systems

We discuss the problem of scheduling several jobs on a single machine with the objective of minimizing the weighted mean absolute deviation of flow times around the weighted mean flow time. We first show that the optimal schedule is W-shaped. For the unweighted case, we show that all optimal schedules are V-shaped. This characterization enables us to show that the problem is NP-hard. We then provide a pseudopolynomial algorithm for the unweighted problem. Finally, we consider three heuristic algorithms for the unweighted problem and report computational experience with these algorithms. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 297–311, 1998     

Solution algorithms for the parallel replacement problem under economy of scale

We consider the parallel replacement problem in which machine investment costs exhibit economy of scale which is modeled through associating both fixed and variable costs with machine investment costs. Both finite- and infinite-horizon cases are investigated. Under the three assumptions made in the literature on the problem parameters, we show that the finite-horizon problem with time-varying parameters is equivalent to a shortest path problem and hence can be solved very efficiently, and give a very simple and fast algorithm for the infinite-horizon problem with time-invariant parameters. For the general finite-horizon problem without any assumption on the problem parameters, we formulate it as a zero-one integer program and propose an algorithm for solving it exactly based on Benders' decomposition. Computational results show that this solution algorithm is efficient, i.e., it is capable of solving large scale problems within a reasonable cpu time, and robust, i.e., the number of iterations needed to solve a problem does not increase quickly with the problem size. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 279–295, 1998     

Values for optimum reject allowances

Industrial situations exist where it is necessary to estimate the optimum number of parts to start through a manufacturing process in order to obtain a given number of completed good items. The solution to this problem is not straightforward when the expected number of rejects from the process is a random variable and when there are alternative penalties associated with producing too many or too few items. This paper discusses various aspects of this problem as well as some of the proposed solutions to it. In addition, tables of optimum reject allowances based on a comprehensive model are presented.     

Open shop scheduling to minimize the number of late jobs

We develop polynomial algorithms for several cases of the NP-hard open shop scheduling problem of minimizing the number of late jobs by utilizing some recent results for the open shop makespan problem. For the two machine common due date problem, we assume that either the machines or the jobs are ordered. For the m machine common due date problem, we assume that one machine is maximal and impose a restriction on its load. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 525–532, 1998     

Single machine sequencing with linear models of release dates

The paper deals with a problem of scheduling a set of jobs on a single machine. Before a job is released for processing, it must undergo some preprocessing treatment that consumes resources. It is assumed that the release date of a job is a linear decreasing continuous function of the amount of a locally and globally constrained, continuously divisible resource (e.g., energy, catalyzer, financial outlay, gas). The problem is to find a sequence of jobs and a resource allocation that will minimize the maximum job completion time. Such a problem appears, for example, in the ingot preheating and hot-rolling process in steel mills. It is shown that the problem is strongly NP-hard. Some polynomially solvable cases of the problem and approximate algorithms with both experimental and worst-case analysis are presented. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 99–113, 1998     

Scheduling of stochastic tasks on two parallel processors

We consider the problem of scheduling n tasks on two identical parallel processors. We show both in the case when the processing times for the n tasks are independent exponential random variables, and when they are independent hyperexponentials which are mixtures of two fixed exponentials, that the policy of performing tasks with longest expected processing time (LEPT) first minimizes the expected makespan, and that in the hyperexponential case the policy of performing tasks with shortest expected processing time (SEPT) first minimizes the expected flow time. The approach is simpler than the dynamic programming approach recently employed by Bruno and Downey.     

(R.Q) inventory problem with unknown mean demand and learning

We address a single product, continuous review model with stationary Poisson demand. Such a model has been effectively studied when mean demand is known. However, we are concerned with managing new items for which only a Bayesian prior distribution on the mean is available. As demand occurs, the prior is updated and our control parameters are revised. These include the reorder point (R) and reorder quantity (Q). Deemer, taking a clue from some earlier RAND work, suggested using a model appropriate for known mean, but using a Compound Poisson distribution for demand rather than Poisson to reflect uncertainty about the mean. Brown and Rogers also used this approach but within a periodic review context. In this paper we show how to compute optimum reorder points for a special problem closely related to the problem of real interest. In terms of the real problem, subject to a qualification to be discussed, the reorder points found are upper bounds for the optimum. At the same time, the reorder points found can never exceed those found by the Compound Poisson (Deemer) approach. And they can be smaller than those found when there is no uncertainty about the mean. As a check, the Compound Poisson and proposed approach are compared by simulation.