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

A Multi-Objective Fuzzy Job Shop Scheduling by Extremal Optimization

مساله زمانبندي كاركارگاهي به‌بررسي نحوه توزيع كارها بين ماشين ها مي پردازد به طوري كه كارها در كمترين زمان ممكن انجام شوند. در اين مساله فاكتورهايي نظير زمان پردازش فعاليت ها و زمان موعد مقرر براي تحويل كارها، اغلب بصورت مبهم براي تحليل گر تعريف مي شوند. در چنين شرايطي، استفاده از پارامترهاي فازي و اهداف چندگانه مبتني بر علم فازي، لازم به نظر مي رسد. كه باعث ايجاد مساله زمانبندي كاركارگاهي فازي مي شود. اين مساله از مسائل غير چندجمله اي (NP) مي باشد، به همين دليل روشي مبتني بر الگوريتم اكتشافي بهينه سازي اكسترمال پيشنهاد مي شود. به طوري كه فعاليت هاي كم ارزش را با احتمال بيشتر انتخاب و تغيير مي دهد، اين باعث مي شود تعداد فعاليت هاي كم ارزش، كمتر و تعداد فعاليتهاي با ارزش يكسان، بيشتر شود در اين حالت هر تغيير جزئي در زمانبندي، تغيرات زيادي در آن ايجاد مي كند بنابراين باعث فرار از بهينه محلي شده و به سمت بهينه سراسري حركت مي‌كند. با توجه به نتايج حاصل از شبيه سازي بر روي داده هاي آزمايشي 6×6 و 10×10، روش پيشنهادي، رضايتمندي مطلوبي از اهداف مساله را با سرعت همگرايي مناسب، در مقايسه با روش هاي ديگر نشان مي دهد، درستي جواب هاي ارائه شده و همچنين صحت روش پيشنهادي با استفاده از اصل همگرايي، آزمون آماري t و خطاي امكان پذيري(F) اثبات شده است.

Job shop scheduling deals with distributions between jobs in order to find a schedule with minimum possible time. To formulate job shop scheduling problems, various factors such as the activity processing time and due date for delivering jobs are often ambiguously known to the analyst. In these situations, the use of fuzzy parameters and multi-objective goals based on fuzzy knowledge seems necessary. Since this problem is non polynomial, we propose a method based on extremal optimization in order to select and modify less valuable but more probable activities. This method leads to decrease the number of less valuable activities and to increase the number of activities with the same value. In such cases, any partial change in scheduling may produce big changes. For instance, it leads to escape from local optima and move toward global one. Lots of simulations on and experimental data, demonstrate proper convergence rate and good results in comparison with other methods. The correctness of given results and proposed algorithm have been proven by means of axiom of convergence, statistical t-test t and possibility error (F).