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

Tatsushi Nishi, Masami Konishi, Shinji Hasebe, Iori Hashimoto

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)


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 flowshop problem with resource constrains minimizing the changeover costs and due date penalties.

Original languageEnglish
Pages (from-to)4173-4178
Number of pages6
JournalProceedings - IEEE International Conference on Robotics and Automation
Publication statusPublished - 2002


  • Decentralized system
  • Lagrangian relaxation
  • Scheduling
  • Simulated annealing

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering


Dive into the research topics of 'Machine-oriented decentralized scheduling method using Lagrangian decomposition and coordination technique'. Together they form a unique fingerprint.

Cite this