This research uses system optimization to assess short, medium, and long-term scenarios to achieve the committed CO₂-emission goals of Ecopetrol while minimizing potential adverse impacts such as incremental operational costs and utility demand. Two Colombian refineries are used as a case study: a medium-complexity and a high-complexity refinery. The study explores whether the level of complexity plays a significant role in the results. Potential technologies were ranked using a multi-criteria decision analysis. The system analysis and optimization were done in Linny-R, a mixed integer linear programming software package developed by TU Delft. In the short-term (2030) scenario, the selected technologies include low-carbon H₂ produced from Steam Methane Reformer units with carbon capture and storage and H₂ produced from renewable electricity sources. The medium and long-term (2050) scenario also included biomass gasification, naphtha reforming, and the cracking unit, all with carbon capture and storage. The refineries were modelled using on-site company data. The results indicate that using low-carbon H₂ and carbon capture and storage to flue gases would allow to reach the net zero target. Furthermore, the results show that the level of complexity in a refinery significantly impacts the decarbonization deployment pathways. The high-complexity refineries benefited from using low-carbon H₂ as feedstock while the medium-complexity refinery relied on a combination of carbon capture and low-carbon H₂ as an alternative fuel. This research highlights the potential to achieve substantial CO₂ emissions reductions with less impact on the total operational cost by using the amount of excess refinery gas generated when H₂ is used as fuel in boilers and process furnaces. A significant challenge remains in identifying suitable applications for surplus refinery fuel gas beyond its conventional use in combustion within boilers and furnaces.