A GA for the Resource Sharing and Scheduling ProblemGaby Pinto1*, Uriel Israelí2, Inessa Ainbinder3, Gad Rabinowitz3
- *Corresponding Author:
- Gaby Pinto
Department of Industrial Engineering and Management, Ben Gurion University of the Negev, Israel
E-mail: [email protected]
Received date: May 2008; Revised date: September 2008; Accepted date: March 2009
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-andbound 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).