منبع پایان نامه ارشد درباره الگوریتم زمانبندی و تخصیص منابع


Widget not in any sidebars

2. هر وظیفه در چه وقت انجام خواهد شد؟
به عبارت دیگر، وظیفه اصلی مسائل زمانبندی به تصمیم‌گیری در مورد تخصیص منابع و توالی عملیات منحصر می‌شود. نوشتارهای زمانبندی مملو از مدل‌های ریاضی برای پاسخگویی به این دو سوال تصمیم‌گیری است[33].
به طور سنتی مسائل زمانبندی به صورت مسائل بهینه‌سازی محدودیت‌دار به ویژه مسائل مربوط به تخصیص منابع است و در این حالت عملیات مورد بررسی قرار گرفته است. در برخی موارد مسأله زمانبندی تنها مربوط به تخصیص منابع است و در این حالات مدل‌های برنامه‌ریزی ریاضی معمولاً می‌تواند برای تعیین تصمیمات در زمینه تخصیص منابع بهینه مورد استفاده قرار گیرد. از طرف دیگر مسائلی که صرفاً مقوله توالی عملیات را در نظر دارد نیز به حوزه زمانبندی مربوط می شود.
عناصر مهم مدلهای زمانبندی کارها و منابعاند. در نوشتارهای مربوط به زمانبندی، منابع نوعاً بر حسب قابلیتهای کمی وکیفی خود مشخص میشوند، به طوری که هر مدل نشان دهنده نوع و میزان هر منبع است. هر کار مشخص بر حسب اطلاعاتی از قبیل منبع مورد احتیاج، مدت انجام آن کار، زمانی که انجام آن را می توان شروع کرد وزمان تحویل آن توصیف می شود. به علاوه مجموعه ای از کارها را بعضاً می توان برحسب محدودیتهای تکنولوژیکی (روابط تقدمی) که در مورد عناصر متشکله آن صدق میکند بیان کرد.
نظریه زمانبندی همچنین شامل شیوه‌های متنوع و مختلفی است که در حل مسائل زمانبندی مفید واقع می‌شود. در واقع حوزه زمانبندی به صورت نقطه کانونی ایجاد، به کارگیری و ارزیابی روش‌های ترکیبی، شیوه‌های شبیه‌سازی، روش‌های شبکه‌ای و رویکردهای ابتکاری حل مسائل در آمده است. انتخاب شیوه مناسب به پیچیدگی مسأله طبیعت مدل و انتخاب معیار کارایی و عوامل دیگر بستگی دارد. در خیلی از حالات بهتر است چند شیوه به عنوان گزینه‌های مختلف برخورد به مسأله در نظر گرفته شود[33].
در عمل، زمانبندی‌ها با استفاده از الگوریتم زمانبندی با قوانین بر پایه دانش ایجاد می‌شوند. الگوریتم‌های زمانبندی، زمانبندی‌هایی را توسعه می‌دهد که یک معیار اندازه‌گیری مانند حداقل کردن انحراف از موعد تحویل، حداقل جریمه دیرکرد یا حداقل حداکثر دیرکرد و همچنین کل مدت زمان ساخت را بهینه می‌کند. امروزه به کارگیری الگوریتم‌های ابتکاری و فراابتکاری برای حل مسائل توالی و زمانبندی و به دست آوردن حل‌های بهینه و یا نزدیک به بهینه بسیار متداول شده است[33].
2-4-1- مدل‌های زمانبندی [64]
در اصطلاح برنامه‌ریزی تولید، مدل‌های زمانبندی می‌تواند به دسته‌های زیر تقسیم بندی شود:
تک ماشین:
تنها یک ماشین در دسترس است و کارهایی که می‌رسند نیاز به خدماتی از این ماشین دارند. در هر زمان یک کار به وسیله ماشین پردازش می‌شود. هر کار یک زمان پردازش و یک موعد تحویل دارد و ممکن است مشخصه‌های دیگری مانند اولویت نیز دارا باشد. همچنین ممکن است که یک تابع جریمه برای کارهایی که از موعد تحویل انحراف دارند داشته باشیم. متداولترین هدف، ترتیب دهی کارها روی ماشین‌ها است به منظور حداقل کردن جریمه دیر بودن که معمولا جریمه دیرکرد نامیده می‌شود. براساس سایر هدف‌ها معیارهای بسیاری ممکن است به عنوان یک پایه برای ایجاد زمانبندی به کار رود.
گردش کاری:
کارها روی چندین ماشین در یک توالی یکسان پردازش می‌شود. لیکن زمان پردازش هر کار روی هر ماشین ممکن است متفاوت باشد. هدف حداقل کردن زمان مورد نیاز برای تکمیل همه کارها می‌تواند باشد که زمان تکمیل کل نامیده می‌شود.
ماشین‌های موازی:
تعدادی ماشین مشابه در دسترس است و کارها می‌تواند روی هر یک از ماشین‌ها پردازش شود. کارها می‌تواند به هم وابسته باشد و هدف می‌تواند به صورت حداقل کردن زمان تکمیل کل باشد.
سیستم تولید کارگاهی:
یکی از متداولترین سیستم‌های تولیدی به کار رفته می‌باشد. ماشین‌های مختلفی در کارگاه وجود دارد و یک کار ممکن است که نیاز به چندین ماشین یا همه ماشین‌ها با توالی‌های خاص داشته باشد. تنها محدودیت آن است که یک کار نمی‌تواند بیش از یک بار از یک ماشین استفاده کند. هدف می‌تواند حداقل کردن زمان کل تکمیل یا حداقل جریمه دیر کرد باشد.
سیستم کارگاهی باز:
شبیه به سیستم تولید کارگاهی است غیر از این نکته که یک کار ممکن است روی ماشین‌ها به هر توالی‌ای که کار نیاز داشته باشد، پردازش شود. به عبارت دیگر، هیچ توالی وابسته عملیاتی وجود ندارد که یک کار دنبال کند. هدف معمولا حداقل کردن زمان تکمیل است.
سیستم کارگاهی وابسته:
یک محیط سیستم کارگاهی است که ترتیب پردازش یک یا چند کار بستگی به پردازش سایر کارها دارد که تولید کارگاهی وابسته گفته می‌شود. هدف معمولا حداقل کردن زمان تکمیل است.
پردازش دسته‌ای:
کارها به صورت دسته ای پردازش می‌شوند، هر دسته نیاز به زمان پردازش معین دارد، ممکن است برای اینکه چند کار می‌تواند در یک زمان پردازش شود محدودیت ظرفیت داشته باشیم. یک فر نانوایی با حجم محدود یک مثال از پردازش دسته‌ای است.
زمان‌های آماده‌سازی وابسته به توالی:
برخی از نویسندگان این مسئله را با عنوان پردازش دسته ای نیز می‌گویند. هر کار ممکن است به یک نوع تعلق داشته باشد. اگر کارهای همان نوع یکی بعد از دیگری پردازش شود هزینه آماده‌سازی وجود ندارد. از طرف دیگر، اگر یک نوع متفاوت از کار پردازش شود هزینه آماده‌سازی وجود دارد. هر کار یک موعد تحویل دارد و ما می‌خواهیم کارها را برای حداقل کردن کل جریمه دیرکرد در نظر بگیریم.

Share this post

Post navigation

You might be interested in...