A new heuristic algorithm for solving the job shop scheduling problem

The job shop scheduling problem is one of the most difficult production scheduling problems in industry. This paper presents a new physical model, in which each operation is looked as a elastic block for the job shop scheduling problem and a new heuristic algorithm based on the model to solve the problem. In the new model, the solution of the problem is created by heuristic strategy of quasi-physic, and then the algorithm is improved by introducing strategy of quasi-human. Computational experiments show that this algorithm is more effective and efficient than those algorithms based on priority dispatching rules. The algorithm is a new idea for solving the job scheduling problem, and it could be a very good basic procedure for designing effective and efficient heuristic algorithm by combining with other heuristic strategy for the problem.