OPTIMIZATION MODELS FOR THE SCHEDULING OF TESTING TASKS IN NEW PRODUCT DEVELOPMENT

This paper presents several models for the optimal scheduling of testi ng tasks in the new product development process of an agricultural che mical or pharmaceutical company. In these industries, many of the task s involved in producing a new product are regulatory requirements, suc h as environmental and safety tests. The failure of a single required test may prevent a potential product from reaching the marketplace and therefore must be explicitly included in the model. As an added compl ication, there are uncertainties in the costs, probabilities of succes s, durations of the tasks, and income resulting from introducing the n ew product. Given the goal of maximizing the expected net present valu e of the research, the scheduling problem is initially formulated as a nonlinear, nonconvex disjunctive program and then reformulated as a m ixed integer linear program (MILP). It is shown that, with some simpli fications, a formulation can be developed involving implicit constrain ts on the paths through a network representing the precedence constrai nts of the schedule. A cutting plane algorithm is presented for such a model, which allows problems of up to 19 tasks to be solved with reas onable computational effort.