The Temporal Resource Reallocation Problem is a problem of augment- ing importance in the fleld of agents, as its solution is a gateway towards fully automated negotiation between agents for the fulflllment of tasks whose requirements are incomparably more complex than those that may be solved when the temporal parameter is not considered. Rela- tively little work has been done in the past in this direction and the applicability of existing negotiation approaches is limited to simplistic cases in which the solutions are rather obvious. In this paper we revise the notion of a promise between agents in order to develop a new ne- gotiation strategy that allows for more sophisticated negotiation among agents, thus being able to successfully tackle a much wider range of problems.