As a trend toward multi-product batch processes is increasing in Chemical Process Industry(CPI), multi-product batch scheduling has been actively studied. But the optimal production scheduling problems for multi-product batch processes are known as NP-complete problems. So the methods which and obtain not exact optimal solution but near optimal solution have been studied. Heuristic methods have been used frequently for near optimal solutions but recently Ku and Karimi[9] have studied the Simulated Annealing(SA) which acquires outperformed results in scheduling problems. But SA method can be improved for better results of batch process scheduling problems. In this paper, we suggest the Modified Simulated Annealing(MSA) which is composed of two stage search algorithms. At the first stage, Rapid Access Extensive Search(RAES) algorithm was used for better location of initial state. At the second stage, a modified Metropolis algorithm with adjusted control parameter was developed and used for better solution. A variety of examples are tested to evaluate the performance of MSA and to be compared with the SA method. From these tests we can show that the MSA is superior to the SA.