최소 단어 이상 선택하여야 합니다.
최대 10 단어까지만 선택 가능합니다.
다음과 같은 기능을 한번의 로그인으로 사용 할 수 있습니다.
NTIS 바로가기The journal of the institute of internet, broadcasting and communication : JIIBC, v.18 no.3, 2018년, pp.201 - 207
There is no known polynomial time algorithm for random-type quadratic assignment problem(RQAP) that is a NP-complete problem. Therefore the heuristic or meta-heuristic approach are solve the approximated solution for the RQAP within polynomial time. This paper suggests polynomial time algorithm for ...
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
핵심어 | 질문 | 논문에서 추출한 답변 |
---|---|---|
2차원 할당문제(quadratic assignment problem, QAP)란 무엇인가? | 2차원 할당문제(quadratic assignment problem, QAP)는 n개 위치(locations, li, i=1, 2, ⋯, n)에 n개 시설(facilities, fj, j=1, 2, ⋯, n)을 배치하는 문제로, 위치 간 n×n 거리 행렬 L과 시설 간 n×n 물동량 행렬 F에 대해 운송비용을 최소화하도록 fj를 li에 1:1로 배정하는문제이다[1]. | |
할당 문제(AP)는 어떻게 분류할 수 있나? | 할당 문제(AP)는 그림 1과 같이 1차원과 2차원으로 분류된다. 1차원 할당 문제는 Kn,n의 완전 이분 그래프로 형태로 작업이 기계에서 소요되는 단방향 시간에 대해 작업과 기계 측면의 양측-최적화를 수행하는 형태로 볼수 있다. | |
할당 문제(AP) 중 2차원 할당 문제는 어떤 문제로 분류되나? | 일반적인 할당문제(assignment problem, AP)는 1차원 할당 문제로 i행과 j열의 1차원의 양측-최적화만을 수행해야 하지만, QAP는 2개의 행렬에 대해 4차원의 4측-최적화를 수행해야 하는 극도로 어려운 문제로 현재까지 다항시간으로 풀 수 있는 알고리즘이 알려져 있지않아 NP-완전(NP-complete) 문제로 분류되고 있다[1]. 일반적으로, QAP는 n!개의 가능한 할당 경우수가 존재한다. |
E. M. Loiola, N. M. M. Abreu, P. O. Boaventura-Netto, P. Hahn, and T. Querido, "A Survey for the Quadratic Assignment Problem," European Journal of Operational Research, Vol. 176, No. 2, pp. 657-690, Jan. 2007. doi:10. 1016/j.ejor.2005.09.032
P. Ji, Y. Wu, and H. Liu, "A Solution Method for the Quadratic Assignment Problem (QAP)," The 6th International Symposium on Operations Research and Its Applications (ISORA), Xinjiang, China, pp. 106-117, 2006.
M. Solimanpur and A. Jafari, "Optimal Solution for the Two-dimensional Facility Layout Problem using a Branch-and-bound Algorithm," Journal of Computers and Industrial Engineering, Vol. 55, No. 3, pp. 606-619, Oct. 2008. doi:10.1016/j.cie. 008.01.018
I. Mihajlovic, Z. Zivkovic, N. Strbac, D. Zivkovic, and A. Jovanovic, "Using Genetic Algorithms to Resolve Facility Layout Problem," Serbian Journal of Management, Vol. 2, No. 1, pp. 35-46, Jan. 2007.
S. U. Lee, "A Reverse-Delete Algorithm for Assignment Problems," Journal of KIIT, Vol. 10, No. 8, pp. 117-126, Aug. 2012. uci:G704-001947.2012.10.8.007
S. U. Lee, "Assignment Problem Algorithm Using Dual-path Competition Method," Journal of KIIT, Vol. 13, No. 12, pp. 75-83, Dec. 2015. doi:10. 4801/jkiit.2015.13.12.75
L. Steinberg, "The Backboard Wiring Problem: A Placement Algorithm," SIAM Review, Vol. 3, pp. 37-50, Jan. 1961. doi:10.1137/1003003
A. N. Elshafei, "Hospital Layout as a Quadratic Assignment Problem," Operations Research Quarterly, Vol. 28, No. 1, pp. 167-179, Mar. 1977.
S. U. Lee, "The Grid Type Quadratic Assignment Problem Algorithm," Journal of KSCI, Vol. 19, No. 4, pp. 91-99, Apr. 2014. doi:/10.9708/jksci.2014.19.4.091
S. U. Lee, "The Random Type Quadratic Assignment Problem Algorithm," Journal of KSCI, Vol. 21, No. 4, pp. 81-88, Apr. 2016. doi:10. 9708/jksci.2016.21.4.081
S. Tsutsui and N. Fujimoto, "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, pp. 2523-2530, Jul. 2009. doi:10.1145/1570256.1570355
P. A. Jensen and J. F. Bard, "Operations Research Models and Methods, Section 7.4 Facility Location Problem," John Wiley and Sons. 2003. ISBN:0-471-38004-0
K. C. Chan and H. Tansri, "A Study of Genetic Crossover Operations on the Facilities Layout Problem," Computers and Industrial Engineering, Vol. 26, No. 3, pp. 537-550, Jul. 1994. doi: 10.1016/0360-8352(94)90049-3
K. L. Mak, Y. S. Wong, and F. T. S. Chan, "A Genetic Algorithm for Facility Layout Problems," Computer Integrated Manufacturing Systems, Vol. 11, No. 1-2, pp. 113-127, Sep. 1998. doi:10. 1016/S0951-5240(98)00018-4
M. A. El-Baz, "A Genetic Algorithm for Facility Layout Problems of Different Manufacturing Environments," Computers & Industrial Engineering, Vol. 47, No. 2-3, pp. 233-246, Nov. 2004. doi:10.1016/j.cie.2004.07.001
S. Jannat, A. A. Khaled, and S. K. Paul, "Optimal Solution for Multi-Objective Facility Layout Problem Using Genetic Algorithm," International Conference on Industrial Engineering and Operations Management, Dhaka, Bangladesh, Jan. 2010.
M. G. Misola and B. B. Navarro, "Optimal Facility Layout Problem Solution Using Genetic Algorithm," World Academy of Science, Engineering and Technology, Vol. 7, No. 8, pp. 545-550, Aug. 2013. doi:scholar.waset.org/1307-6892/16153
*원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다.
출판사/학술단체 등이 한시적으로 특별한 프로모션 또는 일정기간 경과 후 접근을 허용하여, 출판사/학술단체 등의 사이트에서 이용 가능한 논문
※ AI-Helper는 부적절한 답변을 할 수 있습니다.