Solving time/cost trade-off problems with discounted cash flows using generalized benders decomposition

In this article we consider a project scheduling problem where there are cash flows throughout the life of the project and where shorter activity durations can be attained by incurring greater direct costs. In particular, the objective of this problem is to determine the activity durations and a schedule of activity start times so that the net present value of cash flows is maximized. We formulate this problem as a mixed-integer nonlinear program which is amenable to solution using the generalized Benders decomposition technique developed by Geoffrion. We test the algorithm on 140 project scheduling problems, the largest of which contains 30 nodes and 64 activities. Our computational results are quite encouraging inasmuch as 123 of the 140 problems require less than 1 CPU second of solution time. © 1993 John Wiley & Sons, Inc.     

A multi-run interactive method for bicriterion optimization problems

This article introduces a new conceptual and methodological framework for the use of decision makers and their interactions with the computer in bicriterion decision making. The new method, called the multirun interactive method, attempts to estimate the prior of the decision maker on his uncertain preference nature using the minimum cross-entropy principle. A computational study is performed with four hypothesized prior distributions under various interaction conditions. Other important aspects related to the method, such as implementation of the method, decision making under certainty, decision making with multiple decision makers, and bicriterion integer programming, are also discussed.     

Optimal resource extraction with uncertain reserves

We consider the problem of finding a plan that maximizes the expected discounted return when extracting a nonrenewable resource having uncertain reserves. An extraction plan specifies the rate at which the resource is extracted as a function of time until the resource is exhausted or the time horizon is reached. The return per unit of resource extracted may depend on the rate of extraction, time, and the amount of resource previously extracted. We apply a new method called the generalized search optimization technique to find qualitative features of optimal plans and to devise algorithms for the numerical calculation of optimal plans.     

Scheduling workers in a constricted area

A generalization of the equi-partitioning problem, termed the 2D-Partition Problem, is formulated. The motivation is an aircraft maintenance scheduling problem with the following characteristics. The complete maintenance overhaul of a single aircraft requires the completion of some 350 tasks. These tasks require a varying number of technicians working at the same time. For large subsets of these 350 tasks, the constraining resource is physical space—tasks must be completed in a physical space of limited size such as the cockpit. Furthermore, there is no precedence relationship among the tasks. For each subset, the problem is to schedule the tasks to minimize makespan. Let m denote the maximum number of technicians that can work at the same time in the physical area under consideration. We present optimization algorithms for m = 2 and 3. © 1996 John Wiley & Sons, Inc.     

An evaluation of scheduling heuristics for dynamic single-processor scheduling with early/tardy costs

In an endeavor to broaden the application of scheduling models to decisions involving the use of a manager's time we use simulation to investigate the performance of a number of simple algorithms (including eight priority rules and a construction heuristic) in a dynamic setting with tasks arriving (randomly) and scheduling decisions being made, over time. We compare these simple methods relative to a bound that uses an adjacent pairwise interchange algorithm. We model uncertainty in task durations, and costs being incurred for early and tardy task completion (representative of JIT settings). In addition to evaluating the efficacy of the scheduling rules and various preemption strategies (using ANOVA), we highlight the managerial implications of the effects of eight environmental parameters. © 1996 John Wiley & Sons, Inc.     

The single-machine absolute-deviation early-tardy problem with random completion times

We consider sequencing n jobs on a single machine subject to job completion times arising from either machine breakdowns or other causes. The objective is to minimize an expected weighted combination of due dates, completion times, earliness, and tardiness penalties. The determination of optimal distinct due dates or optimal common due dates for a given schedule is investigated. The scheduling problem for a fixed common due date is considered when random completion times arise from machine breakdowns. The optimality of a V-shaped about (a point) T sequence is established when the number of machine breakdowns follows either a Poisson or a geometric distribution and the duration of a breakdown has an exponential distribution. © 1996 John Wiley & Sons, Inc.     

Facility location and capacity acquisition: An integrated approach

The facility location and capacity acquisition decisions are intertwined, especially within the international context where capacity acquisition costs are location dependent. A review of the relevant literature however, reveals that the facility location and the capacity acquisition problems have been dealt with separately. Thus, an integrated approach for simultaneous optimization of these strategic decisions is presented. Analytical properties of the arising model are investigated and an algorithm for solving the problem is devised. Encouraging computational results are reported. © 1995 John Wiley & Sons, Inc.     

Expressions for item fill rates in periodic inventory systems

We examine the problem of estimating the item fill rate in a periodic inventory system. We show that the traditional expressions for line item fill rate, found in many operations management textbooks, perform well for high fill rates (above 90%), but they consistently underestimate the true fill rate. The problem of underestimation becomes significant as the fill rate falls below 90% and is greatly amplified in cases with very low fill rates (below 50%). We review other more accurate expressions for fill rate, discussing their relative merits. We then develop an exact fill rate expression that is robust for both high and low fill rates. We compare the new expression to others found in the literature via an extensive set of simulation experiments using data that reflect actual inventory systems found at Hewlett-Packard. We also examine the robustness of the expressions to violations in the underlying assumptions. Finally, we develop an alternative fill rate expression that is robust for cases of high demand variability where product returns are allowed. © 1995 John Wiley & Sons, Inc.     

A survey of preventive maintenance models for stochastically deteriorating single-unit systems

A survey of the research done on preventive maintenance is presented. The scope of the present survey is on the research published after the 1976 paper by Pierskalla and Voelker [98]. This article includes optimization models for repair, replacement, and inspection of systems subject to stochastic deterioration. A classification scheme is used that categorizes recent research into inspection models, minimal repair models, shock models, or miscellaneous replacement models.