Machine-oriented decentralized scheduling method using Lagrangian decomposition and coordination technique

Abstract

In the conventional Lagrangian relaxation approach, the scheduling problems are decomposed into job-level sub-problems or operation-level sub-problems. However, these approaches are not applicable to the flowshop problems with the changeover cost which depends on the sequence of operations. In this paper, we propose a machine-oriented decomposition method for the flowshop problems using the Lagrangian decomposition and coordination technique. In the proposed method, each sub-problem for single machine is solved by the simulated annealing method. The solutions of the sub-problems are used to generate a feasible schedule by a heuristic procedure. The effectiveness of the proposed method is verified by comparing the results of the example problems solved by the proposed method with those solved by the conventional method. Furthermore, it has been shown that the proposed approach is easily applicable to the flow hop problem with resource constrains minimizing the changeover costs and due date penalties.