Job-shop Scheduling Method Based On Fitness Landscape Theory

Job-shop Scheduling is the most typical problem of Shop Scheduling. Its researchmethods and results have been applied to many other types of scheduling problems and theactual production operations. It is great important for the study of the characteristics and thedesign of algorithm of Job-shop Scheduling problem. In this paper, the research methods itbased on the Fitness Landscape Theory, we had explored the nature and its influencing factorsboth from their distribution and structure characteristics. And then we designed efficientscheduling optimization algorithm according to these results.This paper first proposed a Logistic Model for the study of Fitness Landscape. This modelcan effectively distinguish different instances of the problem. When using this method tostudy the affection of basic properties to the distribution of landscape, we found some rules.The constraints of problem shape will be a huge impact on the terrain. With the ration of jobnumber to machine number goes high, the difficulty of the problem will goes to “Easy-Hard-Easy”. The increase of the constraints of the process paths will make the problem harder tosolve. And the affection of the process time is much weaker. Example test shows that themethod is superior to the current types of methods at reflecting the nature of the problem.Then we use the local search algorithm to study the structure of the fitness landscape,found that, the Logistic distribution also exist in the search process of individuals. Whenstudy the affection of basic properties to the structure of landscape, we use a Local searchalgorithm with2-opt and Insert neighborhood. Results show that, the constraint of processingpath will affect the ration of basin to valley and the nature of the problem landscape, while theshape and size did not change to nature of the landscape. The different structural features oftwo neighborhood strategies provide a guide to the design of the algorithms.Based on the foregoing findings, this paper presents a hybrid algorithm of particle swarmoptimization and variable neighborhood search, which is under the framework of particleswarm optimization model. Logistic model presented in this paper is used to select thecombination of efficient neighborhood strategies, the results show that, the wholeneighborhood based on a random exchange and N5neighborhood based on insertion has agood combination of effects. Instance tests show that the hybrid algorithm is more effectivethan a single neighborhood search. And the tests on the LA series show that, this algorithmcan get38optimal solutions from the total40problems, which verifies the superiority of theproposed algorithm.Finally, a conclusion is given and the further research directions of Job-shop Schedulingproblem and Fitness Landscape are anticipated.