پیشینه تحقیق زمان بندی و مروری بر مدل های زمانبندی و الگوریتم ژنتیک  دارای ۵۵ صفحه می باشد فایل پیشینه تحقیق به صورت ورد  word و قابل ویرایش می باشد. بلافاصله بعد از پرداخت و خرید لینک دنلود فایل نمایش داده می شود و قادر خواهید بود  آن را دانلود و دریافت نمایید . ضمناً لینک دانلود فایل همان لحظه به آدرس ایمیل ثبت شده شما ارسال می گردد.

فهرست مطالب

۱-۱مقدمه۵
۱-۲تعریف مربوط به زمانبندی۵
۱-۳زمانبندی  از دیدگاهی دیگر۷
۱-۴نظریه زمانبندی۸
۱-۵مروری بر مدل های زمانبندی۹
۱-۵-۱چارچوب و نمادها۹
۱-۵-۲ترکیب ماشین ها (محیط های کار)۱۰
۱-۵-۳مدل های تک ماشینه۱۲
۱-۵-۴مدل های ماشین موازی۱۳
۱-۵-۵مدل های جریان کارگاهی۱۴
۱-۵-۶مدل های کار کارگاهی۱۷
۱-۵-۷مدل های کارگاه باز۲۱
۱-۵-۸مدل های کارگاه وابسته۲۳
۱-۵-۹مدل های پردازش دسته ای۲۳
۱-۵-۱۰مدل های خط مونتاژ۲۳
۱-۵-۱۱مدل های خط مونتاژ ترکیبی۲۳
۱-۶محدودیت های زمانبندی۲۴
۱-۶-۱معیارهای ارز یابی عملکرد۲۶
۱-۷الگوریتم ژنتیک۲۸
۱-۷-۱تکنیک‌های حل مسائل بهینه سازی۲۸
۱-۷-۲صورت کلی الگوریتم ژنتیک۳۰
۱-۷-۳تعاریف۳۱
۱-۷-۴نمایش کروموزوم۳۱
۱-۷-۴-۱نمایش باینری۳۱
۱-۷-۴-۲نمایش جایگشتی۳۲
۱-۷-۴-۳نمایش مقداری۳۲
۱-۷-۴-۴نمایش درختی۳۳
۱-۷-۵تابع شایستگی۳۳
۱-۷-۶عملگر انتخاب۳۴
۱-۷-۶-۱انتخاب تصادفی۳۴
۱-۷-۶-۲انتخاب چرخ گردان ۳۴
۱-۷-۶-۳انتخاب رتبه بندی۳۶
۱-۷-۶-۴انتخاب نخبه‌گرا۳۷
۱-۷-۶-۵انتخاب مسابقه‌ای۳۸
۱-۷-۷عملگر تبادل۳۸
۱-۷-۷-۱عملگر تبادل تک نقطهای۳۹
۱-۷-۷-۲عملگر تبادل دو نقطه ای۳۹
۱-۷-۸عملگر جهش۴۰
۱-۷-۸-۱عملگر معکوس سازی۴۱
۱-۷-۹عملگر حذف و کپی۴۱
۱-۷-۱۰عملگر حذف وتولید مجدد۴۲
۱-۷-۱۱پارامترهای الگوریتم ژنتیک۴۲
۱-۷-۱۲همگرایی۴۳
۱-۷-۱۳شرط خاتمه الگوریتم ژنتیک۴۳
۱-۷-۱۴مزایای الگوریتم ژنتیک۴۴
۱-۷-۱۵معایب الگوریتم ژنتیک۴۴
۱-۸کارهای انجام شده۴۵
۱-۸-۱الگوریتم ETPN-GA45
۱-۸-۲الگوریتم AFS Petri Net46
۱-۸-۳الگوریتم GA-ACO47
۱-۸-۴الگوریتم GA-Fuzzy48
۱-۸-۵الگوریتم HGA49
۱-۸-۶الگوریتم GADG50
۱-۸-۷الگوریتم های دیگر۵۱
فهرست منابع و مأخذ۵۳

منابع

[۱] علیرضا مهدی / مقدمه­ای بر الگوریتم ژنتیک و کاربردهای آن / تهران: انتشارات ناقوس / ۱۳۸۶

[۲] C. Low, Y .Yeh, Genetic algorithm-based heuristics for an open shop scheduling problem with setup, processing, and removal times separated, Robotics and Computer-Integrated Manufacturing, Vol. 25, pp. 314–۳۲۲, ۲۰۰۹٫

[۳] M.L. Pinedo, Scheduling: Theory, Algorithms and systems, Fourth Edition, Springer,

۲۰۱۲٫

[۸] M.E. Matta, A genetic algorithm for the proportionate multiprocessor open shop, Computers & Operations Research 36, pp.2601-2618, 2009.

[۹] S. Noori-Darvish, R. Tavakkoli-Moghaddam, Minimizing the total tardiness and makespan in an open shop scheduling problem with sequence-dependent setup times, Journal of Industrial Engineering International, 2012,.

[۱۰] Y. Huang, J. Lin, A new bee colony optimization algorithm with idle-time-based filtering scheme for open shop-scheduling Problems, Expert Syst. 2011.

[۱۲] A. Sedeno-Noda, D. Alcaide Lopez de Pablo, C. Gonzalez-Martin, A network flow based method to solve performance cost and makespan open-shop scheduling problems with time-windows, European Journal of Operational Research, Article inpress, 2008.

[۱۳] R. Chen, W. Huang and G. Tang, Dense open shop schedules with release time, Theoretical Computer Science, Article in press, 2008.

[۱۴] G. Mosheiov, D. Oron, Open shop batch scheduling with identical jobs, European Journal of Operational Research, Vol. 187, pp. 1282-1292, 2008.

[۱۵] H.T. Lin, H.T. Lee, W.J. Pan, Heuristics for scheduling in a no wait open shop with movable dedicated machines, International Journal of Production Economics, Vol.111, pp. 368-377, 2008.

[۱۶] A.S. Noda, D. Alcaide, C.G. Martin, Network flow approaches to preemptive open shop scheduling problems with time windows, European Journal of Operational Research, Vol. 174, pp. 1501-1518, 2006.

[۱۷] C.F. Liaw, Scheduling preemptive open shop to minimize total tardiness, European Journal of Operational Research, Vol. 162, pp. 173-183, 2005.

[۱۸] G. Mosheiov, D. Oron, Open shop batch scheduling with identical jobs, European Journal of Operational Research, Vol. 187, pp. 1282-1292, 2008.

[۱۹] C. Low, Y. Yeh, Genetic algorithm-based heuristics for an open shop scheduling problem with setup, processing and removal times separated, Robotics and Computer-Integrated Manufacturing, In Press, Corrected Proof, Available online 5 March 2008.

[۲۰] C.F. Liaw, Scheduling two machine preemptive open shops to minimize total completion time, Computers & Operations Research, Vol. 31, pp. 1349-1363, 2004.

۱-۱  مقدمه

هر چند در گذشته توجه کمتری نسبت به مسائل کارگاه باز شده اما به نظر می رسد، در سال­های اخیر، مسائل زمانبندی کارگاه باز مورد توجه محققان بسیاری قرار گرفته است. با این حال، مسائل کارگاه باز در مقایسه با  سایر مسائل زمانبندی سهم بسیار کمی از ادبیات موضوع را به خود اختصاص داده اند. تمامی کارهای انجام شده در حقیقت تلاشی برای در نظر گرفتن ویژگی ها و شرایط واقعی در حوزه مسائل زمانبندی بوده است. در این مقاله قصد داریم تا مسائل زمانبندی در محیط کارگاه باز را مورد بررسی قرار دهیم و برای حل آن از روش­های فرا ابتکاری استفاده نماییم. در ادامه مروری بر تعاریف اولیه مسائل زمانبندی کرده و همچنین مطالبی در مورد معیارها و محدودیت­های موجود در مسائل زمانبندی سیستم­های باز را مورد تجزیه و تحلیل قرار می­دهیم.

۱-۲   تعریف مربوط به زمانبندی

زمانبندی نوعی تصمیم­گیری است و فرآیندی است که در جریان برنامه زمانی تعیین می­شود. در واقع زمانبندی تخصیص منابع[۱] در طول زمان برای مجموعه ای از وظایف است. با توجه به این زاویه دید، بیشتر آموخته های ما در مورد زمانبندی را می توان در مورد تصمیم گیری های دیگر نیز به کار گرفت. زمانبندی مبحثی نظری است که مجموعه ای از اصول، مدل ها، روش ها و نتایج منطقی را در بر می گیرد و بینشی عمیق را در مورد برنامه تخصیص عملیات فراهم می آورد. زمانبندی به تخصیص منابع محدود به وظایف مورد انجام، در طی زمان می پردازد. زمانبندی فرآیند تصمیم گیری است که یک یا چند هدف بهینه سازی را شامل می شود. منابع و وظایف ممکن است صورت های مختلفی داشته باشند. منابع ممکن است ماشین ها در یک کارگاه، باند پرواز در یک فرودگاه، کارگردان در یک سایت ساخت وساز، واحدهای پردازش در محیط محاسباتی و غیره باشند. وظایف می توانند شامل یک عملیات فرآیند تولید، فرود یا بلند شدن در یک باند پرواز، مراحل مختلف موجود در یک پروژه ساخت، اجرای برنامه های کامپیوتری و غیره باشند. هر وظیفه می تواند سطوح اولویت متفاوتی داشته باشد مانند زودترین زمان ممکن برای شروع[۲] و یا بر اساس موعد تحویل و غیره. تابع هدف نیز می تواند به فرم های مختلفی باشد و یا در حالت دیگر، می تواند کمینه سازی تعداد کارهایی باشد که  زمان  اتمام  کارها[۳] برای آخرین وظیفه باشد و یا در حالت دیگر، می تواند کمینه سازی تعداد کارهایی باشد که زمان اتمام آن ها بعد از موعد تحویل است. زمانبندی یک فرآیند تصمیم گیری است که در اکثر سیستم های ساخت و تولید و محیط های پردازش اطلاعات موجود است. همچنین، زمانبندی در حمل و نقل، برنامه زمانی توزیع و سایر صنایع خدماتی دارای کاربرد می باشد ]۲،۳[.

اگر بخواهیم تعریف دیگری از زمانبندی ارائه کنیم که در برگیرنده زوایای دیگری باشد، این تعریف می تواند به این گونه بیان شود که زمانبندی عمل تعیین اولویت ها و یا مرتب نمودن فعالیت ها برای برآورده نمودن الزامات مشخص، محدودیت ها و یا اهداف است. از آنجایی که همچنان زمان یک منبع محدودکننده می باشد، ما نیاز داریم تا به طور خودآگاه یا ناخودآگاه فعالیت هایمان را برای بهره برداری بهینه از این منبع محدود زمانبندی کنیم. با توسعه صنعتی، مساله محدودیت منابع بحرانی تر شده است. در حال حاضر ماشین ها، نیروی کار، تسهیلات نیز علاوه بر زمان به عنوان منابع بحرانی در فعالیت های تولیدی و خدماتی شناخته می شوند. زمانبندی این منابع به افزایش کارایی و بهره برداری از ظرفیت، کاهش زمان مورد نیاز برای تکمیل کارها و نهایتا افزایش سوددهی یک سازمان می انجامد. زمانبندی موثر منابعی همچون ماشین و نیروی انسانی، در محیط به شدت رقابتی امروز الزامی است.

در بیشتر موارد، عمل زمانبندی کارها پس از حل برخی مسائل مربوط به برنامه ریزی اصولی مورد توجه قرار می گیرد. باید همواره این نکته را مد نظر داشت که تصمیمات مربوط به زمانبندی اهمیت کمتری نسبت به مجموعه وسیع تری از تصمیمات مدیریتی دارند. برای مثال، در حل مسائل مربوط به ساخت، مسائل اساسی مدیریتی مربوط به انتخاب محصولی که باید ساخته شود و تعیین میزان تولید هر محصول اولویت دارد. بعد از به کارگیری بررسی بازار و تحلیل های اقتصادی برای حل این گونه مسائل، برنامه ریزی  تکنولوژیکی بر روی این مساله که محصول چگونه باید ساخته شود متمرکز می شود. بعد از این که جواب این سوالات مربوط به برنامه ریزی داده شد و در دسترس بودن منابع نیز مورد بررسی قرار گرفت، آنگاه می توان به مسائل زمانبندی به طور مناسب توجه نمود. در واقع زمانبندی ابزاری است که استفاده از منابع در دسترس را بهینه می کند.

۱-۳ زمانبندی  از دیدگاهی دیگر

زمانبندی، تخصیص منابع درطول زمان برای مجموعه ای از وظایف است. این تعریف نسبتا کلی واژه، دو مفهوم مختلف دارد. اولا زمانبندی نوعی تصمیم گیری است و فرایندی است که در جریان آن برنامه زمانی را تعیین می کند. از این لحاظ بیشتر آموخته های ما در مورد زمانبندی را می توان در مورد تصمیم گیری های دیگر نیز بکار بست، لذا این مبحث ارزش علمی عام دارد. ثانیا زمانبندی مبحثی نظری است که مجموعه ای اصول، مدل ها، روش ها و نتایج منطقی را در برمی گیرد، که برای ما بینشی عمیق در مورد عمل زمانبندی به همراه دارد که می توان در مورد سایر نظریه ها به کار برد و بنابراین ارزش مفهومی عام دارد.

عناصر مهم مدلهای زمانبندی کارها و منابع اند. در نوشتار های مربوط به زمانبندی،  منابع نوعا بر حسب قابلیت های کمی و کیفی خود مشخص می شوند، به طوری که هر مدل نشان دهنده نوع و میزان هر منبع است. هر کار مشخص بر حسب اطلاعاتی از قبیل منبع مورد نیاز، مدت انجام آن کار، زمانی که انجام آن را  می توان شروع کرد و زمان تحویل توصیف می شود. به علاوه مجموعه ای از کارها بعضا می توان بر حسب محدودیت های تکنولوژیکی (روابط تقدمی) که در مورد عناصر متشکله آن صدق می کند بیان کرد [۱۷].

تئوری زمانبندی همچنین شامل شیوه های متنوع و مختلف است که در حل مسائل زمانبندی مفید واقع می شود. در واقع، حوزه زمانبندی به صورت نقطه کانونی ایجاد، بکارگیری و ارزیابی روش های ترکیبی ، شیوه های شبیه سازی، روش های شبکه ای و رویکرد های ابتکاری حل مسائل در آمده است. انتخاب شیوه مناسب به پیچیدگی مساله، طبیعت مدل و انتخاب معیار کارایی و عوامل دیگر بستگی دارد. در خیلی از حالات بهتر است چند شیوه به عنوان گزینه های مختلف برخورد به مساله در نظر گرفته شود. به همین دلیل نظریه زمانبندی شاید به همان اندازه که به امر بررسی روشها بپردازد به بررسی مدل ها نیز توجه دارد [۱۸].

برای رده بندی مدل های عمده زمانبندی لازم است ترکیب منابع و رفتار کارها مشخص شود. برای نمونه یک مدل ممکن است یک یا چند نوع منبع داشته باشد. اگر یک نوع منبع داشته باشد کارهای مربوطه احتمالا یک مرحله ای است، در حالی که اگر چند منبع داشته باشد کارها معمولا چند مرحله ای انجام می شود و در هر دو حالت منابع را می توان به صورت یک مجموعه واحد یا موازی در نظر گرفت. به علاوه، اگر مجموعه کارهای در دسترس برای زمانبندی در طول زمان تغییر نکند سیستم، ایستا نامیده می شود، در مقابل اگر یک کار جدید به مجموعه کارها در طول زمان افزده شود سیستم پویا نامیده می شود.

۱-۴ نظریه زمانبندی

نظریه زمانبندی اصولا با مدل های ریاضی سر وکار دارد و بین کار زمانبندی و توسعه مدل­های زمانبندی رابطه برقرار می نماید و به طور پیوسته آن ها را با مسائل نظری و عملی زمانبندی محک می زند.

در این زمینه دیدگاه نظری اغلب به صورت رویکردی کمی است و سعی آن، دست یافتن به ساختار مساله در قالب شکل فشرده ریاضی است. این رویکرد کمی با تفسیر اهداف تصمیم گیری در قالب یک تابع هدف صریح و بیان موانع تصمیم گیری به صورت محدودیت های صریح شروع می­شود. حل هر مسئله زمانبندی برابر پاسخگویی به این دو سوال است :

کدام منبع برای انجام هر وظیفه تخصیص داده خواهد شد ؟

هر وظیفه در چه وقت انجام خواهد شد ؟

به عبارت دیگر،  وظیفه ی اصلی مسائل زمانبندی به تصمیم گیری در مورد تخصیص منابع و توالی عملیات منحصر می شود. تئوری زمانبندی شامل شیوه های متنوع و مختلفی است که در حل مسائل زمانبندی مفید واقع گردد. در واقع حوزه زمانبندی، به یک نقطه کانونی برای ایجاد، به کارکیری و ارزیابی روش های حل مسائل تبدیل شده است. این روش ها عبارتند از: رویکردهای ترکیبی، شیوه های شبیه سازی، روش های شبکه ای و رویکردهای ابتکاری. انتخاب شیوه مناسب به پیچیدگی مساله، طبیعت مدل، انتخاب معیار کارایی و عوامل مرتبط دیگر بستگی دارد [۳۹،۴۰].

۱-۵ مروری بر مدل های زمانبندی

عملکرد سیستم های تولیدی و خدماتی با معیارهای بسیاری مانند تعداد ماشین ها، سطح اتوماسیون، ویژگی های مربوط به ساختار مورد نظر،  نوع سیستم حمل و نقل و غیره تعیین می شود. تفاوت در این معیارها تعداد بسیار زیادی از مدلی های زمانبندی را به وجود می آورد. پارامترهایی که در زیر بیان می شوند در طول این فصل مورد استفاده قرار خواهند گرفت.

۱-۵-۱ چارچوب و نمادها

تعداد کارها برابر با n و تعداد ماشین ها برابر با m در نظر گرفته شده است. اندیس های i وj به کارهای i ام و j ام اشاره دارند و اندیس هایk   و l به ماشین های k و l اشاره دارند. پارامترهای زیر مرتبط با کار i ام می باشند:

زمان پردازش[۴](Pik)  : بیان کننده مدت زمانی است که کار i ام باید بر روی ماشین k ام سپری کند.

زمان آماده به کار بودن[۵] (ri) : زمانی که کار i وارد سیستم می شود و به عبارت دیگر زود ترین زمانی که پردازش کار i می تواند آغاز شود.

[۱] Resource Allocation

[۲] Earliest Start Time

[۳] Completion Time

[۴] Processing Time

[۵] Release Date

تمامی فایل های پیشینه تحقیق و پرسشنامه و مقالات مربوطه به صورت فایل دنلودی می باشند و شما به محض پرداخت آنلاین مبلغ همان لحظه قادر به دریافت فایل خواهید بود. این عملیات کاملاً خودکار بوده و توسط سیستم انجام می پذیرد. جهت پرداخت مبلغ شما به درگاه پرداخت یکی از بانک ها منتقل خواهید شد، برای پرداخت آنلاین از درگاه بانک این بانک ها، حتماً نیاز نیست که شما شماره کارت همان بانک را داشته باشید و بلکه شما میتوانید از طریق همه کارت های عضو شبکه بانکی، مبلغ  را پرداخت نمایید.