Penalty approaches for Assignment Problem with single side constraint via Genetic Algorithms

摘要

The goal of this article is to investigate the applicability of Genetic Algorithms (GAs) to solve Assignment Problem with Single Side Constraint (APSSC) due to either time restriction or budgetary restriction, etc. For this purpose, two different models of APSSC are formulated – one for deterministic cost/time parameters and another for imprecise cost/time parameters. To handle the side constraint in solving each of these models, two new optimization problems are formulated using two different penalty function techniques. Then the reduced problems are solved by using elitist genetic algorithm (EGA). This algorithm employs some new features on initialization, pair-wise careful comparison among feasible and infeasible solutions using tournament selection in conjunction with two heuristic operators one for making feasible solution from the infeasible one and the other for improving feasible solution. To illustrate the models, a set of test problems generated randomly are solved and the computational statistics of each model regarding objective function values, generations, computational times and number of objective function evaluations are compared.