Heuristic Algorithms For The Job Shop Scheduling Problem And The Satellite Broadcasting Scheduling Problem

Scheduling problems widely exist in every field of our life,such as airports scheduling problem,marine ship scheduling problem,cloud load balance problem and so on.These issues are the basic foundation and core part of the various fields in production practice.By solving these scheduling optimization problems,we can improve the efficiency of production,the life will be more convenient and affordable.However,in practice many scheduling problems are usually difficult to solve because of the extremely complex situation and the massive size of data.In addition,most of them is proved to be NP-Hard.Thus,they are challenging problems for the researchers in both academia and industry.As the heuristic algorithms are developing fast in recent years,such algorithms have already attracted much attention from a significant number of researchers and become more and more mature.Nowadays the heuristics algorithms have become a very effective method and tool for solving the NP-Hard problems.This paper studies two classic NP-Hard problems in the scheduling filed(i.e.,the job shop scheduling problem(JSP)and the satellite broadcast scheduling problem(SBSP)).In addition,we proposes two heuristic algorithms for both two problems respectively.Furthermore,this study evaluates the performance of the algorithms by the computational experiments.The important parameters and key strategies of the corresponding algorithms are also analyzed and discussed.The main contribution of this paper includes:(1)By introducing the crossover operator based on the longest common subsequence and the specific population updating strategy based on the population diversity management mechanism,a new hybrid evolutionary algorithm(HEA)is proposed to solve the JSP problem.In addition,the effects of different parameters on the performance of HEA algorithm are also presented.All the experimental results demonstrate that HEA algorithm is effective.(2)This study presents a new TS/PR algorithm for JSP problem by combing the tabu search and path relinking algorithms(TS/PR).By combining the tabu search based on N7 neighborhood structure and the path relinking algorithm based on adaptive distance-control mechanism,the whole algorithm can achieve a better balance between the intensification and diversification.The computational results demonstrate that TS/PR obtains competitive results compared with the reference algorithms in both solution quality and computing time.The additional experiment presents the effects of important parameters on the performance of TS/PR algorithm.(3)This work proposes two new algorithms i.e.iterated local search(ILS)and hybrid path relinking(HPR)for solving SBSP problem.The local search procedure based on 0-slip move and the random perturbation phase based on 1-slip move are employed in the ILS algorithm.HPR algorithm combines the proposed ILS algorithm and the path relinking algorithm based on the adaptive distance-control mechanism.The experimental results present the effectiveness of ILS and HPR algorithms.(4)In the JSP problem,this paper compares the HEA algorithm with two advanced algorithms(TS/SA and HGA).The experiments present that HEA algorithm is able to obtain more instances on matching the best solutions than TS/SA and HGA algorithms,and the matching rate of HEA algorithm is more than 90%.In particular,the HEA algorithm can also improve the upper bounds for two instances.By comparing TS/PR with nine bestperforming algorithms in the literature,the experiments demonstrate that TS/PR is able to improve the upper bounds for 49 instances with the improvement rate up to 64.88%.Especially,TS/PR solves the challenging SWV15,which has remained unsolved for over 20 years.In the SBSP problem,the ILS and HPR algorithms are compared with four advanced methods in the literature.The experimental results show that ILS algorithm can find a good solution in a short time and has a good real-time performance,while the HPR algorithm is able to find a better quality of the solution and can achieve a better tradeoff between the solution quality and computational efficiency.All these research results present that the hybrid evolutionary algorithm,the iterated local search algorithm and the hybrid path relinking algorithm are all effective and efficient heuristic algorithms fr solving the corresponding scheduling optimization problems.Through the study of this thesis,we have deepened the understanding of the scheduling optimization problems with NP-Hard difficulty.According to the research situation of this thesis,the experience are summarized as follows:(1)Combining the problem structure to design the algorithmsWhen we design a heuristic algorithm with high performance,it should be based on the inherent structural characteristics of the problem to guide the design of the algorithm,especially the design of the neighborhood structure.Although two combinatorial optimization problems studied in this paper are scheduling optimization problems,the neighborhood structure between these two problems can not be shared,because of the different inner structure.From the perspective of the solution structure,the JSP problem is essentially a sequencing problem,and the SBSP problem is a 0-1 assignment problem.For the sequencing problems,the neighborhood move based on ”Insert” or ”Swap” move used to be employed.While turning over the variable is usually an effective way for the 0-1 assignment problem,such as the famous Satisfiability Problem(SAT).Therefore,the proposed algorithms in the SBSP problem do not draw on the design method of the neighborhood structure of the JSP problem.Instead,we propose the neighborhood structure based on the 0-slip move by using the way of turning over the variable(communication status between satellite and terminal for SBSP problem).The experimental results also demonstrate the effectiveness of this method.The design method of the heuristic algorithm considering the problem structure is the key to design highly effective heuristic algorithms.(2)The design techniques of hybrid algorithmThe design on hybrid algorithms is one of the development trends of heuristic algorithm in recent years.When designing the hybrid algorithms,we should avoid combining the algorithms in the same type.It is usually a better choice to combine the heuristic algorithm with different type.The reason is that,the design process of the heuristic algorithm is usually the process of balancing the intensification and diversification on the heuristic algorithm.If we combine two heuristic algorithms with the strong intensification and weak diversification,the ”Barrel Effect” will appear.Try combining the local search algorithm and tabu search algorithm is likely to be impractical.Therefore,combining the different types of algorithms can usually obtain a good result,especially for the complementary algorithms.For example,combing the local search(or tabu search)algorithm with the population algorithm is effective.Both the proposed ILS algorithms and tabu search algorithm focus on the intensification,while both the evolutionary algorithm and path relinking algorithm based on population mechanism focus on the intensification.Experimental results prove that HEA,TS/PR and HPR algorithms are able to obtain good results in the corresponding problems.In the future studies,we will try employing these useful algorithms to solve other types of NP-Hard scheduling optimization problems.