This paper aims to present efficient alternative mixed-integer non-linear programming models and a customized hybrid metaheuristic, the Genetic-Based Algorithm (GBA), for a resource-constrained project-scheduling problem with a flexible network structure (RCPSP-FNS). We also consider the cost–time trade-off in the problem with a flexible network by using activity-duration compression. We present three approaches to solve the problem, including a mixed-integer non-linear program (MINLP) using binary variables representing activity completion times (MINLP1), an alternative mixed-integer non-linear program using integer variables representing activity-completion times (MINLP2) that has not presented before in RCPSP-FNS modeling, and the GBA. A total of 35 different problems are solved to examine the computational efficiency of the solution approaches. The MINLP1 and MINLP2 models are both solved by the GEKKO solver. The results indicate that solving the MINLP2 model can reach the optimal objective value obtained by solving the MINLP1 model in significantly less time. In addition, the proposed genetic-based algorithm can solve some large problems in a more efficient way in comparison to solving MINLP1 by using GEKKO. However, solving the MINLP2 model using GEKKO is the most efficient solution approach in comparison to both MINLP1 and the proposed genetic-based algorithm. MINLP2 can be solved to proven optimality (in much less time) for problems in which the MINLP1 model can, at most, reach near-optimal solutions.