تحقیق رایگان درمورد سلسله مراتب، تحلیل حساسیت، نظریه پیچیدگی

دانلود پایان نامه ارشد

شروع شوند. به بیان دیگر این محدودیت تضمین میکند که اولین کار روی هر ماشین یک نوع کار مجازی باشد.
c_jl=s_jl+∑_(i=1)^m▒〖(pt_ijl ).x_ijl 〗; ∀ j,l
این محدودیت در رابطه با محاسبه زمان تکمیل پردازش شماره l از کار نوع j میباشد که برابر با زمان شروع پردازش شماره l از کار نوع j بعلاوه مدت زمان مورد نیاز برای پردازش آن میباشد.
s_jl≥c_(j(l-1))+∑_(i=1)^m▒〖〖su〗_ihl’jl.〖x_ihl’.y〗_hl’jl 〗; ∀h,l^’ j=m+1,…,m+n l=2,…,L_j
s_jl≥[c_hl’+∑_(i=1)^m▒〖su〗_ihl’jl .x_ihl’-(1-y_hl’jl ).M]; ∀j,h,l,l’
این دو محدودیت بههمراه یکدیگر تضمین میکنند که پردازش شماره l از کار نوع j تنها زمانی میتواند شروع شود که فرآیند مقدم بر آن در توالی پردازشهای کارها تکمیل شده باشد. محدودیت اول مربوط به رعایت تقدم بین شماره پردازشهای مربوط به یک کار یکسان و محدودیت دوم مربوط به رعایت تقدم بین شماره پردازش های کارهای متفاوت میباشد.
s_j1≥R_j+∑_(i=1)^m▒〖〖su〗_(ihl^’ j1).〖x_ihl’.y〗_(hl^’ j1) 〗; ∀h,l^’ ,j=m+1,…,m+n
از آنجایی که تمام کارها در ابتدای افق زمانبندی در دسترس نیستند، لذا زمان دسترسی به کارها نیز باید در محدودیتها لحاظ شود. محدودیت فوق بیانگر این مطلب است که پردازش کار j نمیتواند پیش از زمان دسترسی به آن انجام شود. همچنین بدلیل آنکه زمان آمادهسازی وابسته به توالی بین کارها وجود دارد، زمان آمادهسازی بهمنظور سوئیچ کردن از پردازش شماره l^’ از کار نوع h به پردازش شماره 1 از کار نوع j روی ماشین i نیز در محدودیت فوق لحاظ میشود.
∑_(h=1)^(m+n)▒∑_(l^’=1)^(L_j)▒y_hl’jl =1; ∀l , j=m+1,…,m+n
∑_(j=1)^(m+n)▒∑_(l=1)^(L_j)▒y_hl’jl ≤1; ∀h,l’
این دو محدودیت به همراه یکدیگر نشان دهنده محدودیتهای تقدم و تاخر بین دو پردازش متوالی از کارهای یکسان یا متفاوت میباشند. بدین صورت که محدودیت اول بیان میکند که هرشماره پردازش از یک کار واقعی (غیر مجازی) حتما داری یک پردازش مقدم در توالی پردازشها میباشد که ممکن است یک کار مجازی و یا یک شماره پردازش از یک کار اصلی باشد. محدودیت دوم بیانگر این مطلب است که هر پردازش از هر کار در توالی پردازشها میتواند پردازش بعدی داشته باشد و یا نداشته باشد. (در صورتی پردازش بعدی ندارد که خود به عنوان آخرین فرآیند روی ماشین پردازش شود)
y_hl’jl≤∑_(i=1)^m▒〖x_ihl’.x_ijl;〗 ∀j,h,l,l’
این محدودیت بیان میکند که یک توالی زمانی معتبر است که شماره پردازش کارهای موجود در آن توالی روی یک ماشین انجام شده باشند. به عبارت دیگر توالی y_hl’jl یک توالی معتبر است اگر و تنها اگر پردازش شماره l از کار j و پردازش شماره l’ از کار h روی ماشین i انجام گرفته باشند. محدودیت فوق یک محدودیت غیر خطی است و لذا تلاش بر این است که در قالب یک محدودیت خطی بیان شود. از این روی میتوان محدودیت فوق را با استفاده از تکنیکهای خطی سازی بصورت زیر نیز بازنویسی کرد.
y_hl’jl≤1-x_ihl’+x_ijl ∀i,j,h,l,l’

x_ijl≤z_ijl i=1,…,m ; j=1,…,m+n ; l=1,…, L_j
این محدودیت نشان دهنده محدودیت دسترسی به ماشینها میباشد. همانطور که در بخش پارامترهای ورودی به مدل بیان شد، اگر امکان انجام پردازش شماره l از کار j روی ماشین نوع i وجود داشته باشد پارامتر z_ijl مقدار یک و در غیر اینصورت مقدار صفر را اختیار میکند. امکان انجام پردازش شماره l از کار j روی ماشین نوع i با توجه به مجموعه پردازشی کار نوع j یعنیM_j مشخص میشود. M_( j)زیر مجموعه ای از مجموعه ماشینها و شامل ماشینهایی میباشد که میتوانند کار نوع j را انجام دهند. بدین ترتیب این محدودیت مدل را مقید میسازد که برای تخصیص ماشین نوع i به کار نوع j و به تبع آن تخصیص مقدار یک به متغیر تصمیم گیری x_ijl ، مقدار z_ijl را که جزء پارامترهای ورودی مدل میباشد را نیز بررسی نماید و در صورتی این تخصیص صورت می پذیرد که مقدار z_ijl نیز همانند x_ijl یک باشد.
x_ijl , y_hl’jl={0,1} ; ∀i,j,h,l,l’
محدودیت فوق محدویت منطقی112 در مدل میباشد.

با توجه به توضیحات ذکر شده مدل ریاضی بصورت زیر ارائه می شود:
Min Z=C_max
Subject to:
C_max≥E(C_j ); ∀j
E(C_j ) =∑_(i=1)^m▒c_j1 .(1-p_ij1 ).x_ij1+∑_(l=2)^(l_j)▒(∑_(i=1)^m▒〖c_jl.∏_(l^’=1)^(l-1)▒(∑_(i=1)^m▒〖p_(ijl^’ ).x_(ijl^’ ) 〗) 〗×(1-p_ijl ).x_ijl ) ; ∀ j
x_jj1=1; j=1,…,m
∑_(i=1)^m▒〖x_ijl=1〗; ∀l, j=m+1,…,m+n
s_j1=0; j=1,…,m
c_jl=s_jl+∑_(i=1)^m▒〖(pt_ijl ).x_ijl 〗; ∀ j,l
s_jl≥c_(j(l-1))+∑_(i=1)^m▒〖〖su〗_ihl’jl.〖x_ihl’.y〗_hl’jl 〗; ∀h,l^’, j=m+1,…,m+n l=2,…,L_j
s_jl≥[c_hl’+∑_(i=1)^m▒〖su〗_ihl’jl .x_ihl’-(1-y_hl’jl ).M]; ∀j,h,l,l’
s_j1≥R_j+∑_(i=1)^m▒〖〖su〗_(ihl^’ j1).〖x_ihl’.y〗_(hl^’ j1) 〗; ∀h,l^’ ,j=m+1,…,m+n
∑_(h=1)^(m+n)▒∑_(l^’=1)^(L_j)▒y_hl’jl =1; ∀l , j=m+1,…,m+n
∑_(j=1)^(m+n)▒∑_(l=1)^(L_j)▒y_hl’jl ≤1; ∀h,l’
y_hl’jl≤∑_(i=1)^m▒〖x_ihl’.x_ijl;〗 ∀j,h,l,l’
x_ijl≤z_ijl i=1,…,m ; j=1,…,m+n ; l=1,…, L_j
x_ijl , y_hl’jl={0,1} ; ∀i,j,h,l,l’

3-4. اعتبار سنجی مدل
در بخش پیش رو بهمنظور سنجش درستی عملکرد مدل پیشنهادی و تحلیل حساسیت مدل نسبت به تغییر در مقادیر پارامترهای ورودی، از مباحث تحلیل حساسیت بهره گرفته شده است. در ابتدا حساسیت مدل نسبت به فعال بودن و یا نبودن محدودیت دسترسی به ماشینها ارزیابی گردیده و در گام بعدی حساسیت مدل نسبت به تغییر در میزان مقادیر زمانهای نصب وابسته به توالی و وابسته به نوع ماشین سنجیده میشود.
شکل3-1 حل گرافیکی یک مسئله ساده با دو ماشین، سه کار و سه پردازش برای هر کار (m=2,n=3,L=3) در شرایطی که محدودیتی برای دسترسی کارها به ماشینها وجود ندارد را نمایش میدهد. همانطور که پیشتر بدان اشاره شد، به تعداد ماشینها، کارهای مجازی با زمان پردازش، زمان در دسترس بودن و زمان نصب برابر صفر در مدل لحاظ میشود. لذا به طول انجامیدن کار مجازی شماره یک روی ماشین اول نه بهمعنای زمان پردازش کار مجازی بلکه بهمعنای زمان دسترسی به کار شماره 3 میباشد. علاوه بر این، بهمنظور پردازش کار شماره 3 بهعنوان اولین کار روی ماشین اول به 11 واحد زمانی برای نصب و راهاندازی ماشین نیاز است. همچنین همانگونه که مشخص است، زمان نصب برای پردازشهای متوالی از یک کار (کار شماره 4) روی یک ماشین (ماشین شماره یک) صفر در نظر گرفته شده است. مقدار تابع هدف در شرایط فعال نبودن محدودیت دسترسی به ماشینها برابر 65.741 میباشد.

شکل3-1. حل گرافیکی مسئله (m=2,n=3,L=3) در شرایط فعال نبودن محدودیت دسترسی به ماشینها

در ادامه، محدودیت دسترسی کارها به ماشینها بصورت زیر فعال میشود:

همانگونه که در بالا نشان داده شده است، کارهای شماره 3 و 5 بههمراه پردازشهای دوبارهکاری آنها فقط روی ماشین اول و کار شماره 4 بههمراه پردازشهای دوبارهکاری آن فقط روی ماشین دوم قابل پردازش است. پس از اعمال کردن محدودیتهای فوق در مدل، حل گرافیکی مدل در شکل3-2 نمایش داده شده است. همانگونه که مشخص است، محدودیتهای فوق در خروجی مدل لحاظ شده است و مقدار تابع هدف برابر با 88.4853 گردیده که نسبت به حالت قبل بدتر شده است. در نتیجه مشخص شد که مدل نسبت به فعال بودن و یا نبودن محدودیت دسترسی به ماشینها حساسیت نشان میدهد. در ادامه، حساسیت مدل نسبت به تغییر در میزان مقادیر ورودی سنجیده میشود.

شکل3-2. حل گرافیکی مسئله (m=2,n=3,L=3) در شرایط اعمال محدودیت دسترسی به ماشینها
شکل3-3 حل گرافیکی مسئله (m=2,n=3,L=3) را در شرایطی نشان میدهد که زمان نصب مورد نیاز برای آمادهسازی پردازش کار شماره 3 بهعنوان اولین کار روی ماشین شماره 1 به میزان10 واحد زمانی افزایش پیدا کرده و از 11 واحد زمانی به 21 واحد زمانی رسیده است. نتایج حاکی از آن است که مدل نسبت به افزایش در زمان نصب و راهاندازی کار شماره 3 بهعنوان اولین کار روی ماشین اول حساسیت نشان داده است و پردازش اصلی کار شماره4 جایگزین کار شماره 3 بهعنوان اولین پردازش روی ماشین اول گردیده است. همچنین دومین پردازش از کار شماره4 به ماشین شماره 2 و پردازشهای دوبارهکاری کار شماره 5 به ماشین شماره 1 منتقل شدهاند و در نهایت مقدار تابع هدف برابر با 71.5502 گردیده است که نسبت به مسئله اولیه بدتر شده است.

شکل3-3. حل گرافیکی مسئله (m=2,n=3,L=3) در شرایط افزایش در زمان نصب کار شماره 3
لازم به ذکر است که هر سه مسئله یاد شده توسط نرمافزار LINGO 9.0 حل شده و نتایج در قالب اشکال فوق ارائه گردیده است.
نتایج بدست آمده از تغییر در میزان مقادیر پارامترهای ورودی به مدل و فعال یا غیرفعال بودن محدودیتها که در بالا به آنها اشاره شد بیانگر این موضوع است که مدل پیشنهاد شده برای مسئله زمانبندی ماشینهای موازی نامرتبط با فرض وجود امکان دوبارهکاری اقلام معیوب بههمراه محدودیتهای زمان دسترسی به کارها، زمان نصب وابسته به توالی کارها و نوع ماشینآلات و دسترسی محدود به ماشینها با هدف کمینهسازی بیشترین زمان تکمیل کارها در حل مسائل با شرایط گوناگون بهدرستی عمل کرده و از اعتبار لازم برخوردار است. شایان ذکر است که حساسیت مدل نسبت به تغییر در مقادیر سایر پارامترهای ورودی به مدل از جمله تعداد فرآیندهای دوبارهکاری، تعداد کارها، تعداد ماشینها و ضرایب کاهنده زمان سنجیده شده و نتایج بدست آمده از درستی عملکرد مدل خبر میدهند. واضح است که ارائه تمامی نتایج مربوط به مباحث تحلیل حساسیت در قالب پایاننامه پیش رو از حوصله بحث خارج است.

3-5. پیچیدگی مسئله
پیچیدگی مسئله بهمعنای میزان محاسبات مورد نیاز در یک الگوریتم حل113 به منظور رسیدن به جواب بهینه میباشد و در شاخهای از علم کامپیوتر با عنوان نظریه پیچیدگی114 مورد بررسی قرار میگیرد. در صورتی که با بزرگ تر شدن اندازه مسئله، زمان مورد نیاز برای حل مسئله توسط الگوریتم حل از یک الگوی چندجملهای پیروی نماید، الگوریتم حل از درجه چندجملهای115 میباشد. بسیاری از مسائل مهم در زمینه مسائل زمانبندی در کلاس مسائل Np-hard و Strongly NP-hard قرار دارند بدین مفهوم که الگوریتم چند جملهای که قادر به حل این مسائل در زمان محاسباتی معقول باشد، یافت نمیشود و برای حل این مسائل در یک زمان قابل قبول نیاز به الگوریتمهای ابتکاری116 و فراابتکاری117 میباشد.
در مسائل زمانبندی، در مواردی یک مسئله را می توان حالت خاصی از یک مسئله دیگر دانست. برای مثال مسئله 1||∑▒C_j را می توان حالت خاصی از مسئله 1||∑▒〖W_j C_j 〗 دانست. در مجموعه واژگان نظریه پیچیدگی این حالت را بصورت 1||∑▒〖W_j C_j 〗 ∝ 1||∑▒C_j نشان میدهند. بدین ترتیب زنجیرهای از مسائل زمانبندی قابل تولید است که در آن الگوریتمهای حل و پیچیدگی مسائل مختلف به یکدیگر مربوط میشود. پیندو ]4[ سلسله مراتب پیچیدگی مسائل مختلف زمانبندی را بصورت زیر ارائه مینماید. با توجه به این گرافها این نتیجه حاصل میشود که تغییر در عناصر مسائل زمانبندی مانند تغییر در نوع تابع هدف، جزئیات نحوه پردازش و محدودیتهای موجود و نوع محیط کارگاهی موجب تغییر در میزان پیچیدگی آنها میشود.

شکل3-4. سلسله مراتب پیچیدگی محیطهای کارگاهی در مسائل زمانبندی ]4[

شکل 3-5. سلسله مراتب پیچیدگی جزئیات نحوه پردازش و محدودیتها در مسائل زمانبندی ]4[

شکل 3-6. سلسله مراتب پیچیدگی توابع هدف در مسائل زمانبندی ]4[

شکل 3-7. سلسله مراتب پیچیدگی تعدادی از مسائل زمانبندی با تابع هدف Makespan ]4[
گری و جانسون ]67[ نشان دادند که مسئله زمانبندی ماشینهای موازی با تابع هدف کمینهکردن بیشینه زمان تکمیل کارها (P_m ||C_max ) در دسته مسائل Strongly NP-hard قرار میگیرد. بنابراین مسئله زمانبندی ماشینهای

پایان نامه
Previous Entries پایان نامه ارشد رایگان درمورد ايمان، كسي، فردي Next Entries تحقیق رایگان درمورد الگوریتم ژنتیک، فرآیند ارزیابی، انتخاب طبیعی