A genetic algorithm for the resource sharing and scheduling problem

A genetic algorithm for the resource sharing and scheduling problem

0.00 Avg rating0 Votes
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: , , ,
Keywords: heuristics: genetic algorithms
Abstract:

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).

Reviews

Required fields are marked *. Your email address will not be published.