عنوان
بهره‌گيري از رويكرد برنامه‌ريزي مجموعه‌پاسخ براي حل مسئله‌ي جابجايي بلوك‌ها
نويسنده اصلي
جودكي، آساره
محل تحصيل
اصفهان : دانشگاه صنعتي اصفهان
رشته تحصيلي
مهندسي كامپيوتر
مقطع تحصيلي
كارشناسي ارشد
چكيده
مسئله‌ي جابه‌جايي بلوك‌ها BRP به‌عنوان يكي از مسائل مهم در حوزه‌ي بهينه‌سازي تركيبياتي و لجستيك مطرح است كه به‌ويژه در محيط‌هايي مانند انبارها و پايانه‌هاي كانتينري كاربرد گسترده‌اي دارد. در اين مسئله، بلوك‌ها به‌صورت پشته‌اي ذخيره مي‌شوند و هدف آن است كه بلوك‌ها بر اساس يك ترتيب از پيش تعيين‌شده بازيابي شوند، به‌گونه‌اي كه تعداد جابه‌جايي‌ها به حداقل برسد. تنوع و گستردگي نسخه‌هاي مختلف اين مسئله، تعلق آن به دسته‌ي مسائل NP-سخت، و همچنين نقش كليدي پايانه‌هاي كانتينري در حمل‌ونقل بين‌المللي و زنجيره‌ي تأمين، موجب شده است كه مسئله‌ي جابه‌جايي بلوك‌ها به يك چالش پژوهشي تبديل شود. از اين‌رو، پژوهش‌هاي متعددي بر توسعه‌ي روش‌هاي دقيق و غيردقيق براي دستيابي به راه‌حل‌هاي بهينه يا نزديك به بهينه، متمركز بوده‌اند.
در اين پژوهش، رويكرد برنامه‌ريزي مجموعه پاسخ ASP براي مدل‌سازي و حل دقيق مسئله‌ي جابه‌جايي بلوك‌ها مورد استفاده قرار گرفته است. اين رويكرد كه ماهيتي كاملاً اعلاني دارد، با بهره‌گيري از برنامه‌ريزي منطقي، امكان بيان مسئله را به‌صورت فشرده و شفاف فراهم مي‌كند، به‌گونه‌اي كه تمامي قيود و شرايط حاكم بر مسئله به‌شكل صريح و منسجم در مدل لحاظ مي‌شوند. افزون بر اين، استفاده از حل‌كننده‌هاي قدرتمند ASP امكان دستيابي به راه‌حل‌هاي دقيق در زماني قابل قبول را فراهم مي‌سازند. در چارچوب اين پژوهش و با هدف پوشش حداكثري تنوع ساختاري مسئله، هشت نسخه‌ي مختلف از مسئله‌ي جابه‌جايي بلوك‌ها به‌همراه مسئله‌ي پيش‌مرتب‌سازي، مدل‌سازي و حل شده‌اند.
يافته‌هاي اين تحقيق نشان مي‌دهد كه ASP به‌دليل ساختار اعلاني و انعطاف‌پذير خود، ابزاري مناسب و كارآمد براي حل دقيق مسئله‌ي جابه‌جايي بلوك‌ها به‌شمار مي‌رود. برخلاف بسياري از رويكردهاي دقيق متداول مانند برنامه‌ريزي عدد صحيح، كه بهره‌گيري از آن‌ها معمولاً به مدل‌هايي بسيار پيچيده با تعداد زيادي قيد منجر مي‌شود، و اغلب تنها براي يك نسخه‌ي خاص از مسئله طراحي مي‌شوند، و تعميم آن‌ها به ساير نسخه‌ها نيازمند بازطراحي اساسي مدل است، استفاده از ASP در اين پژوهش اين امكان را فراهم كرده است كه يك مدل پايه‌ي واحد تعريف شود و با اعمال تغييرات جزئي در آن، نسخه‌هاي مختلف مسئله به‌سادگي مدل‌سازي و حل شوند. نتايج حاصل از اجراي اين مدل‌ها بر روي بنچمارك‌هاي موجود نشان مي‌دهد كه حل‌كننده‌هاي ASP در زمان‌هاي محاسباتي معقول به راه‌حل‌هاي بهينه دست مي‌يابند كه اين امر بيانگر كارآمدي اين رويكرد در مواجهه با مسئله‌ي NP-سخت جابه‌جايي بلوك‌ها است.
شماره ركورد
237131
گرايش رشته تحصيلي
نرم‌افزار
دانشكده
مهندسي برق و كامپيوتر
دانشگاه
دانشگاه صنعتي اصفهان