랜덤형 2차원 할당문제 알고리즘
The Random Type Quadratic Assignment Problem Algorithm
0
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
The optimal solution of quadratic assignment problem (QAP) cannot get done in polynomial time. This problem is called by NP-complete problem. Therefore the meta-heuristic techniques are applied to this problem to get the approximated solution within polynomial time. This paper proposes an algorithm for a random type QAP, in which the instance of two nodes are arbitrary. The proposed algorithm employs what is coined as a max flow-min distance rule by which the maximum flow node is assigned to the minimum distance node. When applied to the random type QAP, the proposed algorithm has been found to obtain optimal solutions superior to those of the genetic algorithm.
Abstract
The optimal solution of quadratic assignment problem (QAP) cannot get done in polynomial time. This problem is called by NP-complete problem. Therefore the meta-heuristic techniques are applied to this problem to get the approximated solution within polynomial time. This paper proposes an algorithm for a random type QAP, in which the instance of two nodes are arbitrary. The proposed algorithm employs what is coined as a max flow-min distance rule by which the maximum flow node is assigned to the minimum distance node. When applied to the random type QAP, the proposed algorithm has been found to obtain optimal solutions superior to those of the genetic algorithm.
참고문헌 (15)
- C. W. Commander, "A Survey of the Quadratic Assignment Problem, with Applications", European Journal of Operational Research, 176(2), pp.657~690 (2007)
- P. Ji, "A Solution Method for the Quadratic Assignment Problem(QAP)", The 6th International Symposium on Operations Research and Its Applications (ISORA'06), pp.106~117 (2006)
- L. Steinberg, "The Backboard Wiring Problem : A Placement Algorithm", SIAM Review, 3, pp.37~50 (1961)
- A. N. Elshafei, "Hospital Layout as a Quadratic Assignment Problem", Operations Research Quartly, 28, pp.167~179 (1977)
- R. E. Burkard, "QAPLIB-A Quadratic Assignment Problem Library", Journal of Global Optimization, 10(4), pp.391~403 (1997)
- S. Tsutsui, "Solving Quadratic Assignment Problems by Genetic Algorithms with GPU Computation: A Case Study", Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference (GECCO), pp.2523~2530 (2009)
- E. Lawler, "Combinatorial Optimization: Networks and Matroids, 4.5. Combinatorial Implications of Max-Flow Min-Cut Theorem, 4.6. Linear Programming Interpretation of Max-Flow Min-Cut Theorem", 117~120 (2001)
- 이상운, "최대 수용량-기반 최소절단 알고리즘", 한국컴퓨터정보학회논문지, 16(5), pp.153~162 (2011), 한국컴퓨터정보학회
- 최명복, "무방향 그래프의 최대인접병합 방법을 적용한 최소절단 알고리즘", 한국인터넷방송통신학회 논문지, 13(1), pp.143~152 (2013), 한국인터넷방송통신학회[DOI]
- "Operations Research Models and Methods, Section 7.4 Facility Location Problem" (2003)[URL]
- K. C. Chan, "A Study of Genetic Crossover Operations on the Facilities Layout Problem", Computers and Industrial Engineering, 26(3), pp.537~550 (1994)
- K. L. Mak, "A Genetic Algorithm for Facility Layout Problems", Computer Integrated Manufacturing Systems, 11(1-2), pp.113~127 (1998)
- M. A. El-Baz, "A Genetic Algorithm for Facility Layout Problems of Different Manufacturing Environments", Computers & Industrial Engineering, 47, pp.233~246 (2004)
- I. Mihajlovic, "Using Genetic Algorithms to Resolve Facility Layout Problem", Serbian Journal of Management, 2(1), pp.35~46 (2007)
- S. Jannat, "Optimal Solution for Multi-Objective Facility Layout Problem Using Genetic Algorithm", Proceedings of the International Conference on Industrial Engineering and Operations Management, Dhaka, Bangladesh (2010)