Oil refining is one of the most complex activities in the chemical industry due to its nonlinear nature, which ruins the convexity properties and prevents any guarantees of the global optimality of solutions obtained by local nonlinear programming (NLP) algorithms. Moreover, using global optimization algorithms is often not feasible because they typically require large computational efforts. This paper proposes the use of convex relaxations based on McCormick envelopes for the Refinery Operations Planning Problem (ROPP) that can be used to generate both initial solutions for the ROPP and to estimate optimality gaps for the solutions obtained. The results obtained using data from a real-world refinery suggest that the proposed approach can provide reasonably good solutions for the ROPP, even for cases in which there was no solution available using traditional local NLP algorithms. Furthermore, compared with a global optimization solver, the proposed heuristic is capable of obtaining better solutions in less computational time.