A Genetic Algorithm-Based Approach to Flexible Job-Shop Scheduling Problem

Flexible Job-shop Scheduling Problem (FJSP) is one of extremely hard problems because it requires very large combinatorial search space. Genetic algorithm is wildly used to solve Flexible Job-shop Scheduling Problem. This paper presents an improved genetic algorithm. The improved genetic algorithm we proposed uses many different strategies to get a better result. During the phase of create initial population, the improved genetic algorithm takes into account the number of operations in each job. And the intelligent mutation strategy is used which makes every individual and gene have different probability to mutate. In this paper, the object of scheduling algorithm is to get a sequence of the operations on machines to minimize the makespan. And the performance of the improved genetic algorithm is compared with another genetic algorithm. During the experiment, the two improvements are compared respectively with the compared genetic algorithm. The results show that the improved genetic algorithm outperforms the compared algorithm.

1. Introduction

Shop scheduling problem is a NP-hard problem. It is very hard to get a good result because it requires very large combinatorial search space. It is concerned with the determination of an optimal sequencing of operations on machines in order to minimize a given measure of performance, while taking into account constraints such as precedence, release dates, etc [1]. The F JSP is a generalization of the classical JSP. And it is more difficult than the classical JSP, because each job consists of a set of operations which must be processed in a right order that depends on the job. So, it introduces a further decision level besides the sequencing one, i.e., the job routes.