We extend Sandholm’s bidtree-based IDA* algorithm for combinatorial auction winner determination to deal with negotiation over tasks with precedence constraints. We evaluate its performance, and show that the order of items in the bidtree has a major impact on performance. Specifically, performance is enhanced if the items with the largest numbers of bids are at the top of the bidtree. This is due to the fact that the effective branching factor in the search tree is controlled by the number of bids returned from a query to the bidtree, which in turn is strongly related to its construction.