بكارگيري الگوريتم انجماد تدريجي براي زمانبندي كارها در كارگاه جرياني دو ماشيني با هدف توليد به موقع

Using the Simulated Annealing to Solve a JIT Scheduling Problem in the Two-Machine Flow Shop

در اين تحقيق مساله زمانبندي n كار مستقل با زمان سررسيد متفاوت بر روي 2 ماشين در محيط كارگاه جرياني ترتيبي مورد بررسي قرار مي‌گيرد. با توجه به اينكه مساله فوق جز مسايل NP-hard محسوب مي‌گردد، يك الگوريتم انجماد تدريجي براي حل آن ارايه شده است. به منظور ارزيابي جواب‌ها از معيار حداقل جمع وزني ديركردها و زودكردهاي كارها به عنوان تابع هدف استفاده شده است كه اين هدف هم‌راستا با اهداف سيستم‌هاي توليد به موقع محسوب مي‌گردد. الگوريتم پيشنهادي در 4 سناريو ارايه مي‌شود كه اين 4 سناريو با درنظر گرفتن دو حالت مختلف براي زنجيره ماركوف و نحوه كاهش دما حاصل شده و در نهايت باتوجه به تحليل نتايج و كيفيت جوابهاي حاصل، بهترين سناريو به عنوان سناريو نهايي معرفي شده است. كارايي الگوريتم پيشنهادي با حل مسايل متنوع در ابعاد مختلف مورد تحليل و بررسي قرار گرفته و براي مسايل كوچك (تعداد كار كمتر از 25) نتايج بدست آمده از الگوريتم پيشنهادي با جواب بهينه حاصل از مدل رياضي كه با برنامه لينگو اجرا شده مورد مقايسه قرار گرفته است. همچنين عملكرد الگوريتم پيشنهادي در حل مسايل مختلف با مدل استاندارد الگوريتم ژنتيك مقايسه و برتري آن ارايه شده است.

A two-machine permutation flow shop scheduling with n independent jobs and different due dates is considered in this paper. Since this problem is shown to be NP-Hard, We use the simulated annealing to solve this problem. The objective is minimizing the weighted earliness and tardiness that cover JIT concept. We construct our algorithm in four scenarios with considering two Markov chains and two temperature reduction rates. The best scenario is proposed based on the results of computational experiments. A mathematical programming formulation is proposed for the problem, and the solution obtained by proposed SA algorithms are compared with the optimal ones obtained by mathematical model using LINGO software for small size instances. Also the performance of the best scenario is compared by the standard model of genetic algorithm for different sizes problems and its advantages are shown.