Optimization models for the scheduling of testing tasks in new product development

This paper presents several models for the optimal scheduling of testing tasks in the new product development process of an agricultural chemical or pharmaceutical company. In these industries, many of the tasks involved in producing a new product are regulatory requirements, such 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 complication, there are uncertainties in the costs, probabilities of success, durations of the tasks, and income resulting from introducing the new product. Given the goal of maximizing the expected net present value of the research, the scheduling problem is initially formulated as a nonlinear, nonconvex disjunctive program and then reformulated as a mixed integer linear program (MILP). It is shown that, with some simplifications, a formulation can be developed involving implicit constraints on the paths through a network representing the precedence constraints 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 reasonable computational effort.