Meta-heuristic approach based on genetic and greedy algorithms to solve flexible job-shop scheduling problem

• Autorzy: Rezaeipanah Amin , Sarhangnia Fariba , Abdollahi Mohammad Javad

Identyfikatory

DOI

10.7494/csci.2021.22.4.4130

• Języki publikacji: EN

Abstrakty

EN

Job-shop scheduling systems are one of the applications of group technology in industry, the purpose of which is to take advantage of the physical or operational similarities of products in their various aspects of construction and design. Additionally, these systems are identified as cellular manufacturing systems (CMS). In this paper, a meta-heuristic method that is based on combining genetic and greedy algorithms has been used in order to optimize and evaluate the performance criteria of the flexible job-shop scheduling problem. In order to improve the efficiency of the genetic algorithm, the initial population is generated by the greedy algorithm, and several elitist operators are used to improve the solutions. The greedy algorithm that is used to improve the generation of the initial population prioritizes the cells and the job in each cell and, thus, offers quality solutions. The proposed algorithm is tested over the P-FJSP dataset and compared with the state-of-the-art techniques of this literature. To evaluate the performance of the diversity, spacing, quality, and run-time criteria were used in a multi-objective function. The results of the simulation indicate the better performance of the proposed method as compared to the NRGA and NSGA-II methods.

Słowa kluczowe

EN

job-shop scheduling; meta-heuristic method; genetic algorithm; greedy algorithm; jobs priority

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2021
• Tom: T. 22 (4)
• Strony: 463--488
• Opis fizyczny: Bibliogr. 33 poz., rys., tab.

Twórcy

autor

Rezaeipanah Amin

• University of Rahjuyan Danesh Borazjan, Department of Computer Engineering, Bushehr, Iran

autor

Sarhangnia Fariba

• Islamic Azad University, Department of Computer Engineering and Information Technology, Bushehr Branch, Bushehr, Iran

autor

Abdollahi Mohammad Javad

• University of Lian Bushehr, Department of Computer Engineering, Bushehr, Iran

Bibliografia

• [1] Ahmadi E., Zandieh M., Farrokh M., Emami S.M.: A multi objective optimization approach for flexible job shop scheduling problem under random machine breakdown by evolutionary algorithms, Computers & Operations Research, vol. 73, pp. 56–66, 2016.
• [2] Beasley D., Bull D.R., Martin R.R.: An Overview of Genetic Algorithms: Part 2, Research Topics, University Computing, vol. 15(4), pp. 170–181, 1993.
• [3] Brandimarte P.: Routing and scheduling in a flexible job shop by tabu search, Annals of Operations Research, vol. 41(3), pp. 157–183, 1993.
• [4] Driss I., Mouss K.N., Laggoun A.: A new genetic algorithm for flexible job-shop scheduling problems, Journal of Mechanical Science and Technology, vol. 29(3), pp. 1273–1281, 2015.
• [5] Engin O., Doyen A.: A new approach to solve hybrid flow shop scheduling problems by artificial immune system, Future Generation Computer Systems, vol. 20(6), pp. 1083–1095, 2004.
• [6] Erenay B., Suer G.A., Huang J., Maddisetty S.: Comparison of layered cellular manufacturing system design approaches, Computers & Industrial Engineering, vol. 85, pp. 346–358, 2015.
• [7] Flexible Job Shop Problem. http://people.idsia.ch/∼monaldo/fjsp.html (last vis-ited on 7 May. 2021).
• [8] Gao K.Z., Suganthan P.N., Pan Q.K., Chua T.J., Cai T.X., Chong C S.: Pareto-based grouping discrete harmony search algorithm for multi-objective flexible job shop scheduling, Information Sciences, vol. 289, pp. 76–90, 2014.
• [9] Ghalehgolabi M., Rezaeipanah A.: Intrusion Detection System Using Genetic Algorithm and Data Mining Techniques Based on the Reduction, International Journal of Computer Applications Technology and Research, vol. 6(11), pp. 461–466, 2017.
• [10] Gu X., Huang M., Liang X.: An Improved Genetic Algorithm with Adaptive Variable Neighborhood Search for FJSP, Algorithms, vol. 12(11), pp. 243–259, 2019.
• [11] Jadaan Al O., Rajamani L., Rao Raghavendra C.: Non-dominated ranked genetic algorithm for solving constrained multi-objective optimization problems: NRGA, Journal of Theoretical & Applied Information Technology, vol. 5(5), pp. 60–67, 2009.
• [12] Jalilvand-Nejad A., Fattahi P.: A mathematical model and genetic algorithm to cyclic flexible job shop scheduling problem, Journal of Intelligent Manufacturing, vol. 26(6), pp. 1085–1098, 2015.
• [13] Karthikeyan S., Saravanan M., Ganesh K.: GT Machine Cell Formation Problem in Scheduling for Cellular Manufacturing System Using Meta-Heuristic Method, Procedia Engineering, vol. 38, pp. 2537–2547, 2012.
• [14] Kazemi M., Gol S.S., Tavakkoli-Moghaddam R., Kia R. Khorrami J.: A mathematical model for assessing the effects of a lot splitting feature on a dynamic cellular manufacturing system, Production Engineering. Research and Development, vol. 11(4–5), pp. 557–573, 2017.
• [15] Knosala R., Wal T.: A production scheduling problem using genetic algorithm, Journal of Materials Processing Technology, vol. 109(1–2), pp. 90–95, 2001.
• [16] Land W.H., Schaffer J.D.: Background on Genetic Algorithms. In: The Art and Science of Machine Intelligence, pp. 1–44, Springer, Cham, 2020.
• [17] Li Y., Li X., Gupta J.N.: Solving the multi-objective flowline manufacturing cell scheduling problem by hybrid harmony search, Expert Systems with Applications, vol. 42(3), pp. 1409–1417, 2015.
• [18] Maghfiroh M.F., Darmawan A., Vincent F.Y.: Genetic Algorithm for Job Shop Scheduling Problem: A Case Study, International Journal of Innovation, Management and Technology, vol. 4(1), pp. 137–140, 2013.
• [19] Mahmoodian V., Jabbarzadeh A., Rezazadeh H., Barzinpour F.: A novel intelligent particle swarm optimization algorithm for solving cell formation problem, Neural Computing and Applications, vol. 31(2), pp. 801–815, 2019.
• [20] Nouri H.E., Driss O.B., Gh ́edira K.: Solving the flexible job shop problem by hybrid metaheuristics-based multiagent model, Journal of Industrial Engineering International, vol. 14(1), pp. 1–14, 2018.
• [21] Pezzella F., Morganti G., Ciaschetti G.: A genetic algorithm for the Flexible Job-shop Scheduling Problem, Computers and Operations Research, vol. 35(10), pp. 3202–3212, 2008.
• [22] Rauch L., Górecki G., Pietrzyk M.: Hybrid computer system for the identification of metallic material models on the basis of laboratory experiments, Computer Science, vol. 17, pp. 123–143, 2016.
• [23] Reddy V., Narendran T.T.: Heuristics and sequence-dependent set-up jobs in flow line cells, International Journal of Manufacturing Research, vol. 41(1), pp. 193–206, 2003.
• [24] Rezaeipanah A., Ahmadi G., Hajiani M., Darzi M.R.: An Improved Hybrid Cuckoo Search Algorithm for Vehicle Routing Problem with Time Windows, Journal of Quality Engineering and Production Optimization, vol. 4(2), pp. 189–208, 2019.
• [25] Rezaeipanah A., Matoori S.S., Ahmadi G.: A hybrid algorithm for the university course timetabling problem using the improved parallel genetic algorithm and local search, Applied Intelligence, vol. 51(1), pp. 467–492, 2021.
• [26] Shojaedini E., Majd M., Safabakhsh R.: Novel Adaptive Genetic Algorithm Sample Consensus, Applied Soft Computing, vol. 77, pp. 635–642, 2019.
• [27] Solimanpur M., Vrat P., Shankar R.: A heuristic to minimize makespan of cell scheduling problem, International Journal of Manufacturing Economics, vol. 88(3), pp. 231–241, 2004.
• [28] Srinivas M., Patnaik L.M.: Adaptive probabilities of crossover and mutation in genetic algorithms, IEEE Transactions on Systems, Man, and Cybernetics, vol. 24(4), pp. 656–667, 1994.
• [29] Tenschert A., Kubert R.: SLA-based job submission and scheduling with the Globus Toolkit 4, Computer Science, vol. 13, pp. 183–204, 2012.
• [30] Varela M.L., Trojanowska J., Carmo-Silva S., Costa N.M., Machado J.: Comparative Simulation Study of Production Scheduling in the Hybrid and the Parallel Flow, Management and Manufacturing Engineering Review, vol. 8(2), pp. 69–80, 2017.
• [31] Wang C., Tian N., Ji Z.C., Wang Y.: A hybrid evolutionary algorithm for flexible job shop scheduling problems. In: 2016 35th Chinese Control Conference (CCC), pp. 2690–2696, IEEE, 2016.
• [32] Yang Y., Chen Y., Long C.: Flexible robotic manufacturing cell scheduling problem with multiple robots, International Journal of Manufacturing Research, vol. 54(22), pp. 6768–6781, 2016.
• [33] Zeng C., Tang J., Yan C.: Job-shop cell-scheduling problem with inter-cell moves and automated guided vehicles, Journal of Intelligent Manufacturing, vol. 26(5), pp. 845–859, 2015.