Is there a manual which describes the algorithmic procedure on which the Vertical Navigation Guidance is based?
For this answer:


Hard altitude requirement - a fixed altitide which an airplane must
be at. (eg. 7000ft)
Soft altitude requirement - a window of altitudes for the aircraft to
be at (eg. abv. 3500ft, between 9000ft and 12000ft)
Using a 757 for all examples unless specified otherwise.


A simple FMS may simply assume and use the minimum of a soft requirement as the desired altitude, as you correctly stated. 

However, in airliners, it is much more common to use what is called a "Cost Index" (CI) to calculate speeds, climb rates and the like. 
Cost index can be calculated as so:

CI = (Time cost/hr)/(Fuel cost/lb)

A CI of 9999 means that the FMC will aim for Velocity Maximum Operating (VMO) in every stage of flight. Whereas a CI of 0 will result in the FMS aiming for the following:

+=================================+===============+===============+
|              Climb              |    Cruise     |    Descent     |
+=================================+===============+===============+
| Minimum fuel to cruise altitude | Maximum Range | Max L/D ratio |


So that will lead to the following speeds:

+============+=======+========+========+
| Cost Index | Climb | Cruise | Descent|
+============+=======+========+========+
|          0 | 290kn | .778m  | 250kn  |
+------------+-------+--------+--------+
|       9999 | 345kn | .847m  | 334kn  |
+------------+-------+--------+--------+

Now we have climb speeds, we can work backwards to calculate the best climb or descent rate for this speed (I can't find a reliable source for this, so that's where the practical examples end). From here; TOD, TOC and TTC. As long as an FMS can remain at its best CI speed to meet an altitude requirement, it will. Otherwise it will alter best CI speed by the smallest amount possible to meet the requirements.

Some good (debatable) reading is this report by MITRE, an information security organisation. They found that most FMS' tested had very little variation in the time they began descents and climbs, as well as altitudes for a fixed CI. They also found that the RTCA standards for RNP - called RTCA DO-236 where generally adhered to in every tested FMS. 
That means the following was met:


  ... tolerances for a
  flight along a specified vertical path is 160’ for 0’-
  5000’, 210’ for 5000’-29000’, and 260’ for 29000’-
  41,000


MITRE also says:


  If a preceding waypoint is encountered before the altitude of the
  constraint specified for that waypoint has been reached, then the
  constraint altitude of the waypoint is adopted for the reference path
  altitude at the waypoint.


Now, armed with our new CI based climb rates and speeds, my other answer can be used to finish our calculations and work out where (in the Z dimension) the aircraft will reach a soft requirement.