Research On The Application Of Ant Colony Optimization Algorithm In Process Planning And Job Shop Scheduling

The integration and development of the new-generation information and manufacturing technology have nurtured new production methods and accelerated the intelligent transformation of the manufacturing industry.Manufacturing enterprises have increasing concerns about the improvement of production efficiency and product quality,and the reduction of costs in new market environments.Process planning and job shop scheduling,two important components of the manufacturing system,are usually NPhard,which makes it challenging to find a solution within a reasonable time.Hence,many approximation algorithms based on the features need to be developed for them.This dissertation discusses the applications of ant colony optimization algorithms to process planning and job shop scheduling,where the main content and innovations are as follows.First,the dissertation focuses on flexible process planning problems,considering three types of flexible features and the immediate precedence relationship between processes in actual production,and constructs an integer linear programming model with the minimization of time and cost as the objectives,respectively.In consideration of the immediate precedence relationship,the dissertation not only designs new process plan networks but also proposes a method for identifying and correcting network errors.By pheromone matrices in different stages of solution construction,the dissertation develops a multi-level pheromone ant colony optimization(MLP-ACO)algorithm to find a near-optimal solution.In 16 sets of experiments with different job types,the MLP-ACO significantly reduces the running time compared with CPLEX(a commercial optimizer).In addition,the MLP-ACO,compared with the hybrid evolutionary algorithm,reduces the average objective function value by 2%for the time objective and by 6%for the cost objective.Second,the dissertation investigates the application of ant colony optimization algorithm in the two-stage permutation flow shop batch scheduling problem,considering two types of features,namely,different job sizes and arbitrary release time,and establishes a mixed integer programming model with the objective of minimizing the makespan.In the proposed quantum-inspired ant colony optimization(QIACO)algorithm,ants are divided into two groups according to different batching strategies:one group selects the largest job in terms of job size as the initial job for each batch and the other group selects the smallest job as the initial job for each batch.In addition,the algorithm introduces a new local optimization rule to adjust the structure of the batch.The experiment comprises four sets of instances with different scales,and the results indicate that for large-scale instances,the QIACO performs an average objective function value improvement of 10%compared with the hybrid discrete differential evolution algorithm.Moreover,it not only achieves a 6%average objective function value improvement but also significantly reduces the runtime compared with ant colony optimization algorithm based on batch sequencing.For small-scale instances,the new local optimization rule significantly enhances the solution quality in the QIACO.Third,the dissertation further studies the application of ant colony optimization algorithms in integrated process planning and scheduling problem,considering two types of features:orders containing multiple varieties of repeatable job sets and process plan networks containing immediate precedence relationships.Six different ant colony optimization algorithms are designed based on three machine allocation rules and whether to use the adjustment rule based on immediate precedence relationships.In these six algorithms,ants are divided into two types:job ants and machine ants.Job ants correspond one-to-one with the jobs in the order and use their own pheromone matrix to select appropriate branches in process plan networks.After all job ants complete their tasks,machine ants generate scheduling sequences based on the pheromone matrix between processes and then assign the processes to machines based on different machine allocation rules.The experimental results show that the ant colony optimization algorithm combined with the earliest finish time rule obtains higher quality solutions in 22 sets of orders containing different flexible features,and that the adjustment rule based on the immediate precedence relationships improves the quality of the solution in most experiments.