A Two-Stage Linear Assignment Problem

Abstract

Abstract

This research work proposes merging of uncertainties jobs-resources pair assignment with their corresponding risky cost to the linear assignment model. The two-stage model approach of Dantzig [3] was used, resulting in a class of stochastic linear assignment problem. The proposed model was tested by a state of the art software EXCEL/solver-Gurobi 2010 version. The sizes of the test problem increased until unsolvable cases were detected. Therefore, Bender’s decomposition method was applied and developed using MATLAB R2010b to solve these cases. The experimental result showed that the method is capable of expanding the size of the problem solving capabilities, especially when more than one-million decision variables are involved.

Keywords : A Stochastic Linear Assignment; Bender’s Decomposition Method; Uncertainties