Adapting the Jonker-Volgenant algorithm for the linear assignment problem with interval costs
The Linear Assignment Problem (LAP) is one of the most studied problems in linear programming. It is typically illustrated by assigning workers to tasks, with the objective of minimizing the total time required to complete all tasks. One of the most used algorithms to solve the LAP is the Jonker-Volgenant algorithm, originally designed to handle with costs represented by real values. However, uncertainty and imprecision in task completion times or total costs are common in such problems. To address these issues, intervals offer a flexible and effective solution.
In this work, the Jonker-Volgenant algorithm is adapted to solve the LAP with interval costs. During the execution of the algorithm, the order proposed by Xu and Yager is used for the minimum search, and addition and subtraction operations inspired by the uniform distribution are proposed.
Keywords: Linear Assignment Problem Jonker-Volgenant Interval Cost Interval Order.