Research On A Single Batch Processing Machine With Non-identical Job Sizes Using A Neighborhood Search Algorithm

Scheduling is one of the most important combinatorial optimization problems. It is very important in industrial production, manufacturing systems and other fields. A reasonable scheduling scheme can improve production efficiency and reduce production costs,so the research on it has important practical significant.Batch scheduling is an important branch of scheduling problems. Different from the classical ones, a number of jobs can be processed simultaneously by a batch machine. Batch scheduling problem with non-identical jobs sizes (NSBM), in which the jobs are non-identical in size and the total size of the jobs in a batch cannot exceed the capacity of the machine, is an extension of batch scheduling problem.Neighborhood search algorithm is significant method of solving combinatorial optimization problems. Running as evolution in the solution space, it is simple, generic and robust. A novel algorithm called Free Search (FS) is firstly applied to solve the scheduling problems on NSBM in this paper. The main work is as follows: First, solving the problem based on the sequence of jobs. FS is used to search a superior jobs'sequence, then batching according to heuristic rules. A coding approach with vectors is designed due to the discrete of scheduling problems. A heuristic was then combined with FS and then an algorithm based on the sequence of jobs is constructed. By the features of NSBM, the pheromone in the model is redefined and three different values of radius are set to avoid premature convergence. Experiments show that FS is better than the previous method.Secondly, solving the problem based on the sequence of batches. Batching directly, and then optimizing the sequence of batches by an algorithm. The results of the method based on the sequence of jobs will be affected by the heuristic algorithms. If the heuristic algorithms perform not well, the improvement of results based on the optimization of the sequence of jobs. Even the space is shrinking by that method and it isn't conducive to search a better solution. A Hybrid Neighborhood Search is proposed to solve NSBM. In order to avoid stagnation of FS, we apply Differential Evolution and local optimal strategy to modify the algorithm. At last, cusp catastrophe theory is used as elitist reserving mechanism. Computational results are presented to show the better search ability of the algorithm, and testify the validity of HNS. Finally, sum up the thesis, and give some further ideas and future research prospects.