To harness the power of quantum computing, it is essential that a quantum computer provide maximal possible fidelity for a quantum circuit. To this end, much work has been done in the context of qubit routing or embedding, i.e., mapping circuit qubits to physical qubits based on gate performance metrics to optimize the fidelity of execution. Here, we take an alternative approach that leverages a unique capability of a trapped-ion quantum computer, i.e., the all-to-all qubit connectivity. We develop a method to determine a fixed number (budget) of quantum gates that, when calibrated, will maximize the fidelity of a batch of input quantum programs. This dynamic allocation of calibration resources on randomly accessible gates, determined using our heuristics, increases, for a wide range of calibration budget, the average fidelity from 70% or lower to 90% or higher for a typical batch of jobs on an 11-qubit device, in which the fidelity of calibrated and uncalibrated gates are taken to be 99% and 90%, respectively. Our heuristics are scalable, more than 2.5 orders of magnitude faster than a randomized method for synthetic benchmark circuits generated based on real-world use cases.