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

فهرست مطالب

۲-۱٫ مقدمه    ۴
۲-۲٫ محیطهای کارگاهی    ۶
۲-۲-۱٫ تک ماشینه    ۶
۲-۲-۲ . ماشینهای موازی    ۶
۲-۲-۲-۱٫ ماشینهای موازی یکسان    ۶
۲-۲-۲-۲٫ ماشینهای موازی یکنواخت    ۶
۲-۲-۲-۳٫ ماشینهای موازی نامرتبط    ۷
۲-۲-۳ . جریان کارگاهی    ۷
۲-۲-۴ . جریان کارگاهی منعطف    ۷
۲-۲-۵ . کار کارگاهی    ۷
۲-۲-۶ . کار کارگاهی منعطف    ۷
۲-۲-۷ . سیستم کارگاهی باز    ۸
۲-۲-۸ . سیستم ساخت انعطاف پذیر    ۸
۲-۲-۹٫ سیستم کارگاهی وابسته    ۸
۲-۳٫ جزئیات و محدودیتهای نحوه پردازش کارها    ۸
۲-۳-۱٫ زمان دسترسی به کار rj    ۸
۲-۳-۲٫ زمان نصب وابسته به توالی Sijk    ۹
۲-۳-۳٫ شکست در کارها prmp    ۹
۲-۳-۴٫ اولویت در پردازش کارها prec    ۹
۲-۳-۵٫ خرابی ماشین brkdwn    ۹
۲-۳-۶٫ دسترسی محدود به ماشین ها Mj    ۹
۲-۳-۷٫ جایگشت prmu    ۹
۲-۳-۸٫ بلوکه شدن block    ۱۰
۲-۳-۹٫ بدون انتظار nwt    ۱۰
۲-۳-۱۰٫ گردش مجدد rcrc    ۱۰
۲-۳-۱۱٫ گروه های کاری fmls    ۱۰
۲-۳-۱۲٫ پردازش دسته ای batch(b)    ۱۰
۲-۴٫ توابع هدف    ۱۱
۲-۴-۱٫  بیشینه زمان تکمیل کارها Cmax    ۱۱
۲-۴-۲٫  بیشینه زمان تاخیر کارها Lmax    ۱۱
۲-۴-۳٫  مجموع زمان تکمیل کارها Cj    ۱۱
۲-۴-۴٫ مجموع وزنی زمان تکمیل کارها WjCj    ۱۱
۲-۴-۵٫ مجموع زمان دیرکرد کارها Tj    ۱۱
۲-۴-۶٫ مجموع وزنی زمان دیرکرد کارها WjTj    ۱۱
۲-۴-۷٫ مجموع تعداد کارهای با تاخیر Uj    ۱۱
۲-۴-۸٫ مجموع وزنی تعداد کار های با تاخیر WjUj    ۱۲
۲-۴-۹٫ مجموع زمان های زودکرد و دیرکرد کارها Ej+Tj    ۱۲
۲-۴-۱۰٫ مجموع وزنی زمانهای زودکرد و دیرکرد کارها WjEj+W’jTj    ۱۲
۲-۵٫ پیشینه تحقیق    ۱۲
۲-۶٫ ماشینهای موازی نامرتبط    ۱۳
۲-۷٫ دوبارهکاری    ۱۷
۲-۸٫  زمان نصب وابسته به توالی کارها    ۱۹
۲-۹٫ دسترسی محدود به ماشین ها    ۲۳
فهرست منابع    ۲۶

منابع

[۳] Vallada, e., and Ruiz, R., 2011. A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times. European Journal of Operation Research, 211, 612-622.

[۴] Pinedo,M.L., 2008. Scheduling: theory, algorithms and systems. New York: Prentice Hall.

[۵] Karp, R.M., 1972. Reducibility among combinatorial problems, Complexity of Computer Computations, Plenum Press, New York, 85-103.

[۶] Allahverdi, A., Ng, C., Cheng, T., and Kovalyov, M., 2008. A survey of scheduling problems with setup times or costs. European Journal of Operational Research, 187, 985–۱۰۳۲٫

[۷] McNaughton, R., 1959. Scheduling with deadlines and loss functions. Management Science, 6, 1-12.

[۸] Mokotoff, E., 2001. Parallel machine scheduling problems: a survey. Asia-Pacific, Journal of Operational research, 18, 193-242.

[۹] Lam, K., and Xing, W., 1997. New trends in parallel machine scheduling. International Journal of Operations & Production Management, 17, 326–۳۳۸٫

[۱۰] Cheng, T.C.E., and Sin, C.C.S., 1990. A state-of-the-art review of parallel machine scheduling research.  European Journal of Operational Research, 47, 271–۲۹۲٫

[۱۱] Glass, C.A., Potts, C.N., Shade, P. 1994. Unrelated parallel machine scheduling using local search, Mathematical and Computer Modelling 20 (2), 41–۵۲٫

[۱۲] Srivastava.B., 1998. An effective heuristic for minimizing makespan on unrelated parallel machines, Journal of the Operational Research Society, 49 (8), 886–۸۹۴٫

[۱۳] Ghirardi, M., and Potts, C.N., 2005.Makespan minimization for scheduling unrelated parallel

machines: a recovering beam search approach, European Journal of Operational Research, 165 (2),  ۴۵۷–۴۶۷٫

[۱۴] Horowitz. E., and Sahni. S,. 1976. Exact and approximate algorithms for scheduling nonidentical processors. Journal of the ACM, 23(2):317–۲۷٫

[۱۵] Lancia, G., 2000. Scheduling jobs with release dates and tails on two unrelated parallel machines to minimize the Makespan, European Journal of Operational Research, 120 (2), 277–۲۸۸٫

[۱۶] Fanjul-Peyro, L. and Ruiz, R., 2011.Size-reduction heuristics for the unrelated parallel machines scheduling problem. Computers & Operations Research,38, 301-309.

[۱۷] Fanjul-Peyro, L. and Ruiz, R., 2012.Scheduling unrelated parallel machines with optional machines and job selection. Computers & Operations Research, 39, 1745-1753.

[۱۸] Liaw, C.Y., Lin, Y.K., Chen, C.Y., and Chen, M., 2003. Scheduling unrelated parallel machines to minimize total weighted tardiness, Computers & Operations Research, 30(12), 1777–۱۷۸۹٫

۱٫ مقدمه

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

تحقیق در زمینه مسائل زمان­بندی در طی پنجاه سال گذشته به شکل گسترده­تری دنبال شده و تکامل یافته است و به موضوعی با تاریخچه تحقیقاتی غنی از قواعد و الگوریتم­های ساده و پیچیده نظیر قاعده جانسون[۴] ، قاعده زودترین موعد تحویل[۵] ، الگوریتم مور[۶] ، روش شاخه و حد[۷]، روش­های برنامه­ریزی پویا[۸]، و بسیاری از روش­های ابتکاری و فرا­ابتکاری تبدیل شده است.

در دهه شصت میلادی در اغلب مقاله­ها از تکنیک­های برنامه­ریزی پویا و یا مدل­سازی برنامه­ریزی عدد صحیح برای حل مسایل زمان­بندی و توالی عملیات[۹] استفاده می­شد. پس از انتشار مقاله ریچارد کارپ ]۵[ در اوایل دهه هفتاد میلادی در زمینه نظریه پیچیدگی، بسیاری از مطالعات انجام شده در این دهه بر روی سلسله مراتب پیچیدگی مسائل زمان­بندی متمرکز شد. نتایج مطالعات حاکی از آن بود که طیف گسترده­ای از مسائل زمان­بندی دارای پیچیدگی ساختاری می­باشند و به همین دلیل الگوریتم های دقیق[۱۰] قادر نخواهند بود که در یک زمان محاسباتی قابل قبول جواب بهینه این مسائل را بیابند. از این رو در سال­های بعد تلاش­های جدی به منظور ایجاد و توسعه الگوریتم­های ابتکاری و فراابتکاری صورت پذیرفت. یکی از اولین و در عین حال معروفترین الگوریتم­های فرا­ابتکاری، الگوریتم ژنتیک می­باشد که اصول اولیه آن توسط هالند[۱۱]و همکارانش در زمینه مدل­سازی فرآیند سازگاری سیستم­های طبیعی در قالب سیستم­های مصنوعی ارائه شد و ایده اصلی آن مبتنی بر نظریه تکاملی داروین[۱۲] می­باشد. از جمله دیگر الگوریتم­های فراابتکاری شناخته شده در حل مسائل بهینه­سازی می­توان به الگوریتم­های شبکه عصبی[۱۳]، ایمنی مصنوعی[۱۴]، شبیه­سازی تبرید[۱۵] ، اجتماع مورچگان[۱۶] و جستجوی ممنوع[۱۷] اشاره کرد. در راستای همین تلاش­ها در سال­های اخیر نیز الگوریتم­های متعددی به منظور حل مسائل بهینه­سازی در یک زمان محاسباتی قابل قبول ارائه شده است که از آن جمله می­توان از الگوریتم زنبور­عسل، الگوریتم رقابت استعماری[۱۸]، الگوریتم کرم شب­تاب[۱۹]، الگوریتم جستجوی هارمونی[۲۰] و چند الگوریتم دیگر یاد کرد.

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

۲-۲٫ محیط­های کارگاهی

۲-۲-۱٫ تک ماشینه[۲۱]

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

۲-۲-۲ . ماشین­های موازی[۲۲]

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

۲-۲-۲-۱٫ ماشین­های موازی یکسان

حالتی است که در آن ماشین­های کاملا یکسان به موازات یکدیگر قرار می­گیرند. در این حالت زمان پردازش  کار نوع j  روی تمامی ماشین­ها یکسان است.

۲-۲-۲-۲٫ ماشین­های موازی یکنواخت

حالتی است که در آن ماشین­ها دارای سرعت­های متفاوتی هستند ولی هر ماشین با یک نرخ ثابت کار می­کند.

۲-۲-۲-۳٫ ماشین­های موازی نامرتبط

حالتی است که در آن ماشین­ها دارای سرعت­های متفاوتی هستند و هیچ رابطه مشخصی بین سرعت پردازش ماشین­ها وجود ندارد. در این حالت زمان مورد نیاز برای پردازش هر کار هم به نوع کار و هم به نوع ماشین وابسته است.

۲-۲-۳ . جریان کارگاهی[۲۶]

در این سیستم تولیدی، هر کار به چند عملیات برای تکمیل شدن نیاز دارد. کارها روی چند ماشین در یک توالی یکسان پردازش می­شوند، اما زمان پردازش هر کار روی هر ماشین ممکن است متفاوت با زمان پردازش سایر کار­ها روی همان ماشین باشد.

۲-۲-۴ . جریان کارگاهی منعطف[۲۷]

این حالت تعمیم­یافته حالت جریان کارگاهی و ماشین­های موازی می­باشد. در این سیستم تعدادی کارگاه به­صورت متوالی وجود دارد که در هر کارگاه، تعدادی ماشین به طور موازی کار می­کنند و در هر کارگاه، یک کار حداکثر روی یک ماشین می­تواند انجام شود. اغلب مسائل دنیای واقعی، سازگار با محیط جریان کارگاهی منعطف می­باشند.

۲-۲-۵ . کار کارگاهی[۲۸]

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

۲-۲-۶ . کار کارگاهی منعطف[۲۹]

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

۲-۲-۷ . سیستم کارگاهی باز[۳۰]

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

[۱] Henry Laurence Gantt

[۲] Fredrick W.Taylor

[۳] Gantt Chart

[۴] Johnson Rule

[۵] Earliest Due-Date

[۶] Moore Algorithm

[۷] Branch And Bound

[۸] Dynamic Programming

[۹] Scheduling and Sequencing

[۱۰] Exact Algorithm

[۱۱] Holand

[۱۲] Darwin’s Evolutionary Theory

[۱۳] Neural Network

[۱۴] Artificial Algorithm

[۱۵] Simulated Annealing

[۱۶] Ant Colony

[۱۷] Tabu Search

[۱۸] Imperialist Competitive Algorithm

[۱۹] Firefly Algorithm

[۲۰] Harmony Search Algorithm

[۲۱] Single Machine

[۲۲] Parallel Machines

[۲۳] Identical Parallel Machines

[۲۴] Uniform Parallel Machines

[۲۵] Unrelated Parallel Machines

[۲۶] Flow Shop

[۲۷] Flexible Flow Shop

[۲۸] Job Shop

[۲۹] Flexible Job Shop

[۳۰] Open Shop

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