Hybrid genetic algorithm with multi-parents recombination for job shop scheduling problems / Ong Chung Sin
Job Shop Scheduling Problem (JSSP) is one of the well-known hard combinatorial scheduling problems and one of the most computationally difficult combinatorial optimization problems considered to date. This intractability is one of the reasons why the problem has been so widely studied. The problem w...
| Main Author: | |
|---|---|
| Format: | Thesis |
| Published: |
2013
|
| Subjects: | |
| Online Access: | http://pendeta.um.edu.my/client/default/search/detailnonmodal/ent:$002f$002fSD_ILS$002f988$002fSD_ILS:988485/ada?qu=Hybrid+genetic+algorithm http://studentsrepo.um.edu.my/4177/1/ONG_CHUNG_SIN_SGP110004.pdf |
| _version_ | 1848772582540574720 |
|---|---|
| author | Ong, Chung Sin |
| author_facet | Ong, Chung Sin |
| author_sort | Ong, Chung Sin |
| building | UM Research Repository |
| collection | Online Access |
| description | Job Shop Scheduling Problem (JSSP) is one of the well-known hard combinatorial scheduling problems and one of the most computationally difficult combinatorial optimization problems considered to date. This intractability is one of the reasons why the problem has been so widely studied. The problem was initially tackled by “exact methods” such as the branch and bound method, which is based on the
exhaustive enumeration of a restricted region of solutions containing exact optimal solutions. Exact methods are theoretically important and have been successfully applied
to benchmark problems, but sometimes they, in general are very time consuming even for moderate-scale problems. Metaheuristic is one of the “approximation methods” that
is able to find practically acceptable solutions especially for large-scale problems within a limited amount of time. Genetic Algorithms (GA) which is based on biological
evolution is one of the metaheuristics that has been successfully applied to JSSP. In this study an indirect representation incorporating a schedule builder that
performs a simple local search to decode the chromosome into legal schedule called active schedule is proposed. The chromosomes are decoded into active schedules thus
increasing the probability of obtaining near or optimal solution significantly. Crossover between two parents is traditionally adopted in GA while multiparents
crossover (more than two parents) technique is still lacking. This research proposes extended precedence preservative crossover (EPPX) which uses multi-parents
for recombination in the GA. This crossover operator attempts to recombine the good features in the multi-parents into a single offspring with the hope that the offspring iv fitness is better than all its parents. EPPX can be suitably modified and implemented
with, in principal, unlimited number of parents.
JSSP generates a huge search space. An iterative forward-backward pass which reduces search space has been shown to produce significant improvement in reducing
makespan in other field of scheduling problem. The iterative forward-backward pass is applied on the schedules generated to rearrange their operation sequences to seek
possible improvements in minimizing the total makespan.
Reduction of the search space does not guarantee the optimal solution will be found. Therefore, a neighborhood search is embedded in the structure of GA and it acts
as intensification mechanism that exploits a potential solution. This mechanism is restricted to search the possible solutions in a critical path. Modification on the path by using neighborhood search significantly reduces the total length of the makespan. The hybrid GA is tested on a set of benchmarks problems selected from
literatures and compared with other approaches to ensure the sustainability of the proposed method in solving JSSP. The new proposed hybrid GA is able to produce 10
better or comparable solutions when compared to similar GA algorithms that employ two-parent crossover. In general this algorithm produces less than 6% deviation when
compared to the best known solutions, especially in larger problems consisting of 20 jobs and 15 machines. |
| first_indexed | 2025-11-14T13:28:48Z |
| format | Thesis |
| id | um-4177 |
| institution | University Malaya |
| institution_category | Local University |
| last_indexed | 2025-11-14T13:28:48Z |
| publishDate | 2013 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | um-41772014-09-26T01:40:41Z Hybrid genetic algorithm with multi-parents recombination for job shop scheduling problems / Ong Chung Sin Ong, Chung Sin Q Science (General) QA Mathematics Job Shop Scheduling Problem (JSSP) is one of the well-known hard combinatorial scheduling problems and one of the most computationally difficult combinatorial optimization problems considered to date. This intractability is one of the reasons why the problem has been so widely studied. The problem was initially tackled by “exact methods” such as the branch and bound method, which is based on the exhaustive enumeration of a restricted region of solutions containing exact optimal solutions. Exact methods are theoretically important and have been successfully applied to benchmark problems, but sometimes they, in general are very time consuming even for moderate-scale problems. Metaheuristic is one of the “approximation methods” that is able to find practically acceptable solutions especially for large-scale problems within a limited amount of time. Genetic Algorithms (GA) which is based on biological evolution is one of the metaheuristics that has been successfully applied to JSSP. In this study an indirect representation incorporating a schedule builder that performs a simple local search to decode the chromosome into legal schedule called active schedule is proposed. The chromosomes are decoded into active schedules thus increasing the probability of obtaining near or optimal solution significantly. Crossover between two parents is traditionally adopted in GA while multiparents crossover (more than two parents) technique is still lacking. This research proposes extended precedence preservative crossover (EPPX) which uses multi-parents for recombination in the GA. This crossover operator attempts to recombine the good features in the multi-parents into a single offspring with the hope that the offspring iv fitness is better than all its parents. EPPX can be suitably modified and implemented with, in principal, unlimited number of parents. JSSP generates a huge search space. An iterative forward-backward pass which reduces search space has been shown to produce significant improvement in reducing makespan in other field of scheduling problem. The iterative forward-backward pass is applied on the schedules generated to rearrange their operation sequences to seek possible improvements in minimizing the total makespan. Reduction of the search space does not guarantee the optimal solution will be found. Therefore, a neighborhood search is embedded in the structure of GA and it acts as intensification mechanism that exploits a potential solution. This mechanism is restricted to search the possible solutions in a critical path. Modification on the path by using neighborhood search significantly reduces the total length of the makespan. The hybrid GA is tested on a set of benchmarks problems selected from literatures and compared with other approaches to ensure the sustainability of the proposed method in solving JSSP. The new proposed hybrid GA is able to produce 10 better or comparable solutions when compared to similar GA algorithms that employ two-parent crossover. In general this algorithm produces less than 6% deviation when compared to the best known solutions, especially in larger problems consisting of 20 jobs and 15 machines. 2013 Thesis NonPeerReviewed application/pdf http://studentsrepo.um.edu.my/4177/1/ONG_CHUNG_SIN_SGP110004.pdf http://pendeta.um.edu.my/client/default/search/detailnonmodal/ent:$002f$002fSD_ILS$002f988$002fSD_ILS:988485/ada?qu=Hybrid+genetic+algorithm Ong, Chung Sin (2013) Hybrid genetic algorithm with multi-parents recombination for job shop scheduling problems / Ong Chung Sin. Masters thesis, University of Malaya. http://studentsrepo.um.edu.my/4177/ |
| spellingShingle | Q Science (General) QA Mathematics Ong, Chung Sin Hybrid genetic algorithm with multi-parents recombination for job shop scheduling problems / Ong Chung Sin |
| title | Hybrid genetic algorithm with multi-parents recombination for job shop scheduling problems / Ong Chung Sin |
| title_full | Hybrid genetic algorithm with multi-parents recombination for job shop scheduling problems / Ong Chung Sin |
| title_fullStr | Hybrid genetic algorithm with multi-parents recombination for job shop scheduling problems / Ong Chung Sin |
| title_full_unstemmed | Hybrid genetic algorithm with multi-parents recombination for job shop scheduling problems / Ong Chung Sin |
| title_short | Hybrid genetic algorithm with multi-parents recombination for job shop scheduling problems / Ong Chung Sin |
| title_sort | hybrid genetic algorithm with multi-parents recombination for job shop scheduling problems / ong chung sin |
| topic | Q Science (General) QA Mathematics |
| url | http://pendeta.um.edu.my/client/default/search/detailnonmodal/ent:$002f$002fSD_ILS$002f988$002fSD_ILS:988485/ada?qu=Hybrid+genetic+algorithm http://pendeta.um.edu.my/client/default/search/detailnonmodal/ent:$002f$002fSD_ILS$002f988$002fSD_ILS:988485/ada?qu=Hybrid+genetic+algorithm http://studentsrepo.um.edu.my/4177/1/ONG_CHUNG_SIN_SGP110004.pdf |