Research On Algorithms For Scheduling Single Batch-processing Machine With Non-identical Job Sizes

The scheduling of a single batch-processing machine with non-identical job sizes is widely used in the real manufacturing and the problems of this kind are integrated with the characteristics of the classical scheduling and the batch scheduling.The problems of minimizing the makespan and the weighted completion time of a single machine are respectively strongly NP-hard and NP-hard.The optimization of a single batch-processing machine with non-identical job sizes has an influence on the industry and theoretical research.In this paper,intelligent algorithms are applied to solve the problems on a single batch-processing machine with non-identical job sizes and then,the deterministic problems are extended to fuzzy environment and algorithms are designed for the optimization of the fuzzy problems.The main innovations of this paper are listed as follows.(1) The ant colony optimization(ACO) method is studied and designed for a single batch-processing machine with non-identical job sizes(NSBM).The coding and decoding mechanism of ACO is improved and in order to conquer the local optimum of ACO,the Metropolis criterion is adopted as the selection method of the paths to solve the problem.The simulation results demonstrate the efficiency of the algorithm.Additionally,the chaotic optimizer is introduced to improve the quality of ACO.(2) The particle swarm optimization method(PSO) is applied to NSBM.Firstly the coding approach is designed and then the particles are sequenced using the priority value vectors which make PSO appropriate for the discrete optimization problem.In the decoding section,the feasible solutions are produced with batch scheduling mechanism.(3) DNA evolutionary algorithm(DEA) is applied to the problem.The operators of division,level selection,mutation and vertical selection are introduced.DEA has a simple implementation and an outstanding time performance.Additionally,the vertical selection operator is improved by integrating a random selection method. An effective global optimization is achieved by jumping from the local optimum. The numerical results demonstrate the efficiency of DEA.(4) The NSBM in fuzzy manufacturing system is studied in this paper.In the real industry,the uncertainty lies in two factors which consist of the processing time of the batches and the intemals between the batches.The NSBM is extended from the current ideal environment to fuzzy environment and the fuzzy model of minimizing the makespan is established.A hybrid algorithm based on different evolution(DE) and PSO is proposed for the optimization.The simulation results show the good performance of the method.