Research On Unrelated Parallel Machine Scheduling Problems Based On Shuffled Frog Leaping Algorithm

The manufacturing industry is the foundation and support of China’s economic development,which directly reflects the country’s productivity level.Production scheduling plays a vital role in the production process of an enterprise.A reasonable scheduling scheme can help them to maximize the production efficiency by using the limited resources,so that the company has a strong market competitiveness.Parallel machine scheduling problem is a kind of decision-making optimization problem that widely exists in the actual manufacturing process.It refers to solving the distribution problem of jobs on different machines and determining the processing sequence of jobs on the machine by designing efficient optimization techniques to achieve the optimization of scheduling goals.In this thesis,unrelated parallel machine scheduling problems with two constraints of actual working conditions are studied.Two novel shuffled frog leaping algorithms are designed to solve the problems and the effectiveness of the algorithms are verified by simulation experiments.The primary contents of this thesis are listed below:(1)The research status of UPMSP at home and abroad and the application of the shuffled frog leaping algorithm in scheduling problems are summarized,and the problems and shortcomings of existing research are analyzed.Finally,the theory of parallel machine scheduling and several related intelligent optimization algorithms are described.(2)For UPMSP with deteriorating maintenance and setup time,a shuffled frog leaping algorithm with differentiation(DSFLA)is proposed to minimize makespan.The whole search procedure consists of two phases.In the second phase,all memeplexes are divided into good memeplexes and other ones,then the differentiated search processes are implemented between them.A new population shuffling is proposed.A large number of simulation experiments show that DSFLA has a great advantage in solving the considered problem.(3)For UPMSP with one additional resource and learning effect,a shuffled frog leaping algorithm with Q-learning(QSFLA)is presented to minimize makespan.A new solution presentation and decoding process are presented.Two populations are obtained by division.A Q-learning algorithm is constructed to dynamically decide search strategies in memeplex.In order to realize the Q-learning algorithm,twelve states are depicted by population quality and four actions are defined as search operators.Meanwhile,a new action selection and reward function are proposed.Compared with other algorithms by using entensive experiments,QSFLA has a stronger search advantage in solving the above UPMSP.