Abstract
In the last two decades we observed a considerably improvement in algorithms' performances and their ability to solve hard combinatorial optimization problems. One of these problems is the knapsack sharing problem (KSP). The latter problem is a challenging variant of the well-known NP-hard single knapsack problem. In fact, we can find in the literature several exact and heuristic resolution approaches to solve the (KSP). We mainly propose here an improvement and an adaptation to parallel computing of one of the existing and most recent algorithm in the literature. The approach is a constructive tree search that runs in two phases: the initial solution construction phase and the second phase where we build the optimal solution through a customized branch and bound. We applied a parallel computing on this second phase in order to improve the overall computational time. Finally we present a comparative study on instances from literature to show the positive effect of parallel processing on the computing time.