A Network Flow Algorithm for Solving Generalized Assignment Problem

The generalized assignment problem (GAP) is an open problem in which an integer <a:math xmlns:a="http://www.w3.org/1998/Math/MathML" id="M1"> <a:mi>k</a:mi> </a:math> is given and one wants to assign <c:math xmlns:c="http://www.w3.org/1998/Math/MathML" id="M2"> <c:msup> <c:mrow> <c:mi>k</c:mi> </c:mrow> <c:mrow> <c:mo>′</c:mo> </c:mrow> </c:msup> </c:math> agents to <e:math xmlns:e="http://www.w3.org/1998/Math/MathML" id="M3"> <e:mi>k</e:mi> <e:mfenced open="(" close=")" separators="|"> <e:mrow> <e:msup> <e:mrow> <e:mi>k</e:mi> </e:mrow> <e:mrow> <e:mo>′</e:mo> </e:mrow> </e:msup> <e:mo>≤</e:mo> <e:mi>k</e:mi> </e:mrow> </e:mfenced> </e:math> jobs such that the sum of the corresponding cost is minimal. Unlike the traditional <j:math xmlns:j="http://www.w3.org/1998/Math/MathML" id="M4"> <j:mi mathvariant="script">K</j:mi> </j:math> -cardinality assignment problem, a job can be assigned to many, but different, agents and an agent may undertake several, but different, jobs in our problem. A network model with a special structure of GAP is given and an algorithm for GAP is proposed. Meanwhile, some important properties of the GAP are given. Numerical experiments are implemented, and the results indicate that the proposed algorithm can globally and efficiently optimize the GAP with a large range cost.