An application of metaheuristic optimization algorithms for solving the flexible job-shop scheduling problem
Abstract
Abstract. The Flexible Job Planning (FJSP) problem is another planning and scheduling problem. It is a continuation of the classic problem of scheduling jobs, where each operation can be performed on different machines, while the processing time depends on the machine being used. FJSP is a difficult NP problem that consists of two sub-problems, scheduling problems and scheduling operations. The paper presents a model for solving FJSP based on meta-heuristic algorithms: Genetic algorithm (GA), Tabu search (TS) and Ant colony optimization (ACO). The efficiency of the approach in solving the aforementioned problem is reflected in the flexible search of space and the choice of dominant solutions. The results of the computation are graphically represented on the Gantt chart.
Downloads
References
Aslan, E., Şimşek, T., & KarkacieR, A. (2017). A binary integer programming model for exam scheduling problem with sSeveral departments, 13th International Conference on Knowledge, Economoy and Management, Bilgi Ekonomisi ve Yönetimi Dergisi, 12 (2), 169-175.
Blazewicz, J., Domschke, W., & Pesch, E. (1996). The job shop scheduling problem: Conventional and new solution techniques. European Journal of Operational Research, 93, 1-33. DOI: https://doi.org/10.1016/0377-2217(95)00362-2
Bremermann, H. J. (1958). The evolution of intelligence. The nervous system as a model of its environment, Technical Report No. 1, Department of Mathematics, University of Washington, Seattle, WA.
Brucker, P., Schile, R. (1990). Job-shop scheduling with multi-purpose machines. Computing, 45(4), 369–375. DOI: https://doi.org/10.1007/BF02238804
Dorigo, M. (1992). Optimization, learning and natural algorithms (in italian), Ph.D. dissertation, Dipartimento di Elettronica, Politecnico di Milano, Italy.
Dorigo, M., Birattari, M., & Stutzle, T. (2006). Ant Colony Optimization. IEEE Computational Intelligence Magazine 1(4):28-39, DOI: 10.1109/MCI.2006.329691 DOI: https://doi.org/10.1109/CI-M.2006.248054
Fan, K., Wang, M., Zhai, Y., & Li, X. (2019). Scatter search algorithm for the multiprocessor task job-shop scheduling problem. Computers & Industrial Engineering, 127, 677–686.
Fraser, A. S., (1957). Simulation of genetic systems by automatic digital computers. II: Effects of linkage on rates under selection, Austral. J. Biol. Sci. 10:492–499. DOI: https://doi.org/10.1071/BI9570492
Glover, F. W. (1989). Tabu Search – Part 1. ORSA Journal on Computing. 1 (2): 190–206. doi:10.1287/ijoc.1.3.190. DOI: https://doi.org/10.1287/ijoc.1.3.190
Glover, F. W., & Laguna, M. (1997). Tabu Search. Springer US. DOI: https://doi.org/10.1007/978-1-4615-6089-0
Graver, M., Price, W. L. (1987). Using the Kanban in a job shop environment. International Journal of Production Research, 26(6):1105-1118, DOI: 10.1080/00207548808947921 DOI: https://doi.org/10.1080/00207548808947921
Hasan, M., & Arefin, R. (2017). Application of Linear Programming in Scheduling Problem. Dhaka University Journal of Science, 65(2): 145-150.
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor.
Jamili, A., (2018). Job shop scheduling with consideration of floating breaking times under uncertainty. Engineering Applications of Artificial Intelligence, Volume 78, 28-36.
Kennedy, J., & Eberhart, R. (1995). Particle Swarm Optimization. Proceedings of IEEE International Conference on Neural Networks. IV. pp. 1942–1948. doi:10.1109/ICNN.1995.488968. DOI: https://doi.org/10.1109/ICNN.1995.488968
Kirkpatrick, S., Gelatt Jr, C. D., Vecchi, M. P. (1983). Optimization by Simulated Annealing. Science. 220 (4598): 671–680. DOI: https://doi.org/10.1126/science.220.4598.671
Kumar, C. S., Panneerselvam, R., (2007). Literature review of JIT-KANBAN system. International Journal of Advanced Manufacturing Technology 32(3):393-408, DOI: 10.1007/s00170-005-0340-2. DOI: https://doi.org/10.1007/s00170-005-0340-2
Kung, L. C., & Chern, C. C. (2009). Heuristic factory planning algorithm for advanced planning and scheduling. Computers&OperationsResearch, 36(9), 2513—2530. DOI: https://doi.org/10.1016/j.cor.2008.09.013
Lagodimos, A. G., & Leopoulos, V. (2000). Greedy heuristic algorithms for manpower shift planning, International Journal of Production Economics, 68, 95-106. DOI: https://doi.org/10.1016/S0925-5273(99)00099-7
Laguna, M., Marti, R., & Marti, R. C. (2003). Scatter Search: Methodology and Implementation in C. New York: Springer. DOI: https://doi.org/10.1007/978-1-4615-0337-8
Liaw, C. F. (2000). A hybrid genetic algorithm for the open shop scheduling problem. European Journal of Operational Research, 124(1):28-42. DOI: https://doi.org/10.1016/S0377-2217(99)00168-X
Liu, G., Luh, P.B., & Resch, R. (1996). Scheduling permutation flow shop using the lagrangian relaxation technique. IAFC 13th Triennial World Congress. San Francisco. USA, la-Ol 6. DOI: https://doi.org/10.1016/S1474-6670(17)57718-6
Lomnicki, Z. A. (1965). “Branch-and-Bound” Algorithm for the exact solution of the three-machine scheduling problem. J Oper Res Soc 16, 89–100. https://doi.org/10.1057/jors.1965.7 DOI: https://doi.org/10.1057/jors.1965.7
Nowicki, E., & Smutnicki, C. (2005). An advanced tabu search algorithm for the job shop problem. Journal of Scheduling, 8(2), 145–159. DOI: https://doi.org/10.1007/s10951-005-6364-5
Ostergard, P. R. J. (2002). A fast algorithm for the maximum clique problem, Discrete Applied Mathematics, 120(1-3):197-207. DOI: https://doi.org/10.1016/S0166-218X(01)00290-6
Özgüven, C., Özbakır, L., Yavuz, Y. (2010). Mathematical models for job-shop scheduling problems with routing and process plan flexibility, Applied Mathematical Modelling, 34, 1539–1548. DOI: https://doi.org/10.1016/j.apm.2009.09.002
Robson, J.M., (1986). Algorithms for maximum independent sets. Journal of Algorithms, 7(3):425-440. DOI: https://doi.org/10.1016/0196-6774(86)90032-5
Schaefers, J., Briquet, M., & Colin, J. (2000). A generic KANBAN based push-pull schedule in a job shop. IFAC Proceedings Volumes, 33(17):585-590 DOI: https://doi.org/10.1016/S1474-6670(17)39469-7
Sentlelro, J. J. S., (1933). Planning and scheduling: non-classic heuristic, 12th Triennial World Congress. Sydney. Australia.
Sobeyko, O., & Mönch, L. (2017). Integrated process planning and scheduling for large-scale flexible job shops using metaheuristics. International Journal of Production Research, 55:2, 392-409, DOI: 10.1080/00207543.2016.1182227 DOI: https://doi.org/10.1080/00207543.2016.1182227
Sörensen, K., & Glover, F. (2013). Metaheuristics. Encyclopedia of Operations Research and Management Science. Springer, New York. DOI: https://doi.org/10.1007/978-1-4419-1153-7_1167
Spyropoulos, C. D., (2000). AI planning and scheduling in the medical hospital environment. Artificial Intelligence in Medicine, 20(2):101-111. DOI: https://doi.org/10.1016/S0933-3657(00)00059-2
Stanković, A., Marković, D., Petrović, G., Ćojbašić, Ž. (2019). Simulated annealing and particle swarm optimization for the vehicle routing problem and communal waste collection in urban areas, 14th International Conference on Accomplishments in Mechanical and Industrial Engineering, DEMI 2019, 497-505, isbn: 978-99938-39-84-2.
Talbi, E. G. (2009). Metaheuristics: From design to implementation, John Wiley & Sons. DOI: https://doi.org/10.1002/9780470496916
Tamssaouet, K., Dauzère-Pérès, S., & Yugma, C. (2018). Metaheuristics for the job-shop scheduling problem with machine availability constraints. Computers & Industrial Engineering, 125:1-8.
Thomalla, C. (2001). Job shop scheduling with alternative process plans. International Journal of Production Economics 74(1-3):125-134 DOI: 10.1016/S0925-5273(01)00119-0 DOI: https://doi.org/10.1016/S0925-5273(01)00119-0
Thürer, M., Huang, G., Stevenson, M., Silva, C., & Filho, M. (2012). The performance of due date setting rules in assembly and multi-stage job shops: an assessment by simulation. International Journal of Production Research, 50(20), 5949–5965. DOI: https://doi.org/10.1080/00207543.2011.638942
Thürer, M., Land, M. J., Stevenson, M., & Fredendall, L. D. (2017). On the integration of due date setting and order release control. Production Planning & Control, 28(5), 420–430. DOI: https://doi.org/10.1080/09537287.2017.1302102
Vandaele, N. J. (2000). An integrated, hierarcmcal framework for planning, scheduling and controlling job shop. IFAC Proceedings Volumes, 30(14):121-126. DOI: https://doi.org/10.1016/S1474-6670(17)42708-X
Xing, W., & Zhang, J. (2000). Parallel machine scheduling with splitting jobs. Discrete Applied Mathematics, 103(1-3):259-269. DOI: https://doi.org/10.1016/S0166-218X(00)00176-1
Yang, X. S., (2010). Engineering Optimization: An introduction with metaheuristic applications. University of Cambridge, United Kingdom. DOI: https://doi.org/10.1002/9780470640425
Zhang, C. Y., Li, P. G., Guan, Z. L., & Rao, Y. Q. (2007). A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem. Computers & Operations Research, 34(11):3229-3242 DOI: https://doi.org/10.1016/j.cor.2005.12.002
Zhang, G., Gao, L., & Shi, Y. (2011). An effective genetic algorithm for the flexible job-shop scheduling problem, Expert Systems with Applications, 38(4):3563–3573. DOI: https://doi.org/10.1016/j.eswa.2010.08.145
