Efficient Algorithms For The Job Shop Scheduling Problem

The Job Shop Scheduling Problem is known as one of the particularly hard combinatorial optimization cases. It is also a typical NP complete problem. It is a classical problem with high theoretical value. At the same time, the Job Shop Scheduling Problem is a simplification of practical production scheduling problem in the industry. This problem is not only used in production scheduling, but also widely used in economic management, transportation, network telecommunication, etc. Therefore, researching on the Job Shop Scheduling Problem is of great practical value.Researchers from all over the world have deeply studied this problem for several decades. A lot of different methods have been designed to solve the problem. Because the computing time of the exact algorithm for the problem will increases exponentially with the problem's size, it is unwieldy to solve the problem with an exact algorithm. Researchers focus their efforts on the development of efficient approximation algorithms to solve this problem.An efficient algorithm just for the Job Sop Scheduling Problem is designed to test the feasibility of the solution. This algorithm has been tested on 42 benchmark instances. The computational results indicate that this algorithm is much better than DFS.A new search structure and a more efficient search mode are designed and form a hybrid algorithm DLS. This algorithm prevents the search from trapping in a local optimal solution. DLS adopts a new dispatching priority rules approach named Vip-SP. This algorithm has been tested on 42 benchmark instances. The computational results indicate that the algorithm is efficient for the Job Shop Scheduling Problem.