Journal
COMPUTERS & OPERATIONS RESEARCH
Volume 35, Issue 9, Pages 2892-2907Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2007.01.001
Keywords
flexible job shop scheduling; genetic algorithms; variable neighborhood descent; critical path
Ask authors/readers for more resources
This paper addresses the flexible job shop scheduling problem (fJSP) with three objectives: min makespan, min maximal machine workload and ruin total workload. We developed a hybrid genetic algorithm (GA) for the problem. The GA uses two vectors to represent solutions. Advanced crossover and mutation operators are used to adapt to the special chromosome structure and the characteristics of the problem. In order to strengthen the search ability, individuals of GA are first improved by a variable neighborhood descent (VND), which involves two local search procedures: local search of moving one operation and local search of moving two operations. Moving an operation is to delete the operation, find an assignable time interval for it, and allocate it in the assignable interval. We developed an efficient method to find assignable time intervals for the deleted operations based on the concept of earliest and latest event time. The local optima of moving one operation are further improved by moving two operations simultaneously. An extensive computational study on 181 benchmark problems shows the performance of our approach. (c) 2007 Published by Elsevier Ltd.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available