۰

 

در جدول بالا عدد یک در هر درایه نشان دهندهی امکان پردازش کار متناظر با سطر بر روی ماشین متناظر با ستون آن درایه میباشد و عدد صفر عدم امکان پردازش کار بر روی ماشین میباشد.
نتایج محاسباتی:
جدول ۳-۵٫ نتایج محاسباتی برای مسأله ۶ کار و ۳ مرحله

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

مدل ریاضی	Runtime		Optimal solution
مدل ارائه شده	۰′:۰۵″		۰
مدل بهنامیان	۰′:۰۶″		۰

۳-۶.پیچیدگی مسأله
یک دیدگاه سودمند در زمینه مسائل زمانبندی و روشهای حل آنها از شاخهای از علم کامپیوتر با عنوان نظریه پیچیدگی[۵۲] حاصل میشود. پیچیدگی به مفهوم میزان محاسبات مورد نیاز در یک الگوریتم حل[۵۳] میباشد. به عنوان مثال در مسألهای با اندازه n (n نمایانگر میزان اطلاعات لازم برای مشخص شدن مسأله میباشد) تعداد محاسبات لازم برای حل مسأله با یک حد بالا که تابعی از n میباشد، محدود میشود [۷]. در این شرایط هرگاه با افزایش مقدار n میزان محاسبات لازم با استفاده از الگوریتم حل مسأله به صورت یک تابع چند جملهای از n باشد، الگوریتم حل از درجه چندجملهای[۵۴] میباشد. در شرایط یکسان برای حل یک مسأله، الگوریتمهای چند جملهای نسبت به الگوریتمهای غیر چند جملهای سریعتر و عملکرد آنها موجهتر است [۷].
بسیاری از مسائل مهم ترکیباتی نظیر اکثر مسائل زمانبندی در کلاس مسائل NP hard قرار میگیرند. میزان پیچیدگی این مسائل به گونهای است که الگوریتم چند جملهای که قادر به حل این مسائل در زمان محاسباتی معقول باشد، یافت نمیشود. کاربرد این مفهوم در حل مسائل زمانبندی که در کلاس NP hard قرار میگیرند، بسیار مؤثر است بطوری که حل مسائلی از این قبیل نیازمند الگوریتمهای ابتکاری[۵۵] و فراابتکاری[۵۶] است که بتواند در مدت زمان معقول به جواب بهینه دست یابند.
یک الگوریتم حل برای یک مسأله زمانبندی میتواند در مسأله دیگر که حالت خاص مسأله اصلی است، بکار گرفته شود به عنوان مثال حالت خاص مسأله محسوب میشود. در نظریه پیچیدگی این وضعیت را به صورت ∝ نشان میدهند. بدین ترتیب زنجیرهای از مسائل زمانبندی قابل تولید است که در آن الگوریتمهای حل و پیچیدگی مسائل مختلف به یکدیگر مربوط میشود. پیندو [۴۹] سلسله مراتب پیچیدگی مسائل مختلف زمانبندی را از طریق گرافهای منحصر به فردی ارائه مینماید. همانطور که در شکلهای (۳-۱) و (۳-۲) نمایش داده شده است، تغییر در عناصر مسائل زمانبندی مانند تغییر در نوع تابع هدف و نوع محیط کارگاهی موجب تغییر در میزان پیچیدگی آنها میشود.
شکل۳-۱٫ سلسله مراتب پیچیدگی محیطهای کارگاهی در مسائل زمانبندی [۴۹]
شکل۳-۲٫ سلسله مراتب پیچیدگی توابع هدف در مسائل زمانبندی [۴۹]
در این تحقیق مسأله زمانبندی جریان کارگاهی منعطف با معیار زمانهای زودکرد و دیرکرد وزنی بررسی میشود. گاری و همکارانش [۲۴] حالت خاص مسأله را در محیط کارگاهی تک ماشینه بررسی و NP hard بودن آن را به اثبات رساندند.

 

yle="box-sizing: inherit; width: 1104px;" width="531">