منابع پایان نامه با موضوع
ماشين، الگوريتم، توالي

منابع پایان نامه با موضوع ماشين، الگوريتم، توالي

آذر ۷, ۱۳۹۷ 0 By admin3

نشاندهنده اين است که ماشين ها منتظر قرار دادن کارها روي خود هستند و بيکار مانده اند.
زمان هاي پردازش و موعد تحويل براي مثال ارائه شده
j
۱
۲
۳
۴
۵
۶
۷
۸
۱۰
۱۲
۳
۵
۷
۱۱
۹
۴
۷
۴
۲۰
۳۰
۹
۹
۱۳
۶
Dj
۳۲
۲۸
۴۳
۵۱
۳۰
۴۰
۴۷
۵۸
تکرار اول الگوريتم MRS2
obsy hop paralel J
Dj
t2j
Dj – t2j
۱
۳۲
۱۷
۱۵
۲
۲۸
۱۶
۱۲
۳
۴۳
۲۳
۲۰
۴
۵۱
۳۵
۱۶
۵
۳۰
۱۶
۱۴
۶
۴۰
۲۰
۲۰
۷
۴۷
۲۲
۲۵
۸
۵۸
۱۰
۴۸
تکرار دوم الگوريتم MRS2
J
Dj
t2j
Dj – t2j
۱
۳۲
۱۷
۱۵
۳
۴۳
۲۳
۲۰
۴
۵۱
۳۵
۱۶
۵
۳۰
۱۶
۱۴
۶
۴۰
۲۰
۲۰
۷
۴۷
۲۲
۲۵
۸
۵۸
۱۰
۴۸
هنگامي که الگوريتم شروع به کار مي کند. خواهيم داشت :
در فاز اول الگوريتم توالي مربوط به کارها را طبق توضيحات مندرج در الگوريتم مطابق جدول (۳-۸) به دست مي آوريم. براي تخصيص ماشين به اولين کار که کار شماره ۲ است، با توجه به اينکه زودترين ماشين در دسترس در مرحله اول و دوم بيش از يک ماشين است، به دلخواه يکي از آنها را انتخاب مي کنيم. در اينجا فرض مي کنيم کار ۲ را روي ماشين و قرار داده ايم. بنابراين زمان هاي ماشين ها بعد از به روز رساني به صورت زير در مي آيد : ، طبق جدول (۳-۹) کار۵ روي ماشين ها، مينيمم مقدار زمان ماشين ها در مرحله اول و مينيمم مقدار ماشين ها در مرحله دوم را به دست مي آوريم. اين مقدار متعلق به ماشين هاي واست. بعد از به روزرساني زمان ماشين ها به شکل زير است :
، در مراحل بعد به همين ترتيب کارها را روي ماشين هاي مربوطه قرار مي دهيم. نتايج نهايي الگوريتم شامل توالي کارها و ماشين هايي که آن کار در مرحله اول و دوم در جدول (۳-۱۰) ارائه شده است.
توالي به دست آمده براي کارها توسط الگوريتم MRS2
ترتيب انجام کارها
۲
۵
۴
۱
۳
۶
۷
۸
ماشين مرحله اول
ماشين مرحله دوم
برنامه توليد شده توسط الگوريتم پيشنهادي MRS2 براي مثال ارائه شده
ساختار الگوريتم پيشنهادي MRS3
الگوريتم پيشنهادي با استفاده از يک رويکرد پويا و مشابه الگوريتم MRS1 همزمان با توليد توالي کارها، کار تخصيص ماشين به کارها را نيز انجام مي دهد.
مراحل الگوريتم پيشنهادي به شرح زير مي باشد:
مرحله صفر:
فرض مي کنيم :
مرحله يک: در ابتدا با اين فرض که کليه کارها موجود قابل زمان بندي در زمان صفر هستند، زمان اتمام کارها را به دست آورده و با زمان موعد تحويل مقايسه مي کنيم. به عبارت ديگر مقدار را به ازاي تمامي کارها به دست مي آوريم، ابتدا اعداد مثبت را جستجو مي کنيم. ميان اعداد مثبت کاري که کوچکتري داشته باشد انتخاب مي شود. در صورتي که همه اعداد منفي باشند، کاري که مقدار بزرگتري دارد در اولويت است و چنانچه چند کار داراي مقدار برابر باشند کاري انتخاب مي شود که کوچکتري داشته باشد. بعد از انتخاب کار و ماشين هاي مربوطه، با توجه به فرمول به روز رساني زير زمان هاي جديد ماشين ها را به دست مي آوريم.
مرحله دو: اگر آنگاه
و يا اگر آنگاه
بعد از به روزرساني، کار زمانبندي شده از مجموعهحذف شده و به مجموعه اضافه شود.
مرحله سه: اگر ، اجراي الگوريتم متوقف مي شود و تابع هدف محاسبه مي شود. در غير اينصورت به مرحله يک بازمي گرديم.
الگوريتم پيشنهادي براي توضيح بيشتر توسط يک مثال ساده با ۸ کار و دو ماشين در هر مرحله حل شده است. زمان هاي پردازش مربوط به مرحله اول و مرحله دوم کارها به همراه زمان هاي موعد تحويل در جدول (۳-۱۱) ارائه شده است.
زمان هاي پردازش و موعد تحويل براي مثال ارائه شده
j
۱
۲
۳
۴
۵
۶
۱۰
۱۲
۳
۵
۷
۱۱
۷
۴
۲۰
۳۰
۹
۹
Dj
۳۲
۲۸
۴۳
۵۱
۳۰
۴۰
هنگامي که الگوريتم شروع به کار مي کند. خواهيم داشت : در فاز اول الگوريتم توالي مربوط به کارها را طبق توضيحات مندرج در الگوريتم مطابق جدول (۳-۱۲) به دست مي آوريم. در جدول (۳-۱۲) تمامي اعداد ستون مثبت است. لذا کاري انتخاب مي شود که کوچکتري داشته باشد.بنابراين کار ۳ انتخاب مي شود. چون کار ۳ در ۴ حالت خود کمترين مقدار را دارد يکي از آنها به دلخواه انتخاب مي شود.(ماشين و ماشين انتخاب شده است) بعد از به روز رساني زمان ماشين ها عبارتند از: طبق جدول (۳-۱۳) کار شماره ۴ انتخاب مي شود. کار ۴ به ماشين هاي و ماشين تخصيص داده مي شود. بعد از به روز رساني زمان ماشين ها عبارتند از: تکرارهاي بعدي الگوريتم مشابه تکرارهاي اول و دوم انجام مي شود. نتايج حاصل از توالي کارها و تخصيص ماشين ها به کارها در جدول (۳-۱۴) آمده است.
تکرار اول الگوريتم MRS3
Job Number
۱۰
۱۵
۱۷
۳۲
۱
۱۰
۱۵
۱۷
۳۲
۱۰
۱۵
۱۷
۳۲
۱۰
۱۵
۱۷
۳۲
۱۲
۱۲
۱۶
۲۸
۲
۱۲
۱۲
۱۶
۲۸
۱۲
۱۲
۱۶
۲۸
۱۲
۱۲
۱۶
۲۸
۳
۲۰
۲۳
۴۳
۳
۳
۲۰
۲۳
۴۳
۳
۲۰
۲۳
۴۳
۳
۲۰
۲۳
۴۳
۵
۱۶
۳۵
۵۱
۴
۵
۱۶
۳۵
۵۱
۵
۱۶
۳۵
۵۱
۵
۱۶
۳۵
۵۱
۷
۱۴
۱۶
۳۰
۵
۷
۱۴
۱۶
۳۰
۷
۱۴
۱۶
۳۰
۷
۱۴
۱۶
۳۰
۱۱
۲۰
۲۰
۴۰
۶
۱۱
۲۰
۲۰
۴۰
۱۱
۲۰
۲۰
۴۰
۱۱
۲۰
۲۰
۴۰
تکرار دوم الگوريتم MRS3
Job Number
۱۰
۲
۳۰
۳۲
۱
۱۳
۱۲
۲۰
۳۲
۱۳
۲
۳۰
۳۲
۱۰
۱۳
۱۷
۳۲
۸
۱
۱۷
۲۸
۲
۱۵
۹
۱۹
۲۸
۱۱
۱
۲۷
۲۸
۱۲
۵
۲۳
۲۸
۱۵

۵۳
۵۱
۴
۸
۱۳
۳۸
۵۱
۱۸

۵۳
۵۱
۵
۱۶
۳۵
۵۱
۱۳

۳۲
۳۰
۵
۱۰
۱۱
۱۹
۳۰
۱۶

۳۲
۳۰
۷
۱۴
۱۶
۳۰
۹
۸
۳۲
۴۰
۶
۱۴
۱۷
۲۳
۴۰
۱۲
۸
۳۲
۴۰
۱۱
۲۰
۲۰
۴۰
توالي به دست امده براي کارها توسط الگوريتم MRS3
ترتيب انجام کارها
۳
۴
۲
۶
۱
۵
ماشين مرحله اول
ماشين مرحله دوم
ساختار الگوريتم پيشنهادي MRS4
الگوريتم پيشنهادي با استفاده از يک رويکرد پويا، ابتدا توالي مورد نظر را به دست آورده و زودترين ماشين هاي در دسترس در دو مرحله را تعيين کرده و کارها را به ترتيب روي ماشين هاي به دست آمده قرار مي دهد. مرحله اول جريان کارگاهي را با و مرحله دوم را با نشان مي دهيم. همچنين فرض مي کنيم که ماشين موازي در مرحله اول وجود دارد که آنها را به صورت نشان مي دهيم. و ماشين موازي در مرحله دوم وجود دارد که آنها را به صورت نمايش مي دهيم. همچنين نشان دهنده ي زمان هاي پردازش مرحله اول و نشان دهنده ي زمان هاي پردازش مرحله دوم مي باشد. و در نهايت زمان هاي موعد تحويل کارها را بانمايش مي دهيم.
مراحل الگوريتم پيشنهادي به شرح زير مي باشد:
مرحله صفر:
فرض مي کنيم :
مرحله يک: مقدار را براي کليه کارها به دست آورده و به صورت صعودي مرتب مي کنيم. اولين کاري که پردازش مي شود مقدار کمتري دارد و به ترتيب آخرين کاري که پردازش مي شود مقدار بزرگتري دارد. .(در صورتي که بيش از يک کار داراي شرط انتخاب باشد کاري انتخاب مي شود که داراي زمان پردازش بزرگتري در مرحله اول خود مي باشد) کار انتخاب شده را روي زودترين ماشين هاي در دسترس از مرحله اول و دوم قرار مي دهيم. بعد از انتخاب ماشين براي کار انتخاب شده، با توجه به فرمول به روز رساني زير زمان هاي جديد ماشين ها را به دست مي آوريم.
مرحله دو: اگر آنگاه
و يا اگر آنگاه
بعد از به روزرساني، کار زمانبندي شده از مجموعهحذف شده و به مجموعه اضافه شود.
مرحله سه: اگر ، اجراي الگوريتم متوقف مي شود و تابع هدف محاسبه مي شود. در غير اينصورت به مرحله يک بازمي گرديم.
L نشان دهنده مجموعه کارهاي زمان بندي شده است و k مجموعه کارهاي باقي مانده جهت زمان بندي است. الگوريتم پيشنهادي براي توضيح بيشتر توسط يک مثال ساده با ۸ کار و دو ماشين در هر مرحله حل شده است. زمان هاي پردازش مربوط به مرحله اول و مرحله دوم کارها به همراه زمان هاي موعد تحويل در جدول (۳-۱۵) ارائه شده است.
زمان هاي پردازش و موعد تحويل براي مثال ارائه شده
j
۱
۲
۳
۴
۵
۶
۷
۸
۱۰
۱۲
۳
۵
۷
۱۱
۹
۴
۷
۴
۲۰
۳۰
۹
۹
۱۳
۶
Dj
۳۲
۲۸
۴۳
۵۱
۳۰
۴۱
۴۷
۵۸
چگونگي روش حل الگوريتم MRS4
j
۱
۲
۳
۴
۵
۶
۷
۸
۱۰
۱۲
۳
۵
۷
۱۱
۹
۴
۷
۴
۲۰
۳۰
۹
۹
۱۳
۶
۳۲
۲۸
۴۳
۵۱
۳۰
۴۱
۴۷
۵۸
۱۵
۱۲
۲۰
۱۶
۱۴
۲۱
۲۵
۴۸
طبق اعداد به دست آمده از جدول (۳-۱۶) توالي انجام کارها مطابق جدول (۳-۱۷) مي باشد. طبق توالي به دست آمده اولين کار انتخاب شده کار شماره ۲ مي باشد که با توجه به صفر بودن زمان ماشين ها يکي از ماشين هاي مرحله اول و مرحله دوم به دلخواه تخصيص داده مي شود. (در اينجا فرض مي کنيم کار ۲ را روي ماشين و قرار داده ايم) بعد از به روز رساني زمان ماشين ها بربابر است با: کار بعدي کار ۵ مي باشد. زودترين ماشين هاي در دسترس ماشين هاي و مي باشد.لذا کار ۵ را به اين ۲ ماشين تخصيص مي دهيم. بعد از به روز رساني زمان ماشين ها برابراست با: الگوريتم را ادامه مي دهيم تا زماني که مجموعه K تهي شود يا به عبارت ديگر کليه کارها زمانبندي شوند. نتايج نهايي الگوريتم شامل توالي کارها و ماشين هاي تخصيص يافته به کارها در مرحله اول و دوم در جدول (۳-۱۷) ارائه شده است.
توالي به دست آمده براي کارها و ماشين ها توسط الگوريتم MRS4
ترتيب انجام کارها
۲
۵
۱
۴
۳
۶
۷
۸
ماشين مرحله اول
ماشين مرحله دوم
فاز سوم- مسئله با زمان تحويل و زمان آماده کار
در اين بخش علاوه بر زمان هاي پردازش مرحله اول و دوم و زمان موعد تحويل، براي هر يک از کارها زمان ورود به کارگاه در نظر مي گيريم. در اين بخش الگوريتم MRS5,MRS6,MRS7 را پيشنهاد داده ايم.
ساختار الگوريتم پيشنهادي MRS5
الگوريتم پيشنهادي با استفاده از يک رويکرد پويا، ابتدا زودترين ماشين هاي در دسترس در دو مرحله را تعيين مي کند سپس توالي کارها را انجام مي دهد. مرحله اول جريان کارگاهي را با و مرحله دوم را با نشان مي دهيم. همچنين فرض مي کنيم که ماشين موازي در مرحله اول وجود دارد که آنها را به صورت نشان مي دهيم. و ماشين موازي در مرحله دوم وجود دارد که آنها را به صورت نمايش مي دهيم. همچنين نشان دهنده ي زمان هاي پردازش مرحله اول و نشان دهنده ي زمان هاي پردازش مرحله دوم مي باشد. و زمان هاي موعد تحويل کارها را بانمايش مي دهيم. و در نهايت را زمان هاي در دسترس بودن کارگاه يا به عبارت ديگر زمان ورود کار به کارگاه تعريف مي نمائيم.اين الگوريتم مشابه الگوريتم MRS2 مي باشد. تفاوت آنها در نحوه به روزرساني زمان ماشين ها به دليل اضافه نمودن زمان ورود به کارگاه مي باشد.
مراحل الگوريتم پيشنهادي به شرح زير مي باشد:
مرحله صفر:
فرض مي کنيم :
مرحله يک: در ابتدا با اين فرض که کليه کارها موجود قابل زمان بندي در زمان صفر هستند، زمان اتمام کارها را مطابق روش زيربه دست آورده و با زمان موعد تحويل مقايسه مي کنيم. به عبارت ديگر مقدار را به ازاي تمامي کارها به دست مي آوريم، سپس کاري که کمترين

مطلب مشابه :  دانلود پایان نامه دربارهمحیط زیست