A Lagrangian based heuristic for a new class of assignment problem
In this paper, we address a new class of assignment problem arising from the slab production in steel industry. In this problem, items are assigned to knapsacks with the objective of maximizing profit. Comparing with the generalized assignment problem, a new kind of constraints, called flow constraints, are considered. This paper establishes an integer programming model and proposes a heuristic algorithm based on Lagrangian relaxation to solve it. In this algorithm, two relaxations are made: omitting the flow constraints is the first relaxation and relaxing the capacity constraints using Lagrangian multipliers to the objective function is the second one. The second relaxation problem could be decomposed into sub-problems, each for an item, and is solved to optimal by enumeration method. The feasible solutions to the original problems are obtained by adjusting the solutions to the relaxation problems and improved by local search. Numerical results show that designed heuristic based on Lagragian relaxation method provides satisfying assignments.
assignment problem flow constraints Lagrangian Relazation
Jia-xiang Luo Mei Zhang
Engineering Research Center for Precision Electronic Manufacture Equipments,Ministry of Education College of Automatic Science and Engineering,South China University of Technology,Guangzhou,China
国际会议
上海
英文
1706-1710
2009-11-20（万方平台首次上网日期，不代表论文的发表时间）