Flexible job shop scheduling using priority heuristics and genetic algorithm
In this research, flexible job shop scheduling problem has been studied. The aim of this research is to minimize the maximum completion time (makespan). The job shop scheduling is very common in practice and uniform machines (parallel machines with different speeds) have been used in job shop enviro...
Saved in:
| 主要作者: | |
|---|---|
| 格式: | Thesis |
| 语言: | English |
| 出版: |
2010
|
| 主题: | |
| 在线阅读: | http://psasir.upm.edu.my/id/eprint/41178/1/FK%202010%2083%20IR.pdf |
| 标签: |
添加标签
没有标签, 成为第一个标记此记录!
|
| id |
my-upm-ir.41178 |
|---|---|
| record_format |
uketd_dc |
| spelling |
my-upm-ir.411782015-10-28T09:15:18Z Flexible job shop scheduling using priority heuristics and genetic algorithm 2010-11 Farashahi, Hamid Ghaani In this research, flexible job shop scheduling problem has been studied. The aim of this research is to minimize the maximum completion time (makespan). The job shop scheduling is very common in practice and uniform machines (parallel machines with different speeds) have been used in job shop environment for flexibility. Flexible job shop scheduling consists of multistage which in each stage there are one or several parallel machines with different speeds. Each job crosses all these stages based on distinct routing which is fixed and known in advance. The relevant operation is processed by only one of the uniform machines in that stage. Due to Non-deterministic Polynomial-time hard (NP-hard) nature of problem, in order to generate good solution in a reasonable computation time two solution methodologies are proposed. In the first method, five heuristic procedures based on priority rules have been presented and the performances of proposed heuristics have been compared with each other in order to minimize the makespan. Experimental results over all instances indicated that the most work remaining rule with earliest completion time rule (MWKR-ECT) and earliest completion time rule (ECT) achieved the minimum of makespan up to 65% and 34% of all instances in comparison with other proposed heuristic procedures. In the next method, a genetic algorithm has been developed. It has been shown that proposed genetic algorithm with a reinforced initial population (GA2) has better efficiency compared to a proposed genetic algorithm with fully random initial population (GA0). Then, the validation of proposed genetic algorithm with reinforced initial population (GA2) has been checked with random keys genetic algorithm (RKGA). The results of computations showed that an improved rate of 27% has been achieved according to average of loss. Job shops Production scheduling - Mathematical models Genetic algorithms 2010-11 Thesis http://psasir.upm.edu.my/id/eprint/41178/ http://psasir.upm.edu.my/id/eprint/41178/1/FK%202010%2083%20IR.pdf application/pdf en public masters Universiti Putra Malaysia Job shops Production scheduling - Mathematical models Genetic algorithms |
| institution |
Universiti Putra Malaysia |
| collection |
PSAS Institutional Repository |
| language |
English |
| topic |
Job shops Production scheduling - Mathematical models Genetic algorithms |
| spellingShingle |
Job shops Production scheduling - Mathematical models Genetic algorithms Farashahi, Hamid Ghaani Flexible job shop scheduling using priority heuristics and genetic algorithm |
| description |
In this research, flexible job shop scheduling problem has been studied. The aim of this research is to minimize the maximum completion time (makespan). The job shop scheduling is very common in practice and uniform machines (parallel machines with different speeds) have been used in job shop environment for flexibility. Flexible job shop scheduling consists of multistage which in each stage there are one or several parallel machines with different speeds. Each job crosses all these stages based on distinct routing which is fixed and known in advance. The relevant operation is processed by only one of the uniform machines in that stage. Due to Non-deterministic Polynomial-time hard (NP-hard) nature of problem, in order to generate good solution in a reasonable computation time two solution methodologies are proposed. In the first method, five heuristic procedures based on priority rules have been presented and the performances of proposed heuristics have been compared with each other in order to minimize the makespan. Experimental results over all instances indicated that the most work remaining rule with earliest completion time rule (MWKR-ECT) and earliest completion time rule (ECT) achieved the minimum of makespan up to 65% and 34% of all instances in comparison with other proposed heuristic procedures. In the next method, a genetic algorithm has been developed. It has been shown that proposed genetic algorithm with a reinforced initial population (GA2) has better efficiency compared to a proposed genetic algorithm with fully random initial population (GA0). Then, the validation of proposed genetic algorithm with reinforced initial population (GA2) has been checked with random keys genetic algorithm (RKGA). The results of computations showed that an improved rate of 27% has been achieved according to average of loss. |
| format |
Thesis |
| qualification_level |
Master's degree |
| author |
Farashahi, Hamid Ghaani |
| author_facet |
Farashahi, Hamid Ghaani |
| author_sort |
Farashahi, Hamid Ghaani |
| title |
Flexible job shop scheduling using priority heuristics and genetic algorithm |
| title_short |
Flexible job shop scheduling using priority heuristics and genetic algorithm |
| title_full |
Flexible job shop scheduling using priority heuristics and genetic algorithm |
| title_fullStr |
Flexible job shop scheduling using priority heuristics and genetic algorithm |
| title_full_unstemmed |
Flexible job shop scheduling using priority heuristics and genetic algorithm |
| title_sort |
flexible job shop scheduling using priority heuristics and genetic algorithm |
| granting_institution |
Universiti Putra Malaysia |
| publishDate |
2010 |
| url |
http://psasir.upm.edu.my/id/eprint/41178/1/FK%202010%2083%20IR.pdf |
| _version_ |
1747811858695323648 |