《2016 A novel initialization method for solving flexible job-shop scheduling problem》.pdf

A novel initialization method for solving flexible job-shop scheduling problem 1 2 Shi Yang , Zhang Guohui, Gao Liang, Yuan Kun 1 The State Key Laboratory of Digital Manufacturing Equipment and Technology, Huazhong University of Science and Technology, 430074, China (gaoliang@mail.hust.edu.cn) 2 ENIM, Ile du Saulcy, F57045 Metz Cedex 1 ABSTRACT A novel initialization method was proposed for Genetic Algorithm (GA) to generate high-quality initialization population so as to solve Flexible Job-shop Scheduling Problem (FJSP). The novel initialization method consists of two sub-methods: Global Selection (GS) and Local Selection (LS). GS is used to find different initial assignments in different runs of the algorithm, and to enhance the capability of exploring search space considering the workload of all machines, while LS can find the shortest occupation time machine in alternative machine set of each job. To prove the efficiency of this initialization method, various benchmark data taken from the literature are tested, and the computation results show that this method can shorten the computational time and generate better results. Keywords: Genetic algorithm, Flexible job shop scheduling, Initialization 1. INTRODUCTION The research on initialization method is limited, so Scheduling is one of the most important issues in the essential research on the aspect