Minimizing Makespan For Single Batch Processing Machine With Non-indentical Job Sizes Using Improved PSO Algorithms Based On The Clound Model Theory

The scheduling of a single batch-processing machine with non-identical job sizes, called two-dimensional scheduling problem considering constraints of both job sizes and machine capacity, is widely used in the real manufacturing as a new field of research in production scheduling. However, these new features cause high complexity and bring new challenges to the given problems. Thus, seeking the effective methods to solve the single batch-processing machine scheduling problem is of important practical significance.Particle Swarm Optimization is a new swarm intelligence algorithm. The advantages of particle swarm optimization including a simple structure, immediately accessible for practical applications, easy of implementation and robustness make its wide application in a variety of problems, but few for discrete optimization problems.The paper makes deep study on improving the property of the traditional particle swarm algorithm and the discrete particle swarm algorithm and focuses on their applications in the field of the single batch-processing machine scheduling problem. The main and pioneering works of this paper are as follows:(1)Research on the improved basic particle swarm algorithm optimization based on cloud model theory and its application in the problem of a single batch-processing machine with non-identical job sizes.Firstly, a new method for updating location and velocity is proposed.Sencondly, the particles are divided into three groups based on the fitness of every particle. An adaptive strategy for varying parameters of PSO based on cloud model theory is introduced, so different inertia weight generating methods are adopted in different groups.Thirdly, the improved hybrid PSO algorithm is used to minimize the makespan of a single batch-processing machine with non-identical job sizes.The comparative experiments shows that the adaptive algorithm is better than both GA and the traditional PSO algorithm.(2)Research on the improved discrete particle swarm algorithm optimization based on cloud model theory and its application in the problem of a single batch-processing machine with non-identical job sizes.The operators of the discrete PSO algorithm are redefined first for minimizing the makespan of a single batch-processing machine with non-identical job sizes.Then several qualitative association rules between the particle's"gathering"information and parameters are defined for constructing a new adaptive parameter strategy based on cloud model theory to adjust inertia weight and the diversity factor dynamically. Experimental results show that the improved discrete particle swarm algorithm optimization based on cloud model theory proposed in this chapter exhibited excellent performance for solving SBMN problems, especially in large scale problems; the quality of the algorithm is improved significantly.