Research On Ant Conoly Optimization Algorithm For Scheduling Parallel Batch Processing Machines With Incompatible Job Families

Recently, the scheduling theories have been widely applied in industrial production. With the extending of its application, the problem is studied in different directions. From the initially traditional scheduling to the modern ones, the scheduling model has become more and more complicated. The different characters between the jobs are still the main study points, such as different job sizes (which generates the non-identical job size problem), grouping process (batch scheduling problem), different job families (incompatible job families problems), different job arrival times, delivery times (dynamic scheduling problem), and so on. Generally speaking, the more job features are considered in the problem, the more complicated the problem is. Moreover, the change of the processing environment will further complicate the problem.Research on the new-coming problems usually begins from the simpler environment, i.e., scheduling on the single machine. One reason is that scheduling on one single machine is easier to solve than the problem of more than one machine. The algorithms as well as the solutions of scheduling on one machine can used to help solve some more complicated problems. Additionally, scheduling on one single machine is widely applied in real life, and thus, the model of scheduling on one single machine can be abstracted from a lot of practical problems. Similarly, the studied problem in this thesis is solved based on the analysis of the batch scheduling problems on one single machine under different environments.In the first chapter, the batch scheduling problem with incompatible job families is abstracted from the production of the garment enterprises. Then, a common method of describing the scheduling problem is introduced, i.e., the three-parameter representation. The values of all the parameters and the classification of the scheduling problem are summarized. At last, the current research of batch scheduling with incompatible job families is surveyed.The second chapter enumerates some common scheduling problem objectives with the definitions. The polynomial-time algorithms and the heuristics that are often used to solve the corresponding problems are introduced.The third chapter lists the intelligent optimization algorithms to solve the scheduling problems. The key steps of the intelligent optimization algorithms are presented, together with a review of some literatures that have applied them to the scheduling problems.The forth chapter proposes an improved max-min ant system for the studied problem of minimizing the makespan. The flow of the algorithm and the definitions of its vital parameters are introduced in details. The appropriate values of the variables are determined through the preparative experiments. Then, the performance of our algorithm and some other algorithms, including RNRN, LFRN, LFLT and GA, is tested and compared. The results demonstrate the better performance of the proposed algorithm.At last, the whole thesis is concluded, and some possible future research directions are presented on my own view.