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.