Article ID: | iaor20103413 |
Volume: | 1 |
Issue: | 1 |
Start Page Number: | 84 |
End Page Number: | 87 |
Publication Date: | Jun 2010 |
Journal: | Global Journal on Technology and Optimization |
Authors: | Rabinowitz Gad, Pinto Gaby, Israeli Uriel, Ainbinder Inessa |
Keywords: | heuristics: genetic algorithms |
In this paper we consider the resource-sharing and scheduling problem, with makespan minimization as an objective. Although this problem was optimally solved through a customized branch-and-bound algorithm, its complexity motivated the use of heuristics such as genetic algorithms. A previous genetic algorithm used for solving this problem was significantly faster than the branch-and-bound algorithm; however, it suffered from a high rate of infeasible offspring. We propose a new genetic approach, which produces only feasible offspring via a much more compact, genotype representation of the solution. While in the previous genetic algorithm the chromosome consisted of all the solution 0-1 variables (genotype=phenotype), in the new algorithm we define a much smaller chromosome (genotype) that stores sufficient information for efficiently generating a solution for the 0-1 variables (phenotype).