A STUDY ON THE MULTI-PERIOD MULTIPLE KNAPSACK PROBLEM
This paper deals with the Multi-Period Multiple Knapsack Problem (MPMKP). Such problems arises especially when one needs to manage a set of equipments by determining their replacement dates being given a budget over a time horizon. Firstly, the connections with other variants of knapsack problem are studied, especially in terms of complexity. Three special cases are examined and complexity results are reported. Particularly, it is shown that one of the special cases is strongly NP-hard. Next, resolution methods are proposed based on respectively Dantzig and Martello and Toth heuristics as well as Tabu search. The results obtained are compared with these obtained under CPLEX. It shows that for most of the instances tested, Tabu search gives satisfactory results with solutions less than 1％ from optimality. Furthermore, for certain large instances, especially when the number of periods is important, the Tabu search method becomes faster and more efficient than CPLEX.
Multi-period multiple knapsack NP-complezity Tabu search.
X. CAO A. JOUGLET D. NACE
Heudiasyc UMR 6599 Université de Technologie de Compiègne BP 20529 60205 COMPIEGNE CEDEX FRANCE Heudiasyc UMR 6599Université de Technologie de CompiègneBP 20529 60205 COMPIEGNE CEDEX FRANCE
国际会议
上海
英文
1-6
2009-08-02（万方平台首次上网日期，不代表论文的发表时间）