•We present a multi-objective MIP to support wine grape harvest.•We propose a negotiation protocol to ease an agreement between two decision-makers.•Our approach draws from the augmented e-constraint method.•We suggest a substitution rate criteria to chose which solution to present.•The protocol might be extended to other contexts with two decision-makers. In this paper, we present a novel multi-objective mixed-integer linear programming model to support wine grape harvesting. The proposed model considers the opposing nature of operational cost minimization and grape quality maximization, subject to several constraints, such as grape requirements and routing decisions. Based on the operations of a winery we worked with, we develop a negotiation protocol that can lead to an agreed final harvest schedule. The protocol includes an initial Pareto optimal solution obtained through the augmented weighted Tchebycheff method. Then, the solutions are presented to the two decision-makers and, if no agreement is reached, we conduct an iterative process, which includes finding Pareto optimal solutions in a neighborhood using the augmented ∊-constraint method. Finally, we choose, within this set, the solution following a substitution rate criteria. We illustrate our procedure using an educational example.