تحقیق رایگان درمورد مدل ریاضی، ارزیابی عملکرد، معیارهای ارزیابی

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

مجموع(وزنی) زمانهای دیرکرد به عنوان معیارهای ارزیابی عملکرد در این تحقیق مورد استفاده قرار گرفت.
هیو و لیانگ ]60[ مسئله زمانبندی ماشینهای موازی یکسان را با فرض دسترسی محدود به ماشینها و با هدف کمینهسازی بیشترین زمان تکمیل کارها مورد بررسی قرار دادند. آنها یک الگوریتم تقریب زننده برای این مسئله ارائه کردند و مدعی شدند که الگوریتم پیشنهادی آنها نسبت به سایر الگوریتمهای مورد استفاده توسط محققین در ادبیات تحقیق، تقریبهای بهتری از مسائل تولید میکند. سنتنو و آرماکست ]64[ مسئله مشابهی را با هدف کمینهسازی بیشینه زمان تاخیر در یک محیط واقعی که کارگاه تولید مواد نیمه رسانا بود، مطالعه نمودند. گلس و میلز ]57[ مسئله را با سه معیار عملکرد بیشینه زمان تکمیل کارها، میانگین زمان تکمیل کارها و تعداد کارهای با تاخیر برای یک واحد تولید مواد غذایی بررسی نموده و برای حل آنها از چند روش ابتکاری استفاده نمودند. گلس و کلرر ]56[ مسئله را در قالب مسئله تخصیص پردازندههای یک رایانه به برنامههایی که نیاز به پردازش دارند بررسی نمودند. پردازندهها دارای سرعت یکسان و ظرفیت حافظه متفاوت هستند. هر کدام از برنامهها برای اجرا به میزان مشخصی از حافظه پردازنده نیاز دارند و بدین ترتیب تنها توسط تعداد محدودی از پردازندهها میتوانند پردازش شوند.
2-10. جمعبندی
در ابتدای این فصل مروری کلی بر تاریخچه علم زمانبندی و توالی عملیات صورت پذیرفت. سپس توضیحات مختصری در رابطه با مسائل زمانبندی در قالب محیطهای کارگاهی، محدودیتهای پردازش و توابع هدف ارائه شد. در ادامه فصل، مروری بر پیشینه تحقیقات مرتبط با مسئله مورد بررسی در این تحقیق به تفکیک تابع هدف و محدودیتهای موجود در مسئله صورت پذیرفت.

فصل سوم

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

3-1. مقدمه
مسائل زمانبندی بطور گستردهای در محیطهای صنعتی و خدماتی که کارها باید بوسیله منابع محدود انجام شوند، کاربرد دارد. در هر مسئله زمانبندی، هدف و یا اهدافی مورد توجه میباشند و میزان ارضاء هدف (اهداف) مورد نظر به میزان زیادی تحت تاثیر مدل ایجاد شده برای مسئله میباشد. بنابراین روش مورد استفاده برای تعیین توالی بین کارها از اهمیت بالایی برخوردار است.
در بسیاری از مسائل روشهای ریاضی میتوانند ابزار مفید و در عین حال لازم برای تعیین توالی بهینه کارها را مهیا کنند. رویکرد برنامهریزی عدد صحیح104 به عنوان یک روش دقیق105 ظرفیت عملکردی محدودی در بهینهسازی مسائل زمانبندی در زمان محاسباتی معقول دارد. از سوی دیگر، بیشتر مسائل موجود در محیطهای تولیدی و یا خدماتی اندازه بزرگتری نسبت به ظرفیت محاسباتی مدلهای برنامهریزی عدد صحیح دارند. با این وجود، این مدلها جوابهای بهینه لازم برای توسعه و اعتبار سنجی عملکرد الگوریتمهای ابتکاری و فراابتکاری گوناگون را فراهم مینمایند.
در این فصل، مسئله زمانبندی ماشینهای موازی نامرتبط با فرض وجود امکان دوبارهکاری اقلام معیوب بههمراه محدودیتهای زمان دسترسی به کارها، زمان نصب وابسته به توالی کارها و وابسته به نوع ماشینآلات و دسترسی محدود به ماشینها با هدف کمینهسازی بیشترین زمان تکمیل کارها معرفی و مورد بررسی قرار میگیرد. در ادامه، برای مسئله یاد شده یک مدل برنامهریزی عدد صحیح ارئه میشود.
3-2. تعریف مسئله
مسئله زمانبندی ماشینهای موازی نامرتبط با فرض وجود امکان دوبارهکاری اقلام معیوب بههمراه محدودیتهای زمان دسترسی به کارها، زمان نصب وابسته به توالی کارها و وابسته به نوع ماشینآلات و دسترسی محدود به ماشینها با هدف کمینهسازی بیشترین زمان تکمیل کارها به شرح زیر ارائه میگردد:
یک مجموعه از n کار متمایز، N={1,2,…,n} ، بر روی مجموعهای از m M={1,2,…,m} ماشین که بصورت موازی کنار هم قرار گرفتهاند پردازش میشوند. هر کار حداقل نیاز به یک پردازش (در صورت عدم نیاز به دوبارهکاری) و حداکثر نیاز به L_j پردازش (حداکثر تعداد پردازش اصلی و دوباره کاری) دارد. ماشینها نامرتبط بوده و هر پردازش از هر کار تنها بر روی یک ماشین انجام میشود و هر ماشین در هر لحظه قادر به انجام تنها یک پردازش از هر کار میباشد. هر پردازش از هر کار بر روی زیر مجموعه ای از مجموعه ماشینها بصورت M_j میتواند پردازش شود که به این مجموعهها در اصطلاح مجموعههای پردازشی106 گفته میشود. بر روی هر کار در طول یک دوره حداقل یک پردازش و حداکثر L_j پردازش صورت میپذیرد که زمان مورد نیاز برای پردازش اصلی107 هر کار روی هر ماشین هم به نوع کار و هم به نوع ماشین بستگی دارد و زمانهای پردازش دوبارهکاری108 نه تنها به نوع کار و نوع ماشین که به تعداد فرآیندهای دوبارهکاری نیز وابسته است و تابعی از زمان پردازش اصلی میباشد. لازم به ذکر است که بین زمانهای پردازش کارها بر روی ماشینهای مختلف رابطه مشخصی وجود ندارد. قبل از آغاز پردازش هر کار روی هر ماشین، بهمنظور آمادهسازی آن ماشین برای پردازش آن کار عملیاتی انجام میگیرد که از آن با عنوان عملیات نصب روی ماشین یاد میشود و به مدت زمان مورد نیاز که برای عملیات نصب ماشین صرف میشود، زمان نصب ماشین109 اطلاق میشود. این زمان به نوع کار و شماره پرداش آن کار که قرار است روی ماشین پردازش شود، به نوع کار قبلی و شماره پردازش آن کار که روی ماشین پردازش شدهاست و همچنین به نوع ماشین که پردازش بر روی آن صورت میگیرد بستگی دارد و اصطلاحا از آن به عنوان زمان نصب وابسته به توالی کارها و نوع ماشین یاد میشود. هر پردازش از هر کار با در نظر گرفتن موقعیت آن در توالی، بر روی ماشین مربوطه پس از سپری شدن زمان نصب و زمان پردازش تکمیل میشود. تمام کارها در ابتدای افق زمانبندی در دسترس نیستند و زمان دسترسی به هر کار متفاوت است. معیار بیشینه زمان تکمیل کارها به عنوان تابع هدف به منظور ارزیابی مسئله زمانبندی ارائه شده مورد استفاده قرار میگیرد.
3-2. مفروضات مسئله
3-2-1: کار ها مستقل از یکدیگر میباشند.
3-2-2: در سیستم تولیدی، احتمال تولید اقلام معیوب وجود دارد.
3-2-3: تعداد دوبارهکاری برای هر قلم کالا محدود است.
3-2-4: هر ماشین در هر لحظه قادر به انجام یک پردازش از هر کار است.
3-2-5: هر پردازش از هر کار در طول زمان تکمیل خود تنها بر روی یک ماشین پردازش میشود و امکان شکست در کارها وجود ندارد.
3-2-6: کارهای مجازی110 مفروض است. این کارها همواره در اولین موقعیت بر روی تمامی ماشینها پردازش میشوند. زمان پردازش و زمان در دسترس بودن این نوع کار صفر منظور میشود و شروع پردازش آن نیازی به انجام عملیات نصب ماشین ندارد.
3-2-7: زمان آمادهسازی وابسته به توالی و وابسته به ماشین وجود دارد. بهعبارت بهتر، زمانهای آمادهسازی هم به توالی بین پردازشهای کارها و هم به نوع ماشینی که کارها روی آن پردازش میشوند، وابسته است.
3-2-8: زمان بازرسی هر قلم کالای تولیدی به عنوان بخشی از زمان پردازش آن کالا در نظر گرفته میشود.
3-2-9: بیکاری ماشینها مجاز است.
3-2-10: تمام ماشین ها بطور مستمر در دسترس هستند و امکان خرابی ماشین ها وجود ندارد.
3-2-11: برای هر کدام از پردازشهای هر قلم کالا، محدودیت دسترسی به ماشینها وجود دارد.
3-2-12:محدودیت زمان دسترسی به کارها وجود دارد.(تمام کارها در لحظه صفر در دسترس نیستند)
3-2-13: زمان پردازش اصلی، زمان نصب ماشین، ضرایب کاهنده زمان، احتمالات معیوب بودن اقلام تولیدی و زمانهای دسترسی به کارها معین میباشند.
3-3. مدل ریاضی پیشنهادی
در این بخش در ابتدا اندیسها و پارامترهای ورودی به مدل، متغیرهای تصمیمگیری، تابع هدف و محدودیتها بصورت جداگانه مورد بررسی قرار گرفته و تشریح میشوند. سپس مدل ریاضی پیشنهادی برای مسئله یاد شده ارائه میگردد.

3-3-1. اندیسها و پارامترهای ورودی به مدل
m: تعداد ماشینها
n : تعداد کارها
i: اندیس نوع ماشین (i=1,…,m)
j,h: اندیس نوع کار (j,h=1,…,n+m)
l, l’: اندیس شماره پردازش (l,l^’=1,…,L_j )
〖 p〗_ijl: احتمال معیوب بودن پردازش شماره lاز کار نوع j روی ماشین نوع i (〖 p〗_(ijL_j )=0)
)فرض بر این است که کار نوع j حداکثر L_j بار میتواند پردازش شود. (پردازش اصلی و پردازشهای دوبارهکاری)
t_ij : زمان مورد نیاز برای تکمیل پردازش اصلی از کار نوع j روی ماشین نوع i
α_ijl : ضریب کاهنده زمان پردازش برای فرآیندهای دوبارهکاری (0≤α_ijl≤1)
≤فرض بر این است که زمان مورد نیاز برای پردازش شماره l از کار نوع j درصدی از زمان مورد نیاز برای پردازش شماره (l-1) از کار نوع j میباشد.
pt_ijl : زمان مورد نیاز برای تکمیل پردازش شماره l از کار نوع j روی ماشین نوع i
i ( 〖pt〗_ij1=t_ij, pt_ijl=〖pt〗_(ij(l-1)).α_ijl )
〖su〗_ihl’jl : زمان نصب مورد نیاز برای شروع پردازش شماره l از کار نوع j هنگامیکه پس از پردازش شماره l’ از کار نوع h روی ماشین نوع i انجام میشود.
z_ijl : اگر امکان انجام پردازش شماره l از کار نوع j روی ماشین نوع i وجود داشته باشد 1، در غیر این صورت 0
R_j : زمان دسترسی به کار نوع j
M : یک عدد حقیقی مثبت بزرگ
3-3-2. متغیرهای تصمیمگیری
s_jl : زمان شروع پردازش شماره l از کار نوع j
c_jl : زمان تکمیل پردازش شماره l از کار نوع j
c_j : زمان تکمیل کار نوع j
x_ijl : اگر پردازش شماره l از کار نوع j روی ماشین نوع i انجام شود 1، در غیر اینصورت 0
y_hl’jl : اگر پردازش شماره l از کار نوع j دقیقا بعد از پردازش شماره l’ از کار نوع h انجام شود 1، در غیر اینصورت 0
3-3-3. تابع هدف
Min Z=C_max
یکی از پر کاربردترین توابع هدف در مسائل بهینهسازی ماشینهای موازی، کمینهکردن بیشترین زمان تکمیل کارها میباشد. چرا که این هدف سبب میشود کارها تا حد ممکن با یکنواختی بیشتری بین ماشینها توزیع شوند و به نحوی از ظرفیت کاری تمام ماشینها تا حد مطلوب استفاده شود و در نتیجه از تجمع کارها بر روی یک یا تعدادی از ماشینها جلوگیری به عمل میآید. از این رو معیار بیشترین زمان تکمیل کارها بهعنوان معیار بهینهسازی در این مسئله مورد استفاده قرار گرفته است.
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
فرآیندهای دوبارهکاری برای هر نوع کار مانند کار j از جنس احتمالی میباشند، بدین مفهوم که هر کار نوع jحداقل یک مرتبه (در صورت عدم نیاز به دوبارهکاری ) و حداکثر L_j مرتبه مورد پردازش قرار میگیرد. لذا بهدلیل احتمالی بودن جنس مسئله، از تئوری ارزش انتظاری111 بهمنظور تعیین زمان تکمیل کار نوع j استفاده میشود. به منظور فهم سادهتر عبارت ریاضی فوق، این عبارت به صورت ساده شده در ذیل نشان داده میشود:
O_ijl : عملیات پردازش شماره l از کار نوع j روی ماشین نوع i
E(C_j )=∑_(i=1)^m▒〖(C_j1 |است شده تکمیل O_ij1 در).(1-p_ij1 ).x_ij1 〗+ ∑_(i=1)^m▒〖(C_j2 |است شده تکمیل O_ij2 در)×[P_ij1.x_ij1.(1-p_ij2 ).x_ij2 ] 〗+…+ ∑_(i=1)^m▒(C_(jL_j ) |است شده تکمیل O_(ijL_j ) در) ×∏_(l^’=1)^(L_j-1)▒(∑_(i=1)^m▒〖p_(ijl^’ ).x_(ijl^’ ) 〗) .(1-p_(ijL_j ) ).x_ijl
3-3-4. محدودیتها
x_jj1=1; j=1,…,m
کارهای مجازی مفروض است. این محدودیت بیانگر آن است که به تعداد ماشینها (m)، کار مجازی وجود دارد. این کارها همواره در اولین موقعیت بر روی تمامی ماشینها قرار میگیرند. زمان پردازش و زمان در دسترس بودن این نوع کار صفر منظور میشود و شروع پردازش آن نیازی به انجام عملیات نصب روی ماشین ندارد.
∑_(i=1)^m▒〖x_ijl=1〗; ∀l, j=m+1,…,m+n
این محدودیت بیانگر آن است که هر پردازش از هر نوع کار بر روی یک و تنها یک ماشین میتواند پردازش شود.
s_j1=0; j=1,…,m
محدودیت فوق تضمین میکند که کارهای مجازی روی ماشینها در لحظه صفر

پایان نامه
Previous Entries پایان نامه ارشد رایگان درمورد امر به معروف، سوره معارج Next Entries پایان نامه ارشد رایگان درمورد ايمان، كسي، فردي