مقالات کنفرانس بين المللي انجمن ايراني تحقيق در عمليات

در اين تحقيق به کاربرد الگوريتم ژنتيک (GA) براي حل مساله حجم- محدود مسيريابي وسايل نقليه (CVRP) پرداخت شده است. در اين مساله هدف يافتن مسيرهاي بهينه براي تعدادي مشخص وسيله نقليه است که هر کدام حجم معيني دارند و بايد سفارش مشتري ها را از يک انبار مرکزي به آنها برسانند. بهترين نتايج شناخته شده براي اين مسايل از به کارگيري الگوريتم هاي ابتکاري جستجوي ممنوع و بازپخت شبيه سازي شده به دست آمده است. الگوريتم هاي ژنتيک به صورت گسترده در مسايل مختلف بهينه سازي از جمله در شکل هايي از مساله مسيريابي وسايل نقليه به کار گرفته شده اند. الگوريتم ژنتيک استاندارد نتوانسته جواب هايي قابل رقابت با بهترين نتايج شناخته شده توليد کند. در اين مقاله الگوريتم ژنتيک استاندارد با الگوريتم هاي جستجوي همسايگي ترکيب شده است تا بتواند جواب هايي قابل رقابت با جستجوي ممنوع و بازپخت شبيه سازي شده توليد کند. نتايج ارايه شده از حل مسايل استاندارد (گرفته شده از (OR_Library با ساخت نرم افزاري به زبان دلفي محاسبه شده است که داراي درصد خطاي بسيار پايين نسبت به بهترين جواب ها، مي باشد.

در اين مقاله مساله انتخاب سبد سهام بر اساس مدل استاندارد ميانگين- واريانس مارکوويتز به همراه دو محدوديت مازاد جهت کاربردي تر نمودن مدل، درنظر گرفته شده است. مدل استاندارد بدون لحاظ محدوديت هاي مازاد، يک مدل غيرخطي درجه دوم و با لحاظ آنها يک مدل غيرخطي عدد صحيح ميباشد. از آنجا که اغلب، يافتن جواب بهينه براي اين نوع مسايل ميسر نيست، استفاده از الگوريتم هاي ابتکاري ضروري به نظر مي رسد. در گذشته الگوريتم هاي ابتکاري اي عموما بر اساس الگوريتم هاي ژنتيک، Tabu Search، Simulated Annealing و شبکه هاي عصبي مصنوعي براي حل اينگونه مسايل توسعه داده شده اند. در اين مقاله از الگوريتم ايمني مصنوعي براي حل اين نوع مسايل و تعيين مجموعه جواب هاي موثر (منحني ترکيبات کارا) استفاده شده است. نتايج تجربي بدست آمده از حل پنج مساله انتخاب سبد سهام توسط الگوريتم پيشنهادي و مقايسه آن با نتايج الگوريتم هاي پيشين حاکي از برتري نسبي الگوريتم پيشنهادي است.

هسته زير فضايي از فضاي راه حل را مشخص مي کند که در آن راه حل بهينه قرار دارد. در اين مقاله روشي براي شناسايي هسته تقريبي مساله کوله پشتي با چند انتخاب در دو بعد عرضه شده است. اين هسته بر مبناي رابطه بين راه حل بهينه مساله با راه حل بهينه خطي و راحت شده آن توسعه يافته است. بر اساس اين هسته الگوريتم شاخه و قيدي براي حل دقيق مساله توسعه يافته است که فضاي هسته را شمارش کرده و در صورت نياز آن را بزرگ مي کند. الگوريتم حاصل در مقايسه با بهترين الگوريتم حل اين مساله داراي مصرف حافظه با مرتبه کمتر و نتايج تست عملي نشان دهنده بهبود نسبي کارايي و پايداري الگوريتم مي باشند.

زمان بندي کار پرسنل بيمارستان عبارت است از تعيين برنامه کاري دوره اي براي هر يک از پرسنل بيمارستان، به طوريکه،(1  کليه کارهاي بيمارستان توسط پرسنل انجام شود. (2 خواسته هاي پرسنل براي انتخاب ساعت کاري، لحاظ شود. (3 هزينه بيمارستان حداقل شود. در اين مقاله زمان بندي پرسنل بيمارستان نمازي شيراز که يکي از بزرگترين بيمارستانهاي جنوب کشور است مورد بررسي قرار گرفته شده است. در اين بيمارستان شش نوع شيفت کاري صبح، عصر، شب، صبح- عصر، صبح- شب و تعطيل وجود دارد. در بخش جراحي اين بيمارستان که شامل 25 پرسنل پرستاري، بهياري و کمک بهياري است احتياج به برنامه هاي هفتگي براي هر يک از پرسنل مي باشد اين برنامه ها علاوه بر سه ويژگي بالا، بايد به گونه اي باشند که (4 اضافه کاري پرسنل حداقل شود.  (5تعداد پرسنل قرضي از واحدهاي ديگر تا حد امکان کم شود. (6 برنامه هاي هفتگي داراي حداقل شيفتهاي صبح- عصر و صبح- شب باشند و بين تعداد شيفتهاي صبح و عصر تعادل باشد. (7 حداقل تعداد شيفت شب هر پرسنل که به سابقه کاري آن پرسنل بستگي دارد، در برنامه هاي هفتگي رعايت شود. مساله زمان بندي بيمارستان نمازي شيراز يک مساله اعداد صحيح است که حل آن بوسيله مدل اعداد صحيح و توسط نرم افزار هاي موجود در ايران زمان بر است. از طرفي بزرگ شدن تعداد پرسنل بصورت نمايي در زمان حل تاثير گذار مي باشد.

روش هوشمند "آتوماتاي يادگيري تقويتي انتخابي" يک روش ابتکاري جهت حل مسايل بهينه سازي است، که ايده آن از رفتار موجودات زنده هنگام يادگيري برگرفته شده است. اين تکنيک براي حل انواع مسايل برنامه ريزي پويا و شبکه قابل استفاده مي باشد. در اين مقاله براي آزمودن کارايي الگوريتم، مساله فروشنده دوره گرد مدلسازي و حل شده است و در نهايت ضريب کارايي روش نسبت به جواب بهينه به دست آمده است.

مقايسه هاي ابتدايي بين فرآيند طبيعي تکامل با فرآيند بهينه سازي منجر به به وجود آمدن روش هايي به نام الگوريتم هاي تکاملي (EA) شد. در اين الگوريتم ها مهم ترين هدف شبيه سازي فرآيند تکامل به وسيله کامپيوتر است. به طور کلي سه نمونه جامع از الگوريتم هاي تکاملي شناخته شده اند که عبارتند از: استراتژي هاي تکامل، برنامه ريزي تکاملي و الگوريتم ژنتيک.

دراين مقاله از بهينه سازي کلوني مورچگان ترکيب شده با روش جستجوي ممنوع براي مساله زمان بندي توليد کارگاهي استفاده شده است. بجاي روش هاي متداول براي ايجاد يک زمان بندي مجاز از روش جديد تجزيه که از فرآيند تغييرسمت دادن گلوگاه "shifting bottleneck procedure" و مکانيزم باز بهينه سازي زمان بندي هاي جزيي الهام گرفته شده است. در ضمن روش جستجوي ممنوع براي بالا بردن کيفيت جواب بکار برده شده است.
در مساله زمان بندي توليد کارگاهي يک مجموعه متناهي از کارها بايد توسط يک مجموعه متناهي از ماشين ها پردازش شوند، هر کار از يکسري ترتيب اجرايي روي ماشين ها پيروي مي کند؛ بعلاوه زمان پردازش هر شغل روي يک ماشين قطعي است، هر ماشين در يک زمان ميتواند حداکثر يک کار را انجام دهد که اين تابع قيود فصلي و عطفي مي باشد، همچنين يک کار پس از شروع تا زمان اتمامش نميتواند به وقفه بيفتد. اين مساله در حالت کلي يک مساله NP-hard مي باشد.

مساله تخصيص (به کارگماري) که در نظريه گراف به مساله ازدواج معروف است، يکي از حالات خاص و در عين حال بسيار پرکاربرد از مسايل برنامه ريزي خطي مي باشد. با توجه به شرايط خاص مساله تخصيص تاکنون تحقيقات زيادي بر روي آن و به ويژه شيوه حل آن انجام گرفته است. در اين مقاله به ارايه يک اثبات ابتکاري در صحت اين روش مي پردازيم. ايده اين اثبات کاملا ابتکاري بوده و از هيچ يک از مقدمات نظري حل مسايل برنامه ريزي خطي استفاده نمي نمايد. اين ايده مي تواند در حل مسايل مشابه بهينه سازي شبکه مورد استفاده قرار گيرد.

خلاصه:
در اين مقاله الگوريتمي را معرفي خواهيم کرد که مساله  Bin Packingرا که يکي از مسايل مهم شاخه بهينه سازي ترکيبياتي است و مساله اي NP-complete مي باشد، را در زمان O(n²) حل کند.

يکي از اساسي ترين مشکلات روشهاي نقطه دروني براي حل مسايل برنامه ريزي خطي، پيدا کردن يک نقطه شدني در فضاي جواب مساله LP مي باشند. بدليل محدب بودن فضاي جواب ميتوان از هر نقطه شدني، مسيري مستقيم به نقطه بهينه پيداکرد. براي يافتن اين مسير الگوريتم هاي فراواني وجود دارد. در اين مقاله سعي شده است با توسيع فضاي جواب يک مساله برنامه ريزي خطي، مشکل نقطه شدني اوليه حل شود. سپس به کمک يک روش هندسي راستاي اين مسير را از اين نقطه شدني به نقطه بهينه در مساله توسيع يافته، مي يابيم. متناظر با اين نقطه بهينه، در مساله اصلي ميتوان به نقطه بهينه دست يافت.

در اين مقاله در دو مرحله جوابهايي تقريبي قابل استفاده براي مسايل برنامه ريزي توليد مي کنيم، که در واقع از برنامه ريزي پارامتري فازي و برنامه ريزي خطي فازي انتگرال گيري مي کنيم، تا براي مساله برنامه ريزي چند هدفه با ضرايب فازي جوابهايي واقعي بدست آوريم. همچنين يک بهينه سازي متقابل براي رسيدن به جواب بهينه براي همه مسايل برنامه ريزي چند هدفه با درجه ها و دقتهاي متفاوت ارايه مي کنيم. در اين دو مرحله در مرحله اول يک خانواده از بردارهاي بهينه را با کمک روش توليد مي کنيم، و در مرحله دوم با مدل مساله را حل مي کنيم.

موضوع زمانبندي عمليات با زمانهاي راه اندازي وابسته در يک مدل n کار و يک ماشين(n/1)  همواره مورد نظر محققان قرار گرفته است. عليرغم روشهاي توسعه داده شده بدليل پيچيدگي مسايل و زمان بر بودن حل آنها اين موضوع هنوز مورد توجه محققان خصوصا مديران اجراِِيي مي باشد. در اين مقاله سعي شده است بر اساس کاربرد قضاياي تحقيق در عمليات و خواص فضاي حل مدلهاي خطي يک الگوريتم جديد که بتواند به راحتي ترتيب عمليات n/1 را در حالتيکه داراي زمانهاي راه اندازي وابسته بوده را ارايه نمايد، توسعه داده شود. دسترسي سريع به جواب و حل مساله يکي از خصوصيات بارز اين روش مي باشد در حاليکه تمامي روشهاي قبلي داراي زمانهاي حل بسيار طولاني هستند.

هدف از اين مقاله، طراحي و بکارگيري مدلي است که تاثير پارامترهاي موثر در عملکرد الگوريتم ژنتيک را براي مساله فروشنده دوره گرد تعيين نمايد. به منظور دستيابي به اين هدف از رويکرد طراحي آزمايش ها براي تعيين و تخمين ضرايب مدل رياضي استفاده شده است. به کمک روش پيشنهادي مي توان براي يک مساله خاص، رابطه رياضي هر يک از پارامترها را بر سرعت همگرايي و کيفيت جواب هاي الگوريتم تعيين نمود. به منظور صحه گذاري مدل رياضي پيشنهادي و تعيين تاثير پارامترها، اين مدل بر روي مساله استاندارد فروشنده دوره گرد (att 48) پياده سازي و اجرا شده است. نتايج محاسباتي نشان دهنده بهبود قابل توجه عملکرد الگوريتم با استفاده از پارامترهاي تنظيمي حاصل از مدل است. روش به کار رفته قادر است براي ساير مسايل بهينه سازي نيز سطح مناسب پارامترها را تعيين نمايد.