دانلود رایگان مقاله روش اکتشافی تجزیه مساله کوله پشتی برای حل مسایل مدیریت خط لوله R & D

Abstract

The knapsack decomposition algorithm (KDA) (Christian and Cremaschi, 2015) decomposes the R&D pipeline management problem into a series of knapsack problems, which are solved along the planning horizon. It yields tight feasible solutions, and improves the solution times by several orders of magnitude for large instances. This paper investigates the impact of problem parameters and size, and KDA decision rules on KDA solution quality and time. The decision rules are (1) timing of new knapsack problem generations, and (2) formulation of the resource constraints in knapsack problems. The results revealed that the KDA decision trees were insensitive to problem parameters, and the KDA solution times grew super-linearly with linear increases in the length of the planning horizon and the number of products. The results suggest that the KDA where knapsack problems are generated after each realization with the original resource constraint yields the most accurate solutions in the quickest time.

7. Conclusions

The first portion of the presented work studied the sensitivity of the KDA solution to the changes in the values of the fixed parameters (trial cost, revenue, penalty levels, and trial length) of the R&D pipeline management problem. The trial cost, the revenue, and the penalty level parameters were perturbed by ±10% and ±25%. The trial length was extended by one and two time periods. In all of the cases, we observed very little change in the decisions obtained by the KDA. When the problem size was increased the accuracy of the KDA solution was not impacted by increasing the number of resources or the length of the planning horizon. However, when the number of trials was increased the KDA was unable to produce a “do-nothing” solution resulting in a large percent gap between the ENPV of the KDA solution and that of the deterministic equivalent of the rigorous MSSP. Increasing the length of the planning horizon caused exponential growth in the solution time. This can be attributed to the increase in the number of knapsack problems solved. Because the KDAonly generates knapsack problems to solve once uncertainty associated with all packed items (i.e., drug-trial pairs) are realized, longer durations reduces the decision points generated by the KDA, and results in sparser decision trees compared to the true solution. Inthis work, we consideredseveralmodifications to improve the KDA presented in Christian and Cremaschi(2015). The original KDA made decisions after all realizations occurred. Here, we presented two additional approaches, a scheme that generates knapsackproblems at every time period and a scheme that generates knapsack problems at each realization. Using a set of 25 problems including the six original problems solved in Christian and Cremaschi (2015), each scheme was tested. The results suggest that generating new problems at each realization provides solutions closer to the deterministic equivalent MSSP than generating problems after all realizations occurred. By solving new knapsack problems at each time period, the solution was often identical to solving new problems at each realization. In the few cases where solving knapsacks at each time period provided a superior solution,the increase in the algorithm time did not justify selection of the ETP approach over the AER approach.