An FPTAS for scheduling a two‐machine flowshop with one unavailability interval

We study a deterministic two‐machine flowshop scheduling problem with an assumption that one of the two machines is not available in a specified time period. This period can be due to a breakdown, preventive maintenance, or processing unfinished jobs from a previous planning horizon. The problem is known to be NP‐hard. Pseudopolynomial dynamic programming algorithms and heuristics with worst case error bounds are given in the literature to solve the problem. They are different for the cases when the unavailability interval is for the first or second machine. The existence of a fully polynomial time approximation scheme (FPTAS) was formulated as an open conjecture in the literature. In this paper, we show that the two cases of the problem under study are equivalent to similar partition type problems. Then we derive a generic FPTAS for the latter problems with O(n⁵/ε⁴) time complexity. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

Light weight HTPB-clay nanocomposites(HCN)with enhanced ablation performance as inhibition materials for composite propellant

In the present study,organically modified Montmorillonite clay with polar moiety,the Cloisite 30B,is used for preparation of Hydroxyl terminated polybutadiene(HTPB)-clay nanocomposites(HCN)by dispersion of nanoclay in polymer matrix under high shear mixing.The nanocomposites thus prepared are evaluated in composite propellants as inhibitor material for their functional utility.Several inhibition formulations containing 5 wt％-15 wt％of nanoclay,with or without the conventional filler Sb2O3,were prepared.All these formulations were evaluated for their physical,mechanical,thermal,and ablative properties.Ablation rate and density of the compositions containing Cloisite 30B is around 23％and 5％lower respectively in comparison of the base composition.Strain capability of these compositions is twofold higher than that of base composition.These compositions have also been evaluated for their smoke generation tendency by measuring infra red(IR)attenuation in the wavelength range 1.3 μm-5.6 μm and 8 μm-13 μm and thereby compared with the base composition.The corresponding results confirmed that the compositions containing Cloisite 30B as filler have much lower IR attenuation than compositions with conventional filler,Sb2O3.Replacement of 5％Sb2O3 by nanoclay showed 8％reduction in IR attenuation rate which further reduced to 16％on replacement of 15％of Sb2O3.Interfacial bonding of HCN based inhibitors is also comparable or even better than conventional inhibitors.Precisely,the nanoclay composites with Cloisite 30B as filler exhibit all desirable properties of an inhibitor.     

Single machine scheduling with a restricted rate‐modifying activity

In this paper we consider the problem of scheduling a set of jobs on a single machine on which a rate‐modifying activity may be performed. The rate‐modifying activity is an activity that changes the production rate of the machine. So the processing time of a job is a variable, which depends on whether it is scheduled before or after the rate‐modifying activity. We assume that the rate‐modifying activity can take place only at certain predetermined time points, which is a constrained case of a similar problem discussed in the literature. The decisions under consideration are whether and when to schedule the rate‐modifying activity, and how to sequence the jobs in order to minimize some objectives. We study the problems of minimizing makespan and total completion time. We first analyze the computational complexity of both problems for most of the possible versions. The analysis shows that the problems are NP‐hard even for some special cases. Furthermore, for the NP‐hard cases of the makespan problem, we present a pseudo‐polynomial time optimal algorithm and a fully polynomial time approximation scheme. For the total completion time problem, we provide a pseudo‐polynomial time optimal algorithm for the case with agreeable modifying rates. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Maximizing the ratio of two convex functions over a convex set

The purpose of this article is to present an algorithm for globally maximizing the ratio of two convex functions f and g over a convex set X. To our knowledge, this is the first algorithm to be proposed for globally solving this problem. The algorithm uses a branch and bound search to guarantee that a global optimal solution is found. While it does not require the functions f and g to be differentiable, it does require that subgradients of g can be calculated efficiently. The main computational effort of the algorithm involves solving a sequence of subproblems that can be solved by convex programming methods. When X is polyhedral, these subproblems can be solved by linear programming procedures. Because of these properties, the algorithm offers a potentially attractive means for globally maximizing ratios of convex functions over convex sets. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Modeling the operation of multireservoir systems using decomposition and stochastic dynamic programming

Stochastic dynamic programming models are attractive for multireservoir control problems because they allow non‐linear features to be incorporated and changes in hydrological conditions to be modeled as Markov processes. However, with the exception of the simplest cases, these models are computationally intractable because of the high dimension of the state and action spaces involved. This paper proposes a new method of determining an operating policy for a multireservoir control problem that uses stochastic dynamic programming, but is practical for systems with many reservoirs. Decomposition is first used to reduce the problem to a number of independent subproblems. Each subproblem is formulated as a low‐dimensional stochastic dynamic program and solved to determine the operating policy for one of the reservoirs in the system. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

故障诊断效率与评估

叙述了电子设备故障诊断系统所进行检测的不同安排顺序对故障诊断效率的影响.提出了适当的检测顺序与检测方式,提高检查效率,缩短检查过程.还分析了每次进行故障诊断结果确诊或误诊随机现象,评判诊断准确率是抽样检验问题.引入假设检验方法,对设备故障诊断系统的准确率进行评判.对建造设备故障诊断系统有参考价值.     

Minimizing makespan on a single batch processing machine with nonidentical job sizes

We deal with the problem of minimizing makespan on a single batch processing machine. In this problem, each job has both processing time and size (capacity requirement). The batch processing machine can process a number of jobs simultaneously as long as the total size of these jobs being processed does not exceed the machine capacity. The processing time of a batch is just the processing time of the longest job in the batch. An approximation algorithm with worst‐case ratio 3/2 is given for the version where the processing times of large jobs (with sizes greater than 1/2) are not less than those of small jobs (with sizes not greater than 1/2). This result is the best possible unless P = NP. For the general case, we propose an approximation algorithm with worst‐case ratio 7/4. A number of heuristics by Uzosy are also analyzed and compared. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 226–240, 2001     

Analysis of a new vehicle scheduling and location problem

We consider a container terminal discharging containers from a ship and locating them in the terminal yard. Each container has a number of potential locations in the yard where it can be stored. Containers are moved from the ship to the yard using a fleet of vehicles, each of which can carry one container at a time. The problem is to assign each container to a yard location and dispatch vehicles to the containers so as to minimize the time it takes to download all the containers from the ship. We show that the problem is NP‐hard and develop a heuristic algorithm based on formulating the problem as an assignment problem. The effectiveness of the heuristic is analyzed from both worst‐case and computational points of view. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 363–385, 2001