عنوان
|
مسأله زمانبندی تحویل دسته ای با در نظر گرفتن زمانهای دسترسی و آماده سازی وابسته به توالی بر روی یک ماشین
|
نوع پژوهش
|
پایان نامه
|
کلیدواژهها
|
زمانبندی، تک ماشین، تحویل دسته ای، زمانهای دسترسی، زمانهای آماده سازی وابسته به توالی، پنجره های زمانی، قواعد غالب، الگوریتم رقابت استعماری
|
چکیده
|
تحقیق حاضر به بررسی مسأله زمان بندی تحویل دسته ای با در نظر گرفتن زمان های دسترسی و آماده سازی وابسته به توالی بر روی یک ماشین می پردازد. لحاظ نمودن زمان های دسترسی و آماده سازی از جمله واقعیترین مفروضات در نظر گرفته شده در حوزه زمان بندی است. در این تحقیق، زمان های آماده سازی وابسته به توالی بوده و جدایی پذیر هستند. کارها در زمان های متفاوتی در دسترس قرار می گیرند و به صورت دسته ای به مشتریان مربوطه تحویل داده می شوند. موعد تحویل هر کار به صورت یک پنجره زمانی در نظر گرفته شده است. با توجه به پیچیده بودن مسأله مذکور در ابتدا مسأله با در نظر گرفتن زمان های دسترسی و سپس با در نظر گرفتن همزمان زمان های دسترسی و آماده سازی وابسته به توالی مورد بررسی قرار می گیرد. هدف زمان بندی کارها، دسته بندی آنها و تصمیم گیری در مورد زمان تحویل هر دسته می باشد، به طوریکه مجموع هزینه های زودکرد، دیرکرد، نگهداری و تحویل کمینه گردد. هریک از مسائل ابتدا به صورت یک مدل ریاضی فرموله شده و سپس مجموعه ای از قواعد غالب ارائه و اثبات می شوند. به دلیل NP-hard بودن مسائل مذکور، یافتن جواب بهینه مسائل با ابعاد بزرگ در زمانی منطقی مقدور نمی باشد. بنابراین، یک روش حل کارا که متشکل از ترکیب قواعد غالب و یک الگوریتم رقابت استعماری است، برای حل هر یک از آنها توسعه داده می شود. در مسائل مورد بررسی، وجود بیکاری های غیرضروری و دسته بندی غیرپیوسته مجاز می باشد. علاوه بر این، زمان تحویل یک دسته ممکن است بزرگتر از زمان تکمیل آخرین کار موجود درآن دسته باشد. در هریک از مسائل به منظور ارزیابی عملکرد الگوریتم ترکیبی ارائه شده، تعدادی مسأله نمونه تولید و حل می شود. نتایج به دست آمده کارائی الگوریتم ارائه شده را نشان می دهند.
|
پژوهشگران
|
حمید فرورش (استاد مشاور)، سوما فرهادی (دانشجو)، فردین احمدی زر (استاد راهنما)
|