Scaling Populations of a Genetic Algorithm for Job Shop Scheduling Problems Using MapReduce

Inspired by Darwinian evolution, a genetic algorithm (GA) approach is one popular heuristic method for solving hard problems such as the Job Shop Scheduling Problem (JSSP), which is one of the hardest problems lacking efficient exact solutions today. It is intuitive that the population size of a GA may greatly affect the quality of the solution, but it is unclear what are the effects of having population sizes that are significantly greater than typical experiments. The emergence of MapReduce, a framework running on a cluster of computers that aims to provide large-scale data processing, offers great opportunities to investigate this issue. In this paper, a GA is implemented to scale the population using MapReduce. Experiments are conducted on a large cluster, and population sizes up to 10⁷ are inspected. It is shown that larger population sizes not only tend to yield better solutions, but also require fewer generations. Therefore, it is clear that when dealing with a hard problem such as JSSP, an existing GA can be improved by massively scaling up populations with MapReduce, so that the solution can be parallelized and completed in reasonable time.