زمانبندي كارِكارگاهي چند مسيره با استفاده از الگوريتم بهينه ‌سازي گروه ذرات

MULTIPLE ROUTE JOB SHOP SCHEDULING USING PARTICLE SWARM OPTIMIZATION APPROACH

مسئله‌ زمانبندي كارِكارگاهي، در گروه مسائل NP-hard طبقه‌ بندي مي‌شود. وجود چند مسير پردازش براي هركار نيز موجب پيچيده‌تر شدن اين مسئله شده و لذا استفاده از الگوريتم‌هاي فراابتكاري، به عنوان روشي موثر در حل اينگونه مسائل، مورد توجه بسياري از محققين بوده است. در اين مقاله ، ابتدا مدلِ برنامه‌ريزي غيرخطي عدد صحيح مختلط از مسئله‌ زمانبندي كارِكارگاهيِ چند مسيره ارائه خواهد شد. سپس يك الگوريتم فراابتكاري، بر مبناي الگوريتم بهينه ‌سازي گروه ذرات، با هدف كمينه ‌سازي ‌‌زمان اتمام كارها، براي حل مسئله مذكور ارائه مي‌گردد . همچنين جهت ارزيابي عملكرد الگوريتم پيشنهادي، 30 مسئله در ابعاد كوچك، متوسط و بزرگ، كه قبلاً با استفاده از الگوريتم ايمني مصنوعي توسط ديگر محققين حل و نتايج آن گزارش شده است ، با الگوريتم پيشنهادي حل و نتايج با يكديگر مقايسه شده‌اند . از نقطه نظرِ زمان مورد نياز براي توليد جواب و مقدار بدست آمده براي تابع هدف، نتايج حاكي از عملكرد مطلوب الگوريتم پيشنهادي است.

The Job shop Scheduling Problem (JSP) is classified in the group of NP- hard problems. The Multiple Route JSP (MRJSP) is an extension to JSP where each part may have more than one route for its production and the numbers of operations in routes are not necessarily equal. The solution to this problem has become even more complicated due to the existence of multiple alternative routes for parts and, thus, meta-heuristic algorithms are the only approaches that can efficiently obtain good slotions within a reasonable computational time. In this paper, mathematical formulation of the MRJSP is first presented. Then, a meta-heuristic approach based on Particle Swam Optimization (PSO) algorithm is proposed for the minimization of makes pan. In order to evaluate the effectiveness of the proposed approach, 30 problems in small, medium, and large size, which have already been used by other researchers, are adopted and re-solved using the proposed approach. Problems are also formulated and solved using Lingo software and the results are compared. The computational results show that the proposed approach outperforms the approach based on the immune algorithm, already reported by other researchers, and can effectively generate high-quality schedules in a timely fashion.