Research On Batch Scheduling Problem With Non-identical Job Sizes Using Ant Colony Clustering Algorithm

With the rapid development of the global economy, the competition between enterprises is increasingly fierce and intense, How to improve production efficiency, how to reasonably use the limited resources and cut down the production consumption has become the focus of social attention. However, the reasonable and fruitful scheduling can optimize enterprise resources, balance the configuration of various departments and bring about the maximization of resource utilization. So there is a widespread and great concern over the scheduling study in the community. At present, scheduling has a very wide application in arranging daily production, logistics and computer artificial intelligence,etc.Batch scheduling with non-identical job sizes is an important and vital extension of the traditional scheduling. The difference of the processing time and size of the job and also that the job sizes in the same batch cannot exceed the capacity of the machine are difficulties that may appear in batch scheduling with non-identical job sizes. And these difficulties are what makes it more complicated than batch scheduling with the same size jobs, but it is more close to the actual production status, so the research of this kind of problem has important and significant economic value and social effect.The first part of this thesis starts by introducing the basic and elementary knowledge of scheduling, including the introduction of the concept of scheduling problem and the parametric representation. And then the classical scheduling, the transition to a statement of the batch scheduling, This thesis also explains the difference between the classical scheduling and the batch scheduling. In the last part of this chapter introduces the batch scheduling with non-identical job sizes.In the second part of this thesis, a number of important and momentous types of algorithms for solving batch scheduling are described:the Mathematical Programming (Mathematical Programming), the Heuristic Algorithm (Heuristic Algorithm), the Genetic Algorithm (Genetic Algorithm), the Simulated Annealing Algorithm (Simulated Annealing), the Particle Swarm Optimization Algorithm(Particle Swarm Optimization), etc., In this part of thesis, the principle of different algorithms were also introduced in detail, and the solving process of the algorithm of solving the problem were listed.In the third part of the thesis,the fundamental and elementary knowledge of ant colony optimization algorithm (Ant Colony algorithm) has been proposed, which includes the principle of operation, the algorithm model, parameter setting, performance objectives and evaluation method, etc. Next, the background knowledge of Cluster Analysis (Cluster analysis) has been briefly introduced, which includes the definition, the clustering analysis method and measurement standard.This article inquires into single machine batch processing problem providing the number of jobs is m and equipment capacity of machine is B. Each job Ji (i=1,2,..., m) has the processing time pi and the size Si, which is different from each other. Every time a certain group of jobs are treated as one batch for processing, and the size of jobs in this batch do not exceed the capacity of the equipment. If a batch is ready for processing, before the end of the process, it is not permitted that the procedure can be suspended or new jobs are introduced into. The batch processing time is equal to the longest processing time of all the PCBs in the batch, and jobs in one batch have the same completion time. The ultimate goal of this paper is to minimize the makespan.The fourth part of this thesis discusses the Ant Colony Cluster Algorithm as the key to solve single batch-processing machine with non-identical job sizes. In order to solve the shortage of spending too long time on blindly searching by making use of the ant colony algorithm, this paper introduces clustering algorithm optimized by constructing a list of target candidates to make up for this deficiency, more precisely, the dissimilarity between jobs is based on the processing time and size of jobs, also jobs that have similar processing time and size will be in the same batch.Subsequently, taking advantage of ant colony distributed search feature to select the job, and then classify jobs into different batches according to the principal of achieving maximum utilization rate of batches.Since the ant colony algorithm is easy to fall into the local optimal solution and stop searching earlier, thus, this thesis introduces optimized algorithms for processing as the solution, and obtaines the local optimal solution ultimately. Bacause some parameters need to be set in advance of the application of ant colony algorithm, so this thesis obtains optimal settings by means of comparing a large quantity of data experiments. In addition, a great number of experiments data show that compared with several other intelligent algorithms, ant colony clustering algorithm has better performance.Finally, the summary of the whole paper and the prospects of the future research of this topic are given.