The “textbook” treatment of the cutting stock problem, using a method termed column generation, solves the problem as if one is allowed to use fractional amounts of patterns. In practice, one can typically run only an integer quantity of a pattern. Dyckhoff was the first to propose an integer linear programming formulation for the problem of getting a guaranteed global optimum to cutting stock problems under the integrality requirement. We describe and test an extension of a method proposed by Degraeve for embedding a column generation procedure within branch and bound. We show that our algorithm is quite general. It can easily cope with various combinations of real world complications, such as 1) upper bounds on the amount by which the demand may be oversatisfied, 2) a limit on maximum waste allowed in each pattern, and 3) a limit on the maximum number of knives in the cutting patterns. We validate our approach using both industrial data sets from the paper industry and generated data sets. The performance of the algorithm is compared with Dyckhoff's formulation.

Abstract One promising technique for determining long genetic sequences is sequencing by oligonucleotide content. This technique involves probing a segment of the unknown multimillion “character” genetic sequence for the presence or absence of known short subsequences. The information obtained from such hybridization experiments may be represented in network form. Network optimization methods may then be applied to identify the most likely forms of the unknown target sequence. © 1994 by John Wiley & Sons, Inc.

Abstract We classify the features that seem to be encountered in real vehicle routing problems. Given these features, we try to indicate which features cause the greatest difficulty and which modeling approaches allow us to represent the greatest range of practical considerations or features.

A Fortran implementation of a random number generator is described whmh produces a sequence of random mtegers that is machine independent as long as the machine can represent all mtegers m the interval [ -2 . . 3 1 + 1, 2..31 -1]

A single processor provides service to jobs of several different priority classes. The priority ordering remains constant over time; however, the type of priority, i. e., preemptive or nonpreemptive, may depend upon the stage of processing of the job occupying the processor. We allow these preemptible and nonpreemptible intervals to be specified in a relatively arbitrary fashion. If a job is interrupted, a setup time must be incurred before processing can be continued on the job. If arrivals from all classes constitute independent Poisson streams, we are able to obtain expressions for the steady-state expected time in system for jobs of each class. These expressions are then analyzed to determine the optimum manner for assigning the preemptible and nonpreemptible intervals. When setup times are zero and preemptible portions are preemptive-resume, the optimal policy is fairly simple. When setup times are nonzero, the form of the optimal policy is not clear; however, numerical evaluations suggest that at high loads, e.g., greater than 0.9, one should allow much less preemption or time-sharing than one might suspect.