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

( اینجا فقط تکه ای از متن پایان نامه درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

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

• • زمانبندی کارها در سیستم های چند پردازنده ای

• • زمانبندی تخلیه و بارگیری بار در بنادر

• • زمانبندی حرکت تاکسی های بی سیم در داخل شهر

• • زمانبندی سرویس به مشتری در فروشگاه های بزرگ

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

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

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

به عبارت دیگر، وظیفه اصلی مسائل زمانبندی به تصمیم گیری در مورد تخصیص منابع و توالی عملیات منحصر می شود. تئوری زمانبندی شامل شیوه های متنوع و مختلفی است که در حل مسائل زمانبندی مفید واقع گردد. در واقع حوزه زمانبندی، به یک نقطه کانونی برای ایجاد، به کارکیری و ارزیابی روش های حل مسائل تبدیل شده است. این روش ها عبارتند از: رویکردهای ترکیبی، شیوه های شبیه سازی، روش های شبکه ای و رویکردهای ابتکاری. انتخاب شیوه مناسب به پیچیدگی مساله، طبیعت مدل، انتخاب معیار کارایی و عوامل مرتبط دیگر بستگی دارد [۳۹،۴۰].
مروری بر مدل های زمانبندی
عملکرد سیستم های تولیدی و خدماتی با معیارهای بسیاری مانند تعداد ماشین ها، سطح اتوماسیون، ویژگی های مربوط به ساختار مورد نظر، نوع سیستم حمل و نقل و غیره تعیین می شود. تفاوت در این معیارها تعداد بسیار زیادی از مدلی های زمانبندی را به وجود می آورد. پارامترهایی که در زیر بیان می شوند در طول این فصل مورد استفاده قرار خواهند گرفت.
چارچوب و نمادها
تعداد کارها برابر با n و تعداد ماشین ها برابر با m در نظر گرفته شده است. اندیس های i وj به کارهای i ام و j ام اشاره دارند و اندیس هایk و l به ماشین های k و l اشاره دارند. پارامترهای زیر مرتبط با کار i ام می باشند:
زمان پردازش^[۲۹](Pik) : بیان کننده مدت زمانی است که کار i ام باید بر روی ماشین k ام سپری کند.
زمان آماده به کار بودن^[۳۰] (ri) : زمانی که کار i وارد سیستم می شود و به عبارت دیگر زود ترین زمانی که پردازش کار i می تواند آغاز شود.
موعد تحویل^[۳۱] (di) : زمانی است که در آن، کار طبق قرار قبلی باید به مشتری تحویل داده شود. تکمیل کار بعد از موعد تحوید با جریمه همراه خواهد بود.
وزن^[۳۲] (wi) : وزن کار بیان کننده اولویت آن می باشد. وزن کار در حقیقت بیان کننده میزان اهمیت آن در ارتباط با دیگر کارها در سیستم می باشد. درحالی که می تواند مشخص کننده هزینه نگهداری کار در سیستم نیز باشد. داده های اشاره شده از نوع ایستا می باشند به این معنی که به زمانبندی بستگی ندارند. نقطه مقابل داده های دینامیک هستند که از قبل مشخص نبوده و وابسته به زمانبندی می باشند.
زمان تکمیل کار (Cik) : مدت زمانی است که کار i بر روی ماشین k تکمیل شده است.
ترکیب ماشین ها (محیط های کار)
مدل های زمانبندی معمولا از طریق ترکیب ماشین ها، محدودیت ها و توابع هدف مشخص می شوند. پارامترهای متعددی در تعریف مسائل زمانبندی و طبقه بندی آن ها مطرح هستند. از این رو لازم است که ابتدا پارامترهایی را که به نوعی در طبقه بندی مسائل دخیل هستند، مشخص نماییم. در ذیل فهرستی از این پارامترها گرد آوری شده اند.
تابع هدف (مانند حداقل کردن زمان اتمام کل کارها^[۳۳]، حداقل کردن حداکثر زمان دیرکردها)
زمان های آماده سازی (وابسته یا مستقل از توالی عملیات)
افق برنامه ریزی (کوتاه مدت – بلند مدت – میان مدت )