بخشی از مقاله
چکیده
مسئلهی زمانبندی سیستمهای باز یک مسئله زمانبندی بسیار مهم میباشد که مسئلهی زمانبندی سیستمهای باز یک مسئله زمانبنـدی بسـیار مهم میباشد که دارای مفهوم استدلالی Np-hard و نمونههای استاندارد برای اندازه بسیار کوچکی است که بـه مشـکل عملـی در حـل مسـئله اذعان دارد. این مقوله در رابطه با مسئله زمان بندی سیستم های بازشامل برخی الگوریتم های تقریبی و دقیق می باشد .در این مقاله به چگـونگی حل مساله پیچیده زمانبندی به کمک برنامه نویسی پویا پرداخته، سپس الگوریتم جدیدی با استفاده از الگوریتم های پیشین معرفی می شـود کـه باعث افزایش سرعت اجرای برنامه نویسی پویا شده و منجر به دستیابی به پاسخ های بهتر برای این مساله می شود.
کلمات کلیدی
مسئله ی زمانبندی کارگاه های باز،برنامهنویسی پویا،مسئلههای .NP-Hard
-1 مقدمه
زمانبندی در واقع به تخصیص منابع در طول زمان برای اجـرای مجموعهای از کارها در وضعیتهای مختلف می پردازد .از آنجا که محیط سیستمهای باز در بسیاری از محیطهای دنیای واقعـی رخ می دهد، ارائه مدل مناسب و دقیق کمـک بزرگـی بـه مـدیران و صنعتگران خواهد نمود .بیان دادههای دقیق در مسایل زمانبندی
عموماً دور از تصور است. رخدادهای پیشبینی نشده و خطاهـای اندازهگیری موجب عدم قطعیت اطلاعات میشود سیستم های باز جزءمســئلههــای NP-Hard بــه شــمار مــیآینــد. بســیاری از
رویکردهای اکتشافی و تحلیلی در ایـن زمینـه در جهـت بدسـت اوردن راه حل های بهینه مناسب برای مسئله زمانبندی سیستم های باز پیشنهاد شده اند. لیـاو[8] الگـوریتمی بـر مبنـای شـبیه سازی تبرید برای حل مساله سیستمهای باز ارایه کـرد. وی یـک روش تقریبی برای یافتن کمترین مقـدار حـداکثر زمـان تکمیـل
کارها در یک مساله سیستم های بـاز بـا ایجـاد یـک جسـتجوی همسایگی جدیـد در الگـوریتم شـبیه سـازی تبریـد نمـود. ایـن ساختار جسـتجوی همسـایگی در الگـوریتم باعـث ایجـاد کـران پایینی از جوابهای با کیفیت بالا در زمان مناسب گردید.
لیونگ و همکاران [6] مسـاله کارگـاه بـاز را بـا فـرض کارهـای متداخل مطالعه نمودند .آنها مساله را در حالـت دو ماشـینه مـورد بررسی قرار داده و فرض کردند که هر کار باید روی هر دو ماشین پردازش شوند .البته در تحقیق آنان بـرخلاف مسـاله کارگـاه بـاز کلاسیک، هر دو عملیات مربوط به یک کار می توانند در یک زمان با یکدیگر تداخل داشته باشند.
سراج و توکلی مقدم[5] ، یک الگوریتم جستجوی ممنـوع چنـد هدفه جدید برای مساله کارگاه باز دوهدفه که بر مبنـای رویکـرد تصمیم گیری چند هدفه فازی است، ارایـه نمودنـد .آنهـا مسـاله پیشنهادی خود را با پارامترهای قطعی در نظر گرفته و در آن بـه حداقل سازی میانگین زمان های تکمیل و میانگین مقادیر دیرکرد
کارها به طور همزمان پرداختند .در مدل ارایه شده، زمانهای آماده سازی به صورت مستقل از دنباله در نظرگرفته شده است. لیاو[7] الگوریتمی را بـر مبنـای جسـتجوی ممنـوع بـرای حـل مساله زمانبندی سیستم های باز دو ماشینه با فرض مجاز بـودن بریدگی کارها ارایه داده است. تابع هدف مدل ارایه شـده کمینـه سازی کل دیرکرد است. الگوریتم زمان سنجی بهینهای نیز بـرای معین کردن زمان اتمام هر کار در دنباله مربوطه ارایه شده است. وی برای شروع الگوریتم جستجوی ممنوعـه پیشـنهادی خـود از روش ابتکاری کارایی به منظـور تعیـین اسـتراتژیهـای پراکنـده سازی استفاده نموده است.
برنامه نویسی پویا تخصیص کارا منابع است که می تواند مقادیر مختلفی از متغییرها را جستجو کرده تا سودرا به حداکثر رسـانده و همچنین باعث کاهش هزینهها شود. بازده حاصله از اجرا برنامه نویسی پویا بهینه میباشد. این الگورتیم از این جهت با مدلهای دیگر متفاوت است که تصـمیمگیـری را در طـول زمـان بررسـی میکند. حل سیستمهای باز به علت داشتن فضـای حـل مسـئله گسترده کمی دشوارتر است که برای حل آن از برنامه نویسی پویا که مسایل را حتی الامکان سادهتر کرده و اجازه میدهد کـه هـر مقطع زمانی به صورت مجزا بررسی شود استفاده میکنیم. مزیت این الگورتیم در کارایی محاسباتی است .حل یک نمونه از مسئله زمانبندی سیستمهای باز به وسیله الگورتیمهای برنامـه نویسـی پویا می تواند مارا قادر به حل بهینه مسئلههای مشابه سازد.
-2 تعاریف زمانبندی
زمان بندی نوعی تصمیم گیری است و فراینـدی اسـت کـه در جریان برنامه زمانی تعیین می شود.در واقع زمان بندی تخصیص منابع در طول زمان برای اجرای مجموعه ای از وظـایف اسـت.مـا می توانیم اکثر کارهای انجام شـده در زمـان بنـدی را در مـوارد تصمیم گیری دیگر نیز به کارگرفت.زمان بندی یک مبحث نظری است که مجموعهای از اصـول،روش،مـدلهـا و نتـایج منطقـی را شامل می شود و دیدکاملی را در مورد برنامه تخصـیص عملیـات فراهم میآورد.منابع و وظایف ممکن است صورت هـای مختلفـی در مسائل داشته باشند به طور مثال منابع ممکن است ماشینها در یک تعمیر گاه،باند پرواز در فرودگاه،کارگران در یک سـاخت و ساز ،واحدهای پردازشی در محیط محاسباتی و غیره باشد وظایف مــی تواننــد شــامل یــک فرایندتولیــد،فرود یــا بلنــد شــدن هواپیما،مراحل مختلف سـاخت و سـاز،برنامههـای کـامپیوتری و غیره باشد.هر وظیفه می توان دارای اولویت متفـاوتی باشـد.مـثلا
زودترین زمان ممکن برای شروع و یـا براسـاس موعـد تحویـل و غیره. معیارهای هر مسئله می تواند متفاوت باشد، کمینـه سـازی زمان اتمام کار برای آخرین وظیفه و یـا در حالـت دیگـر کمینـه سازی زمان تکمیل کارهاو یا کمینه سازی تعداد کارهـایی باشـد که زمان اتمام آنها بعد از موعد تحویل است.
که زمینـه نظـری کمـی اسـت و سـعی آن ، دسـت یـافتن بـه ساختارمسئله در قالب ریاضی اسـت.کـه ایـن رویکـرد بـا تفسـیر اهداف تصمیم گیری در قالب یک تابع هدف صریح و بیان موانع تصمیم گیری به صـورت محـدودیت هـای صـریح شـروع مـی شود.حل هر مساله زمان برابر با پاسـخ گفـتن بـه ایـن دو سـوال است:
- کدام منبع برای انجام هر وظیفه تخصیص داده خواهدشد؟
- هر وظیفه در چه زمانی انجام می شود؟
به عبارت دیگر وظیفه اصلی زمان بندی بـه تصـمیم گیـری در مورد تخصیص منابع و توالی عملیات منحصـر مـی شـود تئـوری زمان بندی شامل شیوههای متنوع و مختلفی اسـت کـه در حـل مسائل زمان بندی مفید واقع می شوند. از جمله روش های کـه در مسئله ی زمانبندی در نظر گرفتـه شـده انـد مـی تـوانیم بـه شــیوههــای دقیــق(کــار بــرای نمونــه هــایی بــا حجــم بســیار محدود)،شیوه های ابتکاری و الگوریتم هـای بـرآورد زمـان چنـد جملــهای اشــاره کــرد انتخــاب شــیوه مناســب بــه پیچیــدگی مساله،طبیعت مدل،انتخاب معیارکـارایی و عوامـل مـرتبط دیگـر بستگی دارد.
