In this project, we aim to minimize the total time needed to complete a group of batches from the beginning of processing on the first batch until the completion of processing on the last batch. This objective is often referred to as minimizing the “makespan” in scheduling theory. Traditionally mathematical programming (e.g., mixed integer programming) can be used to find optimal solutions to such scheduling problem. For example, Sadykov and Wolsey (2006) combined integer programming and global constraint to find minimum cost assignment of jobs. Magatão et al. (2004) also developed an optimization structure to schedule activities in the pipeline industry based on mixed integer programming. For large-scale batch scheduling involving multiple batches, too many variables and constraints would have to be considered. As such, it is very difficult, if possible, to find the optimal solution to the mathematical programming. Therefore many heuristic algorithms have been widely investigated in the scheduling research to approximate the optimal solution to the mathematical programming. For example, Chen et al. (2008b) presented a hybrid approach of genetic algorithm and extremal optimization to solve a class of manufacturing scheduling problems. Guo et al. (2008) adopted bi-level genetic algorithm to solve a flexible assembly scheduling problem. Hansen and Mladenovic (2001) also introduced the application of Variable neighborhood search on scheduling problem. However, it was extremely difficult to set up constraints for no wait conditions by mathematical programming. In addition, the implementation of these kinds of algorithms would require expertise at the plant level that was not generally available.