Evaluating flexible job shop algorithms and comparison with 2 part genetic algorithm

Authors

semnan university

Abstract

This paper consider flexible jobshop scheduling problem with minimizing maximum completion time of orders(Cmax), maximum workload of machines(Wmax) and total workloads (WT). The problem is known as Np-Hard. So finding the optimal solution in a reasonable time is impossible. A genetic algorithm named 2 part genetic algorithm is proposed for solving the problem. For evaluating the problem, we used 2 test data sets and proposed genetic algorithm is compared with other algorithms in the literature. Results show proposed genetic algorithm has higher performance for solving the problem in comparison with other algorithms.

Keywords

References

 
[1] Pinedo, M.(2002)."Scheduling: Theory, Algorithms and Systems". Prentice-Hall, Englewood Cliffs, NJ.
[2]Roshanaei, V., Naderi, B., Jolai, F., Khalili, M. (2009). " A variable neighborhood search for job shop scheduling with set-up times to minimize makespan". Future Generation Computer Systems, Vol. 25, pp. 654-661.
[3] Ombuki, B., Ventresca, M.(2004)."Local search genetic algorithms for the job shop scheduling problem". Applied Intelligence, Vol. 21, pp. 99-109.
[4] Bagheri, A., Zandieh M., Mahdavi I., Yazdani M.(2010). "An artificial immune algorithm for the flexible job-shop scheduling problem". Future Generation Computer Systems, Vol. 26, pp. 533-541.
[5] Brucker, P., Schile, R. (1990). "Job-shop scheduling with multi-purpose machines". Computing, Vol. 45, pp.369–375.
[6] Kacem, I., Hammadi, S., Borne, P. (2002). "Pareto-optimality approach for flexible job-shop scheduling problems: Hybridization of evolutionary algorithms and fuzzy logic". Mathematics and Computers in Simulation, Vol. 60, pp. 245–276.
[7] Brandimarte, P.(1993). "Routing and scheduling in a flexible job shop by taboo search". Annals of operations Research, Vol. 41, pp. 157-183.
[8] Kacem, I., Hammadi, S., Borne, P.(2002). "Approach by localization and multi objective evolutionary optimization for flexible job-shop scheduling problems". IEEE Transactions on Systems, Man, and Cybernetics, Vol. 32, pp. 1-13.
[9] Xia, W., Wu, Z.(2005). "An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problem". Computers and Industrial Engineering, Vol. 48, pp. 409-425.
 [10] Chen, H., Ihlow, J., Lehmann, C.(1999). "A genetic algorithm for flexible Job-shop scheduling", IEEE International Conference on Robotics and Automation, Detroit,pp.1120-1125.
[11] Zhang,H., Gen, M. (2005). Multistage-based genetic algorithm for flexible job-shop scheduling problem, Journal of Complexity International, Vol. 11, 223-232.
[12] Ong, Z.X., Tay, J.C., Kwoh, C.K.(2005). "Applying the Clonal Selection Principle to Find Flexible Job-Shop Schedules", in: LNCS, Vol. 3627, pp. 442-455.
[13] Pezzella, F., Morganti, G., Ciaschetti, G.(2008). "A genetic algorithm for the flexible jobshop scheduling problem". Computers and Operations Research, Vol. 35 (10), pp. 3202-3212.
[14] Gao, J., Sun, L., Gen, M.(2008). "A hybrid genetic and variable neighborhood descent for flexible job shop scheduling problems", Computers and Operations Research, Vol. 35 (9), pp. 2892-2907.
[15] Fattahi, P., Saidi Mehrabad, M., Jolai, F.(2007). "Mathematical modeling and heuristic approaches to flexible job shop scheduling problems". Journal of Intelligent Manufacturing, Vol. 18 (3), pp. 331-342.
[16] Yuan, Y. , Xu, H. (2013). A hybrid harmony search algorithm for the flexible job shop scheduling problem. Applied Soft Computing,Volume 13, Issue 7, Pages 3259–3272.
[17] Yuan, Y. , Xu, H. (2013). An integrated search heuristic for large-scale flexible job shop scheduling problems. Computers & Operations Research, Volume 40, Issue 12, Pages 2864–2877.
[18] Wang, L., Wang, S., Xu, Y., Zhou, G., & Liu, M. (2012). A bi-population based estimation of distribution algorithm for the flexible job-shop scheduling problem. Computers & Industrial Engineering, 62(4), 917–926.
[19]Thammano, A., Phu-ang, A.(2013). A Hybrid Artificial Bee Colony Algorithm with Local Search for Flexible Job-Shop Scheduling Problem. Procedia Computer Science 20 ,Pages 96 – 101.
[20] Teekeng, W., Thammano,A. (2012). Modified Genetic Algorithm for Flexible Job-Shop Scheduling Problems. Procedia Computer Science 12,Pages 122 – 128.
[21] Ak, B., Koc, E.(2012). A guide for genetic algorithm based on parallel machine scheduling
and flexible job-shop scheduling. Procedia - Social and Behavioral Sciences 62, Pages 817 – 823.
[22] Zejko, W., Hejducki, Z., Uchro´nski, M., Wodecki,M.(2012). Solving the Flexible Job Shop Problem on Multi-GPU. Procedia Computer Science 9, Pages 2020 – 2023.
[23] Ho, N. B., Tay, J. C., Edmund, M., Lai, K. (2007). "An effective architecture for learning and evolving flexible job shop schedules". European Journal of Operational Research, Vol. 179, pp. 316–333.
[24] Mesghouni, K., Hammadi, S., Borne, P. (1997). "Evolution programs for job-shop scheduling". In Proceedings of the IEEE international conference on computational cybernetics and simulation ,Vol. 1, pp. 720–725.
[25] Shahryar, R., Hamid, R. T., Magdy, M. A. S. (2007). "A novel population initialization method for accelerating evolutionary algorithms". Computers and Mathematics with Application, Vol. 53, pp. 1605–1614.
 [26] Jia, H.Z., Nee, A.Y.C., Fuh, J.Y.H., Zhang, Y.F.(2003). "A modified genetic algorithm for distributed
scheduling problems". International Journal of Intelligent Manufacturing, Vol. 14, pp. 351-362.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Journal of Modeling in Engineering
Volume 13, Issue 40
April 2015
Pages 1-16

Files

History

  • Receive Date: 28 January 2017
  • Revise Date: 18 September 2017
  • Accept Date: 28 January 2017

Share

How to cite

Statistics