화학공학소재연구정보센터
Computers & Chemical Engineering, Vol.96, 18-32, 2017
Variants to a knapsack decomposition heuristic for solving R&D pipeline management problems
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. (C) 2016 Elsevier Ltd. All rights reserved.