The assignment problem with external interactions

✍ Scribed by Vander Wiel, Russ J.; Sahinidis, Nikolaos V.

• Publisher: John Wiley and Sons
• Year: 1997
• Tongue: English
• Weight: 205 KB
• Volume: 30
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/(sici)1097-0037(199710)30:3<171::aid-net3>3.0.co;2-i

✦ Synopsis

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 stateof-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.