Product selection, machine time allocation, and scheduling decisions for manufacturing perishable products subject to a deadline

We are concerned about the following problem: a manufacturer owns a certain amount of perishable raw material which can be produced into different types of products. He must, however, finish the manufacturing process before a deadline (which represents, e.g., a fixed flight schedule). Due to the deadline constraint and the raw material limit, it is imperative for the manufacturer to determine three decisions: (i) the product types to be produced; (ii) the machine time to be allocated for each product type; and (iii) the sequence to process the products selected. We develop, in this paper, a model to formulate this problem. We show that (i) and (iii) can be determined by analytical rules, and (ii) can be computed by an efficient algorithm. The optimal policy with the three decisions for the problem is therefore completely constructed. We also show the relationships of our model to stochastic scheduling and stochastic knapsack, and discuss the contributions of our work to the two areas. (c) 2006 Elsevier Ltd. All rights reserved.