Knowledge that Transforms

Given n items, each having a weight w i , and a container of capacity W, the Subset-Sum Problem (SSP) is to select a subset of the items whose total weight is closest to, without exceeding, W. The paper presents a mixed approach (depth first search-dynamic programming) to the exact solution of the problem. An extensive computational experience is presented, comparing the proposed algorithm with that of Ahrens-Finke, as well as with the Balas-Zemel algorithm for large problems. Both “easy” and “hard” problems with values of n up to 10,000 are considered.

Planning is a process of inquiry. Inquiry can be enhanced if different views-of-the-world are used to inform each other. In an exploratory field study, a sense-making exercise was used in the initial, goal definition stage of planning. Its use is antithetical because sense-making denies that management action is based on preconceived goals or objectives. Instead, sense-making assumes management action is a continuous, equivocal stream of experience that can only be understood (or made sense of) when it is viewed in retrospect. Accounting reports were prepared to describe a fictitious, but plausible future scenario for an organization. A number of alternative future directions that the organization could have followed—different kinds of organization it could have become—were used as a basis for creating the accounting reports. The management group then imagined themselves even further out into the future, looking back over the accounting data. They tried to understand what they had done during this period, why they had done it, and how they felt about having done it. The impact of this exercise on the managers' cognitive and emotional experience and their commitment to use the method in other decisions suggest that sense-making can enhance the group process of inquiry during the initial stages of planning.

This paper gives optimality conditions to obtain a priori precedence relationships among some of the jobs in a single machine scheduling problem so as to curtail the enumeration while using branch-and-bound technique. The objective is to minimize a quadratic (or generalized quadratic) penalty function of job completion times.

In the scheduling situation considered here, we are given a set of routes, each associated with a particular school. A single bus is assigned to each route, picking up the students and arriving at their school within a specified time window. The scheduling problem is to find the fewest buses needed to cover all the routes while meeting the time window specifications. We present two integer programming formulations of the scheduling problem and apply them to actual data from New Haven, Connecticut for two different years, as well as to 30 randomly generated problems. Linear programming relaxations of these integer programs were found to produce integer solutions more than 75 percent of the time. In the remaining cases, we found that the few fractional values can be adjusted to integer values without increasing the number of buses needed. Our method reduces the number of buses needed by about 25 percent compared to the manual solutions developed by the New Haven school bus scheduler.

We introduce in this note the consistent organizational structure (COS) problem, which can be viewed as a generalization of the college admission and room-mates problems. Both the room-mates problem and the COS problem may have no stable solution. When side payments are allowed, the COS problem, but not the room-mates problem, always has a nonempty core. We further study some nucleoli of the COS problem with side payments.

We examine a multi-server queueing system with Poisson arrivals in which customers require simultaneous service from a random number of servers. Servers assigned to the same customer begin and end service concurrently. Service times are, in general, assumed to be exponentially distributed. A system point approach is presented as a framework for obtaining the waiting time distribution for each customer type. Explicit solutions are derived for the two-server system.

In this paper the problems of using aggregate monthly data to estimate learning curves are investigated. Here, aggregate monthly data on labor hours are assumed to contain some of both fixed and variable labor hours. They are also assumed to be influenced by fluctuating quantities of work in process. A distributed lag model is developed to deal with these two characteristics of aggregate monthly data. The model is generalized to permit production rate to influence labor productivity. This generalized model is then estimated and compared to a cumulative average learning curve in analyzing the impact of a production break. A set of production data which arose from a government contract claim is used for this purpose.

Optimal solutions for the dynamic lot-sizing problem with deterministic demands but stochastic lead times are “lumpy.” If lead time distributions are arbitrary except that they are independent of order size and do not allow orders to cross in time, then each order in an optimal solution will exactly satisfy a consecutive sequence of demands, a natural extension of the classic results by Wagner and Whitin. If, on the other hand, orders can cross in time, then optimal solutions are still “lumpy” in the sense that each order will satisfy a set, not necessarily consecutive, of the demands. An example shows how this characterization can be used to find a solution to a problem where interdependence of lead times is critical. This characterization of optimal solutions facilitates dynamic programming approaches to this problem.

Control charts are given for monitoring an input-output model against changes in form, against changes in its coefficients, and against changes in process variance. When a process is not in control due to changes in some coefficients, monitoring shifts to a diagnostic mode to identify the altered coefficients and thus the needed adjustments to the process. Control limits from special aid tables are used; these are considered along with the choice of design. Operating characteristics of the charts are summarized under standard assumptions.

One reason existing approaches for dealing with benefit interactions in economic R and D project selection models are difficult to apply is that it is difficult to assess the interactions directly. This difficulty can be traced at least in part to the lack of a modeling framework within which different types of interaction can be identified and related to project and portfolio benefit. In this paper, a modeling framework is proposed within which certain kinds of benefit interactions, called present value (PV) interactions, are assessed indirectly by explicitly modeling R and D project impacts on profitability. Within the proposed framework, the role of traditionally recognized types of interaction in the calculation of present value is clarified, and it is shown that PV interaction exists even when traditionally recognized types of interaction are assumed to be absent. The proposed framework offers one method for assessing PV interactions. An example illustrates the framework and shows that ignoring PV interactions can result in both nonoptimal project selections and resource allocations, even when traditionally recognized types of interactions are absent. The framework and resulting model should be useful in enhancing decision making in firms using PV-based approaches to project selection, whether or not they are interested in using a model that accounts for PV interactions. This is expected since the overall framework provides a basis for analyzing the probable consequences of assuming that no PV interaction is present and for communicating these probable consequences to management