A genetic algorithm methodology for complex scheduling problems

This paper considers the scheduling problem to minimize total tardiness given multiple machines, ready times, sequence dependent setups, machine downtime and scarce tools. We develop a genetic algorithm based on random keys representation, elitist reproduction, Bernoulli crossover and immigration type mutation. Convergence of the algorithm is proved. We present computational results on data sets from the auto industry. To demonstrate robustness of the approach, problems from the literature of different structure are solved by essentially the same algorithm. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 199–211, 1999     

A robust regression technique using compound estimation

Least squares fitting of regression models is a widely used technique. The presence of outliers in the data can have an adverse effect on the method of least squares, resulting in a model that does not adequately fit to the bulk of the data. For this situation, robust regression techniques have been proposed as an improvement to the method of least squares. We propose a robust regression procedure that performs well relative to the current robust methods against a variety of dataset types. Evaluations are performed using datasets without outliers (testing efficiency), with a large percentage of outliers (testing breakdown), and with high leverage outliers (testing bounded influence). The datasets are based on 2-level factorial designs that include axial points to evaluate leverage effects. A Monte Carlo simulation approach is used to evaluate the estimating capability of the proposed procedure relative to several competing methods. We also provide an application to estimating costs for government satellites. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 125–139, 1998     

Artificial intelligence & future warfare: implications for international security

Recent developments in artificial intelligence (AI) suggest that this emerging technology will have a deterministic and potentially transformative influence on military power, strategic competition, and world politics more broadly. After the initial surge of broad speculation in the literature related to AI this article provides some much needed specificity to the debate. It argues that left unchecked the uncertainties and vulnerabilities created by the rapid proliferation and diffusion of AI could become a major potential source of instability and great power strategic rivalry. The article identifies several AI-related innovations and technological developments that will likely have genuine consequences for military applications from a tactical battlefield perspective to the strategic level.     

Risk pooling in a two-period,two-echelon inventory stocking and allocation problem

The object of this article is to investigate the risk-pooling effect of depot stock in two-echelon distribution system in which the depot serves n retailers in parallel, and to develop computationally tractable optimization procedures for such systems. The depot manager has complete information about stock levels and there are two opportunities to allocate stock to the retailers within each order cycle. We identify first- and second-order aspects to the risk-pooling effect. In particular, the second-order effect is the property that the minimum stock available to any retailer after the second allocation converges in probability to a constant as the number of retailers in the system increases, assuming independence of the demands. This property is exploited in the development of efficient procedures to determine near-optimal values of the policy parameters.     

Optimal policies for stochastic clearing systems with time-dependent delay penalties

We study stochastic clearing systems with a discrete-time Markovian input process, and an output mechanism that intermittently and instantaneously clears the system partially or completely. The decision to clear the system depends on both quantities and delays of outstanding inputs. Clearing the system incurs a fixed cost, and outstanding inputs are charged a delay penalty, which is a general increasing function of the quantities and delays of individual inputs. By recording the quantities and delays of outstanding inputs in a sequence, we model the clearing system as a tree-structured Markov decision process over both a finite and infinite horizon. We show that the optimal clearing policies, under realistic conditions, are of the on-off type or the threshold type. Based on the characterization of the optimal policies, we develop efficient algorithms to compute parameters of the optimal policies for such complex clearing systems for the first time. We conduct a numerical analysis on the impact of the nonlinear delay penalty cost function, the comparison of the optimal policy and the classical hybrid policy (ie, quantity and age thresholds), and the impact of the state of the input process. Our experiments demonstrate that (a) the classical linear approximation of the cost function can lead to significant performance differences; (b) the classical hybrid policy may perform poorly (as compared to the optimal policies); and (c) the consideration of the state of the input process makes significant improvement in system performance.     

On the equivalence of jit and mrp as technologies for reducing wastes in manufacturing

JIT (just-in-time) is widely regarded as an excellent tool for reducing costs and cycle times, and for improving quality in manufacturing operations. JIT follows a multistep procedure. First, it identifies and prioritizes wastes or non-value-adding activities. Second, it forces these wastes to be removed. MRP (materials requirements planning) can identify the same wastes and prioritize them in the same way that JIT does, by using data from the MRP database and master production schedule, and a waste identification model. In this article, a model is developed which describes the process by which the classic JIT system identifies and prioritizes waste. An equivalent MRP waste identification model is then developed for the production environment of the classic JIT system. (The classic JIT system was developed to produce many products having low to medium volumes.) The results developed here can be extended to other production environments where adaptations of the classic JIT system are used. An example, taken from an actual application, is presented to illustrate the models and the equivalence of JIT and MRP as systems for identifying and prioritizing wastes in manufacturing. © 1993 John Wiley & Sons, Inc.     

Vector processing approach to constrained network problems

Modification of algorithms designed for scalar computing, to take advantage of vector processing, raises several challenges. This article presents the vectorization of the primal simplex based network algorithm and results in a 50% improvement in computational time. One of the major contributors to this improvement is the matching of the size of the pricing candidate list to the vector register size. The side constraints are relaxed into a single surrogate constraint. The single constraint network algorithm is vectorized and used as the basis for solving large-scale constrained network problems. Computational experiments are presented which illustrate the vectorization of the network code as well as the ability of the surrogate constraint approach to deal with large constrained network problems.     

Scheduling of parallel processors: A posterior bound on LPT sequencing and a two-step algorithm

This article considers the problem of scheduling parallel processors to minimize the makespan. The article makes two key contributions: (1) It develops a new lower bound on the makespan for an optimal schedule, and (2) it proposes an efficient two-step algorithm to find schedules of any desired accuracy, or percent above optimal. In addition, a posterior bound on LPT (longest processing time) sequencing is developed in the article. It is proved that this bound dominates the previously reported bounds on LPT sequencing.