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

Project Resource Leveling with an Efficient Simulated Annealing Algorithm

در مسيله‌ي تسطيح منابع الگوي استفاده از منابع طي زمان مورد توجه قرار مي ‌گيرد و سعي مي‌شود يك زمان‌بندي اساسي، كه سطح استفاده از منابع در آن تا حد ممكن يكنواخت باشد، ارايه شود. اين مسيله ازجمله مسايل كلاسيك در حوزه‌ي زمان‌بندي پروژه است كه براي آن راه حل هاي كاراي اندكي در ادبيات موضوع مي توان يافت. در اين مقاله با استفاده از شبيه‌سازي تبريد اقدام به حل اين مسيله مي ‌كنيم. شيوه‌ي نمايش جواب و توليد همسايگي براساس ويژگي هايي است كه در اين مقاله بررسي و اثبات شده است. كارايي الگوريتم شبيه‌سازي تبريد از طريق مقايسه با سه روش ابتكاري ديگر و نيز با مقايسه با جواب‌هاي مدل رياضي صفر ـ يك غيرخطي كه با نرم افزار لينگو حل شده است، مورد بررسي قرار گرفته است. در اين بررسي ها مجموعه‌ي متنوعي از مسايل آزمايشي مد نظر قرار داشته است. نتايج محاسباتي نشان مي دهد، الگوريتم ارايه‌شده، نسبت به سه روش ابتكاري برتري دارد و نتايج قابل رقابتي را با جواب‌هاي مدل رياضي به دست مي دهد.

Resource leveling problem considers resource usage pattern in the project plan during the project execution time and attempts to create a levelled baseline schedule. In this problem one aims at completing the project within its deadline with a resource usage which is as level as possible over the entire project horizon. Mostly no explicit resource considerations - like resource constrained property- are taking into account when this problem is considered. This problem is one of the most well-known and classical problems for which one can hardly find an efficient solution procedure in the literature. Most procedures in the literature are based on repetitive time consuming forward/backward methods in which the performance are rarely studied through various comprehensive test problems. We use Simulated Annealing meta heuristic algorithm to solve the resource leveling problem. The solution representation and neighborhood generation method in this algorithm is based on a theorem which has been proved in this article. Using our theorem and Floyd- Warshall longest path algorithm together with distance matrix with temporary precedence relations leads to an efficient new way of solution representation and neighborhood generation method. We study the efficiency of this algorithm by comparing with the results of two other heuristic methods and also with a zero-one non-linear mathematical programming model solved with Lingo. Numerous test problems with a vast variability in parameters are generated to compare these methods. To produce the test problems we have used the Rangen software which is well-known in literature to generate project networks with resources. The performance of different procedures are compared through different performance and computational time indicators. The results show that this algorithm outperforms the other heuristics and obtains highly competitive results in comparison with mathematical programming approach. more over the suggested meta heuristic completely outruns the mathematical programming approach considering computational time.