Document Type : Original Article


Department of Industrial Management, Faculty of Management and Accounting, Shahid Beheshti University, G.C., Tehran, Iran.


This paper considers the job scheduling problem in virtual manufacturing cells (VMCs) with the goal of minimizing two objectives namely, makespan and total travelling distance. To solve this problem two algorithms are proposed: traditional non-dominated sorting genetic algorithm (NSGA-II) and knowledge-based non-dominated sorting genetic algorithm (KBNSGA-II). The difference between these algorithms is that, KBNSGA-II has an additional learning module. Finally, we draw an analogy between the results obtained from algorithms applied to various test problems. The superiority of our KBNSGA-II, based on set coverage and mean ideal distance metrics, is inferred from results.


Back, T., 1996. Evolutionary Algorithms in Theory and Practice, Oxford University Press: New York, NY.
Branke, J., 1999. Memory-enhanced evolutionary algorithms for dynamic optimization problems. Proceedings of the Congress on Evolutionary Computation, IEEE Press, Piscataway, 1875-1882.
Louis, S.J., McDonnell, J., 2004. Learning with case-injected genetic algorithms. IEEE Transactions on Evolutionary Computation 8(4).
Chung, C.J., Reynolds, R.G., 1996. A test-bed for solving optimization problems using cultural algorithm, in: Proceedings of the Fifth Annual Conference on Evolutionary Programming, MIT Press, Cambridge, 225-236.
Deb, K., Pratap, A., Agarwal, S., Meyarivan, T., 2002. A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Trans Evolutionary Comput. 6, 182–197.
Gao, J., Sun, L.,  Gen, M., 2008. A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Computers and Operations Research 35(9), 2892-2907.
Ho, N.B., Tay, J.C., Lai, E.M.K., 2007. An effective architecture for learning and evolving flexible job-shop schedules. European Journal of Operational Research 179(2), 316-333.
Kesen, S.E., Toksari, M.D., Gungor, Z., Guner, E., 2009. Analyzing the behaviors of virtual cells (VCs) and traditional manufacturing systems: Ant colony optimization (ACO)- based metamodels. Computers & Operations Research 36(7), 2275-2285.
Kesen, S.E., Das, S.K., Gungor, Z., 2010. A genetic algorithm based heuristic for scheduling of virtual manufacturing cells (VMCs). Computers and Operations Research 37, 1148-1156.
McLean, C.R., Bloom, H.M.,  Hopp T.H., 1982. The virtual manufacturing cell. In: Proceedings of  the fourth IFAC/IFIP conference on information control problems in manufacturing  technology,  Gaithersburg, MD, 1–9.
Michalski, R.S., 2000. Learnable evolution model: evolution process guided by machine learning. Machine Learning 38(1), 9-40.
Nomden, G., Slomp, J., Suresh, N.C., 2006. Virtual manufacturing cells: A taxonomy of past research and identification of future research issues. International Journal of Flexible Manufacturing System 17, 71-92.
Montreuil, B., Venkatadri, U., Lefrancois, P., 1991. Holographic layout of manufacturing systems. 19th HE Systems Integration Conference, 1-13.
Ruiz, R., Allahverdi, A., 2007. Some effective heuristics for no-wait flow-shops with setup times to minimize total completion time. Annals of Operations Research 156, 143-171.
Srinivas, N., & Deb, K., 1994. Multi-objective function optimization using nondominated sorting genetic algorithms. Evolutionary Computation Journal 2(3),221-248.
Gen, M., Tsujimura, Y., Kubota E., 1994. Solving job-shop scheduling problem using genetic algorithms. In: Proceedings of the 16th international conference on computer and industrial engineering, Ashikaga, Japan,  576–9.
Slomp, J., Chowdary, B.V., Suresh, N.C., 2005. Design of virtual manufacturing cells: a mathematical programming approach, Robotics and Computer-Integrated Manufacturing 21, 273–288.
Xing, L.N., Chen, Y.W., Wang, P., Zhao, Q.S., Xiong, J., 2010. A knowledge-based ant colony optimization for flexible job shop scheduling problems. Applied Soft Computing 10, 888-896.