An application of metaheuristic optimization algorithms for solving the flexible job-shop scheduling problem

Aleksandar Stanković; Goran Petrović; Žarko Ćojbašić; Danijel Marković

Aleksandar Stanković Faculty of Mechanical Engineering, University of Niš, Serbia
Goran Petrović Faculty of Mechanical Engineering, University of Niš, Serbia
Žarko Ćojbašić Faculty of Mechanical Engineering, University of Niš, Serbia
Danijel Marković Faculty of Mechanical Engineering, University of Niš, Serbia

Keywords: Scheduling, Flexible job-shop, Genetic algorithm, Tabu Search, Ant Colony Optimization, Local search.

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.

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.

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.

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

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.

Glover, F. W. (1989). Tabu Search – Part 1. ORSA Journal on Computing. 1 (2): 190–206. doi:10.1287/ijoc.1.3.190.

Glover, F. W., & Laguna, M. (1997). Tabu Search. Springer US.

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

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.

Kirkpatrick, S., Gelatt Jr, C. D., Vecchi, M. P. (1983). Optimization by Simulated Annealing. Science. 220 (4598): 671–680.

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.

Kung, L. C., & Chern, C. C. (2009). Heuristic factory planning algorithm for advanced planning and scheduling. Computers&OperationsResearch, 36(9), 2513—2530.

Lagodimos, A. G., & Leopoulos, V. (2000). Greedy heuristic algorithms for manpower shift planning, International Journal of Production Economics, 68, 95-106.

Laguna, M., Marti, R., & Marti, R. C. (2003). Scatter Search: Methodology and Implementation in C. New York: Springer.

Liaw, C. F. (2000). A hybrid genetic algorithm for the open shop scheduling problem. European Journal of Operational Research, 124(1):28-42.

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.

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

Nowicki, E., & Smutnicki, C. (2005). An advanced tabu search algorithm for the job shop problem. Journal of Scheduling, 8(2), 145–159.

Ostergard, P. R. J. (2002). A fast algorithm for the maximum clique problem, Discrete Applied Mathematics, 120(1-3):197-207.

Ö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.

Robson, J.M., (1986). Algorithms for maximum independent sets. Journal of Algorithms, 7(3):425-440.

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

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

Sörensen, K., & Glover, F. (2013). Metaheuristics. Encyclopedia of Operations Research and Management Science. Springer, New York.

Spyropoulos, C. D., (2000). AI planning and scheduling in the medical hospital environment. Artificial Intelligence in Medicine, 20(2):101-111.

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.

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

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.

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.

Vandaele, N. J. (2000). An integrated, hierarcmcal framework for planning, scheduling and controlling job shop. IFAC Proceedings Volumes, 30(14):121-126.

Xing, W., & Zhang, J. (2000). Parallel machine scheduling with splitting jobs. Discrete Applied Mathematics, 103(1-3):259-269.

Yang, X. S., (2010). Engineering Optimization: An introduction with metaheuristic applications. University of Cambridge, United Kingdom.

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

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.