بخشی از مقاله
چکیده
در این مقاله زمانبندی مسائل تک ماشینه با محدودیت فسادپذیری زمان انجام فرآیند و محدودیت دسترسی با هدف کمکردن زمان تکمیل کارها مورد بررسی قرار گرفته است. ما فرض کردیم که ماشین در زمانهای از پیش تعیین شدهای در دسترس نمیباشد و زمان پردازش واقعی هر کار وابسته به موقعیت آن کار و موقعیت دسته است. برای حل این مسئله، یک مدل برنامهنویسی عدد صحیح باینری جدید ارائه شدهاست. از آنجا که این مسئله قویاً -NPسخت است، برای یافتن جواب نزدیک به بهینه مسئله با ابعاد بزرگ در زمان معقول، الگوریتم فرا ابتکاری ژنتیک توسعه دادهشدهاست. در نهایت، نتایج محاسباتی با نرمافزار لینگو و الگوریتم ژنتیک آمادهشدهاست.
کلمات کلیدی:زمانبندی تک ماشینه، فسادپذیری کار، محدودیت دسترسی، الگوریتم ژنتیک
.1 مقدمه
در بسیاری از مسائل زمانبندی فرض میشود که همهی ماشینها در افق برنامهریزی دردسترس و آماده به کار میباشند. درحالی که ممکن است این فرض همیشه درست نباشد، مانند زمانهای خرابیهای دستگاه، نگهداری و تعمیرات پیشگیرانه، تعویض ابزار و موارد دیگر که ماشین در دسترس نمیباشد. در دهههای اخیر به این مسئله توجه بیشتری شده است.در مسائل زمانبندی و تئوریهای مرسوم، معموال زمان انجام فرآیند را ثابت در نظر میگیرند. با این حال، ما معموال با مسائلی مواجه میشویم که زمان پردازش ممکن است به دلیل پدیده فسادپذیری تغییر کند، به این معنی که کاری که دیرتر شروع میشود نیاز به زمان پردازش بیشتری دارد؛ یا ممکن است اثر یادگیری داشته باشیم، به این صورت که کاری که دیرتر زمانبندی میشود، زمان پردازش آن کمتر میشود؛ یا اینکه با تخصیص منابع بیشتر زمان پردازش کوتاهتر میشود.
در این مقاله تابع هدف بررسی زمان تکمیل کارها میباشد. در ادامه مطالعات مرتبط با مسائل تک ماشینه با هدف زمان تکمیل، فسادپذیری کار و محدودیت دسترسی مورد بررسی قرار میگیرد. آدیری و همکارانش و همچنین لی و لیمان مسئله با محدودیت دسترسی ثابت را بررسی کردند .[4] اشمیت، ما و همکارانش نیز در این زمینه بررسی جامعی انجام دادند. مسئله با اثرات یادگیری و فسادپذیری کار را میتوان در مطالعات گاویجنویز، بیسکاپ، جانیاک و همکارانش مشاهده کرد .[5] یانگ و یانگ مسئله زمانبندی تک ماشینه با اثرات یادگیری و فسادپذیری کار تحت تکنولوژی گروهی را بررسی کردهاند .[3]
روحی و فتحی و دیگر همکارانشان، مسئله تک ماشینه با اثرات یادگیری و محدودیت دسترسی را مورد بررسی قرار داده و مدل آن را نوشته و دو الگوریتم فرا ابتکاری برای حل آن ارائه کردهاند .[1] نا این، لینگ کانگ و شیائو یوان وانگ، نیز زمانبندی مسئله تک ماشینه بازمان پردازش وابسته به موقعیت کار، زمان شروع آن و میزان منابع اختصاص یافته به آن را بررسی کردهاند.در این مقاله، مسائل تک ماشینه با فسادپذیری زمان انجام فرآیند و محدودیت دسترسی به ماشین مورد بررسی قرار گرفته و مدلی برای زمانبندی آن ارائه شدهاست. از آنجا که مدل کالسیک آن از نوع -NP سخت است، مسئله ما نیز -NPسخت میباشد. در نتیجه برای حل آن الگوریتم مت هیورستیک ژنتیک ارائه شده است.
.2 تشریح مسئله
بیشتر تحقیقات انجام شده به بررسی فسادپذیری کار در مسائل تک ماشینه پرداختهاند و محدودیت دسترسی را در نظر نگرفتهاند. ما در این مقاله عالوه بر فسادپذیری کارها، دو بازه زمانی را که ماشین در دسترس نمیباشد، را نیز در نظر گرفتهایم.مسئله را به صورت زیر بررسی میکنیم. n کار مستقل وجود دارد که روی یک دستگاه پردازشمیشوند. زمان نرمال پردازش کار Ji با Pi نشان داده شده است. فرض بر این است که زمان پردازش کار دچار فسادپذیری میشود؛ زمان واقعی پردازش کار طبق تابعی از موقیت آن در توالی کارها، افزایش مییابد. فرض میشود زمان پردازش واقعی کار Ji که در موقعیت r قرار دارد از رابطه زیر بدست میآید:که β_≥0 نرخ فسادپذیری، S[r] زمان شروع کار در موقعیت r میباشد [2] و .[3] دستگاه بهطور پیوسته برای پردازش در دسترس نیست و چند دوره تعمیرات از پیش تعیین شده دارد.فرضیات مسئله به صورت زیر میباشد:
1.دستگاه در یک زمان میتواند تنها یک کار را انجام دهد.
2. تمام کارها در زمان صفر برای انجام فرآیند در دسترس میباشند.
3.زمان آمادهسازی در زمان پردازش گنجانده شدهاست.
4.بریدگی کارها مجاز نیست.
5.دستگاه در دورههای از پیش تعیین شدهای در دسترس نمیباشد.
نمای کلی مسئله در شکل 1 آورده شده است.همانطور که در شکل مشخص است، در اینجا ما دو بازهی زمانی در دسترس نبودن دستگاه - Mj - برای مسئله در نظر گرفتهایم.همچنین کارهای قرار گرفته در یک بازهی دسترسی را به عنوان یک دسته در نظر میگیریم. Bi ها شماره دستهها و TBi ها ظرفیت هر دسته میباشد.هدف مسئله کمکردن زمان تکمیل کارها میباشد - . - Ciبا استفاده از نمادهای سهگانه گراهام وهمکاران [6]، مسئله به صورت 1 nr a, Ci مشخص میشود، که در آن 1 نشاندهنده یک واحد دستگاه، nr نشاندهنده دردسترس نبودن، a محدودیت دسترسی، β ضریب فسادپذیری و Ci نشاندهندهی زمان تکمیل کارهاست. قضیه.1 مسئله 1 nr a, Ciقویاً -NPسخت است.اثبات. مسئله حداقلسازی حداکثر زمان تکمیل با محدودیت دسترسی - 1 - nr pm Cmax قویاً -NPسخت است، درنتیجه مسئله 1 nr a, Ciنیز قویاً -NPسخت است.
.2.1 مدل عددصحیح باینری مسئله
در این مقاله از عالئم زیر استفاده شدهاست:
