Knowledge that Transforms

This paper reviews the flowshop-sequencing research since 1954 that has been devoted to the static deterministic case in which n jobs are to be processed through a shop in which the processing times at each stage are fixed. The paper then comments on NP-completeness, the selection of criteria for optimization, and the lack of applications of this work in industry. Finally, it draws some conclusions about the possible future of sequencing research and the lessons that this area's work has to teach the rest of operations research.

Motivated by modeling manufacturing systems in which job arrivals and processing times are essentially deterministic, but the environment is typically random, we develop a fluid model with random disruptions. The quality and relevance of such a model are supported by the following facts which we establish in this study. The fluid model is more susceptible to analysis: Its (dynamical) sample paths are continuous and piecewise linear, and its stationary behavior can be studied using standard approaches in random walk; the model is a limit of corresponding queueing systems with random disruptions that are usually difficult to analyze; there exist pathwise bounds between the fluid model and D/D/1 queues with random disruptions, and the bounds are simple and tight.

This paper proposes a new method for representing and solving Bayesian decision problems. The representation is called a valuation-based system and has some similarities to influence diagrams. However, unlike influence diagrams which emphasize conditional independence among random variables, valuation-based systems emphasize factorizations of joint probability distributions. Also, whereas influence diagram representation allows only conditional probabilities, valuation-based system representation allows all probabilities. The solution method is a hybrid of local computational methods for the computation of marginals of joint probability distributions and the local computational methods for discrete optimization problems. We briefly compare our representation and solution methods to those of influence diagrams.

The vehicle routing problem with time windows (VRPTW) is a generalization of the vehicle routing problem where the service of a customer can begin within the time window defined by the earliest and the latest times when the customer will permit the start of service. In this paper, we present the development of a new optimization algorithm for its solution. The LP relaxation of the set partitioning formulation of the VRPTW is solved by column generation. Feasible columns are added as needed by solving a shortest path problem with time windows and capacity constraints using dynamic programming. The LP solution obtained generally provides an excellent lower bound that is used in a branch-and-bound algorithm to solve the integer set partitioning formulation. Our results indicate that this algorithm proved to be successful on a variety of practical sized benchmark VRPTW test problems. The algorithm was capable of optimally solving 100-customer problems. This problem size is six times larger than any reported to date by other published research.

The PAIRS method developed in this paper introduces imprecise preference statements into value trees. The assessment of attribute weights in PAIRS extends the well known SMART technique so that in addition to exact statements the decision maker can enter interval judgments which indicate ranges for the relative importance of the attributes. The interval judgments and the possibly range-valued information about the outcomes of the alternatives are processed with linear programming into value intervals and dominance relations. As the decision maker refines the description of his preferences, either by entering new statements or by tightening his earlier judgments, these results become more detailed and convey more information about which alternatives are preferred. Throughout the interactive refinement process PAIRS supports the decision maker by deriving and displaying the consequences of his earlier judgments.

We describe an approximation algorithm for the problem of finding the minimum makespan in a job shop. The algorithm is based on simulated annealing, a generalization of the well known iterative improvement approach to combinatorial optimization problems. The generalization involves the acceptance of cost-increasing transitions with a nonzero probability to avoid getting stuck in local minima. We prove that our algorithm asymptotically converges in probability to a globally minimal solution, despite the fact that the Markov chains generated by the algorithm are generally not irreducible. Computational experiments show that our algorithm can find shorter makespans than two recent approximation approaches that are more tailored to the job shop scheduling problem. This is, however, at the cost of large running times.

A typology of service organizations is presented and a conceptual framework is advanced for exploring the impact of physical surroundings on the behaviors of both customers and employees. The ability of the physical surroundings to facilitate achievement of organizational as well as marketing goals is explored. Literature from diverse disciplines provides theoretical grounding for the framework, which serves as a base for focused propositions. By examining the multiple strategic roles that physical surroundings can exert in service organizations, the author highlights key managerial and research implications.

Many individual companies and some industries monitor customer satisfaction on a continual basis, but Sweden is the first country to do so on a national level. The annual Customer Satisfaction Barometer (CSB) measures customer satisfaction in more than 30 industries and for more than 100 corporations. The new index is intended to be complementary to productivity measures. Whereas productivity basically reflects quantity of output, CSB measures quality of output (as experienced by the buyer). The author reports the results of a large-scale Swedish effort to measure quality of the total consumption process as customer satisfaction. The significance of customer satisfaction and its place within the overall strategy of the firm are discussed. An implication from examining the relationship between market share and customer satisfaction by a location model is that satisfaction should be lower in industries where supply is homogeneous and demand heterogeneous. Satisfaction should be higher when the heterogeneity/homogeneity of demand is matched by the supply. Empirical support is found for that proposition in monopolies as well as in competitive market structures. Likewise, industries in general are found to have a high level of customer satisfaction if they are highly dependent on satisfaction for repeat business. The opposite is found for industries in which companies have more captive markets. For Sweden, the 1991 results show a slight increase in CSB, which should have a positive effect on the general economic climate.