A large-scale powder-painting scheduling problem is explored. The purpose is to find out the optimal sequence of a number of batches that dynamically arrive from upstream processes within a given scheduling horizon. The objective is to enhance the production efficiency and decrease the production cost as well. To solve this problem, a mixed integer nonlinear programming (MINLP) model is constructed and an algorithm called greedy randomized adaptive search procedure (GRASP) is designed. Case studies demonstrate that the proposed approach can improve the production performance significantly.