Assignment Problem for System with Precedence Relation among Elements
-
- Kaji Taichi
- Otaru University of Commerce
-
- Ohuchi Azuma
- Hokkaido University
Bibliographic Information
- Other Title
-
- 要素間に先行順位をもつシステムの配置問題
- ヨウソカン ニ センコウ ジュンイ オ モツ システム ノ ハイチ モンダイ
Search this article
Abstract
We think about the problem to assign the elements to an ordered sequence of stations such that the precedence relations are satisfied. At this time, we obtain the best evaluation value decided under a certain constrained condition to the assignment. This kind of problem includes the line balancing problem etc. In addition, this problem can adjust to various problems by changing constrained condition and objective function. These problems can be shown as a problem for sequential partitions of the nodes of a directed acyclic graph into subsets. We especially consider problem for finding a minimum total cost of the cut edge under the restriction of the size of block.<br>In this paper, we propose the general framework for sequential partitions of directed acyclic graphs. And we describe an efficient algorithm that can be used to reduce computational requirements and, possibly storage. We estimate that complexity of the algorithm is the polynomial order, if structure of directed acyclic graphs is near parallel.
Journal
-
- IEEJ Transactions on Electronics, Information and Systems
-
IEEJ Transactions on Electronics, Information and Systems 117 (2), 136-142, 1997
The Institute of Electrical Engineers of Japan
- Tweet
Details 詳細情報について
-
- CRID
- 1390001204607712768
-
- NII Article ID
- 130006843613
- 10002809315
- 10006759358
-
- NII Book ID
- AN10065950
-
- ISSN
- 13488155
- 03854221
-
- NDL BIB ID
- 4128397
-
- Data Source
-
- JaLC
- IRDB
- NDL
- Crossref
- CiNii Articles
-
- Abstract License Flag
- Disallowed