Premium
A tabu search approach to the optimal sequential partitions of directed acyclic graphs
Author(s) -
Kaji Taichi,
Ohuchi Azuma
Publication year - 1997
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/(sici)1520-6416(199706)119:4<42::aid-eej5>3.0.co;2-j
Subject(s) - tabu search , heuristics , guided local search , mathematical optimization , mathematics , combinatorial optimization , partition (number theory) , directed acyclic graph , directed graph , constraint (computer aided design) , algorithm , graph , computer science , combinatorics , geometry
Tabu search is a novel technique for solving combinatorial optimization problems. The process in which the tabu search method seeks to transcend local optimality is based on an evaluation function which chooses the highest‐evaluation move in terms of objective function and tabu restrictions. This paper presents a tabu search algorithm for finding a minimum‐cost partition of the nodes of a directed acyclic graph into subsets of a given size, subject to the constraint that the precedence relations are satisfied. A standard tabu search approach cannot realize good solutions for this problem, because the problem is a complex multiple partitioning problem in which the number of subsets and the number of nodes in each subset are unsettled. For this problem, we use an appropriate data structure for this method and develop effective neighborhood structure and heuristics. We also assess the effectiveness of the developed algorithm. The results show that this algorithm is effective in obtaining a near‐optimal solution to this problem. The running time of the procedure is proportional to the number of nodes in the graph. © 1997 Scripta Technica, Inc. Electr Eng Jpn, 119(4): 42–51, 1997