ارائه یک الگوریتم مبتنی بر آتاماتای یادگیر با ساختار متغیر برای زمانبندی کارها در یک ماشین

چكيده

در این مقاله روشی تصادفی مبتنی بر یادگیری¬ماشین برای حل مسئله زمانبندی کارها روی یک ماشین که یکی از مسائل مشکل است، ارائه شده است. در این مسئله با افزایش تعداد ورودی، زمان محاسبه راه حل بهینه، بصورت نمایی افزایش می¬یابد. هدف روش پیشنهادی، ارائه ترتیبی از اجرای کارها می¬باشد بطوریکه از نظر میزان تاخیر، دارای کمترین اختلاف از موعد مقرر خود باشند. به منظور ارزیابی کارایی این روش، نتایج اجرای برخی از الگوریتمهای قبلی مورد مقایسه قرار گرفته¬اند. در این راستا، از شبیه¬سازیهای کامپیوتری استفاده شده است. در نهایت نتایج تولیدی روش ارائه¬شده با بهترین پاسخهای موجود در کتابخانه OR مورد مقایسه قرار گرفته¬اند. نتایج نشان می¬دهند که روش پیشنهادی توانایی تولید پاسخهایی با اختلاف 53/1 درصدی از پاسخهای بهینه را دارد.

كلمات كليدي: آتوماتای یادگیر، الگوریتم ژنتیکی، زمانبندی.

چكيده

در این مقاله روشی تصادفی مبتنی بر یادگیری­ماشین برای حل مسئله زمانبندی کارها روی یک ماشین که یکی از مسائل مشکل است، ارائه شده است. در این مسئله با افزایش تعداد ورودی، زمان محاسبه راه حل بهینه، بصورت نمایی افزایش می­یابد. هدف روش پیشنهادی، ارائه ترتیبی از اجرای کارها می­باشد بطوریکه از نظر میزان تاخیر، دارای کمترین اختلاف از موعد مقرر خود باشند. به منظور ارزیابی کارایی این روش، نتایج اجرای برخی از الگوریتمهای قبلی مورد مقایسه قرار گرفته­اند. در این راستا، از شبیه­سازیهای کامپیوتری استفاده شده است. در نهایت نتایج تولیدی روش ارائه­شده با بهترین پاسخهای موجود در کتابخانه OR مورد مقایسه قرار گرفته­اند. نتایج نشان می­دهند که روش پیشنهادی توانایی تولید پاسخهایی با اختلاف 53/1 درصدی از پاسخهای بهینه را دارد.

كلمات كليدي:

آتوماتای یادگیر، الگوریتم ژنتیکی، زمانبندی.