An optimization apparatus for repeatedly obtaining a constraint violating solution, a constraint satisfying solution, and an approximate solution in a resource-constrained project scheduling problem performs setting an end time of a target optimization period at a point between a first finish time equal to a finish time of a latest version of the constraint violating solution and a second finish time equal to a finish time of a latest version of the constraint satisfying solution, followed by obtaining the approximate solution using a metaheuristic algorithm, making a determination as to whether the approximate solution violates constraint or satisfy the constraint, and performing, based on the determination, updating the first finish time with a finish time of the approximate solution when the approximate solution violates the constraint, and updating the second finish time with a finish time of the approximate solution when the approximate solution satisfies the constraint.