A two-step approach for solving the flexible job shop scheduling problem

The flexible job shop scheduling problem is one of the most difficult production scheduling problems in industry. This paper presents a two-step approach to solve this problem. In the first step, all the operations are disputed to the machines such that each operation is processed by a certain machine which means that the problem becomes the job shop scheduling problem. In the second step, a quasi-physic and quasi-human algorithm is proposed to solve the job shop scheduling problem. Our approach is tested on several common benchmarks, and the computational experiments show that this two-step approach is quite effective and efficient. Further more, The quasi-physic and quasi-human 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.