A decentralized scheduling method for flowshop problems with resource constraints

In this paper, we propose a decentralized scheduling method for flowshop scheduling problems with resource constraints using the Lagrangian decomposition and coordination approach. When a flowshop scheduling problem with resource constraints is decomposed into machine-level subproblems, the decomposed problem becomes very difficult to solve so as to obtain the optimal solution, even when the production sequence of operations is given. In this study, the decomposed subproblems are solved by a simulated annealing algorithm combined with dynamic programming. By decomposing the problem into single machine subproblems, the changeover cost can easily be incorporated in the objective function. In order to reduce the computation time, a heuristic algorithm for calculating the starting times of operations is also proposed. The performance of the proposed method is compared with that of the simulated annealing method by which the schedule of the entire machine is successively improved. Numerical results have shown that the proposed method can generate better solutions than the conventional method.