Premium
A decentralized scheduling method for flowshop problems with resource constraints
Author(s) -
Nishi Tatsushi,
Konishi Masami,
Hasebe Shinji
Publication year - 2004
Publication title -
electrical engineering in japan
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.136
H-Index - 28
eISSN - 1520-6416
pISSN - 0424-7760
DOI - 10.1002/eej.10364
Subject(s) - changeover , mathematical optimization , simulated annealing , computer science , job shop scheduling , computation , schedule , scheduling (production processes) , algorithm , mathematics , telecommunications , transmission (telecommunications) , operating system
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. © 2004 Wiley Periodicals, Inc. Electr Eng Jpn, 149(1): 44–51, 2004; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/eej.10364