Research On Optimization Algorithms For Single Machine Batch Scheduling Under Uncertainty

Production scheduling is the kernel of management in modern enterprisesbecause it plays the important role in manufacturing systems for running theproductive process efficiently. Effective optimization technology and productionscheduling method could be used to decrease the cost of production, reduce wasteand further to strengthen competitiveness of the enterprise. The practical schedulingproblems are kinds of combinatorial optimization problems with dynamic nature andmultiple constraints, which have been proved to be NP-hard. So it is of highsignificance to develop reasonable methods for tackling the above problems intheory research and practical applications.As far as we know, most of existing researches on production scheduling aredeterministic. There are some shortcomings in the research of uncertain schedulingbased on recent literature. On the one hand, constraint conditions are less in most ofuncertain scheduling research. On the other hand, deterministic accurate solvingmethods are used to solve this kind of problems in most existing literature. Theresearch on uncertain batch scheduling is relative less. The main work of this thesisis as follows:(1) The single machine batch scheduling problem with the dynamic arrival ofjobs，different size of jobs, uncertainty of process time and due date is researched.The problem is expanded to fuzzy environment closer to the actual productioncondition. The single machine batch scheduling uncertain problem used the fuzzymathematical theory to build model, and designed encoding scheme based on jobpermutation, used partial strategies to improve the overall performance of thealgorithm.(2) The particle swarm optimization (PSO) algorithm is adopted to solve thesingle machine batch scheduling problem in uncertain environment, respectively. Wepresent non-linearity adaptation inertia weight factor to avoid the local optimum ofPSO and modify the self adaptive strategy. The performance of the proposedalgorithm is evaluated using experimental results.(3) The differential evolution (DE) algorithms are adopted to solve the singlemachine batch scheduling problem in uncertain environment, crossover operatorsbased on the parameter mating and self adaptive mutation based on alternativemutation method are put forwarded for the DE algorithm. The effectiveness of the proposed algorithms are verified by simulation experiments.(4) As PSO algorithm is easy to fall into local optimal problems, anddifferential evolution algorithm is a global search technique based on heuristicalgorithm. To optimize the single machine batch scheduling problem in uncertainenvironment better, the hybrid DEPSO algorithm is presented based on the improvedPSO and DE, which could keep the capability of PSO and DE in diversity,exploration and exploitation. The improved hybrid DEPSO algorithm is Applied toseveral instances and compared with some previous algorithms, which is clearlyoutperforms these comparative algorithms. Finally, concluded this paper as well asput forwarded the prospects of the uncertain scheduling problem.In this paper, there exists16figures,16tables and79references.