Faculty of Technology Management
A new genetic algorithm tool for the multiple modes per operation, resource collaboration, and constrained scheduling problem (MRCCSP) and the resource sharing and scheduling problem (RSSP)
Dr. Gaby Pinto
30.3.2014 | 14:00 | Building 2, Room 105
This paper introduces for the first time a heuristic that is based on a genetic algorithm (GA) to solve the multiple modes per operation, resource collaboration, and constrained scheduling problem (MRCCSP), with makespan minimization as an objective. This work also shows how the new GA can solve the resource-sharing and scheduling problem (RSSP), which is a private case of the MRCCSP.
Although the problems were optimally solved through a customized branch and bound (B&B) algorithm, its complexity motivated the use of heuristics such as GAs. A previous GA used for solving the RSSP was significantly faster than the B&B algorithm and its truncated heuristics; however, due to the algorithms encoding it suffered from a high rate of infeasible offspring. This work proposes a new evolutionary tool, which produces only feasible offspring via a much more compact way for genotype encoding.
While in the previous GA the DNA consisted of all the solution 0-1 variables (genotype=phenotype), in the current algorithm a much smaller DNA (genotype) that stores sufficient information for efficiently generating a phenotype was define. Also, a customized Bellman-Ford algorithm replaces the Lindo API software that was used in the previous GA.
The new tool was developed over several years by a number of student teams from: Holon Institute of Technology (department of technology management), Ben-Gurion University (software engineering and industrial engineering and management departments), Azrieli Jerusalem Collage of Engineering (software engineering).
Key words: genetic algorithm, resource-sharing and scheduling problem, Bellman-Ford algorithm