Abstract: In this research, a parallel implementation of a Modular Simulated Annealing (MSA) algorithm, applied to classical Job-Shop Scheduling (JSS) problems is presented. The implementation has been done as a multiple island system suitable to run on the Distributed Resource Machine (DRM) environment, which is a novel scalable, distributed virtual machine developed based on Java technology. The support of the DRM environment was very effective with respect to message passing, having collaboration with a remote machine. The empirical results show that the method proposed is quite successful compared to the ordinary MSA and other systems described in literature.