توسعه روش هاي فرا ابتكاري براي حل مسئله زمانبندي نيروي انساني در محيط جريان كارگاهي

Developing metaheuristic approaches to solve flow shop scheduling problem with worker assignment

در اين تحقيق مسئله يكپارچه زمانبندي كارها و نيروي انساني در محيط جريان كارگاهي مورد بررسي قرار گرفته است كه در آن تعدادي نيروي انساني با مهارت‌هاي مختلف وجود دارند كه قابليت انجام كارهاي متفاوت با سرعت‌هاي مختلف را دارند. هدف مسئله تعيين زمانبندي كارها در مراحل مختلف و تخصيص نيروي انساني به اين مراحل است به‌گونه‌اي كه بيشنه زمان تكميل كارها (Cmax) كمينه شود. براي اين منظور يك مدل رياضي خطي عدد صحيح مختلط ارائه شده است كه اين مدل در نرم‌افزار CPLEX اجرا شده است كه مي‌تواند مسائل با ابعاد كوچك را در مدت‌زمان معقول حل‌شده است؛ اما به دليل NP-hard بودن مسئله، اين نرم‌افزار قادر به توليد جواب‌هاي بهينه براي مسائل با ابعاد بزرگ نمي‌باشد. براي اين منظور، دو روش فراابتكاري مبتني بر الگوريتم بهينه‌سازي ازدحام ذرات ارائه‌شده است؛ چون احتمال قرار گرفتن الگوريتم بهينه‌سازي ازدحام ذرات (PSO) در بهينه محلي زياد است، عملكرد اين الگوريتم با استفاده از الگوريتم تبريد شبيه‌سازي شده (SA) بهبود داده‌شده است (IPSO). نتايج نشان مي‌دهد كه الگوريتم IPSO عملكرد بهتري نسبت به الگوريتم PSO در تمامي ابعاد دارد و با بزرگ‌تر شدن ابعاد مسئله برتري الگوريتم IPSO محسوس‌تر مي‌باشد.

This research addresses a simultaneous jobs scheduling and worker assignment problem in flow shop environment in which there are some workers with different skills who can operate the jobs with different speed. The primary aim of the research is to schedule the jobs and assign the worker so that maximum completion time (Cmax) is minimized. To tackle this problem, a mixed integer linear programming model is introduced and is coded in CPLEX software so that it can obtain the optimal solutions in reasonable time. Due to NP-hardness of the research problem, CPLEX cannot achieve the optimal solutions for large-scale problems. Thus, two metaheuristic approaches based on particle swarm optimization (PSO) is proposed here. In order to trapping the PSO algorithm in local optima with high probability, the performance of the PSO algorithm is improved by simulated annealing (SA) algorithm (IPSO). The experimental results show that the IPSO algorithm can generate better results in entire scales and the superiority of the IPSO is significant in the large scale.