Generalized quadratic multiple knapsack problem and two solution approaches

被引:20
作者
Sarac, Tugba [1 ]
Sipahioglu, Aydin [1 ]
机构
[1] Eskisehir Osmangazi Univ, Dept Ind Engn, TR-26480 Meselik, Eskisehir, Turkey
关键词
Generalized Quadratic Multiple Knapsack; Problem (G-QMKP); F-MSG; Genetic Algorithm (GA); Production with plastic injection; Combinatorial optimization; GENETIC ALGORITHM; OPTIMIZATION;
D O I
10.1016/j.cor.2013.08.018
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
The Quadratic Knapsack Problem (QKP) is one of the well-known combinatorial optimization problems. If more than one knapsack exists, then the problem is called a Quadratic Multiple Knapsack Problem (QMKP). Recently, knapsack problems with setups have been considered in the literature. In these studies, when an item is assigned to a knapsack, its setup cost for the class also has to be accounted for in the knapsack. In this study, the QMKP with setups is generalized taking into account the setup constraint, assignment conditions and the knapsack preferences of the items. The developed model is called Generalized Quadratic Multiple Knapsack Problem (G-QMKP). Since the G-QMKP is an NP-hard problem, two different meta-heuristic solution approaches are offered for solving the G-QMKP. The first is a genetic algorithm (GA), and the second is a hybrid solution approach which combines a feasible value based modified subgradient (F-MSG) algorithm and GA. The performances of the proposed solution approaches are shown by using randomly generated test instances. In addition, a case study is realized in a plastic injection molding manufacturing company. It is shown that the proposed hybrid solution approach can be successfully used for assigning jobs to machines in production with plastic injection, and good solutions can be obtained in a reasonable time for a large scale real-life problem. (C) 2013 Elsevier Ltd. All rights reserved.
引用
收藏
页码:78 / 89
页数:12
相关论文
共 50 条
[41]   The Statement and Solution of the Knapsack Problem with Fuzzy Data [J].
Donets, G. A. ;
Yemets, A. O. .
JOURNAL OF AUTOMATION AND INFORMATION SCIENCES, 2009, 41 (09) :1-13
[42]   The fractional multidimensional knapsack problem: solution and uniqueness [J].
John Y. Zhu .
Economic Theory Bulletin, 2022, 10 :95-103
[43]   The fractional multidimensional knapsack problem: solution and uniqueness [J].
Zhu, John Y. .
ECONOMIC THEORY BULLETIN, 2022, 10 (01) :95-103
[44]   A genetic engineering algorithm for the generalized quadratic assignment problem [J].
Sohrabi, Majid ;
Fathollahi-Fard, Amir M. ;
Gromov, Vasilii A. ;
Dulebenets, Maxim A. .
Neural Computing and Applications, 2025, 37 (18) :12253-12279
[45]   METAHEURISTIC APPROACHES FOR THE QUADRATIC MINIMUM SPANNING TREE PROBLEM [J].
Palubeckis, Gintaras ;
Rubliauskas, Dalius ;
Targamadze, Aleksandras .
INFORMATION TECHNOLOGY AND CONTROL, 2010, 39 (04) :257-268
[46]   Improved Swap Heuristic for the Multiple Knapsack Problem [J].
Laalaoui, Yacine .
ADVANCES IN COMPUTATIONAL INTELLIGENCE, PT I, 2013, 7902 :547-555
[47]   VARIABLE FIXING METHOD BY WEIGHTED AVERAGE FOR THE CONTINUOUS QUADRATIC KNAPSACK PROBLEM [J].
Sun, Hsin-Min ;
Sun, Yu-Juan .
NUMERICAL ALGEBRA CONTROL AND OPTIMIZATION, 2022, 12 (01) :15-29
[48]   An algorithm for the generalized quadratic assignment problem [J].
Peter M. Hahn ;
Bum-Jin Kim ;
Monique Guignard ;
J. MacGregor Smith ;
Yi-Rong Zhu .
Computational Optimization and Applications, 2008, 40
[49]   An algorithm for the generalized quadratic assignment problem [J].
Hahn, Peter M. ;
Kim, Bum-Jin ;
Guignard, Monique ;
Smith, J. MacGregor ;
Zhu, Yi-Rong .
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2008, 40 (03) :351-372
[50]   Reduction approaches for a generalized line balancing problem [J].
Battaia, Olga ;
Dolgui, Alexandre .
COMPUTERS & OPERATIONS RESEARCH, 2012, 39 (10) :2337-2345