بخشی از مقاله
چکیده :
در اکثر سیستمهای ساخت و تولید، "زمان" بعنوان یک منبع محدود بشمار می رود، از این رو فعالیتهای این سیستمها، باید بگونهای "زمانبندی" شود که از مصرف بهینه این منبع اطمینان حاصل شود. در دنیای رقابتی امروز، توالی و زمانبندی کارآمد شرط لازم برای بقا است. بدین منظور باید کلیه فعالیتها برای رسیدنِ به موقع به هدف نهایی، زمانبندی و ترتیبدهی شوند. در این مقاله، یک مدل برنامهریزی ریاضی برای مسأله کارگاه باز چندهدفه با هدف حداقل کردن حداکثر زمان تکمیل کارها و مجموع زمان دیرکرد و زودکرد کارها به طور همزمان ارائه گردیده است. اساسا ماهیت چنین مسألهای چند جمله ای سخت می باشد و امکان استفاده از روشهایی که جوابهای بهینه تولید میکنند تنها برای مسائل با اندازه کوچک میسر است.
لذا بکارگیری روشهای فرا ابتکاری نه تنها امکان حل مسائل بزرگ را به ما میدهد، بلکه مدت زمان رسیدن به جوابهای بهینه یا نزدیک به بهینه نیز بسیار کوتاه میشود. در این مقاله مسأله زمانبندی کارگاه باز را با استفاده از الگوریتم جستجوی گرانشی به عنوان یک روش حل فرا ابتکاری، مورد بررسی قرار دادیم. سپس مسأله را با شبکه پتری زمانی مدلسازی نمودیم. جهت نشان دادن کارایی الگوریتم پیشنهادی، چند مسأله نمونه در ابعاد کوچک از الگوی Taillard حل شده و نتایج آن با بهترین نتایج ارائه شده توسط این الگو مقایسه میشود. سپس با حل مسأله نمونه در ابعاد متوسط و بزرگ، کارایی روش پیشنهادی بر اساس سه شاخص مهم کیفیت، تنوع و پراکندگی با الگوریتم کارامد SPEA-II مورد مقایسه قرار میگیرد. نتایج حاصل از مقایسات نشان از عملکرد بهتر روش پیشنهادی در هر سه نمونه مسأله کوچک، بزرگ و متوسط نسبت به روشهای مورد مقایسه دارد.
کلید واژهها: زمانبندی،کار گاه باز،حداکثر زمان تکمیل کارها، زمان دیرکرد و زودکرد، الگوریتم جستجوی گرانشی،شبکه پتری زمانی
-1 مقدمه
در دنیای رقابتی امروز یک برنامه زمانبندی کارا میتواند منجر به بهره برداری مؤثر از ظرفیتهای تولید و افزایش سوددهی واحد تولیدی گردد. در واقع زمانبندی، تخصیص منابع در یک افق برنامه ریزی برای اجرای مجموعهای از وظایف است. زمان همواره یک موضوع اساسی بوده و با توسعه جهان صنعتی، منابع در دسترس بحرانیتر می شوند. زمانبندی این منابع به افزایش کارایی و بهرهبرداری مناسب از ظرفیت تولید، کاهش زمان مورد نیاز برای تکمیل کارها ونهایتاً افزایش سوددهی یک سازمان منجر میشود.
یک مسأله زمانبندی در محیط کارگاه باز، با مجموعهای از فعالیتهایی مواجه است که در انجام آنها لزومی به رعایت ترتیب خاصی وجود ندارد. بنابراین فضای حل در مسائل زمانبندی کارگاه باز به طور قابل ملاحظه ای از فضای جواب مسائل زمانبندی دیگر بزرگتر است. در این مقاله از الگوریتم جستجوی گرانشی برای زمانبندی مسأله کارگاه باز استفاده خواهد شد. در الگوریتم جستجوی گرانشی مجموعهای از اجرام فضا را به صورت تصادفی جستجو می کنند. در این الگوریتم از نیروی جاذبه به عنوان ابزاری جهت تبادل اطلاعات استفاده شده است. هر جرم از طریق تاثیر نیروی سایر اجرام به درک تقریبی از فضایی پیرامون خود می رسد.
-1-1 تعریف زمانبندی مفهوم زمانبندی
اهمیت زمانبندی در سالهای اخیر به دلایلی نظیر افزایش تنوع در تقاضای مشتریان، کاهش چرخه عمر محصولات، تغییرپذیری بازارهای رقابتی و رشد سریع و روز افزون فرآیندها و تکنولوژیهای نوین در محیطهای ساخت و تولید، افزایش چشمگیری یافته است.[2] تقسیم بندی های مختلفی برای مسائل زمانبندی در ادبیات وجود دارد. به طور کلی این مسائل را میتوان بر اساس شش عامل، نیازهای تولید - کارگاه باز و کارگاه بسته - ، پیچیدگی پردازش - یک مرحله ای و چند مرحله ای - ، معیار عملکرد - تک معیاری و چند معیاری و عادی و غیرعادی - ، تغییرپذیری و طبیعت پارامترها مسأله - قطعی، تصادفی و حالت فازی - ، ترکیب و الگوی جریان کارگاه - تک ماشینی و چند ماشینی - و الگوی ورود کارها به کارگاه - کارگاه ایستا و پویا - دسته بندی کرد.
مسائل زمانبندی بسته به نوع کارگاه، قطعیت دادهها، نوع ورود قطعات و رویکردهای حل به دسته های مختلفی تقسیم می شود. این دسته بندی میتواند بر اساس نوع کارگاه به صورت تک ماشین، تولید کارگاهی 1ماشینهای موازی، جریان کارگاهی2، تولید سلولی 3، سیستم تولید انعطاف پذیر 4و خط مونتاژ در نظر گرفته شود. اگر کلیه پارامترهای مسئله به صورت قطعی در دسترس باشد، مسئله جزء دسته قطعی است و در مقابل اگر حداقل یک پارامتر قطعی نباشد مسئله به صورت احتمالی یا فازی در نظر گرفته میشود. اگر مجموعه کارهای در دسترس برای زمانبندی در طول زمان تغییر نکند سیستم، ایستا و اگر در طول زمان یک کار به مجموعه کارها اضافه شود سیستم، پویا نامیده میشود. سیستم پویا نیز خود به دو دسته برون خط 5و بر خط 6تقسیم میشود. در حالت برون خط تمام اطلاعات مربوط به فعالیتهایی که قرار است زمانبندی شوند مشخص است ولی در حالت بر خط اطلاعاتی در مورد فعالیتهایی که موجود نیستند، وجود ندارد[2] .رویکردهای حل مسئله نیز به دو دسته روشهای بهینه و ابتکاری7 تقسیم میشوند.
-2-1 تعریف کارگاه باز
یک مسأله زمانبندی در محیط کارگاه باز با مجموعهای از فعالیتها مواجه است که در انجام آنها لزومی به رعایت ترتیب خاصی وجود ندارد. بنابراین فضای حل در مسایل زمانبندی کارگاه باز به طور قابل ملاحظهای از فضای جواب مسایل زمانبندی دیگر نظیر زمانبندی گردش کاری و تولید کارگاهی بزرگتر است. در یک مسأله زمانبندی در محیط کارگاه باز m ماشین و n کار در نظر گرفته می شوند که هر کار حداکثر میتواند شامل n عملیات باشد. مسأله تولید کارگاه باز مشابه مسأله تولید کارگاهی بوده ولی با این تفاوت که ممکن است که کارها بر روی یک ماشین با هر توالی دلخواهی پردازش شوند. بنابراین در این مسائل توالی وابسته به عملیات وجود ندارد.
-3-1 الگوریتم جستجوی گرانشی
الگوریتم جستجوی گرانشی - Gravitational Search Algorithm - یک الگوریتم وابسته به هوش جمع و البته، بدون حافظه است.[3] محیط سیستم همان محدوده تعریف مساله می باشد. طبق قانون گرانش هر جرم محل و وضعیت سایر اجرام را از طریق نیروی جاذبه گرانشی درک میکند. بنابراین میتوان از این نیرو به عنوان ابزاری برای تبادل اطلاعات استفاده کرد. از بهینه یاب طراحی شده، می توان برای حل هر مساله بهینه سازی که در آن هر جواب مساله به صورت یک موقعیت در فضا قابل تعریف است و میزان شباهت آن با سایر جوابهای مساله به صورت یک فاصله قابل بیان باشد، استفاده نمود. میزان اجرام با توجه به تابع هدف تعیین میشوند.
-4-1 شبکه پتری زمانی
شبکههای پتری یکی از بهترین ابزارها برای مدلسازی سیستمهای وقایع گسسته تولیدی می باشند. مدل شبکه پتری مدلی گرافیکی است که دارای قابلیت دستیابی به معادلات حالت سیستم نیز می باشد. وجود شبکههای پتری زمانی، این امکان را در اختیار ما قرار می دهد که زمان تغییرات حالتهای سیستم را نیز در مدلسازی آن در نظر بگیریم و بتوانیم از این مدل در تحلیل و کنترل زمانی سیستم استفاده کنیم. به دلیل گرافیکی بودن شبکههای پتری می توان آنها را به عنوان فلوچارت یا بلوک دیاگرام برای نمایش رفتار سیسستم در نظر گرفت. در یک شبکه پتری منابع و شرایط موجود در سیستم را توسط مکانها به صورت دایره و وقایع و رخدادها را توسط گذارها به صورت یک مستطیل باریک نمایش می دهند. وجود منابع، برقراری شرایط و به طور کلی حالت توزیع شده سیستم توسط توکنها که به صورت نقطههایی درون مکانها قرار می گیرند مشخص میشود. Gonzalez و همکارانش در سال 1976 نشان دادند که مسأله زمانبندی کارگاه باز یک مسأله NP-hard است.[4] بنابراین رسیدن به یک جواب بهینه برای حل این مسأله کاری دشوار و پیچیده است. به همین دلیل در این مقاله از الگوریتم ابتکاری جستجوی گرانشی برای زمانبندی مسأله کارگاه باز استفاده نمودهایم.
-6-1 الگوریتم جستجوی گرانشی پیشنهادی
در این مقاله ما یک ساختار به صورت آرایه یک بعدی برای نمایش جوابهای مسأله ارائه دادهایم. هر آرایه یک عامل نامیده میشود که بیانگر نحوه زمانبندی مسأله کارگاه باز میباشد. گام اول در الگوریتم جمعیتی جستجوی گرانشی تولید مجموعهای از عامل ها بصورت تصادفی به عنوان جمعیت اولیه میباشد . در مرحله بعد با بکارگیری عملیات جستجوی گرانشی عاملهای جدید تولید میشود. عملیات جستجوی گرانشی شامل محاسبه نیروی بین عاملها، محاسبه شتاب، سرعت و موقعیت جدید عامل ها می باشد. بر اساس عملیات گرانشی عاملهای جدید تولید می شوند. پس از تولید عاملهای جدید، نوبت به مرحله ارزیابی عامل ها می رسد. سپس برازنده ترین عامل ها از میان عامل های جدید و قبلی انتخاب می شوند. از آنجا که مسأله تحقیق یک مسأله بهینه سازی چندهدفه می باشد، از روش بهینهسازی پارتو برای بدست آوردن جواب بهینه استفاده شود.سرانجام، الگوریتم جستجوی گرانشی پس از طی چندین نسل به تدریج به سمت جواب بهینه همگرا شده و با برقراری شرط توقف، به پایان خواهد رسید.
-5-1 رویکرد حل مسأله
مسأله زمانبندی کارگاه باز به دو زیر مسأله تعیین اولویت کلی و جزئی تقسیم میشود. زیر مسأله تعیین اولویت کلی بیان می کند که کلیه عملیاتهای کارهای مختلف با چه ترتیبی روی ماشینها انجام می شوند. زیر مسأله تعیین اولویت جزئی بیان می کند که عملیات مربوط به یک کار با چه ترتیبی روی ماشینها انجام می شوند. تابع هدف مسأله شامل حداقل کردن زمان تکمیل کارها و مجموع زمان دیرکرد و زودکرد کارها به طور همزمان میباشد. ساختار کلی الگوریتم جستجوی گرانشی پیشنهادی شامل طراحی عامل، تولید جمعیت اولیه، مقدار دهی اولیه آرشیو پارتو، عملیات جستجوی گرانشی و تولید عامل های جدید، انجام فرایند ارزیابی و بروز رسانی آرشیو پارتو میباشد. رویه کلی الگوریتم جستجوی گرانشی پیشنهادی در شکل 1-1 نشان داده شده است.
