Scheduling jobs and maintenances in flexible job shop with a hybrid genetic algorithm |
| |
Authors: | Jie Gao Mitsuo Gen Linyan Sun |
| |
Affiliation: | (1) School of Management, Xi’an Jiaotong University, Xi’an, 710049, China;(2) Graduate School of Information, Production and Systems, Waseda University, Kitakyushu 808-0135, Japan |
| |
Abstract: | Most flexible job shop scheduling models assume that the machines are available all of the time. However, in most realistic
situations, machines may be unavailable due to maintenances, pre-schedules and so on. In this paper, we study the flexible
job shop scheduling problem with availability constraints. The availability constraints are non-fixed in that the completion
time of the maintenance tasks is not fixed and has to be determined during the scheduling procedure. We then propose a hybrid
genetic algorithm to solve the flexible job shop scheduling problem with non-fixed availability constraints (fJSP-nfa). The
genetic algorithm uses an innovative representation method and applies genetic operations in phenotype space in order to enhance
the inheritability. We also define two kinds of neighbourhood for the problem based on the concept of critical path. A local
search procedure is then integrated under the framework of the genetic algorithm. Representative flexible job shop scheduling
benchmark problems and fJSP-nfa problems are solved in order to test the effectiveness and efficiency of the suggested methodology.
Received: June 2005 /Accepted: December 2005 |
| |
Keywords: | Flexible job shop scheduling Availability constraints Genetic algorithm Local search Critical path Maintenance scheduling |
本文献已被 SpringerLink 等数据库收录! |
|