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

Scheduling is one of the important combinatorial optimization problems, and is widely applied in fields such as manufacturing, modern logistics, network communication, computer science and so on. Batch scheduling is an extension of the classical scheduling problem. The machine in batch scheduling problem can simultaneously process multiple jobs. Batch scheduling problem is to schedule the jobs with non-identical job sizes and non-identical processing times on batch processing machines, which is closer to reality than the batch scheduling with identical job sizes and thus more complex. Therefore, it has more research value and application prospects to study this problem.This thesis firstly introduces the application background, problem expression and classification, and current research status. Then the relative concepts of batch scheduling problem and the differences between the classical scheduling and batch scheduling are depicted, as well as the studied batch scheduling problem with non-identical job sizes.Secondly, several types of algorithms for batch scheduling problem are introduced, including mathematical programming, heuristics and meta-heuristics, and examples are given to each type of these algorithms. Specifically, the FFLPT, BFLPT and other classical heuristics and the intelligent batch scheduling algorithms based on genetic algorithm, simulated annealing and so on.Next, the classical ant colony system (ACS) algorithm is introduced in detail, including the origin, the basic principles, the algorithm model and flow, the method of performance evaluation. The advantages and disadvantages of ACS is also analyzed. Additionally, the max-min ant colony algorithm (MMAS) is introduced.Then, to minimize the makespan for single machine batch scheduling problem with non-identical job sizes, an improved max-min ant system algorithm is proposed. By converting the objective to minimizing the wasted space, a candidate set strategy is used to construct the batches. Besides applying a wasted-space based heuristic to update the pheromone, a local optimization strategy is adopted to further improve the performance of the proposed algorithm. Then the appropriate values of the parameters are determined by a number of comparative experiments. The simulation results show that the proposed algorithm outperforms several other existing algorithms.Finally, the overall work and the future research directions are given.