Improvement of Lagrangian relaxation convergence for production scheduling

It is widely accepted that new production scheduling tools are playing a key role in flexible manufacturing systems to improve their performance by avoiding idleness machines while minimizing set-up times penalties, reducing penalties for do not delivering orders on time, etc. Since manufacturing scheduling problems are NP-hard, there is a need of improving scheduling methodologies to get good solutions within low CPU time. Lagrangian Relaxation (LR) is known for handling large-scale separable problems, however, the convergence to the optimal solution can be slow. LR needs customized parametrization, depending on the scheduling problem, usually made by an expert user. It would be interesting the use of LR without being and expertise, i.e., without difficult parameters tuning. This paper presents innovative approaches on the LR method to be able to develop a tool capable of solve scheduling problems applying the LR method without requiring a deep expertise on it. First approach is the improvement of an already existing method which use Constraint Programming (CP) to obtain better primal cost convergence. Second approach is called Extended Subgradient Information (ESGI) and it speed up the dual cost convergence. Finally, a set of step size rules for the Subgradient (SG) method are compared to choose the most appropriate rule depending on the scheduling problem. Test results demonstrate that the application of CP and ESGI approaches, together with LR and the selected step size rule depending on the problem, generates better solutions than the LR method by itself. © 2006 IEEE.