Approximate solution of a profit maximization constrained virtual business planning problem. (December 2015)

• Record Type: Journal Article
• Authors: Dolgui, Alexandre; Kovalev, Sergey; Pesch, Erwin
• Is Part Of: Omega. Volume 57:Part B(2015:Dec.)
• Page Start: 212
• Page End: 216
• Publication Date: 2015-12
• Subjects: Virtual business planning -- Knapsack problem -- Dynamic programming -- Fully polynomial time approximation scheme; Management -- Periodicals; 658.4005
• DOI: 10.1016/j.omega.2015.05.001
• Languages: English
• ISSNs: 0305-0483

Abstract

Abstract: A virtual business problem is studied, in which a company-contractor outsources production to specialized subcontractors. Finances of the contractor and resource capacities of subcontractors are limited. The objective is to select subcontractors and distribute a part of the demanded production among them so that the profit of the contractor is maximized. A generalization of the knapsack problem, called Knapsack-of-Knapsacks (K-of-K), is used to model this situation, in which items have to be packed into small knapsacks and small knapsacks have to be packed into a large knapsack. A fully polynomial time approximation scheme is developed to solve the problem K-of-K. Abstract : Highlights: We study a profit maximization constrained virtual business planning problem. A generalization of the knapsack problem called Knapsack-of-Knapsacks is used. We developed a fully polynomial time approximation scheme to solve this problem.