Exact and Approximation Approach of Assignment Problem for System with Precedence Relationships among Elements

Bibliographic Information

Other Title
  • 要素間に先行順位をもつシステム要素の配置問題に対する厳密解法と近似解法の提案
  • ヨウソカン ニ センコウ ジュンイ オ モツ システム ヨウソ ノ ハイチ モ

Search this article

Description

We think about the problem to assign the elements to an ordered sequence of stations such that the precedence relationships are satisfied. This problem can be shown as a problem for sequential partitions of the nodes of a directed acyclic graph into subsets. We describe an efficient exact algorithm that can be used to reduce computational requirements and, possibly storage. And, we presents approximation algorithm using the tabu search approach with effective neighbourhood structure, that is effective in obtaining near-optimal solutions to this problem. The running time of the procedure is proportional to the number of nodes in the graph.

Journal

References(11)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top