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

Preview PDF FK 2010 83 IR.pdf Download (667kB) | Preview

Actions (login required)

View Item