Study on job shop scheduling problem

In this paper, we propose an improved Lagrangian relaxation algorithm to solve job shop scheduling problems. Besides the addition of augmented objective, we expand the search scope of near-optimal solutions and improve the computational efficiency greatly by restricting the solution scope of sub-problems and modifying the search method of dual problem. At the same time, we develop a genetic algorithm combining with the LR (Lagrangian Relaxation) method. Using the numerous useful solutions we get in the Lagrangian Relaxation as the original genes, we can improve the solution further. Test results show that these methods achieve satisfactory outcome for job shop problems. They can also be applied to other programming problems with constraints.