Swarm Intelligence Based Algorithms For Job Shop Scheduling Problem

Scheduling problem is well known in your daily life. the transportation system is onegood example, the train, the airline...... They all need to be well arranged to get the bestmarket profit. In addition, we can also see some thoughts of scheduling in our studentCourse scheduling system, how to avoid the situation of two different classes in the sameclassroom at the same time. How to make the best use of school resources.those problemsall need the knowledge of scheduling. Therefore,although scheduling problem is not a newone for researchers.it is widely applied to many areas.its’ value should not be ignored.The job shop scheduling problem is one of the combination optimization problems. Ithas attracted attentions of many researchers in the past few decades. Those researchers hasput forward many solution algorithms based on genetic algorithm, simulated annealing,Tabu Search, particle swarm optimization and so on. Those algorithms can be put into thecategory of Evolutionary algorithm, which are inspired from the natural phenomena. Thosealgorithms all become the good solution of scheduling problem like job shop problem.Particle swarm algorithm with its own advantages, has become one of the main methods tosolve the job shop problem. Swarm intelligence algorithm mainly involved particleoptimization algorithm, ant colony algorithm, which also get inspiration form nature.Swarm intelligence has become one of the efficient algorithm to solve the schedulingproblem.After reading a lots of papers and books of swarm intelligence, especially particleswarm optimization algorithm. I get a relatively comprehensive understanding of job shopscheduling problem and swarm intelligence. Based on those preparation,I have done a lot ofresearch and experimental work..In this thesis, I will first introduce the research status of the job shop schedulingproblem, describe the usual solutions, and in accordance with the usual thinking, I conductsome analysis of the advantages and disadvantages of those algorithms. On the basis ofthese reflections,and the problems of the existing algorithms, I give some new ideas.The following is the main content of this thesis:After reading reference of relative fields. I find that many algorithms to solve the jobshop scheduling problem are generalization ones, that is to say those algorithms have thesame strategy for problems of different scale. With the increasing of the size of the problem,the search space will also span, it is not reasonable to deal with problems with differentscale using the same search strategy. Therefore, I introduce “adaptive” factors,use the scaleof the problem as a heuristic information, guiding throughout the search process, changing the search strategy dynamically. I also find that many existing hybrid algorithms are lackof “self-learning” and ignore the information in the search process, those algorithms aresimply the combination of several algorithms framework. Therefore, I add a dynamiclearning component into my algorithm. The final algorithm proposed in this this paperbased on the above ideas.1. Learn from the benchmark,using the scale information as heuristic information.2. Add more self-learning factors into particle swarm optimization.: updating part andousting part. Decrease the possibility of trapping into the local optima.3. Introduce new neighborhood search into simulated annealing algorithm.Also, I do a lot work to hold the balance of exploration and exploitation. Which influencethe algorithm greatly.