An Efficient Approximation Algorithm For Job Shop Scheduling Problem

The job shop scheduling problem is a classical problem with both highly theoretical and practical value. In fact, people's experience shows that it is among the hardest combinatorial optimization problems. Nowadays researchers focus their efforts on the development of efficient approximation algorithms for solving this problem.The definition of the job shop scheduling problem is very difficult to be understood. This difficulty can be overcome by using the quasi-physical method, which is derived from the physical world. After being stated by using the quasi-physical method, the job shop scheduling problem is very easy to be understood.The double-frontline-greed algorithm is a new basic algorithm. It assigns the start times of all the operations successively. The double-frontline-greed algorithm assigns the double-frontline operation to start at the earliest start time of it. While consuming a little more computing time, the double-frontline-greed algorithm can always produce solutions whose quality is better or equal to the quality of the solutions produced by the disjunctive-graph algorithm, which is common in the literature.A local search procedure is based on the double-frontline-greed algorithm. The definition of neighborhood, which is crucial for the performance of the local search procedure, is based on critical path. The new idea of this procedure is that the search procedure impartially randomly chooses one neighbor from the best three neighbors and updates current solution with this neighbor instead of stopping when local optimal solution is found out.The single machine scheduling procedure changes the sequence on one machine, while keeping the sequences on all other machines fixed. The single machine scheduling procedure can be extended into the double machine scheduling procedure, which changes sequences on two machines while keeping the sequences on all other machines fixed.Local search procedure is easy to be trapped in local optimal solutions. Hence three off-trap strategies: single machine scheduling, double machine scheduling and random disturbing, can be used to jump from local optimal solutions and guide the search into promising areas.The hybrid algorithm, which is based on the double-frontline-greed algorithm and which is the combination of local search, single machine scheduling, and off-trap strategies, can be used for solving the job shop scheduling problem. This hybrid algorithm has been tested on 138 benchmark instances whose sizes vary form 6 jobs and 6 machines to 100 jobs and 20 machines.The computational results of this hybrid algorithm can be summarized as following three aspects.Firstly, this hybrid algorithm produces better solutions than those solutions produced by BV-best, which is the best approximation algorithm available in the literature. BV-best has been tested on 131 benchmark instances. For 27 instances, the hybrid algorithm generates better solutions than BV-best. For 16 instances, the hybrid algorithm generates worse solutions than BV-best. For 88 instances, the quality of the solutions generated by the hybrid algorithm is equal to the quality of the solutions generated by BV-best.Secondly, this hybrid algorithm produces a solution, whose makespan is 1339, to a benchmark instance named TA15. This solution is even better than the best solution presented in the literature. The makespan of the best solution of TA15 presented in the literature is 1340.Thirdly, this hybrid algorithm is definite and strongly uniform. It does not adopt any parameter whose value is adjusted according to the problem instances. BV-best is not definite.The study of hybrid algorithm is a very promising area.Moreover, the permutation flow shop scheduling problem and the traveling salesman problem are related to the job shop scheduling problem. The permutation flow shop scheduling problem can be solved by a local search algorithm. Computational results based on 29 benchmark problems show the effectiveness of this algorithm. In comparable amount of computer time with an improved genetic algorithm, this local search algorithm generates better solutions than this improved genetic algorithm. And the improved local search algorithm, which combines a constructive algorithm with the local search algorithm, turns out to be more efficient than the local search algorithm. The traveling salesman problem can be solved by a new local search algorithm, which is based on a novel basic algorithm. In short computer time, this algorithm generates optimal solutions for 24 out of 27 standard benchmark instances, and outperforms a famous and efficient algorithm in the literature.