The SARS-CoV-2 pandemic is a major concern all over the world and, as vaccines became available at the end of 2020, optimal vaccination strategies were subjected to intense investigation. Considering their critical role in reducing disease burden, the increasing demand outpacing production, and that most currently approved vaccines follow a two-dose regimen, the cost-effectiveness of delaying the second dose to increment the coverage of the population receiving the first dose is often debated. Finding the best solution is complex due to the trade-off between vaccinating more people with lower level of protection and guaranteeing higher protection to a fewer number of individuals. Here we present a novel extended age-structured SEIR mathematical model that includes a two-dose vaccination schedule with a between-doses delay modelled through delay differential equations and linear optimization of vaccination rates. By maintaining the minimum stock of vaccines under a given production rate, we evaluate the dose interval that minimizes the number of deaths. We found that the best strategy depends on an interplay between the vaccine production rate and the relative efficacy of the first dose. In the scenario of low first-dose efficacy, it is always better to vaccinate the second dose as soon as possible, while for high first-dose efficacy, the best strategy of time window depends on the production rate and also on second-dose efficacy provided by each type of vaccine. We also found that the rate of spread of the infection does not affect significantly the thresholds of the best window, but is an important factor in the absolute number of total deaths. These conclusions point to the need to carefully take into account both vaccine characteristics and roll-out speed to optimize the outcome of vaccination strategies.