۳-۲- مدلسازی سیستم تولید در برنامه ریزی و زمانبندی
بهتر است در ابتدا یک محیط تولیدی عمومی را فرض کنیم و سپس نقش برنامه ریزی و زمانبندی را در آن توصیف نماییم. سفارشاتی که به یک سیستم تولیدی ارائه میشوند باید به کارهایی[۳۸] با زمانهای سررسید معین تبدیل شوند. هرکدام از این کارها باید در یک مرکزکاری[۳۹] مشخص روی تعدادی ماشین با ترتیب یا توالی از پیش طراحی شدهای اجرا شوند. از آنجایی که هرکدام از ماشینها ممکن است در مقاطع زمانی خاصی درگیر انجام کار باشند، اجرای هرکدام از کارها ممکن است بعلت مشغول بودن ماشینهای مربوطه با تأخیر مواجه شود. رویدادهای ناخواستهای در کارگاه مانند خرابی ماشین(ها)، زمانهای کار طولانیتر از انتظار و غیره میتوانند برنامه زمانبندی اجرای کارها را با مشکل مواجه کنند. در چنین محیطهایی تهیه یک برنامه زمانی دقیق و کامل می تواند به کارایی و کنترل بهتر عملیات کمک کند.
کارگاه تنها قسمتی از سازمان که تحت تأثیر فرایند زمانبندی قرار دارد نیست. فرایند زمانبندی همچنین با فرایند برنامه ریزی تولید – که برنامه های میان مدت و دراز مدت تولید را برای سازمان مشخص می کنند – در ارتباط تنگاتنگ است. تصمیم گیریهایی که دراین سطح از سازمان گرفته می شود ممکن است بر برنامه های زمانبندی کارگاهی نیز مستقیماً تأثیر گذار باشند. شکل ۳-۱ نمودار جریان اطلاعات را در یک سیستم تولیدی نوعی نمایش میدهد [۹].
سیستم زمانبندی تولید دارای سه نوع ورودی است. سفارش مشتری (یا محصولاتی که باید تولید شوند)، برنامه تولید (هرکدام از عملیات مورد نیاز برای تولید هر محصول باید روی چه منبع یا منابعی اجرا شوند)، وضعیت منابع با توجه به محدودیتها و قیود کارگاه. سفارش مشتری دارای خصوصیات نوع محصول، تعداد یا مقدار و زمان تحویل میباشد. برنامه تولید باید مشخص کننده روتینگ[۴۰] تولید محصول و تخمین زمان یا هزینه استاندارد تولید هر عملیات در روتینگ بر روی منبع مقتضی است. خروجی سیستم زمانبندی تولید، ترتیب زمانی اجرای عملیات برای تولید محصول یا محصولات نهایی در قالب گانت چارت[۴۱] است که در آن دقیقاً مشخص شده که هر کدام از عملیات بر روی کدام یک از منابع و با چه زمانهای آغاز و پایانی اجرا میشوند.
در تولید، سیستمهای برنامه ریزی و زمانبندی باید با فرایندهای دیگر تصمیم گیری سازمان در تعامل باشند. یک فرایند بسیار عمومی در این زمینه برنامه ریزی مواد (MRP)[42] است. هنگامی که زمانبندی عملیات در حال برنامه ریزی است، مهم است که تمام مواد خام و منابع مورد نیاز در زمان مقتضی فراهم باشند. زمانهای برنامه ریزی شده اجرای کار باید توسط سیستم برنامه ریزی و زمانبندی و با هماهنگی سیستم MRP بدست آیند.
سیستمهای MRP بطور معمول دارای جزئیات نسبتاً کمی از برنامه اجرای کارها هستند. هر کار، دارای یک ساختار مواد (BOM)[43] است که قطعات و مواد مورد نیاز برای انجام عملیات تولید را مشخص میسازد. سیستم MRP انبار مربوط به هرکدام از قطعات یا مواد را زیرنظر دارد. بعلاوه زمان سفارش هرکدام از قطات را نیز معین می کند. در سازمانهایی که هیچ سیستم برنامه ریزی و زمانبندی وجود ندارد، عمدتاً به برنامه MRP بسنده می شود. بدیهی است که یک سیستم تولیدی پیچیده نمیتواند به برنامه حاصل از MRP بسنده کند. در چنین سازمانهایی، وجود یک سیستم برنامه ریزی وزمانبندی عملیات، ضروری است.
امروزه کارخانجات تولیدی مدرن از سیستمهای اطلاعات تولید[۴۴] که شامل شبکه ای از کامپیوترهای بهم پیوسته و پایگاههای داده[۴۵] مختلف است استفاده می کنند. کامپیوترهای محلی،
شکل ۳-۱: نمودار جریان اطلاعات در یک سیستم تولیدی [۹]
ایستگاههای کاری و ترمینالهای ورود اطلاعات به سرورهای مرکزی یا پایگاههای داده مرتبط هستند و از داده های ثبت شده استفاده یا داده های جدید را ثبت می کنند. برنامه ریزی و زمابندی هم توسط یکی از کامپیوترهای مستقر در این شبکه انجام میگردد. هرکدام از ترمینالهای شبکه میتوانند از اطلاعات برنامه ریزی و زمابندی استفاده کنند و همچنین نقش اساسی در ثبت رویدادهای کارگاه مانند تغییرات در وضعیت ماشینها، کارها و انبار ایفا کنند.
در سیستمهای امروزیتر، کلیه فرایندها و جریانهای اطلاعات سازمان در یک سیستم یکپارچه اطلاعاتی تحت عنوان Enterprise Resource Planning System مجتمع شده و امکانات وسیعی در کنترل، تصمیم گیری و ارزیابی فرایندها، از بالاترین سطوح سازمان و زیرمجموعههای آن و حتی تأمینکنندگان و مشتریان تا جزئیترین سطوح فعالیت در سازمان را در اختیار قرار می دهند.
۳-۳- کارها، ماشینها و کارگاهها
در این بخش تعاریف پایهای و نمادهای استفاده شده در مدلسازی مسئله برنامه ریزی و زمانبندی شرح داده شده است. در تمام این پایان نامه تعداد کارها با و تعداد ماشینها با نمایش داده شده است. زیرنویسهای برای نشان دادن اندیس کار و زیرنویسهای برای نشان دادن اندیس ماشین استفاده شده اند.
زمان کار[۴۶] (): زمان کار نشان دهنده مدت زمانی است که انجام کار روی ماشین بطول میانجامد. درصورتیکه زمان کار به ماشین وابسته نباشد از زیر نویس صرفنظر کرده و آن را با نمایش میدهیم. نرخ تولید یک ماشین برهمین اساس بصورت تعریف می شود که بیانگر تعداد دفعات انجام کار در واحد زمان است.
زمان ورود[۴۷] (): زمان ورود کار زمانی است که کار به سیستم وارد می شود؛ یعنی زودترین زمانی که کار می تواند آغاز شود را زمان ورود آن کار مینامند.
زمان تحویل[۴۸] (): زمان تحویل زمانی است که نتیجه انجام کار باید به مشتری تحویل داده شود یا به بیان دیگر زمانی است که انجام کار در آن باید خاتمه یافته باشد. زمان خاتمه انجام کار می تواند دیرتر از زمان تحویل آن باشد اما باعث ایجاد جریمه[۴۹] می شود. درصورتیکه زمان تحویل بطور قطع باید رعایت شود، به این زمان، مهلت[۵۰] گفته می شود.
وزن کار (): وزن یک کار در واقع یک ضریب اولویت برای آن کار است که بیانگر اهمیت اجرای آن کار در مقایسه با کارهای دیگر در سیستم است.
چهار مشخصهای که در بالا ذکر شدند، اطلاعات ایستا بودند چراکه به زمانبندی انجام شده وابسته نیستند. در مقابل این مشخصات، اطلاعاتی که ثابت نبوده و به زمانبندی وابسته هستند اطلاعات پویا نام دارند. در ادامه به چند مورد از مهمترین اطلاعات پویا میپردازیم.
زمان شروع (): زمان شروع ، زمان آغاز اجرای کار روی ماشین است و در صورتیکه زیرنویس در آن نیامده باشد، به معنی زمان شروع اولین عملیات[۵۱] مربوط به کار در سیستم است.
زمان تکمیل (): زمان تکمیل ، زمان خاتمه اجرای کار روی ماشین است و درصورتیکه زیرنویس در آن نیامده باشد، به معنی زمان تکمیل آخرین عملیات مربوط به کار در سیستم است.
یکی از مشخصههای مهم در مدل زمانبندی، جانمایی ماشینها در سیستم است. چندین جانمای مهم در طراحی کارگاه برای ماشینها وجود دارد که در ادامه به آنها اشاره می شود.
مدل تک ماشین[۵۲]: بسیاری از سیستمهای تولید میتوانند بعنوان یک مدل تک ماشین درنظر گرفته شوند. بعنوان مثال اگر در یک سیستم چند ماشین، یک ماشین بعنوان گلوگاه سیستم مطرح باشد، تنها همان ماشین تعیین کننده عملکرد سیستم زمانبندی در سیستم خواهد بود. در چنین شرایطی منطقی است که ابتدا ماشین گلوگاه سیستم در مرحله اول برنامه ریزی و زمانبندی شده و ماشینهای دیگر به طبع آن در مراحل بعدی قرار بگیرند. این راه حل ایجاب می کند که در مرحله اول مسئله برنامه ریزی و زمانبندی به یک مدل تک ماشین تقلیل پیدا کند. مدل تک ماشین همچنین در سیستمهایی که دارای پیچیدگی بسیار زیاد هستند کاربرد دارد. در این سیستمها معمولاً سعی می شود که مسئله بزرگ مورد مطالعه به چندین مسئله تقلیل یافته کوچکتر (مانند مسئله زمانبندی مدل تک ماشین) شکسته شده و سپس حل شود.
مدل ماشینهای موازی[۵۳]: یکی از تعمیمهای مدل تک ماشین بصورت مجموعه ای از ماشینهاست که بصورت موازی در کنار هم کار می کنند. تعداد زیادی از سیستمهای تولیدی از تعدادی مراکز کاری تشکیل شده اند که هر کدام از آنها شامل تعدادی ماشین موازی هستند. در اغلب موارد ماشینهای موجود در یک مرکز کاری مشابه هستند، و بدین ترتیب یک کار که به مرکز کاری وارد شده است می تواند روی هرکدام از آن ماشینها اجرا شود. دلایلی که در اهمیت توجه به مدل تک ماشین مطرح شدند میتوانند درمدل ماشینهای موازی هم مطرح باشند. مثلاً اگر در یک سیستم با چندین مرکز کاری، یکی از مراکز گلوگاه اجرای فرایندهای سیستم باشد، میتوان آن را بعنوان یک مرکز کاری با ماشینهای موازی فرض کرده و برنامه ریزی و زمانبندی را ابتدا برای آن و سپس برای باقی مراکز کاری انجام داد.
باید به این نکته توجه داشت در مدل ماشینهای موازی لزوماً همواره تمام ماشینها مشابه نیستند مثلاً برخی ماشینهای مجموعه ممکن است قدیمیتر باشند و درنتیجه سرعت یا کیفیت اجرای کارها روی این ماشینها کمتر از سرعت یا کیفیت اجرای همان کارها روی ماشینهای دیگر از همان نوع باشد.
مدل جریان کارگاهی [۵۴]: در بسیاری از سیستمهای تولیدی، خصوصاً تولید کنندگان محصولات مونتاژی، اجرای هر کار مستلزم انجام تعدادی عملیات پشت سر هم روی تعدادی ماشین است. درصورتی که روتینگ همه کارها یکسان باشند یعنی همه کارها برای اجراشدن به ترتیب یکسان از ماشینهای یکسانی عبور کنند، به آن جریان کارگاهی گفته می شود. در چنین سیستمی، ماشینها بصورت سری قرار داشته و با هم راه اندازی میشوند. هر کار پس از اجرا شدن روی یک ماشین به صف انتظار اجرای ماشین بعدی منتقل می شود. یک تعمیم از مدل جریان کارگاهی، مدل جریان کارگاهی منعطف[۵۵] است. جریان کارگاهی منعطف دارای تعدادی مراحل مختلف است که هر کدام از مراحل شامل تعدادی ماشین موازی هستند و در مجموع شیوه ارتباط مراحل مختلف بصورت یک جریان کارگاهی است. در هرکدام از مراحل، این انعطاف وجود دارد که کار رسیده بتواند روی هرکدام از ماشینهای آن مرحله اجرا شود.
مدل کار کارگاهی[۵۶]: در برخی کارگاهها، کارهای رسیده دارای روتینگهای متفاوتی هستند. در نتیجه هر کار برای اجرا شدن باید از ماشینهای مشخصی که در روتینگ آن معین است عبور کند. چنین مدلی را مدل کار کارگاهی نامیده اند. در واقع مدل جریان کارگاهی حالت خاصی از مدل کار کارگاهی است که در آن تمام کارها دارای روتینگ یکسان هستند. یک تعمیم از مدل کار کارگاهی، مدل کار کارگاهی منعطف[۵۷] است. در این مدل، هر کار می تواند روی یک یا چند ماشین اجرا شود. بنابراین در مدل کار کارگاهی منعطف، پیش از زمانبندی اجرای عملیات باید معین شود هر کار روی کدام ماشین اجرا گردد.
مدل زنجیره تأمین[۵۸]: این مدل، یک مدل سطح بالا است که در آن یک محیط تولیدی به شبکه ای از اجزای بهم مرتبط تقسیم می شود که هرکدام از این اجزا خود دارای یک مدل کار کارگاهی (منعطف) یا جریان کارگاهی (منعطف) هستند.
۳-۴- معیارهای کارایی در زمانبندی تولید
در عمل از معیارهای کارایی مختلفی برای برنامه ریزی و زمانبندی در سیستمهای تولیدی استفاده می شود اما در واقع همگی این معیارهای کارایی ترکیبی از تعدای معیار پایه هستند. در ادامه به چند نمونه از معیارهای پایهای و معروف در بررسی عملکرد سیستمهای زمانبندی تولید اشاره میگردد.
معیارهای توان عملیاتی[۵۹] و Makespan: در بسیاری از سیستمهای تولیدی، افزایش میزان توان عملیاتی یکی از مهمترین معیارهایی کارایی برنامه ریزی به شمار میرود تا جایی که در بسیاری از موارد عملکرد مدیران براساس میزان بهبود در این معیار اندازه گیری می شود. زمان throughput یک قطعه، مدت زمانی است که طول میکشد تا آن قطعه از سیستم عبور کند. توان عملیاتی یک سیستم تولیدی که برابر نرخ خروجی آن نیز است، بر اساس ظرفیت ماشینهای گلوگاهها (یعنی ماشینهای دارای کمترین ظرفیت) مشخص می شود. بنابراین بیشینه کردن میزان توان عملیاتی یک سیستم تولیدی معادل بیشینه کردن ظرفیت تولید ماشینهای گلوگاه سیستم است.
معیار Makespan زمانی مهم ارزیابی می شود که تعداد کارها محدود باشد. Makespan که با نشان داده می شود عبارت از زمانی است که آخرین کار خاتمه پیدا کند.
که در آن زمان خاتمه کار است. معیار Makespan شباهت زیادی به معیار توان عملیاتی دارد.
معیارهای وابسته به زمان تحویل[۶۰]: تعداد زیادی معیار کارایی وابسته به زمان تحویل کار وجود دارد که در ادامه به برخی از آنها اشاره شده است.
اغلب سیستمهای زمانبندی براین اساس ایجاد میشوند که دیرشدگی[۶۱] انجام کارها را به حداقل برسانند. دیرشدگی انجام یک کار بصورت زیر تعریف می شود:
که در آن زمان تحویل کار است. حداکثر دیرشدگی در یک سیستم بصورت زیر تعریف می شود:
کمینهسازی بیشینه دیرشدگی معادل کمینهسازی دیرشدگی مربوط به بدترین شرایط کارایی در سیستم زمانبندی است.
معیار کارایی دیگری که در این زمینه قابل توجه است، تعداد کارهای دیرکرد[۶۲] است. دیرکرد با رابطه زیر بدست می آید:
مجموع دیرکرد کارها بعنوان یک معیار کارایی سیستم زمانبندی نیز بصورت تعریف می شود.
هزینه های برپایی[۶۳]: اغلب هنگامی که قصد داریم به بیشینهسازی توان عملیاتی یا کمینهسازی Makespan بپردازیم، باید به کمینه بودن هزینه های راه اندازی کارها نیز توجه لازم را داشته باشیم. باید توجه داشت که هزینه های راه اندازی لزوماً متناسب با زمانهای راه اندازی نیستند. بعنوان مثال هزینه های راه اندازی برای ماشینی که دارای ظرفیت بسیار زیادی است، قابل توجه نیست حتی اگر این راه اندازی شامل به هدر رفتن منابع یا زمان زیادی شود.
هزینه های انبارداری کالای درجریان ساخت[۶۴]: هدف مهم دیگر در یک سیستم زمانبندی کمینه کردن هزینه های نگهداری و انبارداری کالای در جریان ساخت (WIP) است. WIP باعث افزایش هزینه های نقل و انتقال می شود ضمن آنکه WIPهای قدیمیتر همواره در معرض آسیبهای ناشی از نقل و انتقال و نگهداری قرار دارند. معیار دیگری که می تواند بعنوان جایگزین WIP مورد استفاده قراربگیرد میانگین زمان throughput است. کمینهسازی میانگین توان عملیاتی، با وجود سطح خروجی ثابت، باعث کاهش WIP خواهد شد. همچنین کمینهسازی زمان throughput وابستگی نزدیکی به کمینهسازی مجموع زمانهای تکمیل کارها یعنی دارد. هدف شرح داده شده اخیر، معادل کمینهسازی میانگین تعداد کارهای سیستم نیز میباشد.
هزینه های انبارداری محصول نهایی[۶۵]: کمینهسازی هزینه های انبارداری محصولات تولید شده نیز یکی دیگر از اهداف مهم در سیستمهای زمانبندی محسوب میگردد. درصورتیکه سیستم تولیدی از نوع ساخت-براساس-سفارش[۶۶] باشد، آنگاه هزینه های انبارداری محصول معادل هزینه های تعجیل[۶۷] در تولید خواهند بود. در سیستمهای Just-In-Time معمولاً کمینهسازی مجموع تعجیل کارها بعنوان یک هدف مهم مطرح است. چرا که در یک سیستم JIT بدلیل اجتناب از هزینه های نگهداری و رسیدگی نباید کارها زودتر از موعد انجام شوند.
هزینه های انتقال[۶۸]: در سیستمهایی که شامل بخشهای تولیدی مجزا و دور از هم هستند، هزینه های انتقال کالاها بین مراکز کاری می تواند قسمت چشمگیری از هزینه های تولید باشد. از این روی کاهش هزینه های انتقال نیز می تواند از جمله اهداف مهم سیستمهای برنامه ریزی و زمانبندی محسوب گردد.
۳-۵- مدلسازی ریاضی مسأله زمانبندی کار کارگاهی منعطف[۶۹]
مسائل زمانبندی در تمام حوزه های علوم از مهندسی کامپیوتر گرفته تا اقتصاد وجود داشته و نقش مهمی دارند. اغلب مسائل زمانبندی، از نوع مسائل بهینهسازی ترکیبیاتی پیچیده هستند که حل آنها در حوزه زمان بوسیله الگوریتمهایی که دارای پیچیدگی زمانی چندجملهای هستند ناممکن است. در میان این مسائل، زمانبندی کار کارگاهی منعطف یکی از پیچیدهترین مسائل بهینهسازی ترکیبیاتی است.
زمانبندی کار کارگاهی منعطف یکی از مباحث مهم در مدیریت تولید و همچنین بهینهسازی ترکیبیاتی است. ثابت می شود که بدلیل پیچیدگیهای محاسباتی بسیار زیاد، غیرممکن است که بتوان جواب بهینه چنین مسألهای را در مقیاسهای عملی با روش های متداول در بهینهسازی ترکیبیاتی بدست آورد. برای حل مسأله زمانبندی در محیط کارگاهی دو رویکرد وجود دارد: رویکرد سلسله مراتبی[۷۰] و رویکرد یکپارچه[۷۱]. در رویکرد سلسله مراتبی، تخصیص وظایف به ماشینها و توالی عملیات روی ماشینها بطور جداگانه بررسی و حل میشوند. در رویکرد یکپارچه، تخصیص وظایف و توالی عملیات توأمان مورد توجه و حل قرار میگیرند. از آنجایی که مسأله زمانبندی کار کارگاهی منعطف یک مسأله NP-hard است روش بکار گرفته شده در این پایان نامه یک روش مکاشفهای[۷۲] مبتنی بر همکاری تعدادی عاملهای واکنشی ساده و تکامل آنها در جهت جستجوی جواب(های) بهینه است.
در مسأله کلاسیک زمانبندی کارگاهی[۷۳]، اجرای تعداد کار روی ماشین مستقل زمانبندی می شود. برای هر کار مسیر[۷۴] اجرا، بطور کامل مشخص و معین است. همه ماشینها از لحظه صفر تا انتهای کارها آماده هستند و کارها بدون هیچگونه رقابتی برای در اختیار گرفتن ماشینها اجرا میشوند. مسأله عمومی زمانبندی کارگاهی یک مسأله شدیداً NP-hard است. امروزه انعطافپذیری ماشینها و خطوط تولید در صنایع نیازمند سیستمهایی برای برنامه ریزی چنین شرایطی است. مسأله زمانبندی کار کارگاهی منعطف تعمیمی از مسأله زمانبندی کارگاهی عمومی که در بالا شرح داده شد است که در آن فرض می شود که به ازای هر عملیات، حداقل یک نوع ماشین برای اجرای آن در کارگاه وجود دارد. بنابراین زمانبندی کار کارگاهی منعطف علاوه بر مسأله زمانبندی شامل یک زیر مسأله تخصیص وظایف برای تخصیص هر کدام از عملیات به یکی از ماشینهایی که قابلیت اجرای آنرا دارند نیز میباشد. بنابراین مسأله زمانبندی کار کارگاهی منعطف دارای دو مشکل است: یکی تخصیص هرکدام از عملیات به ماشین مقتضی و دوم زمانبندی آنها در جهت حداقل سازی یک یا تعدادی از توابع هدف[۷۵] معین از پیش تعریف شده.
مدل ریاضی مسأله زمانبندی کار کارگاهی منعطف در این تحقیق بصورت زیر درنظر گرفته شده است. در این مدل ماشین و کار[۷۶] تعریف شده است. هر کار شامل تعدادی عملیات است که با نمایش داده میشوند که در آن اندیس کار مربوطه و اندیس عملیات مربوط به کار ام است و تعداد عملیات مربوط به کار ام میباشد. درنتیجه نشان دهنده عملیات ام از کار ام است. بهمین ترتیب مجموعه ماشینها با نمایش داده می شود. مجموعه ای از ماشینهایی را که میتوانند عملیات را انجام دهند را با نمایش میدهیم. مجموعه توسط ماتریس با اعضای زیر تعریف می شود.
که در آن اندیس ماشین، اندیس کار و اندیس عملیات مربوط به کار است. اجرای هر عملیات روی ماشین به اندازه واحد زمانی بطول خواهد انجامید.
با توجه به تعاریف فوق ماتریسهای زیر را تعریف میکنیم:
فرم در حال بارگذاری ...
