Research On Unrelated Parallel Machine Scheduling Algorithm Based On Intelligent Optimization

The Unrelated Parallel Machine Scheduling Problem(UPMSP)is the most common shop job scheduling problem in modern industrial production and widely used in communication equipment manufacturing,kiln calcination manufacturing,textile manufacturing and other industrial activities.Without considering other constraints,the UPMSP usually requires assigning a limited number of jobs to a limited number of machines,and ensuring that the objectives are optimal.However,numerous additional considerations need to be considered in real-life production,such as the possibility of machine disruptions,allocation of scarce resources,setup times and many others,which make the problem more complex.Traditional commercial solvers and exact algorithms usually have high computational time when solving UPMSP.Heuristic algorithms are usually efficient,but they can not avoid local optima.Besides,the structure of the neighborhood and the parameters setting of the algorithm could also affect the quality of the solutions.In order to solve the problems exsited of heuristic algorithms,an adaptive large neighborhood search with learning automata(LA-ALNS)is proposed and successfully applied to solve UPMSP.Although LA-ALNS can improve the quality of the solution to a certain extent,its search efficiency is heavily affected by revisiting the previous solutions,which known as the “short-trem cycle”.And the probability of "shortterm cycle" is higher when LA-ALNS repeate uses the same destory and repair operators.At the same time,the LA-ALNS algorithm is not capable for solving multi-objective UPMSP.The following work aims to solve the existed problems of LA-ALNS:(1)In order to improve the search efficiency and the quality of solutions,a hybrid metaheuristic algorithm LA-ALNS-TS which combines LA-ALNS and tabu search(TS)together is proposed.On the one hand,the TS algorithm could reconstruct the previous solutions and store the used movements,which can alleviate the phenomenon of "short-term cycle".On the other hand,LA-ALNS could increase the diversity of the search scope through the destory and repair operators.A hybrid local search strategy is proposed to balance the search efficiency and the computational time.The core idea of the local search strategy is to use the first local search to balance the allocation among the machines to obtain a coarse-grained solution,and then use the second local search which based on random variable neighborhood descent to fine-tuning the obtained solution.Moreover,a dynamic perturbation scheme is introduced to extand the search scope by increasing the perturbation strength to help avoid the algorithm falling into local optima.The experimental results show that the proposed LA-ALNS-TS has the best performance among all the compared algorithms.(2)Since the multi-objective problems are more widely used in the field of production scheduling,based on the previous work,a challenging two-objective unrelated parallel machine scheduling problem is proposed.The problem considers production resources with shelf-life constraints and setup times and the objectives are to minimize the waste costs of production resources and makepan.An 0-1 integer programming model is also proposed for the twoobjective UPMSP.Since the LA-ALNS is not capable for solving multi-objective problemes,a multi-objective hybrid heuristic algorithm(LA-ALNS-MOEA/D)which combines LA-ALNSTS and MOEA/D is proposed.In the framework of MOEA/D,the destory and repair operators in LA-ALNS-TS are redesigned and improved and the LA is used to adjust the weights of them.TS is also used to alleviate the phenomenon of "short-term cycle".In addition,a greedy-based hybrid heuristic initialization strategy is introduced,and the local search method is designed as an improvement strategy for optimizing the two objectives respectively.Experimental results suggest that the proposed LA-ALNS-MOEA/D outperforms the comparison algorithms and also has a good performance in computational time.Based on the LA-ALNS algorithm,this paper designs two heuristic algorithms for single and multi-objective UPMSP,and checks their performances on benchmark datasets.The TS algorithm is incorporated with LA-ALNS,which reduces the probability of "short-term cycle" and improves the search efficiency.Moreover,the combination of LA-ALNS-TS and MOEA/D is a direct extension of LA-ALNS-TS,which increase the practical value of LA-ALNS-TS.