Unbounded knapsack problem with controllable rates: The case of a random demand for items

Unbounded knapsack problem with controllable rates: The case of a random demand for items

0.00 Avg rating0 Votes
Article ID: iaor2004938
Country: United Kingdom
Volume: 54
Issue: 6
Start Page Number: 594
End Page Number: 604
Publication Date: Jun 2003
Journal: Journal of the Operational Research Society
Authors:
Keywords: knapsack problem
Abstract:

This paper focuses on a dynamic, continuous-time control generalization of the unbounded knapsack problem. This generalization implies that putting items in a knapsack takes time and has a due date. Specifically, the problem is characterized by a limited production horizon and a number of item types. Given an unbounded number of copies of each type of item, the items can be put into a knapsack at a controllable production rate subject to the available capacity. The demand for items is not known until the end of the production horizon. The objective is to collect items of each type in order to minimize shortage and surplus costs with respect to the demand. We prove that this continuous-time problem can be reduced to a number of discrete-time problems. As a result, solvable cases are found and a polynomial-time algorithm is suggested to approximate the optimal solution with any desired precision.

Reviews

Required fields are marked *. Your email address will not be published.