In a shop floor, minimization of makespan (Total Completion Time) has been an interesting area for many researchers for over six decades. The problem for the process planning engineer is to find a processing order of the 'n' jobs, the same for each machine, such that the make span is minimized, that is, the 'n' jobs are finished as soon as possible. In this paper, one attempt has been made to develop and use one 'Random Simulation Algorithm', with the objective of improving the makespan. Benchmark problems proposed by Taillard are used here for the validation purpose. These values have been compared with the makespans obtained from the original NEH algorithm and the 'NEF family' of algorithms proposed by the authors. For the 120 number of problem instances analyzed, the new algorithm reports better makespans, than the original NEH algorithm, in 114 cases. The ANOVA indicates that, the Random Simulation Algorithm performs slightly better.