حل مسیله زمانبندی کارگاه باز با استفاده از الگوریتم جستجوی گرانشی و مدلسازی آن با شبکه پتری

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

کلیدواژه ها:

زمان بندی ، کار گاه باز ، حداکثر زمان تکمیل کارها ، زمان دیرکرد و زودکرد ، الگوریتم جستجوی گرانشی ، شبکه پتری زمانی