Assignment problem for system with precedence relationships among elements.

We have studied the problem of assign elements to an ordered sequence of stations such that the precedence relations are satisfied. At this time, we can obtain the best evaluation value decided under certain constrained conditions to the assignment. This kind of problem includes the line balancing problem. In addition, this can be adjusted to various problems by changing the constrained condition and objective function. These problems can be shown as sequential partitions of the nodes of a directed acyclic graph into subsets. We especially consider the problem of finding a minimum total cost of the cut edge under the restriction of the size of block. In this paper, we propose the general framework for sequential partitions of directed acyclic graphs. We also describe an efficient algorithm that can be used to reduce computational requirements and, possibly, storage. We estimate that the complexity of the algorithm is the polynomial order, if structure of directed acyclic graphs is near parallel. © 1997 Scripta Technica, Inc. Electr Eng Jpn, 121(2): 54–62, 1997 [ABSTRACT FROM AUTHOR]