Using ant colony algorithm to solve NP-complete problems
Author
Source
Issue
Vol. 3, Issue 1 (31 Jul. 2011), pp.125-134, 10 p.
Publisher
University of Thi-Qar College of Science
Publication Date
2011-07-31
Country of Publication
Iraq
No. of Pages
10
Main Subjects
Topics
Abstract AR
تناولنا في هذا البحث نوعا من مسائل جدولة الماكنة الواحدة و بموعد تسليم ثابت.
الهدف من المسالة هو حساب موعد التسليم و إيجاد متتابعة النتاجات القديمة و إعادة ترتيب النتاجات الجديدة لتصغير المجموع الوزني النتاجات التبكير و التأخير و زمن الإتمام و علاقة النتاجات بموعد تسليمها.
و كذلك قمنا بإعداد بعض الخواص التي يمكن استخدامها لإيجاد أفضل موعد تسليم ثابت و متتابعة الإعمال.
هذه المسألة من الأنواع المعقدة (NP – hard) لذلك فإن وجود خوارزمية متعددة الحدود مقيدة (polynomial bounded algorithm) لإيجاد الحل الأمثل غير ممكن لذلك افترضنا خوارزمية مستعمرة النمل لإيجاد حلول كفؤة للمسالة.
النتائج الحسابية أظهرت إن خوارزمية مستعمرة النمل أعطت نتائج قريبة من الحل الأمثل.
Abstract EN
We consider the problem of scheduling jobs on a single machine about a common due date.
Our objective is to determine the common due date and processing sequence of new jobs together with the re-sequencing of old jobs which minimize the sum of jobs’ earliness / tardiness, completion time penalties and due date related penalty.
We drive properties that can be used to find the optimal common due date and processing sequence.
Since our problem is NP-hard, we propose Ant colony algorithm (ACO) to solve the problem efficiently.
Results from computational study reveal that Ant colony algorithm (ACO) can.
American Psychological Association (APA)
Abd al-Abbas, Wafa. 2011. Using ant colony algorithm to solve NP-complete problems. Journal of Thi-Qar Science،Vol. 3, no. 1, pp.125-134.
https://search.emarefa.net/detail/BIM-333001
Modern Language Association (MLA)
Abd al-Abbas, Wafa. Using ant colony algorithm to solve NP-complete problems. Journal of Thi-Qar Science Vol. 3, no. 1 (Jul. 2011), pp.125-134.
https://search.emarefa.net/detail/BIM-333001
American Medical Association (AMA)
Abd al-Abbas, Wafa. Using ant colony algorithm to solve NP-complete problems. Journal of Thi-Qar Science. 2011. Vol. 3, no. 1, pp.125-134.
https://search.emarefa.net/detail/BIM-333001
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references : p. 134
Record ID
BIM-333001