An efficient solution to biobjective generalized assignment problem

作     者：Zhang, Cai Wen Ong, Hoon Liong 

作者机构：Natl Univ Singapore Dept Ind & Syst Engn Singapore 119260 Singapore 

出 版 物：《ADVANCES IN ENGINEERING SOFTWARE》 (工程软件进展)

年 卷 期：2007年第38卷第1期

页      面：50-58页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：epsilon-nondominated solution generalized assignment problem LP-based heuristic multiobjective integer programming 

摘      要：The generalized assignment problem (GAP) has found applications in many real world problems. In this paper, we examine the GAP from a multiobjective point of view to accommodate some real world situations where more than one objective is involved. An efficient LP-based heuristic is proposed to solve the biobjective generalized assignment problem (BiGAP). Extensive computational experiments are carried out to evaluate the performance of the proposed method. The results show that the proposed approach is able to generate good approximations to the nondominated frontier of the BiGAP efficiently, especially when the ratio of the number of items to the number of knapsacks is large. (C) 2006 Elsevier Ltd. All rights reserved.