A solution of the job shop scheduling problem by decomposition method

A two-phase methodology for scheduling workshop jobs based on decomposition is presented in this article. The methodology uses a partition of the workshop in manufacturing cells for solving the global problem in a decomposed way. The scheduling is obtained by an approximate procedure that solves the job shop disjunction while taking into account the release and due dates. The proposed methodology allows us to efficiently solve some large size examples and works in real time, despite the non-polynomial nature of the problems studied. The corresponding program is written in C++ and runs on a microcomputer.