This paper addresses a complicated problem in project management termed the payment scheduling negotiation problem (PSNP). The problem is a practical extension of the classical multi-mode resource constrained project scheduling problem (MRCPSP) and it considers the financial aspects of both the project client and contractor in a contracting project. The client and contractor negotiate with each other to determine an optimal payment schedule and an activity schedule so as to maximize their net present values (NPVs). As the NPV of the client and the NPV of the contractor are conflicting objectives, this paper first formulates the PSNP as a bi-objective optimization problem. To solve this problem effectively, a non-dominated sorting genetic algorithm II (NSGA-II) approach is proposed. In the negotiation, the client and contractor may have two preferences: the ideal NPVs for the client and the contractor, and the optimization degree of the activity schedule. In order to tackle these preferences, this paper further introduces a new dominance relation named the extended r-dominance (er-dominance) relation. The er-dominance relation extends the r-dominance relation and is able to deal with multiple preferences described by aspiration functions. Experimental results show that by incorporating the NSGA-II with the er-dominance, the proposed approach is promising for the PSNP.