The last two decades have seen a growing interest in automated agents that are able to negotiate on behalf of human negotiators in a wide variety of negotiation domains. One key aspect of a successful negotiating agent is its ability to make appropriate concessions at the right time, especially when there are costs associated with the duration of the negotiation. However, so far, there is no fundamental approach on how much to concede at every stage of the negotiation in such time-sensitive domains. We introduce an efficient solution based on simultaneous search, which is able to select the optimal sequence of offers that maximizes expected payoff, given the agent's beliefs about the opponent. To this end, we show that our approach is consistent with known theoretical results and we demonstrate both its effectiveness and natural properties by applying it to a number of typical negotiation scenarios. Finally, we show in a number of experiments that our solution outperforms other state of the art strategy benchmarks.