Design problems for process systems engineering applications often require multi-scale modeling integrating detailed process models. Consequently, black-box optimization and surrogate modeling have continued to play a fundamental role in mission-critical design applications. Inherent in surrogate modeling applications, particularly those constrained by “expensive” function evaluations, are the questions of how to properly balance “exploration” and “exploitation” and how to do so while harnessing parallel computing in techniques. We devise and investigate a one-step look-ahead GRASP heuristic for balancing exploration and exploitation in a parallel environment. Computational results reveal that our approach can yield equivalent or superior surrogate quality with near linear scaling in the number of parallel samples.