Adlino Vital Afonso

Shridhar Mhalsekar

Do Rosario E Souza Jacqueline

Abstract

Every organizations objective is to maximize its profit or minimize their costs incurred on the resources. One of the immediate opportunity is in the Assignment problem, which involves assignment of right task to a right agent, that is assigning a job to a machine or to a worker in order to minimize the cost of performing the job on that machine (or by the worker). This is a standardize Assignment problem.When constraints are taken into consideration, that is, when the agents are assumed to have a limited capacity, we have the Generalised assignment problem. Generalised assignment problem is a well-known NP-hard combinatorial problem. The objective is to find the maximum profit or minimum cost of assignment of n jobs to m agents such that each job is assigned to exactly one agent for utilizing the resources offered by the agent but not exceeding its capacity. On the basis of dominant principle technique an Arbitrage method is developed for solving Generalised Assignment Problem. The algorithm used in this method can obtain the optimal solution in minimum computational time. Simulation of the method for solving the generalised assignment model was done using MATLAB. The proposed method is then applied to problems defined as per open source standard OR library available for Generalised Assignment Problem. These solutions were compared with the important standard heuristics. The simulation of generalised assignment problem using MATLAB gives near optimal solutions for small sized problems and an optimal solution for large sized problems defined in standard 0R library.

Keywords- Generalised Assignment Problem, Simulation, Arbitrage, Optimal Solution, Dominant Principle, Heuristics.