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...

Full description

Saved in:

Bibliographic Details
Main Author:	Farashahi, Hamid Ghaani
Format:	Thesis
Language:	English
Published:	2010
Subjects:	Job shops Production scheduling - Mathematical models Genetic algorithms
Online Access:	http://psasir.upm.edu.my/id/eprint/41178/1/FK%202010%2083%20IR.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

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

Flexible job shop scheduling using priority heuristics and genetic algorithm

Similar Items