6632

بتول عظيمي

كارشناسي ارشد

رياضي كاربردي گرايش تحقيق در عمليات

پيام نور , كتابخانه مركزي دانشگاه پيام نور

1391

87ص

فرهمندراد، شهريار

احمدي آملي ، خديجه

87-85

پ عظيمي ، بتول , ع

جوهره مسائل زمان بندي به تصميم گيري در مورد تخصيص منابع و ترتيب عمليات منحصر مي شود و نوشته هاي مختلف مملو از مدل هاي رياضي براي پاسخگويي به اين دو سËال تصميم گيري است .به عبارتي زمان بندي، تخصيص منابع در طول زمان براي اجراي مجموعه اي از كارها است .نظريه زمان بندي شامل شيوه هاي متنوع و مختلفي است كه در حل مسائل زمان بندي مفيد واقع مي شوند .انتخاب شيوه مناسب به پيچيدگي مسÊله ، طبيعت مدل و انتخاب معيار كارايي و عوامل ديگر بستگي دارد .از آنجا كه زمان بندي كارگاه جرياني جايگشتي يك نوع خاص از مسائل زمان بندي كارگاه جرياني است بيشترين بحث را در اين پايان نامه به خود اختصاص داده و با تعيين ترتيب بهينه ي كارهايي كه قرار است روي تعدادي ماشين و در يك ترتيب ثابت پردازش شوند سرو كار پيدا مي -كند .بيشتر از 06 سال است كه با شروع از الگوريتم جانسون ، تحقيقات زيادي بر روي مسائل كارگاه جرياني انجام شده است .نتايج بدست آمده از اين تحقيقات نشان داده اند كه مسÊله زمان -بندي كارگاه جرياني hard - NPاست و الگوريتم هاي ارائه شده در اين زمينه جواب بهينه را حتي براي مسائل كوچك ، در زمان چندجمله اي بدست نمي دهند .از جمله الگوريتم هاي موجود و خوب براي حل مسائل كارگاه جرياني ، الگوريتم NEH، ارائه شده توسط نواز، انسكور و هم مي باشد كه براي مي نيمم سازي حداكثر زمان صرف شده به كار مي رود كه به دليل سادگي ، كيفيت جواب و پيچيدگي زمانش ، عمومي ترين الگوريتم موجود است

فصل اول : مقدمه اي بر زمان بندي. فصل دوم : مسÊله زمان بندي گارگاه جرياني جايگشتي . فصل سوم : مفهوم پيچيدگي در مسائل زمان بندي. فصل چهارم : ارائه ابتكاري جديد براي مسÊله كارگاه جرياني جايگشتي . فصل پنجم : بررسي نقاط ضعف و قوت و مقايسه ابتكار HEN با برخي ابتكارهاي ساختاري و اصلاح شده

1931/11/10

6632پ

1

20632