![](/images/graphics-bg.png)
A new heuristic procedure for quadratic assignment problems
Author
Source
al- Rafidain Journal of Computer Sciences and Mathematics
Issue
Vol. 1, Issue 2 (31 Dec. 2004), pp.153-172, 20 p.
Publisher
University of Mosul College of Computer Science and Mathematics
Publication Date
2004-12-31
Country of Publication
Iraq
No. of Pages
20
Main Subjects
Topics
Abstract AR
يشمل هذا العمل تطوير إجراء حدسي إيجادي لحل مسائل التعيين التربيعي و ذلك بعد استعراض الإجراءات المتوافرة و محاولة زيادة كفاءة الحلول القريبة الأمثلية المستحصلة باستخدام الإجراءات الإيجادية الحدسية المعروفة.
تستخدم التعيينات التربيعية في حل مجموعة واسعة من المسائل منها مسائل تصميم لوحات التحكم لتقليص وقت التنفيذ و توزيع أقسام الإنتاج على المواقع لتحقيق أفضل كلفة لانتقال المنتجات بين الأقسام.
يرتكز العمل الأساسي للبحث على تطوير إجراء إيجادي جديد من خلال عملية اتخاذ قرار محسنة مشتقة من طبيعة مسائل التعيين التربيعي و التي تعتبر من نوع آل (NP-Complete).
و لتقييم كفاءة الطريقة المطورة، و التي اعتمدت أسلوب بناء الحل، و مقارنتها مع إجراء (Vollman, Nugent and Zartler-VNZ) التي تعتبر إحدى أكفأ الإجراءات المستخدمة لحل مثل هذه المسائل، و التي تعتمد أسلوب تحسين حل أولي معطى.
توضح النتائج النهائية تحسنا ملحوظا في حلول المسائل المختلفة المتولدة عشوائيا، و من الطبيعي فإن وجود الحل الدقيق المستحصل بإجراءات السرد الكلي أكثر أهمية و ضرورة كمقياس لعمليات المقارنة بين الحلول الناتجة من الإجراءات المذكورة.
Abstract EN
In this work, a new heuristic procedure is developed for the solution of Quadratic assignment problems after illustrating various known procedures, and an attempt to increase the efficiency of near-optimal solutions obtained from known heuristic procedures is carried out.
Quadratic assignments are used for solving a wide range of problems such as the design of control panels to minimize execution time and the assignment of manufacturing departments among locations to achieve optimal product movements.
This work is based on developing a new heuristic procedure using an improved decision procedure developed form the NP-complete nature and environment of assignment problems.
In order to assess the efficiency of the new procedure, which depends on constructing the solution, a comparison is made with that of VNZ (for Vollmann, Nugent and Zartler) which is considered to be one of the most efficient procedures used for solving such problems, and which depends on improving a given initial solution.
Final results show a distinctive improvement in the solutions of the various randomly generated problems, and obviously, evidence of the exact solution gained using total enumeration techniques is far essential, as a measure, in the comparisons carried out between the resulting solutions of the mentioned procedures.
Three different tests are carried out in this work including 26 randomly generated problem, each is represented by adistance and a volume flow matrix with different matrix dimensions, to be employed in the process of evaluating the efficiency of the improved heuristic procedure in terms of solution accuracy and processing time consumption.
C++ was employed in constructing the program structures of the mentioned procedures.
American Psychological Association (APA)
al-Saati, Najla A.. 2004. A new heuristic procedure for quadratic assignment problems. al- Rafidain Journal of Computer Sciences and Mathematics،Vol. 1, no. 2, pp.153-172.
https://search.emarefa.net/detail/BIM-361047
Modern Language Association (MLA)
al-Saati, Najla A.. A new heuristic procedure for quadratic assignment problems. al- Rafidain Journal of Computer Sciences and Mathematics Vol. 1, no. 2 (2004), pp.153-172.
https://search.emarefa.net/detail/BIM-361047
American Medical Association (AMA)
al-Saati, Najla A.. A new heuristic procedure for quadratic assignment problems. al- Rafidain Journal of Computer Sciences and Mathematics. 2004. Vol. 1, no. 2, pp.153-172.
https://search.emarefa.net/detail/BIM-361047
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references : p. 172
Record ID
BIM-361047