IIAE CONFERENCE SYSTEM, The 5th IIAE International Conference on Industrial Application Engineering 2017 (ICIAE2017)

Font Size: 
Weighted Item Collecting in Directed Bipartite Structure with a Reversing Cost Penalty
Yoshiyuki Karuno, Seiya Tanaka

Last modified: 2017-02-21


In this paper, a weighted item collecting problem in directed bipartite structure containing a set of items with profits and a set of players with costs is discussed. The problem is viewed as a generalization of an integrated circuit design problem considered by Tang (2005), that is, collecting an item in the problem may correspond to avoiding an undesirable via in the integrated circuit design. In this paper, an objective function not only with the total profit of collected items, but also with a penalty term of the costs paid by the players is treated. A greedy heuristic algorithm is proposed, and numerical experiments are conducted to demonstrate the performance.


Electronic; Information

Full Text: PDF