JH
J. Han
info
Please Note
<p>This page displays the records of the person named above and is not linked to a unique person identifier. This record may need to be merged to a profile.</p>
1 records found
1
Project Scheduling Problem with Mitigation Measures under Renewable Resource Constraints
A Time-Indexed Integer Linear Programming Approach
This thesis studies an extension of the Resource-Constrained Project Scheduling Problem (RCPSP) that incorporates multiple execution modes, time--cost trade-offs, and project tardiness penalties. In contrast to traditional time-indexed formulations that use activity start times as their primary decision reference, this research proposes a finish-time indexed integer linear programming formulation. The proposed model allows project schedules and activity execution modes to be optimized simultaneously while respecting precedence relations and renewable resource constraints.
From a theoretical perspective, the computational complexity of the problem is analysed. It is shown that the proposed formulation is NP-hard through a polynomial-time reduction from the classical RCPSP. Furthermore, even when renewable resource constraints are removed, the resulting problem remains NP-complete through a reduction from the Discrete Time--Cost Trade-Off Problem (DTCTP). These results indicate that the integration of discrete execution modes, precedence constraints, and tardiness penalties leads to a computationally challenging optimization problem.
To enable practical solution of the model, a computational framework was implemented in Python using Pyomo and the Gurobi Optimizer. Several preprocessing techniques were introduced, including sparse variable generation, earliest-time feasibility filtering, and resource activity preprocessing. In addition, a lexicographic optimization procedure was developed to identify the shortest project schedule among solutions with the same optimal objective value. Computational experiments were conducted on 72 benchmark instances derived from DTCTP datasets and extended with renewable resource information.
The results show that the preprocessing procedures substantially reduce the number of binary variables without affecting solution quality. Their impact on runtime depends on the formulation and instance characteristics, but they consistently reduce model size. A comparison with a start-time indexed formulation inspired by Bianco and Caramia demonstrates that both formulations produce identical objective values, makespans, and tardiness values across all benchmark categories. The computational results further show that the proposed finish-time indexed formulation generally achieves shorter solution times and generates fewer constraints than the benchmark formulation, despite not always containing fewer binary variables. These findings indicate that finish-time indexing provides a competitive exact solution approach for project scheduling problems with discrete time--cost trade-offs and renewable resource constraints. ...
From a theoretical perspective, the computational complexity of the problem is analysed. It is shown that the proposed formulation is NP-hard through a polynomial-time reduction from the classical RCPSP. Furthermore, even when renewable resource constraints are removed, the resulting problem remains NP-complete through a reduction from the Discrete Time--Cost Trade-Off Problem (DTCTP). These results indicate that the integration of discrete execution modes, precedence constraints, and tardiness penalties leads to a computationally challenging optimization problem.
To enable practical solution of the model, a computational framework was implemented in Python using Pyomo and the Gurobi Optimizer. Several preprocessing techniques were introduced, including sparse variable generation, earliest-time feasibility filtering, and resource activity preprocessing. In addition, a lexicographic optimization procedure was developed to identify the shortest project schedule among solutions with the same optimal objective value. Computational experiments were conducted on 72 benchmark instances derived from DTCTP datasets and extended with renewable resource information.
The results show that the preprocessing procedures substantially reduce the number of binary variables without affecting solution quality. Their impact on runtime depends on the formulation and instance characteristics, but they consistently reduce model size. A comparison with a start-time indexed formulation inspired by Bianco and Caramia demonstrates that both formulations produce identical objective values, makespans, and tardiness values across all benchmark categories. The computational results further show that the proposed finish-time indexed formulation generally achieves shorter solution times and generates fewer constraints than the benchmark formulation, despite not always containing fewer binary variables. These findings indicate that finish-time indexing provides a competitive exact solution approach for project scheduling problems with discrete time--cost trade-offs and renewable resource constraints. ...
This thesis studies an extension of the Resource-Constrained Project Scheduling Problem (RCPSP) that incorporates multiple execution modes, time--cost trade-offs, and project tardiness penalties. In contrast to traditional time-indexed formulations that use activity start times as their primary decision reference, this research proposes a finish-time indexed integer linear programming formulation. The proposed model allows project schedules and activity execution modes to be optimized simultaneously while respecting precedence relations and renewable resource constraints.
From a theoretical perspective, the computational complexity of the problem is analysed. It is shown that the proposed formulation is NP-hard through a polynomial-time reduction from the classical RCPSP. Furthermore, even when renewable resource constraints are removed, the resulting problem remains NP-complete through a reduction from the Discrete Time--Cost Trade-Off Problem (DTCTP). These results indicate that the integration of discrete execution modes, precedence constraints, and tardiness penalties leads to a computationally challenging optimization problem.
To enable practical solution of the model, a computational framework was implemented in Python using Pyomo and the Gurobi Optimizer. Several preprocessing techniques were introduced, including sparse variable generation, earliest-time feasibility filtering, and resource activity preprocessing. In addition, a lexicographic optimization procedure was developed to identify the shortest project schedule among solutions with the same optimal objective value. Computational experiments were conducted on 72 benchmark instances derived from DTCTP datasets and extended with renewable resource information.
The results show that the preprocessing procedures substantially reduce the number of binary variables without affecting solution quality. Their impact on runtime depends on the formulation and instance characteristics, but they consistently reduce model size. A comparison with a start-time indexed formulation inspired by Bianco and Caramia demonstrates that both formulations produce identical objective values, makespans, and tardiness values across all benchmark categories. The computational results further show that the proposed finish-time indexed formulation generally achieves shorter solution times and generates fewer constraints than the benchmark formulation, despite not always containing fewer binary variables. These findings indicate that finish-time indexing provides a competitive exact solution approach for project scheduling problems with discrete time--cost trade-offs and renewable resource constraints.
From a theoretical perspective, the computational complexity of the problem is analysed. It is shown that the proposed formulation is NP-hard through a polynomial-time reduction from the classical RCPSP. Furthermore, even when renewable resource constraints are removed, the resulting problem remains NP-complete through a reduction from the Discrete Time--Cost Trade-Off Problem (DTCTP). These results indicate that the integration of discrete execution modes, precedence constraints, and tardiness penalties leads to a computationally challenging optimization problem.
To enable practical solution of the model, a computational framework was implemented in Python using Pyomo and the Gurobi Optimizer. Several preprocessing techniques were introduced, including sparse variable generation, earliest-time feasibility filtering, and resource activity preprocessing. In addition, a lexicographic optimization procedure was developed to identify the shortest project schedule among solutions with the same optimal objective value. Computational experiments were conducted on 72 benchmark instances derived from DTCTP datasets and extended with renewable resource information.
The results show that the preprocessing procedures substantially reduce the number of binary variables without affecting solution quality. Their impact on runtime depends on the formulation and instance characteristics, but they consistently reduce model size. A comparison with a start-time indexed formulation inspired by Bianco and Caramia demonstrates that both formulations produce identical objective values, makespans, and tardiness values across all benchmark categories. The computational results further show that the proposed finish-time indexed formulation generally achieves shorter solution times and generates fewer constraints than the benchmark formulation, despite not always containing fewer binary variables. These findings indicate that finish-time indexing provides a competitive exact solution approach for project scheduling problems with discrete time--cost trade-offs and renewable resource constraints.