Knowledge that Transforms

We study pooled (or group) testing as a cost-effective alternative for screening donated blood products (sera) for HIV; rather than test each sample individually, this method combines various samples into a pool, and then tests the pool. A group testing policy specifies an initial pool size, and based on the HIV test result, either releases all samples in the pool for transfusion, discards all samples in the pool, or divides the pool into subpools for further testing. We develop a hierarchical statistical model that relates the HIV test output to the antibody concentration in the pool, thereby capturing the effect of pooling together different samples. The model is validated using data from a variety of field studies. The model is embedded into a dynamic programming algorithm that derives a group testing policy to minimize the expected cost due to false negatives, false positives, and testing. Because the implementation of the dynamic programming algorithm is cumbersome, a simplified version of the model is used to develop near optimal heuristic policies. A simulation study shows that significant cost savings can be achieved without compromising the accuracy of the test. However, the efficacy of group testing depends upon the use of a classification rule (that is, discard the samples in the pool, transfuse them or test them further) that is dependent on pool size, a characteristic that is lacking in currently implemented pooled testing procedures.

An important class of machine scheduling problems is characterized by a no-wait or blocking production environment, where there is no intermediate buffer between machines. In a no-wait environment, a job must be processed from start to completion, without any interruption either on or between machines. Blocking occurs when a job, having completed processing on a machine, remains on the machine until a downstream machine becomes available for processing. A no-wait or blocking production environment typically arises from characteristics of the processing technology itself, or from the absence of storage capacity between operations of a job. In this review paper, we describe several well-documented applications of no-wait and blocking scheduling models and illustrate some ways in which the increasing use of modern manufacturing methods gives rise to other applications. We review the computational complexity of a wide variety of no-wait and blocking scheduling problems and describe several problems which remain open as to complexity. We study several deterministic flowshop, jobshop, and openshop problems and describe efficient and enumerative algorithms, as well as heuristics and results about their performance. The literature on stochastic no-wait and blocking scheduling problems is also reviewed. Finally, we provide some suggestions for future research directions.

The Ontario Ministry of Natural Resources (OMNR) operates a fleet of nine CL-215 airtankers for forest fire control. The aircraft are based at a small number of airports that serve as home bases, from which they are deployed to a larger set of airports that serve as initial attack bases for fire fighting operations each day. We helped regional fire managers derive subjective airtanker deployment rules that specified how many airtankers were to be deployed at each initial attack base each day. We then developed a mathematical programming model that was used to help identify a home-basing strategy that would minimize the average annual cost of satisfying daily airtanker deployment demands. Our analysis provided OMNR decision makers with valuable insight into airtanker management and was used to help decide where to base the OMNR airtankers for the 1993 and subsequent fire seasons.