DOI: https://doi.org/10.1016/j.ejor.2024.02.041
تاريخ النشر: 2024-03-04
المؤلف: Tom Servranckx وآخرون
الموضوع الرئيسي: جدولة المشاريع ذات الموارد المحدودة
نظرة عامة
تقدم هذه الدراسة نهج حل مبتكر لمشكلة جدولة المشاريع المقيدة بالموارد مع الرسوم البيانية البديلة (RCPSP-AS)، والتي تتضمن علاقات معقدة مثل البدائل المتداخلة والمترابطة. يوسع إطار RCPSP-AS جدولة المشاريع التقليدية من خلال السماح فقط بمجموعة فرعية من الأنشطة ليتم جدولتها، مما يتوافق مع أوضاع التنفيذ البديلة لحزم العمل. نظرًا لأن كل من RCPSP و RCPSP-AS هما من المشاكل الصعبة NP، يقترح المؤلفون خوارزمية جينية قائمة على حل القابلية للإرضاء (GA-SAT) مصممة لمعالجة القيود المحددة لـ RCPSP-AS. تظهر التجارب الحسابية على كل من الحالات الصغيرة والكبيرة النطاق أن نهج GA-SAT يتنافس بفعالية مع الخوارزميات الميتاهيرستية الموجودة وحل رياضي دقيق، مما يبرز مرونة حلول SAT في هذا السياق.
تشير النتائج إلى أن طريقة GA-SAT، التي تدمج حلاً هيرستياً لـ RCPSP مع حل SAT، قادرة على التعامل مع التعقيد المتزايد لـ RCPSP-AS. تكشف الاختبارات الأولية أن تثبيت بدائل معينة يمكن أن يعزز جودة الحل، بينما تؤثر الاختيارات العشوائية سلبًا على النتائج. تشمل اتجاهات البحث المستقبلية تطوير خوارزميات أكثر تخصصًا لـ RCPSP-AS، وتوسيع حل القابلية للإرضاء ليشمل سيناريوهات أكثر تعقيدًا، وتنقيح الصيغ الرياضية لفهم معلمات المشكلة وتعقيدها العام بشكل أفضل. تهدف هذه الجهود إلى تحسين كفاءة وفعالية حلول الجدولة في سياقات إدارة المشاريع.
مقدمة
تركز مشكلة جدولة المشاريع المقيدة بالموارد (RCPSP) على جدولة مجموعة محددة من الأنشطة لتقليل مدة المشروع مع الالتزام بالعلاقات التكنولوجية وتوافر الموارد المحدودة. تفترض الصيغ التقليدية لـ RCPSP هيكل مشروع ثابت، وهو ما يمكن أن يكون غير واقعي للمشاريع المعقدة. لمعالجة هذه القيود، قدم سيرفراكنكس وفانهوك (2019a) RCPSP مع الرسوم البيانية البديلة (RCPSP-AS)، والذي يسمح باختيار أنشطة مترابطة بديلة ضمن شبكة المشروع. تتضمن هذه الإضافة مشكلتين فرعيتين: اختيار فرع بديل واحد من كل رسم بياني بديل وجدولة الأنشطة المختارة مع مراعاة قيود الأولوية والموارد.
في هذه الدراسة، يقترح المؤلفون نهجًا هيرستيًا مبتكرًا، GA-SAT، والذي يجمع بين حل القابلية للإرضاء (SAT) لمشكلة الاختيار مع خوارزمية جينية للجدولة. يهدف هذا الأسلوب إلى التنقل بكفاءة في مشهد اتخاذ القرار المعقد لـ RCPSP-AS، مما يؤدي إلى حلول قريبة من المثالية في إطار زمني معقول. يبني البحث على التحقق السابق من حلول SAT في جدولة المشاريع ويعدل المنهجيات الحالية لنمذجة القيود بشكل فعال. يحدد البحث هيكله، موضحًا مراجعات الأدبيات، وصيغ المشاكل، ونهج GA-SAT، والتجارب الحسابية لتقييم فعالية الحل المقترح مقابل الأساليب الميتاهيرستية الموجودة.
نقاش
في قسم النقاش من الورقة، يستعرض المؤلفون الأبحاث الحالية حول مشكلة جدولة المشاريع المقيدة بالموارد مع الرسوم البيانية البديلة (RCPSP-AS) والقضايا المتعلقة بالجدولة. يبرزون المساهمات الكبيرة من دراسات متنوعة، مثل عمل كيلينبرينك وهيلبر حول الهياكل المرنة المعتمدة على النموذج، وتوسعات تاو ودونغ التي تقدم سلاسل أنشطة بديلة وطرق عشوائية. تؤكد هذه الدراسات على تعقيد الجدولة عندما يمكن أن تؤدي الأنشطة إلى اختيار أنشطة أخرى، وتستكشف خوارزميات متنوعة، بما في ذلك البرمجة الخطية الصحيحة والتبريد المحاكي، لمعالجة هذه التحديات. كما يشير المؤلفون إلى أن الأبحاث السابقة غالبًا ما تقيد بناء الهياكل البديلة للمشاريع من خلال الاعتماد على مجموعات بيانات محددة مسبقًا، مما يحد من المرونة في النمذجة.
يقترح المؤلفون نهجًا مبتكرًا يسمح بتوليد هياكل مشاريع بديلة من الصفر، مما يعزز درجة الحرية في بناء هذه الهياكل. يجادلون بأن طريقتهم تمكن من استكشاف أكثر منهجية لتكوينات المشاريع، حيث يمكن التحكم في جميع المعلمات، مما يؤدي إلى مجموعة شاملة من حالات المشاريع. علاوة على ذلك، يناقشون تطبيق حلول SAT في مجال RCPSP، موضحين منهجيات متنوعة تدمج SAT مع تقنيات تحسين أخرى لحل مشاكل الجدولة المعقدة. يسلط هذا التجميع للأدبيات الضوء على المشهد المتطور لأبحاث جدولة المشاريع، لا سيما في استيعاب العمليات والهياكل البديلة، وهو أمر حاسم للتطبيقات العملية في مجالات مثل بناء السفن والبناء.
DOI: https://doi.org/10.1016/j.ejor.2024.02.041
Publication Date: 2024-03-04
Author(s): Tom Servranckx et al.
Primary Topic: Resource-Constrained Project Scheduling
Overview
This study presents a novel solution approach for the Resource-Constrained Project Scheduling Problem with Alternative Subgraphs (RCPSP-AS), which incorporates complex relationships such as nested and linked alternatives. The RCPSP-AS framework extends traditional project scheduling by allowing only a subset of activities to be scheduled, corresponding to alternative execution modes for work packages. Given that both the RCPSP and RCPSP-AS are NP-hard, the authors propose a genetic algorithm-based satisfiability solver (GA-SAT) tailored to address the specific constraints of the RCPSP-AS. Computational experiments on both small and large-scale instances demonstrate that the GA-SAT approach competes effectively with existing metaheuristic algorithms and an exact mathematical solver, highlighting the versatility of SAT solvers in this context.
The findings indicate that the GA-SAT method, which integrates a heuristic RCPSP solver with a SAT solver, is capable of handling the increased complexity of the RCPSP-AS. Initial tests reveal that fixing certain alternatives can enhance solution quality, while random selections detrimentally affect outcomes. Future research directions include developing more specialized algorithms for the RCPSP-AS, extending the satisfiability solver to encompass more complex scenarios, and refining mathematical formulations to better understand problem parameters and overall complexity. These efforts aim to improve the efficiency and effectiveness of scheduling solutions in project management contexts.
Introduction
The Resource-Constrained Project Scheduling Problem (RCPSP) focuses on scheduling a defined set of activities to minimize project makespan while adhering to technological relationships and limited resource availability. Traditional formulations of the RCPSP assume a fixed project structure, which can be unrealistic for complex projects. To address this limitation, Servranckx and Vanhoucke (2019a) introduced the RCPSP with alternative subgraphs (RCPSP-AS), which allows for the selection of alternative interconnected activities within the project network. This extension involves two subproblems: selecting one alternative branch from each alternative subgraph and scheduling the selected activities while considering precedence and resource constraints.
In this study, the authors propose a novel heuristic approach, GA-SAT, which combines a boolean satisfiability (SAT) solver for the selection subproblem with a genetic algorithm for scheduling. This method aims to efficiently navigate the complex decision-making landscape of the RCPSP-AS, yielding near-optimal solutions in a reasonable timeframe. The research builds on previous validations of SAT solvers in project scheduling and adapts existing methodologies to model constraints effectively. The paper outlines its structure, detailing literature reviews, problem formulations, the GA-SAT approach, and computational experiments to assess the effectiveness of the proposed solution against existing metaheuristic methods.
Discussion
In the discussion section of the paper, the authors review existing research on the Resource-Constrained Project Scheduling Problem with Alternative Subgraphs (RCPSP-AS) and related scheduling issues. They highlight significant contributions from various studies, such as Kellenbrink and Helber’s work on model-endogenous flexible project structures, and Tao and Dong’s extensions introducing alternative activity chains and stochastic methods. These studies emphasize the complexity of scheduling when activities can trigger the selection of others, and they explore various algorithms, including integer linear programming and simulated annealing, to address these challenges. The authors also note that previous research often constrains the construction of alternative project structures by relying on predefined datasets, which limits flexibility in modeling.
The authors propose a novel approach that allows for the generation of alternative project structures from scratch, thereby enhancing the degree of freedom in constructing these structures. They argue that their method enables a more systematic exploration of project configurations, as all parameters can be controlled, leading to a comprehensive range of project instances. Furthermore, they discuss the application of SAT solvers in the RCPSP domain, detailing various methodologies that integrate SAT with other optimization techniques to solve complex scheduling problems. This synthesis of literature underscores the evolving landscape of project scheduling research, particularly in accommodating alternative processes and structures, which is crucial for practical applications in fields such as shipbuilding and construction.