Optimal allocation of safety strategies in order to reduce threats of dust explosions is very challenging, particularly when all potential accident contributors and various safety measures are to be taken into account. In this paper, we have proposed a risk-based optimal allocation of safety measures while considering both available budget and acceptable residual risk. The methodology is based on a Bayesian network (BN) to model the risk of dust explosions, which in turn helps identify key contributing factors, assess performances of relative safety measures, and decide on those safety measures to most efficiently control the risks of dust explosions within a limited budget. The Bayesian network also facilitates the implementation of diagnostic analysis to determine vulnerable parts in the system to which special attention should be paid in safety measure allocation. The Net Risk Reduction Gain (NRRG) for each relevant safety measure is also used to simultaneously account for both the cost of a safety measure and the respective risk reduction. Accordingly, the risk-based optimal allocation of safety measures will be achieved by maximizing the sum of the NRRG of all relevant safety measures under limited budgets, which is regarded as a knapsack problem. We applied the methodology to the aluminum dust explosion that occurred at Hayes Lemmerz International, Huntington, Indiana, US in October 2003. The result shows the efficacy and applicability of the proposed methodology for optimal risk reduction within a limited budget.