USU-IR Home    USU Library        Feedback

USU Institutional Repository » PhD Dissertations (PD) » Mathematics and Natural Sciences » PD - Mathematics »

Please use this identifier to cite or link to this item:

http://repository.usu.ac.id/handle/123456789/57846


Title: Strategi Kombinasi Untuk Menyelesaikan Quadratic Assignment Problem
Authors: Ahyaningsih, Faiz
Advisors: Sitompul, Opim Salim
Issue Date: 5-Apr-2016
Abstract: The quadratic assignment problem is a combinatorial problem of deciding the placement of facilities in specified locations in such a way as to minimize a nonconvex objective function expressed in terms of flow between facilities, and distance between location. Due to the non-convexity nature of the problem, therefore to get a good starting point is necessary in order to obtain a better optimal solution. In this paper we propose a combination strategy (random point strategy to get initial starting point and then forward exchange strategy and backward exchange strategy) to get optimal solution. As a computational experience we solve the problem of Had12, Esc 16b, Esc 16c and Esc 16h from QAPLIB. Finally, we present a comparative study between Combination Strategy, Data-Guided Lexisearch Algorithm (DGLSA), and Discrete Linear Reformulation (DLR). The computational study shows the effectiveness of our proposed Combination Strategy
Abstract (other language): Quadratic Assignment Problem (QAP) adalah suatu permasalahan kombinatorial dalam menentukankan penempatan fasilitas pada lokasi tertentu sedemikian rupa sehingga meminimumkan fungsi tujuan nonconvex yang dinyatakan dalam bentuk alur antar fasilitas, dan jarak antar lokasi. Oleh karena sifat non-konveksitas dari masalah, maka diperlukan suatu titik awal yang ’baik’ untuk mendapatkan solusi optimal yang lebih baik. Dalam makalah ini penulis mengusulkan strategi kombinasi (dengan menggunakan random point strategy untuk mendapatkan titik awal, kemudian dilanjutkan dengan forward exchange strategy dan backward exchange strategy) untuk mendapatkan solusi ’optimal’. Sebagai pengalaman komputasi penulis menyelesaikan problema Had12, Esc 16b, Esc 16c dan Esc 16h dari QAPLIB. Akhirnya, penulis menyajikan studi komparatif antara Strategi Kombinasi, Data Guided Lexisearch Algorithm (DGLSA), dan Discrete Linear Reformulation (DLR). Studi komputasi menunjukkan efektivitas dari Strategi Kombinasi yang penulis usulkan
Keywords: QAP
Strategi kombinasi
Random point strategy
Forward exchange strategy
URI: http://repository.usu.ac.id/handle/123456789/57846
Appears in Collections:PD - Mathematics

Files in This Item:

File Description SizeFormat
Cover.pdfCover1.02 MBAdobe PDFView/Open
Abstract.pdfAbstract55.43 kBAdobe PDFView/Open
Chapter I.pdfChapter I96.34 kBAdobe PDFView/Open
Chapter II.pdfChapter II103.49 kBAdobe PDFView/Open
Chapter III-VI.pdfChapter III-VI182.96 kBAdobe PDFView/Open
Reference.pdfReference75.54 kBAdobe PDFView/Open
Appendix.pdfAppendix64.93 kBAdobe PDFView/Open
 

Items in USU-IR are protected by copyright, with all rights reserved, unless otherwise indicated.