Premium
The assignment problem with external interactions
Author(s) -
Vander Wiel Russ J.,
Sahinidis Nikolaos V.
Publication year - 1997
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199710)30:3<171::aid-net3>3.0.co;2-i
Subject(s) - assignment problem , initialization , heuristics , mathematical optimization , shortest path problem , computer science , flow network , algorithm , minimum cost flow problem , path (computing) , generalized assignment problem , set (abstract data type) , mathematics , theoretical computer science , graph , programming language
The classical assignment problem matches n jobs to n machines in a way that minimizes total assignment costs. To allow for the possibility of diverting internal jobs outside the machine shop and accepting external jobs into the machine shop, we define the assignment problem with external interactions (APEX) as a linear assignment problem with a single unrestricted arc. A feasible solution of APEX may involve up to twice as many assignments as an assignment problem of the same size. An efficient sequential shortest path algorithm is developed for APEX. The algorithm uses initialization heuristics to obtain a dual feasible solution that satisfies the complementary slackness conditions with a partial set of assignments. Primal feasibility is then obtained through a shortest augmenting path algorithm that makes the remaining assignments. As APEX can be formulated as a minimum‐cost network flow problem and as a standard assignment problem of larger size, we compare the proposed algorithm with state‐of‐the‐art network flow and assignment approaches. The algorithm developed here has much smaller storage requirements than have alternative approaches. In addition, extensive computational results demonstrate that it is from 2 to 52 times faster. © 1997 John Wiley & Sons, Inc. Networks 30:171–185, 1997