Scheduling with parallel processors and linear delay costs

This paper deals with the sequencing problem of minimizing linear delay costs with parallel identical processors. The theoretical properties of this m-machine problem are explored, and the problem of determining an optimum scheduling procedure is examined. Properties of the optimum schedule are given as well as the corresponding reductions in the number of schedules that must be evaluated in the search for an optimum. An experimental comparison of scheduling rules is reported; this indicates that although a class of effective heuristics can be identified, their relative behavior is difficult to characterize.     

A heuristic procedure for allocating tasks in fault-tolerant distributed computer systems

One way of achieving the increased levels of system reliability and availability demanded by critical computer-based control systems is through the use of fault-tolerant distributed computer systems. This article addresses the problem of allocating a set of m tasks among a set of n processors in a manner that will satisfy various task assignment, system capacity, and task scheduling constraints while balancing the workload across processors. We discuss problem background, problem formulation, and a known heuristic procedure for the problem. A new solution-improving heuristic procedure is introduced, and computational experience with the heuristics is presented. With only a modest increase in the amount of computational effort, the new procedure is demonstrated to improve dramatically solution quality as well as obtain near-optimal solutions to the test problems.     

An optimal critical level policy for inventory systems with two demand classes

Traditional inventory systems treat all demands of a given item equally. This approach is optimal if the penalty costs of all customers are the same, but it is not optimal if the penalty costs are different for different customer classes. Then, demands of customers with high penalty costs must be filled before demands of customers with low penalty costs. A commonly used inventory policy for dealing with demands with different penalty costs is the critical level inventory policy. Under this policy demands with low penalty costs are filled as long as inventory is above a certain critical level. If the inventory reaches the critical level, only demands with high penalty costs are filled and demands with low penalty costs are backordered. In this article, we consider a critical level policy for a periodic review inventory system with two demand classes. Because traditional approaches cannot be used to find the optimal parameters of the policy, we use a multidimensional Markov chain to model the inventory system. We use a sample path approach to prove several properties of this inventory system. Although the cost function is not convex, we can build on these properties to develop an optimization approach that finds the optimal solution. We also present some numerical results. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

A simulated annealing approach to the cyclic staff-scheduling problem

This article presents the application of a simulated annealing heuristic to an NP-complete cyclic staff-scheduling problem. The new heuristic is compared to branch-and-bound integer programming algorithms, as well as construction and linear programming-based heuristics. It is designed for use in a continuously operating scheduling environment with the objective of minimizing the number of employees necessary to satisfy forecast demand. The results indicate that the simulated annealing-based method tends to dominate the branch-and-bound algorithms and the other heuristics in terms of solution quality. Moreover, the annealing algorithm exhibited rapid convergence to a low-cost solution. The simulated annealing heuristic is executed in a single program and does not require mathematical programming software. © 1993 John Wiley & Sons, Inc.     

A note on a model for evasive vehicle movement along a fixed path

A model for a vehicle moving evasively along a fixed path is defined in terms of a two- state semi-Markov process. An important feature of this model is the continuous movement of the vehicle as a function of time. One potential application of this model is the development of a strategy for the deployment of long-range missiles on long underground tracks.     

The Rebirth of Insurgency in Peru

Peru has battled two major insurgent movements since 1980. Around 25,000 Peruvians have died in this war between the government against the Shining Path and the MRTA. The Peruvian military has been incapable of achieving total victory after several major operations and the capture of just about every major rebel leader. Even worse, after a few years of almost no activity, Shining Path seems to be re-emerging. The last remaining members of this insurgent group have made alliances with foreign terrorist groups, used drug traffic to fund their fight and sweet talked people who are very disappointed and mad at the current Toledo administration, to gain more supporters. Major changes have to occur to prevent both groups from becoming threats to national security and society as a whole, taking the country back to times when around half of the nation was declared to be under terrorist control. The defense budget must be increased to open new bases, buy new equipment and train soldiers better to fight the insurgents more effectively. At the same time, major social changes need to occur; Toledo and his government must gain the trust and sympathy of Peruvians again by working for and with them.     

Transporting jobs through a two‐machine open shop

We consider the two‐machine open shop scheduling problem in which the jobs are brought to the system by a single transporter and moved between the processing machines by the same transporter. The purpose is to split the jobs into batches and to find the sequence of moves of the transporter so that the time by which the completed jobs are collected together on board the transporter is minimal. We present a ‐approximation algorithm. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2009     

Note: A local-search heuristic for large set-covering problems

In this note we describe a local-search heuristic (LSH) for large non-unicost set-covering problems (SCPs). The new heuristic is based on the simulated annealing algorithm and uses an improvement routine designed to provide low-cost solutions within a reasonable amount of CPU time. The solution costs associated with the LSH compared very favorably to the best previously published solution costs for 20 large SCPs taken from the literature. In particular, the LSH yielded new benchmark solutions for 17 of the 20 test problems. We also report that, for SCPs where column cost is correlated with column coverage, the new heuristic provides solution costs competitive with previously published results for comparable problems. © 1995 John Wiley & Sons, Inc.     

Present practices and future plans for MIL-STD-781

MIL-STD-781 specifies reliability acceptance test procedures based on both fixed-length tests and probability ratio sequential tests. The assumption underlying MIL-STD-781 is a constant mean time between failures (MTBF) and typical practice applies MIL-STD-781 to electrical, electronic, and mechanical equipment. This article discusses some of the difficulties that have prompted the C and D revisions of MIL-STD-781. In addition, it discusses the relationship of MIL-STD-781 with MIL-STD-1635(EC) which deals with reliability growth testing. The article concludes with a discussion of needed research in reliability growth testing, in support of MIL-STD-781, and in the area of stress and its impact of MTBF.