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

Solving the MRCPSP/Max with the Objective of Minimizing Tardiness Costs and Maximizing Earliness Rewards of Activities with a Two-stage Genetic Algorithm

در اين مقاله، براي اولين بار مسيله زمانبندي پروژه در شرايط محدود بودن منابع، امكان اجراي فعاليت‌ها در چندين مد و با در نظر گرفتن تاخيرات زماني بيشينه و كمينه ميان زمان‌هاي شروع فعاليت‌ها، MRCPSP/max ، با هدف كمينه‌كردن جريمه ديركرد و بيشينه كردن پاداش زودكرد اتمام فعاليت‌ها، مطرح شده و مورد بررسي قرار گرفته است. پس از بررسي تاريخچه و روند استفاده از روش‌هاي مختلف در حل مسايل مشابه در سال‌هاي گذشته، الگوريتم ژنتيك به عنوان الگوريتم مورد استفاده در اين تحقيق برگزيده شده است. در اين مقاله، شيوه پيداكردن جواب براي مسيله مورد نظر به اين ترتيب است كه با استفاده از يك الگوريتم ژنتيك، مسيله اصلي را به مسيله‌اي كه در آن هر فعاليت فقط يك حالت اجرايي دارد، ساده كرده و سپس در فاز دوم حل، با استفاده از يك الگوريتم ژنتيك مستقل ديگر، بهترين جواب مسيله حاصله از فاز اول الگوريتم را مي‌يابيم. عناصر اصلي و عملگرهاي هر دو الگوريتم، از هم مستقل هستند. در انتها نيز نتايج عددي حاصل از الگوريتم‌هاي پيشنهادي كه به وسيله زبان برنامه نويسي MATLAB نوشته شده است، با نتايج موجود در كتابخانه مسايل زمانبندي مقايسه شده‌اند و مشاهده مي‌شود كه الگوريتم ارايه شده در اين تحقيق در چندين مورد جواب‌هاي موجود را بهبود داده است.

In this study, we present a MRCPSP/max (Multi-mode Resource-Constrained Project Scheduling Problem with Minimum and Maximum time lags) model with minimization tardiness costs and maximization earliness rewards of activities as objective. The proposed model is nearby to real-world problems and has wide applications in various projects. This problem is not available in the literature exactly and we developed it for the first time. In order to solve this problem, we developed a two-stage genetic algorithm. In the first stage, the main problem is simplified, through applying a genetic algorithm, in which each activity has only one executive mode. In the second phase, with developing another genetic algorithm, the best answer of the problem is achieved. Each phase has its own codification, fitness function, crossover operator and mutation operator. Finally, the computational results obtained from the algorithms of this research, which was written in MATLAB programming language, was compared with the results existing in the project scheduling problems library (PSPLIB). The findings show that, our algorithm improved some of the best solutions, recorded in the PSPLIB.