Study on critical operations in job shop scheduling in productive systems
DOI:
https://doi.org/10.33448/rsd-v11i5.28035Keywords:
Local search; Critical path; Scheduling; Manufacturing; Process plan.Abstract
This work studies the classic problem of job shop scheduling for makespan minimizing. Due to the combinatorial nature and computational complexity of this problem, the use of metaheuristic techniques combined with local search methods is quite widespread as it allows satisfactory results in a viable computational time. In general, local search methods are based on empirical permutations of the operations that make up the critical path of a solution, the so-called critical operations, which demand the calculation of the critical path for each of the solutions generated in the search process. In addition to increasing the computational cost of local search, this approach promotes permutations of operations that do not result in any improvement in the solution. This work investigates the distribution of critical operations on the machines and the correlation between this distribution and problem characteristics. The objective is to estimate machines that concentrate critical operations and identify characteristics that contribute to the definition of local search methods that do not depend on the calculation of the critical path for each solution. Computational experiments with usual instances from literature show that there is a concentration of critical operations in some machines and, in some cases, a positive correlation between this concentration and the average processing times of the operations, which can provide subsidies for creating more efficient local search methods.
References
Aarts, E., & Lenstra, J. K. (Eds.). (1993). Local Search in Combinatorial Optimization. Princeton University Press. https://apps.crossref.org/coaccess/coaccess.html?doi=10.2307%2Fj.ctv346t9c
Abdullahi, M., Ngadi, M., & Abdulhamid, S. (2016). Symbiotic organism search optimization based task scheduling in cloud computing environment. Future Generation Computer Systems, 56, pp. 640-650. https://doi.org/10.1016/j.future.2015.08.006
Akram, K., Kamal, K., & Z. A. (2016). Fast simulated annealing hybridized with quenching for solving job shop scheduling problem. Applied Soft Computing, 49, pp. 510-523. https://doi:10.1016/j.asoc.2016.08.037
Amirghasemi, M., & Zamani, R. R. (2015). An effective asexual genetic algorithm for solving the job shop scheduling problem. Computers & Industrial Engineering, 83, pp. 123-138. https://doi:10.1016/j.cie.2015.02.011
Asadzadeh, L. (2015). A local search genetic algorithm for the job shop scheduling problem with intelligent agents. Computers & Industrial Engineering, 85, pp. 123-138. https://doi:10.1016/j.cie.2015.04.006
Balas E, V. A. (1998). Guided local search with shifting bottleneck for job shop scheduling. Management Science, 44, pp. 262-275. Fonte: https://www.jstor.org/stable/2634500
Beasley, J. E. (1990). OR-Library. http://people.brunel.ac.uk/~mastjjb/jeb/info.html
Bierwirth, C., & J., K. (2017). Extended GRASP for the Job Shop Scheduling Problem with Total Weighted Tardiness Objective. European Journal of Operational Research, 261(3), pp. 835-848. https://doi:10.1016/j.ejor.2017.03.030
Blazewicz, J., Domschke, W., & Pesch, E. (1996). The job shop scheduling problem: Conventional and new solution techniques. European Journal of Operational Research, 1, N.93, pp. 1-33. https://doi.org/10.1016/0377-2217(95)00362-2
Bueno, A., Godinho Filho, M., & Frank, A. G. (2020). Bueno, A.; Godinho Filho, M.; Frank, A. G. (2020). Smart production planning and control in the Industry 4.0 context: A systematic literature review. Computers & Industrial, 149. https://doi:10.1016/j.cie.2020.106774.
Burgy, R., & Bulbul, K. (2018). The job shop scheduling problem with convex costs. European Journal of Operational Research., 268 (1), pp. 82-100. https://doi:10.1016/j.ejor.2018.01.027
Çalis, B., & Bulkan, S. (2015). A research survey: review of AI solution strategies of job shop scheduling problem. Journal of Intelligent Manufacturing, 26(5), pp. 961-973. https://doi:10.1007/s10845-013-0837-8
Chan, F. T., Wong, T. C., & Chan, L. Y. (2008). A Genetic algorithm-based approach to job shop scheduling problem with assembly stage. In 2008 IEEE International Conference on Industrial Engineering and Engineering Management (pp. 331-335). Singapore: IEEE. https://doi:10.1109/IEEM.2008.4737885
Cruz-Chávez, M. A. (2014). Neighbourhood Generation mechanism applied in simulated annealing to job shop scheduling problems. International Journal of Systems Science, pp. 2673-2685. https://doi:10.1080/00207721.2013.876679
Dell’Amico, M., & Trubian, M. (s.d.). Applying tabu-search to job-shop scheduling problem. 41, pp. 231-252. https://doi.org/10.1007/BF02023076
Freitag, M., & Hildebrandt, T. (2016). Automatic design of scheduling rules for complex manufacturing systems by multi-objective simulation-based optimization. CIRP Annals-Manufacturing Technology, 65 (1), pp. 433-436. https://doi.org/10.1016/j.cirp.2016.04.066.
Fuchigami, H. Y., Moura, M. A., & Branco, F. J. (2017). Modelos Matemáticos para Programação Job Shop com Tempos de Configuração Independentes de Sequência. Revista Produção Online, 17 (1), pp. 245-267. https://doi:10.14488/1676-1901.v17i1.2504.
Goldberg, D. (1989). Genetic algorithms in search, optimization, and machine learning. Addison-Wesley.
Gonçalves, J. F., Mendes, J. J., & Resende, M. G. (2005). A hybrid genetic algorithm for the job shop scheduling problem. European Journal of Operational Research,, 167, pp. 77-95. https://doi:10.1016/j.ejor.2004.03.012
Grabowski, J., & Wodecki, M. (2005). A very fast tabu search algorithm for job shop problem. In book: Metaheuristic optimization via memory and evolution; tabu search and scatter search. Em A. B. Rego C, & A. Rego C. (Ed.), Metaheuristic optimization via memory and evolution; tabu search and scatter. Kluwer Academic Publishers. https://doi:10.13140/2.1.2986.6880
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. The University of Michigan Press. Ann Harbor.
Jain, A. S., Rangaswamy, B., & Meeran, S. (2000). New and “stronger” job-shop neighbourhoods: A focus on the method of Nowicki and Smutnicki (1996). Journal of Heuristcs, 6, pp. 457-480. https://doi:10.1023/A:1009617209268
Kong, W., Lei, Y., & Ma, J. (2016). Virtual machine resource scheduling algorithm for cloud computing based on auction mechanism. Optik-International Journal for Light and Electron Optics, 127 (12), pp. 5099-5104. https://doi:10.1016/j.ijleo.2016.02.061
Kuhpfahl, J., & Bierwirth, C. (2016). A study on local search neighborhoods for the job shop scheduling problem with total weighted tardiness objective. omputers & Operations Research, 66, pp. 44-57. https://doi:10.1016/j.cor.2015.07.011
Lawrence, S. (1984). Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques (Supplement). Tese (Doutorado em Administração Industrial) - Carnegie-Mellon University, Pittsburgh.
Lenstra, J. K., Rinnooy Kan, A. H., & Brucker, P. (1977). Complexity of machine. Em E. J. P.L. Hammer (Ed.), Annals of Discrete Mathematics. 1, pp. 343-362. Elsevier.
Li, K., Zhang, X., Leung, J.-T., & Yang, S. (2016). Parallel machine scheduling problems in green manufacturing industry. Journal of Manufacturing Systems, 38, pp. 98-106. https://doi:10.1016/j.jmsy.2015.11.006
Li, X., Peng, Z., Du, B., Jun, G., Wenxiang, X., & Zhuang, K. (2017). Hybrid artificial bee colony algorithm with a rescheduling strategy for solving flexible job shop scheduling problems. Computers & Industrial Engineering, 113, pp. 10-26. https://doi:10.1016/j.cie.2017.09.005
Liu, W., Liang, Z., Ye, Z., & Liu, L. (2016). The optimal decision of customer order decoupling point for order insertion scheduling in logistics service supply chain. International Journal of Production Economic, 175, pp. 50-60. https://doi:10.1016/j.ijpe.2016.01.021
Lu, H., Shi, J., Fei, Z., Zhou, Q., & Mao, K. (2018). Analysis of the similarities and differences of job-based scheduling problems. European Journal of Operational Research, 270 (3), pp. 809-825. https://doi:10.1016/j.ejor.2018.01.051
Mahmud, S., Abbasi, A., Chakrabortty, R. K., & Ryan, M. J. (2021). Multi-operator communication based differential evolution with sequential Tabu Search approach for job shop scheduling problems. Applied Soft Computing, 108, pp. 1-15. https://doi:10.1016/j.asoc.2021.107470
Mati, Y., Dauzre-Prs, S., & Lahlou, C. (2011). A general approach for optimizing regular criteria in the job-shop scheduling problem. European Journal of Operational Research, 212, pp. 33-42. https://doi:10.1080/00207721.2013.876679
Matsuo, H. D., Suh, C., & Sullivan, R. (1988). Controlled search simulated annealing method for general job shop scheduling problem. Working Paper, Department of Management, The University of Texas at Austin, Austin, TX.
Mattfeld, D. C., & Bierwirth, C. (2004). n efficient genetic algorithm for job shop scheduling with tardiness objectives. European Journal of Operational Research, 155 (3), pp. 616-630. https://doi:10.1016/S0377-2217(03)00016-X
Michalewicz, Z. (1996) Genetic Algorithms + Data Structures = Evolution Programs. 3rd revised and extended. Berlim, Springer-Verlag.
Mirshekarian, S., & Sormaz, D. N. (2016). Correlation of Job-Shop Scheduling Problem Features with Scheduling EfÞciency. Expert Systems With Applications, 62, pp. 131-147. https://doi:10.1016/j.eswa.2016.06.014
Mitchell, T. M. (1997). Machine Learning (16 ed.). New York: McGraw-Hill.
Muminu, O. A., & A., A. (2016). inimizing the weighted number of tardy jobs on multiple machines: A review. Journal of Industrial & Management Optimization, 12 (4), pp. 1465-1493. https://doi:10.3934/jimo.2016.12.1465
Nowicki, E., & Smutnicki, C. (1996). A Fast Taboo Search Algorithm for the Job Shop Problem. Management Science, 42 (6), pp. 797-813. https://www.jstor.org/stable/2634595
Parente, M., Figueira, G., Amorim, P., & Marques, A. (2020). roduction scheduling in the context of Industry 4.0: review and trends. International Journal of Production Research, 58 (17), pp. 5401-5431. https://doi:10.1080/00207543.2020.1718794
Pérez, E., Posada, M., & Herrera, F. (2012). Analysis of new niching genetic algorithms for finding multiple solutions in the job shop scheduling. Journal of Intelligent Manufacturing, 23, pp. 341-356. https://doi:10.1007/s10845-010-0385-4
Pinedo, M. L. (2016). Scheduling: Theory, Algoritms, and Systems (5a ed.). Springer. https;//doi:10.1007/978-3-319-26580-3
Pongchairerks, P. A. (2019). A Two-Level Metaheuristic Algorithm for the Job-Shop Scheduling Problem. Complexity, 2019, pp. 1-11. https://doi:10.1155/2019/8683472
Ponsich, A., & Coello, C. A. (2013). A Hybrid Differential Evolution Tabu Search Algorithm for the Solution of Job-Shop Scheduling Problems. Applied Soft Computing, 13 (1), pp. 462-474. https://doi:10.1016/j.asoc.2012.07.034
Tamssaouet, K., Dauzère-Pérès, S., & Yugma, C. (2018). Metaheuristics for the Job-Shop Scheduling Problem with Machine Availability Constraints. Computers and Industrial Engineering, 125, pp. 1-8. https://doi:10.1016/j.cie.2018.08.008
Tang, H., Chen, R., Li, Y., Peng, Z., Guo, S., & Du, Y. (2019). Flexible job-shop scheduling with tolerated time interval and limited starting time interval based on hybrid discrete PSO-SA: An application from a casting workshop. Applied Soft Computing, 78, pp. 176-194. https://doi:10.1016/j.asoc.2019.02.011
Van Laarhoven, P. E. (1992). Job shop scheduling by simulate annealing. Institute for Operations Research and the Management Sciences, 40, n.1, pp. 113-125. https://www.jstor.org/stable/171189
Wall, M. (1996). GAlib: A C++ library of genetic algorithm components. Mechanical Engineering Departament, Massachussetts Institute of Technology. Fonte: http://lancet.mit.edu/ga/dist/
Wang, B., Wang, X., Lan, F., & Pan, Q. (2018). A hybrid local-search algorithm for robust job-shop scheduling under scenarios. Applied Soft Computing, 62, pp. 259-271. https://doi:10.1016/j.asoc.2017.10.020
Wang, X., Wang, B., Zhang, X., Xia, X., & Pan, Q. (2021). wo-objective Robust Job-Shop Scheduling with Two Problem-Specific Neighborhood Structures. Swarm and Evolutionary Computation, 61, p. 100805. https://doi:10.1016/j.swevo.2020.100805
Wu, Z., Sun, S., & Yu, S. (2020). Optimizing makespan and stability risks in job shop scheduling. Computers and Operations Research, 122, p. 104963. https://doi:10.1016/j.cor.2020.104963
Yamada, T. (2003). Studies on metaheuristics for jobshop and flowshop scheduling problems. PhD dissertação Kyoto University. http://www.kecl.ntt.co.jp/as/members/yamada/YamadaThesis.pdf
Yamada, T., & Nakano, R. (1997). Job shop scheduling. IEE Control Engineering Series, 55, pp. 134-160. https://www.kecl.ntt.co.jp/as/members/yamada/galbk.pdf
Yang, J., Sun, L., Lee, H. P., Qian, Y., & Liang, Y. C. (2008). Clonal Selection Based Memetic Algorithm for Job Shop Scheduling Problems. Journal of Bionic Engineering, 5 (2), pp. 111–119. https://doi:10.1016/S1672-6529(08)60014-1
Zhang, J., Ding, G., Zou, Y., Qin, S., & Fu, J. (2019). Review of job shop scheduling research and its new perspectives under Industry 4.0. Journal of Intelligent Manufacturing, 30, pp. 1809–1830. https://doi:10.1007/s10845-017-1350-2
Zhang, R., & Wu, C. (2011). An artificial bee colony algorithm for the job shop scheduling problem with random processing times. Entropy, 13 (9), pp. 1708–1729. https://doi:10.3390/e13091708
Zhang, R., Song, S., & Wu, C. (2013). A hybrid differential evolution algorithm for job shop scheduling problems with expected total tardiness criterion. Applied Soft Computing, pp. 1448–1458. https://doi:10.1016/j.asoc.2012.02.024
Zhang, R., Song, S., & Wu, C. (2013(b)). A hybrid artificial bee colony algorithm for the job shop scheduling problem. International Journal of Production Economics, 141((1)), pp. 167-178. https://doi:10.1016/j.ijpe.2012.03.035
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 Jonathan Farias Bordignon; Luis Carlos Caparroz dos Santos; Marilda Fátima de Souza da Silva; Fabio Henrique Pereira
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
1) Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
2) Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
3) Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
