A hybrid parallel genetic algorithm for solving job-shop scheduling problems

The effort of searching an optimal solution for scheduling problems is important for real-world industrial applications especially for mission-time critical systems. In such an environment, an optimal result should be obtained within a relatively reasonable time. Genetic algorithms (GA) have long be...

Full description

Saved in:
Bibliographic Details
Main Author: Gan, Teck Hui
Format: Thesis
Language:English
Published: 2005
Subjects:
Online Access:http://eprints.utm.my/id/eprint/34719/1/GanTeckHuiMFKE2005.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
id my-utm-ep.34719
record_format uketd_dc
spelling my-utm-ep.347192017-10-11T04:41:54Z A hybrid parallel genetic algorithm for solving job-shop scheduling problems 2005 Gan, Teck Hui Unspecified The effort of searching an optimal solution for scheduling problems is important for real-world industrial applications especially for mission-time critical systems. In such an environment, an optimal result should be obtained within a relatively reasonable time. Genetic algorithms (GA) have long been applied to the many scheduling problems especially for solving job shop scheduling problems. However there are several problems when implementing GA into job shop scheduling problem (JSSP) such as slow and premature convergence. GA on one single personal computer is very time consuming while harder problems need bigger population and this has translate directly into higher computational costs. Therefore, this research proposes a different approach in solving JSSP using GA. Instead of conventional approach of using “serial” GA on a single PC, this research looks into the possibility of using parallel and distributed computing techniques and parallel genetic algorithm (PGA) in solving the same problems. Island model is chosen in this research to suit the implementation of distributed computing environment. The proposed PGA is a combination of both Asynchronous Colony Genetic Algorithm (ACGA) and Autonomous Immigration Genetic Algorithm (AIGA). This hybrid PGA is originally applied to symmetric multiprocessor machine (SMP) by Haruki Inoue. This type of modeling of PGA is based on the biologically reported observation that isolated environments, such as islands, often produce animal species that are more specifically adapted to the peculiarities of their environments than corresponding areas of wider surfaces. This theory also led to the hypothesis that several competing subpopulations could be more search-effective than a wider one in which all the members are held together. Each “island” is a different type of serial GA which represents one PC. Each island is using a combination of different crossover operator (GOX, Giffler and Thompson (GT) Crossover) and selection method (random selection, roulette wheel selection) into different types of serial GA. Every “island” has a certain convergence point where the improvement of the population fitness is almost stagnant. Therefore to solve this kind of undesired situation; a more sophisticated idea is used in this coarse grained PGA. This model of parallelization introduces a migration operator that is used to send some individual from one “island” to another “island”. The individual can migrate to any other “island” at their own judgment. Communication overhead during migration process is reduced by implementing a global mailbox method. Results show that PGA with a combination of different types of GA that creates a partially isolated environment for each sub demes, allowing a wider and more effective search, has outperformed PGA with a single type of GA. This research does not consider network topology in the scope as the system is linked via office network. To further improve the robustness of the system in the future, functions such as process migration and parallel input/output - by migrating intensive I/O processes to file servers (rather than the traditional way of bringing data to the processes) should be developed. 2005 Thesis http://eprints.utm.my/id/eprint/34719/ http://eprints.utm.my/id/eprint/34719/1/GanTeckHuiMFKE2005.pdf application/pdf en public http://dms.library.utm.my:8080/vital/access/manager/Repository/vital:61226?queryType=vitalDismax&query=A+hybrid+parallel+genetic+algorithm+for+solving+job-shop+scheduling+problems&public=true masters Universiti Teknologi Malaysia, Faculty of Electrical Engineering Faculty of Electrical Engineering
institution Universiti Teknologi Malaysia
collection UTM Institutional Repository
language English
topic Unspecified
spellingShingle Unspecified
Gan, Teck Hui
A hybrid parallel genetic algorithm for solving job-shop scheduling problems
description The effort of searching an optimal solution for scheduling problems is important for real-world industrial applications especially for mission-time critical systems. In such an environment, an optimal result should be obtained within a relatively reasonable time. Genetic algorithms (GA) have long been applied to the many scheduling problems especially for solving job shop scheduling problems. However there are several problems when implementing GA into job shop scheduling problem (JSSP) such as slow and premature convergence. GA on one single personal computer is very time consuming while harder problems need bigger population and this has translate directly into higher computational costs. Therefore, this research proposes a different approach in solving JSSP using GA. Instead of conventional approach of using “serial” GA on a single PC, this research looks into the possibility of using parallel and distributed computing techniques and parallel genetic algorithm (PGA) in solving the same problems. Island model is chosen in this research to suit the implementation of distributed computing environment. The proposed PGA is a combination of both Asynchronous Colony Genetic Algorithm (ACGA) and Autonomous Immigration Genetic Algorithm (AIGA). This hybrid PGA is originally applied to symmetric multiprocessor machine (SMP) by Haruki Inoue. This type of modeling of PGA is based on the biologically reported observation that isolated environments, such as islands, often produce animal species that are more specifically adapted to the peculiarities of their environments than corresponding areas of wider surfaces. This theory also led to the hypothesis that several competing subpopulations could be more search-effective than a wider one in which all the members are held together. Each “island” is a different type of serial GA which represents one PC. Each island is using a combination of different crossover operator (GOX, Giffler and Thompson (GT) Crossover) and selection method (random selection, roulette wheel selection) into different types of serial GA. Every “island” has a certain convergence point where the improvement of the population fitness is almost stagnant. Therefore to solve this kind of undesired situation; a more sophisticated idea is used in this coarse grained PGA. This model of parallelization introduces a migration operator that is used to send some individual from one “island” to another “island”. The individual can migrate to any other “island” at their own judgment. Communication overhead during migration process is reduced by implementing a global mailbox method. Results show that PGA with a combination of different types of GA that creates a partially isolated environment for each sub demes, allowing a wider and more effective search, has outperformed PGA with a single type of GA. This research does not consider network topology in the scope as the system is linked via office network. To further improve the robustness of the system in the future, functions such as process migration and parallel input/output - by migrating intensive I/O processes to file servers (rather than the traditional way of bringing data to the processes) should be developed.
format Thesis
qualification_level Master's degree
author Gan, Teck Hui
author_facet Gan, Teck Hui
author_sort Gan, Teck Hui
title A hybrid parallel genetic algorithm for solving job-shop scheduling problems
title_short A hybrid parallel genetic algorithm for solving job-shop scheduling problems
title_full A hybrid parallel genetic algorithm for solving job-shop scheduling problems
title_fullStr A hybrid parallel genetic algorithm for solving job-shop scheduling problems
title_full_unstemmed A hybrid parallel genetic algorithm for solving job-shop scheduling problems
title_sort hybrid parallel genetic algorithm for solving job-shop scheduling problems
granting_institution Universiti Teknologi Malaysia, Faculty of Electrical Engineering
granting_department Faculty of Electrical Engineering
publishDate 2005
url http://eprints.utm.my/id/eprint/34719/1/GanTeckHuiMFKE2005.pdf
_version_ 1747816239793700864