Research On Parallel Machine Batch Scheduling Problem Using Ant Colony Optimization Algorithm

As a type of combinatorial optimization problems, production scheduling, with plentiful research results, has been widely applied in practice. Different from classical scheduling problem, more than one job can be processed on one single batching processing machine (BPM) at the same time. Any job only if satisfing the constraints can be processed on the BPM. Thus, the batching scheduling is closer to the practical production scheduling. It is of great significance to explore and investigate the batching scheduling problem deeply.Firstly, this paper briefly introduces the background and concepts associated with production scheduling problems, as well as the classification of scheduling problems. Then, the batching scheduling problem and those with additional constraints, such as non-identical job sizes and dynamic arrival jobs. The research status of these problems is also presented.Secondly, two prevalent approaches for batching scheduling and their characterstics are described, i.e., the deterministic method and the approximate method. Some typical algorithms and their frameworks among the two categories are briefly discussed next.Thirdly, the problem of minimizing the makespan for parallel BPMs with non-identical machine capacities, non-identical jobs sizes and machine eligibility restriction, an effective ant colony optimization (AC01) algorithm is proposed. After the assumptions being provided, the problem complexity is analyzed. A lower bound is given to evaluate the algorithm performance. Then, a Multifit-based heuristic and an ACO1-based meta-heuristic are presented respectively. According to the proved correlation between the wasted space of the solution and the objective, the wasted-space-based heuristic information is defined to guide the ants’ behavior. Meanwhile, a candidate set strategy for constructing the solution is adopted to narrow the search space. Additionally, to further enhance the solution quality, a local optimization approach is incorporated. Finally, the performance of the proposed algorithm is compared with the available algorithms by the computational experiments. The results demonstrate that the proposed ACO1 algorithm outperforms the other algorithms.Fourthly, to address the problem of minimizing the makespan for parallel BPMs with non-identical machine capacities, non-identical-size and unequal-arrival jobs and machine eligibility restriction, an effective ant colony optimization (ACO2) algorithm is proposed. Besides the key strategies used in the static batching scheduling, the ERT-sult is applied to sort the obtained batches on each matchine when building the solution, resulting in the reduction the impact of the job arrival times on the solution. Additionally, to further enhance the solution quality, a problem-oriented local optimization approach is incorporated. The performance of the proposed algorithm is also compared with the available algorithms by the computational experiments. The results demonstrate that the proposed AC02 algorithm outperforms the other algorithms.Finally, this paper summarizes batching scheduling problem studied in this paper, as well as the provided approaches.The research directions in future of the studied problems are then discussed.