Note: On the set-union knapsack problem

We consider a generalization of the 0-1 knapsack problem called the set-union knapsack problem (SKP). In the SKP, each item is a set of elements, each item has a nonnegative value, and each element has a nonnegative weight. The total weight of a collection of items is given by the total weight of the elements in the union of the items' sets. This problem has applications to data-base partitioning and to machine loading in flexible manufacturing systems. We show that the SKP remains NP-hard, even in very restricted cases. We present an exact, dynamic programming algorithm for the SKP and show sufficient conditions for it to run in polynomial time. © 1994 John Wiley & Sons, Inc.     

Minimizing flow time on a single machine with job classes and setup times

We examine the static sequencing problem of ordering the processing of jobs on a single machine so as to minimize the average weighted flow time. It is assumed that all jobs have zero ready times, and that the jobs are grouped into classes with the property that setup tasks are only required when processing switches from jobs of one class to jobs of another class. The time required for each setup task is given by the sum of a setdown time from the previous class and a setup time for the new class. We show that an algorithm presented in the literature for solving a special case of this problem gives suboptimal solutions. A number of properties of the optimal solution are derived, and their use in algorithms is evaluated. Computational results are presented for both a branch-and-bound procedure and a simpler depth-first search.     

An analytic basis for decision support in negotiations

Mediators increase the effectiveness of negotiation processes. The art of mediation includes interpersonal skills, ability to convince, and proficiency in argumentation. The science of mediation represents an analytical approach to problem solving, a systematic analysis of the process, of players' positions, and of their goals, aspirations, and concessions. Analytical tools for mediation can be used by mediators, but these tools can also support negotiators in their analysis, verification of their positions, and choices. The knowledge of effective and safe alternatives, of sets of compromises, and the knowledge of the possible outcomes of concessions may be used to develop an effective strategy and to increase a negotiator's bargaining power. Models to analyze alternatives, to verify concessions made by the opponents, to determine effective alternatives, and to search for solutions that yield mutual gains, to aggregate opponents' proposals, to look for coalition members, and to simulate some of the actions of a mediator are discussed in the article.     

Heterogeneous multitrunking queueing systems with thresholds

Queueing systems with multiple servers are commonly used to model telecommunications systems. But, in general, the service rate of each of the servers is not the same. This fact is indeed true in a communication network where one path (server) may be a terrestrial link and the other (server) a satellite link with its inherent propagation delay. In this article we consider a two-server system where arriving customers are first placed in the queue for the faster server until that queue size reaches a certain threshold, whereupon they are diverted to the slower server. Additional arriving customers are assigned to the slower server until the faster server's queue drops to another lower threshold, at which point arrivals are reassigned to the faster server. We develop an exact mathematical model of the steady-state behavior of each queueing system and a simple analytic approximation.     

An approach to modeling electric utility capacity expansion planning

This article describes an algorithm for solving the static electric utility capacity expansion problem. The advantages of this algorithm are twofold. First, it is simpler and yet more efficient than previous algorithms for the same problem. Second, by making simplifying but realistic assumptions on plant sizes it is possible to use this algorithm for the case where one does not allow fractional plant additions. While the model has n variables, it has a clear two-dimensional geometric representation for understanding its properties, developing an algorithm, and interpreting the optimal solution. This algorithm has been implemented in the Intermediate Future Forecasting (IFFS) capacity expansion model at the Department of Energy.     

Use of a classifier in a knowledge-based simulation optimization system

This article defines and develops a simulation optimization system based upon response surface classification and the integration of multiple search strategies. Response surfaces are classified according to characteristics that indicate which search technique will be most successful. Typical surface characteristics include statistical measures and topological features, while search techniques encompass response surface methodology, simulated annealing, random search, etc. The classify-then-search process flow and a knowledge-based architecture are developed and then demonstrated with a detailed computer example. The system is useful not only as an approach to optimizing simulations, but also as a means for integrating search techniques and thereby providing the user with the most promising path toward an optimal solution. © 1995 John Wiley & Sons, Inc.     

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.     

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.     

An inventory model of incentives for on-time delivery in just-in-time purchasing contracts

This article formulates an analytic model of just-in-time purchasing contracts and compares the minimum cost solution with the cost attainable through vertical integration. The models use standard inventory theory cost parameters and decision variables. The results quantify the increase in cost of buying an item rather than making it. Optimal incentives are characterized when JIT purchasing contracts are used. When JIT purchasing is implemented, buffer inventories are typically reduced. This inventory reduction makes on-time delivery critical to the buyer; yet timeliness is controlled by the supplier. As an incentive to provide on-time delivery, the buyer offers the supplier a bonus for on-time delivery. The supplier chooses a flow time allowance based upon the bonus offered. First- and second-order conditions are characterized in general, and examples are provided for exponentially and uniformly distributed flow times. The delivery timeliness obtainable in a vertically integrated firm is determined and compared with timeliness obtainable between separate firms. This comparison indicates that buyers who choose to purchase materials from a separate firm are more likely to experience late deliveries. The relationship between the value of the bonus and the proportion of on-time deliveries is also considered. The bonus required to achieve the same probability of on-time delivery as under vertical integration is also determined. © 1993 John Wiley & Sons, Inc.     

Component part stocking policies

This article presents research designed to aid firms who assemble many components into a final product. We assume that purchase quantities are fixed, and that all parts and components are assembled at one stage in a short time. Demand for the final product is represented by a stationary independent and identically distributed random variable; and unmet demand is backordered. Ordering is done on a periodic review basis. We develop infinite horizon, approximate expected cost, and expected service level functions, and we present an algorithm for finding approximately minimum cost reorder points for each part subject to a service level constraint. Extensive results on the accuracy of the approximations are presented. Due to the size of the problem, we present only limited results on the performance of the optimization algorithm.