A Lagrangian based heuristic for a new class of assignment problem

作者：Luo Jia xiang^*; Zhang Mei

来源：IEEE International Conference on Intelligent Computing and Intelligent Systems, Shanghai, 2009-11-20 To 2009-11-22.

DOI：10.1109/ICICISYS.2009.5358263

• assignment problem flow constraints
• Lagrangian Relaxation

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

• 出版日期2009
• 单位华南理工大学