A NOVEL ANT COLONY OPTIMIZATION BASED APPROACH FOR FLEXIBLE JOB-SHOP SCHEDULING PROBLEM WITH OPERATION AND PROCESSING FLEXIBILITY

摘要

This paper addresses the Flexible Job-shop Scheduling Problem with Operation and Processing flexibility (FJSP-OP), a practical case of the Integrated Process Planning and Scheduling (IPPS) problem. First, a Four-Tuple Scheme (FTS) is proposed to represent a job with operation and processing flexibility. Then, an Ant Colony Optimization (ACO) based approach is developed for solving the problem. In this approach, more efficient algorithms of path generation, incorporated with the FTS, are designed. Catering for the characteristic of the FJSP-OP that not all operations of all jobs need to be processed, we introduce a new type of pheromone, i.e., pheromone on nodes, which reinforces the learning search experience of a single node. To improve performance, the pheromone update strategy and the search strategy are modified. Computational experiments with different sizes are conducted and comparisons of results show that the proposed approach achieves significant improvements.