The total budget of a breeding program must be divided across its different parts to maximize gain. How to optimize budget allocations for a two-part strategy breeding scheme is an unsolved problem. We used Bayesian optimization coupled with stochastic simulations of breeding schemes to determine budget allocations that maximized gain. The breeding schemes focused on a clonal crop and included a population improvement cycle (PIC) allowing one or two breeding cycles per year leading to phenotypic evaluations in a variety development pipeline (VDP) with three stages. Gain was maximized at target years 6 or 12 after initiation of genomic selection. The breeding scheme was simulated using the AlphaSimR package. Bayesian optimization was implemented using the BoTorch module of Python to optimize budget allocations to the PIC and each stage of the VDP. Allocations to the last stage of the VDP were small because information from that stage was relatively ineffective at improving genomic prediction accuracy. An unexpected interaction between the number of PIC cycles and the target year for gain affected the budget of the PIC and could be explained by conflicting needs to increase gain in the VDP or increase genomic prediction accuracy. Divergent budget allocations could generate selection gains close to the maximum, indicating some leeway in the design of breeding schemes. Simple rules of thumb for heuristic optimization did not emerge, suggesting that breeders will need to rely on simulation coupled to optimization.