Skip to main content



HCIL-2010-14

Huang, D., Lin, J.
Scaling Populations of a Genetic Algorithm for Job Shop Scheduling Problems using MapReduce
HCIL-2010-14

Inspired by Darwinian evolution, a genetic algorithm (GA) approach is one of the popular heuristic methods for solving hard problems, such as the Job Shop Scheduling Problem (JSSP), which is one of the hardest problems where there lacks efficient exact solutions. It is intuitive that the population size of a GA may greatly affect the quality of the solution, but it is unclear how a large population helps in finding good solutions. In this paper, a GA is implemented to scale the population using MapReduce, a framework running on a cluster of computers that aims to provide largescale data processing. The experiments are conducted on a cluster of 414 machines, and population sizes up to 107 are inspected. It is shown that larger population sizes not only tend to find better solutions, but also require fewer generations. It is clear that when dealing with a hard problem like JSSP, an existing GA can be improved by scaling up populations, whereby MapReduce can handle massive populations efficiently within reasonable time.



Graph Visualization Screenshot

Graph Visualization
More information

Tech Reports
Video Reports
Annual Symposium

News
Seminars + Events
Calendar
HCIL Seminar Series
Annual Symposium
HCIL Service Grants
Events Archives
Awards
HCIL Conference Travel Award
Job Openings
For the Press
HCIL Overview
Become a Member
Collaborators
Collaborating Groups + People
Academic Visitors
Join our Mailing List
Contact Us
Visit Us
HCIL Store
Give the HCIL a Hand
HCIL T-shirts for Sale
Our Lighter Side
HCIL Memories Page
Faculty/ Staff
Students
Ph.D. Alumni
Past Members
Research Areas
Communities
Design Process
Digital Libraries
Education
Physical Devices
Public Access
Visualization
Research Histories
Faculty Listed by Research
Project Highlights
Project Screenshots
Publications and TRs
Videos
Books
Products
Presentations
Studying HCI
Masters in HCI
PhD in HCI
Visiting Scholars
Class Websites
Sponsor our Research
Sponsor our Annual Symposium
Active Sponsorship
Industrial Visitors