7487

قدرت ثنايي

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

رياضي كاربردي

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

1392

90ص

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

90ص

پ ثنايي ، قدرت , ع

زمانبندي كارگاه جرياني با تعيين ترتيب كارهايي كه بر روي تعداد ماشين دريك ترتيب ثابت پردازش مي شوند ،سروكار دارد.در حالت كلي نشان داده شده است كه مسئله زمانبندي كارگاه جرياني -كامل است . الگوريتم هاي دقيق مانند برنامه ريزي صحيح وشاخه وكران بهينگي راتضمين مي كند،اما جواب بهينه را حتي براي مسايل كوچك در زمان چند جمله اي نمي دهند،اين روش ها نشان دادند كه جواب هاي كار آمد خوبي (نه لزومابهينه )در زمان معقول مي دهند. چند دهه است كه با شروع از الگوريتم جانسون تحقيقات زيادي روي مسايل كارگاه جرياني انجام شده است اما فقط تعداد بسيار كمي الگوريتم خوب وجودداردازجمله از آنها روش جانسون وپالمر ونواز براي مينيمم سازي ماكزيمم زمان تكميل به كار مي رود.در اين تحقيق چند تا ازالگوريتم ها را بررسي مي كنيم وبعد از توضيح مفهوم پيچيدگي ،در فصل 4 بااستفاده ازالگوريتم هاي تقريب ،كران هاي بسته براي الگوريتم زمانبندي كارگاه جرياني جايگشتي بدست مي آوريم .

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

2931/40/50

7487پ

1

21325