An approximate solution of machine scheduling problems by decomposition method

To obtain an approximate solution for a large-scale job-shop scheduling problem the decomposition method was investigated. This means that an original problem is decomposed into subproblems, which are solved separately, and then the solution of the original problem is composed from the subproblems' solutions. Different methods to decompose the problem were tested by computational experiments and evaluated from the viewpoint of the goodness of schedule and computation time.