تکه هایی از متن پایان نامه به عنوان نمونه : (ممکن است هنگام انتقال از فایل ...
۴-۳- جبهه پارتو. ۶۳
۴-۴- تنظیم پارامتر با بهره گرفتن از روش سطح پاسخ (RSM) 65
۴-۵- شاخصهای مقایسه. ۶۸
۴-۶- نتایج مقایسهای ۶۸
۴-۷- مقایسه زمان اجرا ۷۲
۴-۸- جمعبندی ۷۴
فصل پنجم: نتیجه گیری و پیشنهادها ۷۵
۵-۱- نتیجه گیری ۷۶
۵-۲- پیشنهادهای آتی ۷۶
منابع و مراجع ۷۸
پیوستها ۸۳
پ ۱- مدل ریاضی ارائه شده در نرمافزار GAMS. 84
پ ۲- کد نوشته شده در محیط Matlab برای دو روش حل DE و NSGA-II و روشهای مقایسه آنها ۸۸
چکیده لاتین ۱۰۶
فهرست جداول:
عنوان شماره صفحه شماره صفحه
جدول ۴-۱- مفروضات اصلی کد نوشته شده در محیط GAMS. 62
جدول ۴-۲- اعداد توابع هدف ۶۴
جدول ۴-۳- پارامترهای تعیین شده برای روشهای حل ۶۷
جدول ۴-۴- نتایج مقایسهای دو الگوریتم DE و NSGA-II 70
جدول ۴-۵- زمانهای اجرا ۷۳
فهرست اشکال:
عنوان شماره صفحه شماره صفحه
شکل ۲-۱- محیط متغیرهای تصمیم و فضای هدف. ۲۱
شکل ۲-۲- مجموعه جوابهای مغلوب و غیرمغلوب. ۲۲
شکل ۲-۳- بررسی وظیفه اول الگوریتم های چندهدفه. ۲۵
شکل ۲-۴- بررسی وظیفه دوم الگوریتمهای چندهدفه. ۲۵
شکل ۳-۱- ساختار کلی الگوریتم. ۴۶
شکل ۳-۲- نمای کلی الگوریتم DE تلفیقی ۴۸
شکل ۳-۳- نحوه نمایش جواب ۴۹
شکل ۳-۴- ساختار کلی VNS. 55
شکل ۳-۵- میزان مغلوبیت جوابها ۵۶
شکل ۳-۶- برتری جوابها در سطح اول ۵۷
شکل ۳-۷- برتری جواب با فاصله ازدحام بیشتر. ۵۷
شکل ۳-۸- محاسبه فاصله ازدحام برای جواب i 58
شکل ۳-۹- NSGA-II و عملگر مسابقهای دودویی ۵۸
شکل ۳-۱۰- ساختار کلی الگوریتم NSGA-II 59
شکل ۴-۱- جواب حل مدل مورد نظر در محیط GAMS. 63
شکل ۴-۲- جبهه پارتو برای ۵۰ جواب مختلف ۶۵
شکل ۴-۳- نتیجه حاصل از استفاده از روش RSM برای الگوریتم حل DE. 66
شکل ۴-۴- نتیجه حاصل از استفاده از روش RSM برای الگوریتم حل NSGA-II 67
شکل ۴-۵- نمودار مقایسهای شاخص کیفیت برای دو الگوریتم DE و NSGA-II 71
شکل ۴-۶- نمودار مقایسهای شاخص فاصلهگذاری برای دو الگوریتم DE و NSGA-II 71
شکل ۴-۷- نمودار مقایسهای شاخص پراکندگی برای دو الگوریتم DE و NSGA-II 72
شکل ۴-۸- نمودار زمانهای اجرا ۷۳
فصل اول
کلیات تحقیق
۱-۱- مقدمه
در جهان رقابتی حاضر، توالی و زمانبندی مناسب، ضرورتی برای بقا در فضای بازار است. زمانبندی، ابزاری است که استفاده از منابع در دسترس را بهینه می کند. منابع و کارها در زمانبندی ممکن است انواع گوناگونی داشته باشد [۱]. با توسعه جهان صنعتی، منابع بحرانیتر میشوند. زمانبندی این منابع، افزایش کارایی و بهره برداری از ظرفیت، کاهش زمان مورد نیاز برای تکمیل کارها و نهایتاً افزایش سوددهی یک سازمان را به دنبال خواهد داشت. در نتیجه، زمانبندی مناسب و مؤثر منابع مانند
مطلب دیگر :
سازمان تأمین اجتماعی – سبز اندیشان امروز
ماشینها، نیروی انسانی و غیره در محیط به شدت رقابتی امروز الزامیست [۱،۲].
زمانبندی یک فرایند تصمیم گیری است که نقش مهمی را در اکثر صنایع تولیدی و خدماتی ایفا می کند. زمانبندی در تدارکات، تولید، حمل و نقل، توزیع، پردازش اطلاعات و ارتباطات کاربرد دارد. عمل زمانبندی در یک سازمان، از مدلها و روشهای ریاضی یا روشهای ابتکاری برای تخصیص منابع محدود به کارهای در حال جریان استفاده می کند. تخصیص درست منابع، سازمان را برای بهینه کردن اهداف و به دست آوردن آرمانها توانمند میسازد. منابع میتوانند ماشینها در کارگاه تولیدی، خطوط هوایی در فرودگاه، کارگران در پروژه ساختمانی یا واحدهای پردازشی در محیط کامپیوتر باشند. کارها نیز میتوانند عملیات در کارگاه تولیدی، پرواز و فرود در فرودگاه، مراحل در یک پروژه ساختمانی و برنامه های کامپیوتری در محیط کامپیوتر باشند. هر کار دارای ویژگیهایی همچون سطح اولویت، زمان آماده به کار بودن و موعد تحویل[۱] میباشد. تابع هدف همچنین می تواند به صورتهای مختلفی مانند حداقل کردن زمان اتمام کل کارها یا حداقل کردن تعداد کارهای دارای دیرکرد در نظر گرفته شود [۳].
مسأله زمانبندی ماشین، زمینهای غنی و مناسب برای تحقیقات است که کاربردهای فراوانی در تولید، پشتیبانی، معماری کامپیوتر و مانند این را به همراه خواهد داشت. حوزه مورد بررسی در این پایان نامه، مسأله ماشینهای موازی[۲] است. زمانبندی ماشینهای موازی در ارتباط با چگونگی زمانبندی گروهی از کارها بر روی تعدادی از ماشینها به منظور اطمینان از پردازش کارها در مدت زمانی منطقی میباشد. ماشینهای موازی از دو دیدگاه تئوری و عملی دارای اهمیت میباشند. از دیدگاه تئوری، تعمیمی از تک ماشین[۳] و حالت خاصی از محیط جریان کارگاهی انعطافپذیر[۴] است. از دیدگاه عملی به این جهت که در دنیای واقعی بسیار معمول هستند دارای اهمیت میباشند [۱]. علاوه بر این، روشهایی که در محیط ماشینهای موازی مورد استفاده قرار میگیرند، قابل استفاده در فرایندهای تجزیه برای سیستمهای چند مرحلهای نیز میباشد. زمانبندی صنایع به طور کلی از کاربرد مدل ماشینهای موازی سود برده است. ماشینهای موازی توانایی انجام عملیات یکسان با داشتن ظرفیتها و استعدادهای متفاوت را دارا میباشند. در واقع ماشینهای موازی، افزایش ظرفیت و انعطافپذیری سیستم را با پردازش کارهای متفاوت به همراه خواهند داشت.
عموماً ماشینها در محیط موازی قادر به پردازش گروه یکسانی از کارها میباشند، اما بر اساس زمان پردازش کار به سه دسته عمده طبقه بندی میشوند: ماشینهای یکسان[۵]، ماشینهای یکنواخت[۶] و ماشینهای نامرتبط[۷]. در حالتیکه زمان پردازش کار بر روی همه ماشینها یکسان باشد، ماشینهای موازی یکسان نامیده میشوند. اگر ماشینها دارای سرعت متفاوت باشند، یعنی زمان پردازش کارها بر روی ماشینها متناسب با میزان سرعت در نظر گرفته شده باشد، ماشینهای موازی یکنواخت نامیده میشوند. در حالتی که زمانهای پردازش یک کار بر روی ماشینهای مختلف به طور دلخواه متفاوت باشند، ماشینهای موازی نامرتبط نامیده میشوند [۳]. در این پایان نامه، مسأله ماشینهای موازی یکنواخت مورد بررسی قرار میگیرد.
در ادامه به معرفی کار و نظریه زمانبندی و نحوه تعامل آن با برنامه ریزی خواهیم پرداخت. با توجه به این که مدلهای زمانبندی معمولاً بر اساس ترکیب ماشینها، نوع محدودیتها و معیارهای در نظر گرفته شده مشخص میشوند، سپس به معرفی انواع متداولی از موارد بالا خواهیم پرداخت.
۱-۲- کار زمانبندی
زمانبندی شامل برنامه ریزی و اولویتدهی فعالیتهایی است که لازم است به ترتیب عملیات انجام شوند [۲]. در بیشتر موارد عمل زمانبندی پس از حل برخی مسائل مربوط به برنامه ریزی اصولی مورد توجه قرار میگیرد و باید همواره این نکته را مد نظر داشت که تصمیمات مربوط به زمانبندی اهمیت کمتری نسبت به مجموعه وسیعتری از تصمیمات مدیریتی دارد. برای مثال، در حل مسائل مربوط به ساخت، مسائل اساسی مدیریتی مربوط به انتخاب محصولی که باید ساخته شود و تعیین میزان تولید هر محصول اولویت دارد. بعد از بهکارگیری بررسی بازار و تحلیلهای اقتصادی برای حل اینگونه مسائل، برنامه ریزی تکنولوژیکی به این مسأله که محصول چگونه باید ساخته شود متمرکز میشود و تنها بعد از اینکه جواب سوالات مربوط به برنامه ریزی داده شد و در دسترس بودن منابع دانسته شد، زمان برای توجه به مسائل زمانبندی مناسب است. تصمیمات اصولی مدیریت به مسائل سه گانه زیر مرتبط میشوند.
۱- چه محصول یا خدمتی قرار است عرضه شود؟
۲- در چه مقیاسی قرار است عرضه شود؟
۳- چه منابعی قرار است تأمین شود؟
پاسخ دادن به این پرسشها کار برنامه ریزی است. در مقابل، در کار زمانبندی فرض بر این است که جواب پرسشها از پیش فراهم شده است. بنابراین کار زمانبندی صرفاً به وضعیتی مربوط میشود که در آن طبیعت کارهایی که باید زمانبندی شود توصیف شده و ترکیب منابع موجود تعیین شده باشد[۴]. در واقع زمانبندی ابزاری است که استفاده از منابع در دسترس را بهینه می کند.
در عمل وظیفه برنامه ریزی و زمانبندی کاملاً مستقل از هم نیست. برنامهریز ابتدا وظایفی را که باید انجام شود مشخص و حدودی برای میزان منابع دسترسپذیر تعیین می کند. سپس زمانبند این اطلاعات را میگیرد و مشخص می کند که منابع موجود چگونه به انجام کارهای تعیین شده تخصیص یابد.
[۱] Due Date
[۲] Parallel Machines
[۳] Single Machine
