In the current paper we analyse an extended SIRS epidemic model in which immunity at the individual level wanes gradually at exponential rate, but where the waning rate may differ between individuals, for instance as an effect of differences in immune systems. The model also includes vaccination schemes aimed to reach and maintain herd immunity. We consider both the informed situation where the individual waning parameters are known, thus allowing selection of vaccinees being based on both time since last vaccination as well as on the individual waning rate, and the more likely uninformed situation where individual waning parameters are unobserved, thus only allowing vaccination schemes to depend on time since last vaccination. The optimal vaccination policies for both the informed and uniformed heterogeneous situation are derived and compared with the homogeneous waning model (meaning all individuals have the same immunity waning rate), as well as to the classic SIRS model where immunity at the individual level drops from complete immunity to complete susceptibility in one leap. It is shown that the classic SIRS model requires least vaccines, followed by the SIRS with homogeneous gradual waning, followed by the informed situation for the model with heterogeneous gradual waning. The situation requiring most vaccines for herd immunity is the most likely scenario, that immunity wanes gradually with unobserved individual heterogeneity. For parameter values chosen to mimic COVID-19 and assuming perfect initial immunity and cumulative immunity of 12 months, the classic homogeneous SIRS epidemic suggests that vaccinating individuals every 15 months is sufficient to reach and maintain herd immunity, whereas the uninformed case for exponential waning with rate heterogeneity corresponding to a coefficient of variation being 0.5, requires that individuals instead need to be vaccinated every 4.4 months.