Improving the TSAB algorithm through parallel computing

• Autorzy: Rudy Jarosław , Pempera Jaroslaw , Smutnicki Czesław

Identyfikatory

DOI

10.24425/acs.2020.134672

• Języki publikacji: EN

Abstrakty

EN

In this paper, a parallel multi-path variant of the well-known TSAB algorithm for the job shop scheduling problem is proposed. Coarse-grained parallelization method is employed, which allows for great scalability of the algorithm with accordance to Gustafon’s law. The resulting P-TSAB algorithm is tested using 162 well-known literature benchmarks. Results indicate that P-TSAB algorithm with a running time of one minute on a modern PC provides solutions comparable to the ones provided by the newest literature approaches to the job shop scheduling problem. Moreover, on average P-TSAB achieves two times smaller percentage relative deviation from the best known solutions than the standard variant of TSAB. The use of parallelization also relieves the user from having to fine-tune the algorithm. The P-TSAB algorithm can thus beused as module in real-life production planning systems or as a local search procedure in other algorithms. It can also provide the upper bound of minimal cycle time for certain problems of cyclic scheduling.

Słowa kluczowe

EN

job shop scheduling; parallel computing; operations research; taboo search; TSAB algorithm; coarse-grained parallelization

• Wydawca: Polish Academy of Sciences, Committee of Automatic Control and Robotics
• Czasopismo: Archives of Control Sciences
• Rocznik: 2020
• Tom: Vol. 30, No. 3
• Strony: 411--435
• Opis fizyczny: Bibliogr. 52, rys., tab., wykr., wzory

Twórcy

autor

Rudy Jarosław

• Department of Computer Engineering, Faculty of Electronics, Wrocław University of Science and Technology, Janiszewskiego 11-17, 50-372 Wrocław, Poland

autor

Pempera Jaroslaw

• Department of Automatics, Mechatronics and Control Systems, Faculty of Electronics, Wrocław University of Science and Technology, Janiszewskiego 11-17, 50-372 Wrocław, Poland

autor

Smutnicki Czesław

• Department of Computer Engineering, Faculty of Electronics, Wrocław University of Science and Technology, Janiszewskiego 11-17, 50-372 Wrocław, Poland

Bibliografia

• [1] G. M. Amdahl: Validity of the single processor approach to achieving large scale computing capabilities, In Proceedings of the Spring Joint Computer Conference (New York, NY, USA, 1967), AFIPS’67 (Spring), ACM, 483–485.
• [2] L. Asadzadeh: A local search genetic algorithm for the job shop scheduling problem with intelligent agents, Computers & Industrial Engineering, 85(2015), 376–383.
• [3] E. Balas and A. Vazacopoulos: Guided Local Search with Shifting Bot-tleneck for job shop scheduling, Manage. Sci.,44(2), (1998), 262–275.
• [4] J. C. Beck and N. Wilson: Proactive algorithms for job shop scheduling with probabilistic durations, J. Artif. Int. Res., 28(1), (2007), 183–232.
• [5] C. Blum and M. Dorigo: Search bias in Ant Colony Optimization: on the role of competition-balanced systems, IEEE Transactions on Evolutionary Computation, 9(2), (2005), 159–174.
• [6] C. Blum and M. Sampels: An Ant Colony Optimization algorithm for shop scheduling problems, Journal of Mathematical Modelling and Algorithms, 3(3), (2004), 285–308.
• [7] W. Bożejko, C. Smutnicki and M. Uchroński: Parallel calculating of the goal function in metaheuristics using GPU. In Computational Science – ICCS 2009 (Berlin, Heidelberg, 2009), G. Allen, J. Nabrzyski, E. Seidel, G. D. van Albada, J. Dongarra, and P. M. A. Sloot, Eds., Springer Berlin Heidelberg, 1014–1023.
• [8] W. Bożejko and M. Uchroński: Distributed Tabu Search algorithm for the job shop problem, In 1st Australian Conference on the Applications of Systems Engineering ACASE’12 (2012), 54.
• [9] W. Bożejko, M. Uchroński and M. Wodecki: Parallel cost function determination on GPU for the job shop scheduling problem, In Parallel Processing and Applied Mathematics (Berlin, Heidelberg, 2012), R. Wyrzykowski, J. Dongarra, K. Karczewski, and J. Waśniewski, Eds., Springer Berlin Heidelberg, 1–10.
• [10] T. C. E. Cheng, B. Peng and Z. Lü: A hybrid evolutionary algorithm to solve the job shop scheduling problem, Annals of Operations Research, 242(2), (2016), 223–237.
• [11] T. C. Chiang and H.-J. Lin: A simple and effective evolutionary algorithm for multiobjective flexible job shop scheduling. International Journal of Production Economics,141(1), (2013), 87–98.
• [12] C. Chong, M. Low, A. I. Sivakumar and K. Leng Gay: Using a Bee Colony algorithm for neighborhood search in job shop scheduling problems, 21st European Conference on Modelling and Simulation: Simulations in United Europe, ECMS 2007, (June 2007).
• [13] C. S. Chong, M. Y. Hean Low, A. I. Sivakumar and K. L. Gay: A Bee Colony Optimization algorithm to job shop scheduling, In Proceedings of the 2006 Winter Simulation Conference, (Dec 2006), 1954–1961.
• [14] U. Dorndorf, E. Peschand T. P. Huy: Recent developments in scheduling, In Operations Research Proceedings 1998, (Berlin, Heidelberg, 1999), P. Kall and H.-J. Lüthi, Eds., Springer Berlin Heidelberg, 353–365.
• [15] J. F. Gonçalves and M. G. C. Resende: An extended Akers graphical method with a biased random-key genetic algorithm for job-shop scheduling, International Transactions in Operational Research, 21(2), (2014), 215–246.
• [16] H. Ge, L. Sun, Y. Liang and F. Qian: An effective PSO and AIS-based hybrid intelligent algorithm for job-shop scheduling, IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 38(2), (2008), 358–368.
• [17] F. Geyik and I. H. Cedimoglu: The strategies and parameters of Tabu Search for job-shop scheduling, Journal of Intelligent Manufacturing,15(4), (2004), 439–448.
• [18] A. Gibbons and P. Spirakis: Lectures in parallel computation, vol. 4, Cambridge University Press, 1993.
• [19] M. A. González C. R. Vela, I. González-Rodríguez and R. Varela: Lateness minimization with Tabu Search for job shop scheduling problem with sequence dependent setup times, Journal of Intelligent Manufacturing, 24(4), (2013), 741–754.
• [20] J. F. Gonçalves, J. J. de Magalhães Mendes and M. G. Resende: A hybrid genetic algorithm for the job shop scheduling problem, European Journal of Operational Research,167(1), (2005), 77–95.
• [21] J. Grabowski, E. Nowicki and S. Zdrzałka: A block approach for single-machine scheduling with release dates and due dates, European Journal of Operational Research, 26(1986), 278–285.
• [22] J. Grabowski and M. Wodecki: A Very Fast Tabu Search Algorithm for Job Shop Problem, Springer US, Boston, MA, 2005, 117–144.
• [23] J. L. Gustafson: Reevaluating Amdahl’s law, Commun. ACM, 31(5), (1988), 532–533.
• [24] D.-W. Huang and J. Lin: Scaling populations of a genetic algorithm for job shop scheduling problems using MapReduce, In Proceedings of the 2010 IEEE Second International Conference on Cloud Computing Technology and Science (Washington, DC, USA, 2010), CLOUDCOM ’10, IEEE Computer Society, 780–785.
• [25] K.-L. Huang and C.-J. Liao: Ant Colony Optimization combined withTaboo Search for the job shop scheduling problem, Computers and Operations Research, 35(4), (2008), 1030–1046.
• [26] Hui J. Yang, L. Sun, H. P. Lee, Y. Qian and Chun Y. Liang: Clonal selection based memetic algorithm for job shop scheduling problems, Journal of Bionic Engineering, 5(2), (2008), 111–119.
• [27] A. S. Jain, B. Rangaswamy and S. Meeran: New and “stronger” job-shop neighbourhoods: A focus on the method of Nowicki and Smutnicki (1996), Journal of Heuristics, 6(4), (2000), 457–480.
• [28] J. Kuhpfahl and C. Bierwirth: A study on local search neighborhoods for the job shop scheduling problem with total weighted tardiness objective, Computers & Operations Research, 66(2016), 44–57.
• [29] M. Kurdi: An effective new island model genetic algorithm for job shop scheduling problem.Computers & Operations Research, 67(2016), 132–142.
• [30] S. Lawrence: Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques (Supplement), Graduate School of Industrial Administration, Carnegie-Mellon University, 1984.
• [31] X. Li, X. Shao, L. Gao and W. Qian: An effective hybrid algorithm for integrated process planning and scheduling, International Journal of Production Economics,126(2), (2010), 289–298.
• [32] C.-F. Liaw: A hybrid genetic algorithm for the open shop scheduling problem, European Journal of Operational Research, 124(1), (2000), 28–42.
• [33] E. Nowicki and C. Smutnicki: A fast Taboo Search algorithm for the job shop problem, Management Science, 42(6), (1996), 797–813.
• [34] E. Nowicki and C. Smutnicki: An advanced Tabu Search algorithm for the job shop problem, J. of Scheduling, 8(2), (2005), 145–159.
• [35] P. M. Pardalos and O. V. Shylo: An algorithm for the job shop scheduling problem based on Global Equilibrium Search techniques, Computational Management Science, 3(4), (2006), 331–348.
• [36] P. M. Pardalos, O. V. Shylo and A. Vazacopoulos: Solving job shop scheduling problems utilizing the properties of backbone and “big valley”, Computational Optimization and Applications, 47(1), (2010), 61–76.
• [37] B. Peng, Z. Lü and T. Cheng: A Tabu Search/Path Relinking algorithm to solve the job shop scheduling problem, Computers & Operations Research, 53(2015), 154–164.
• [38] C. Rego and R. Duarte: A filter-and-fan approach to the job shop scheduling problem, European Journal of Operational Research, 194(3) (2009), 650–662.
• [39] A. Rossi and G. Dini: Flexible job-shop scheduling with routing flexibility and separable setup times using Ant Colony Optimisation method, Robotics and Computer-Integrated Manufacturing, 23(5), (2007), 503–516.
• [40] C. R. Scrich, V. A. Armentano and M. Laguna: Tardiness minimizationin a flexible job shop: A Tabu Search approach, Journal of Intelligent Manufacturing,15(1), (2004), 103–115.
• [41] D. Sha and C.-Y. Hsu: A hybrid Particle Swarm Optimization for job shop scheduling problem, Computers & Industrial Engineering, 51(4), (2006), 791–808.
• [42] C. Smutnicki: Cyclic job shop problem [cykliczny problem gniazdowy], In Advanced models and optimisation algorithm for cyclic systems [Zaawansowane modele i algorytmy optymalizacji w systemach cyklicznych], W. Bożejko, J. Pempera, C. Smutnicki, and M. Wodecki, Eds., Akademicka Oficyna Wydawnicza EXIT, Warszawa, 2017, ch. 6, pp. 105–160 (in Polish).
• [43] L. Sun, X. Cheng and Y. Liang: Solving job shop scheduling problem usinggenetic algorithm with penalty function, International Journal of Intelligent Information Processing, 1 (2010), 65–77.
• [44] S. Sundar, P. N. Suganthan, C. T. Jin, C. T. Xiang and C. C. Soon: A hybrid Artificial Bee Colony algorithm for the job-shop scheduling problem with no-wait constraint, Soft Computing, 21(5), (2017), 1193–1202.
• [45] E. Taillard: Benchmarks for basic scheduling problems, European Journal of Operational Research, 64(2), (1993), 278–285.
• [46] J. J. van Hoorn: The current state of bounds on benchmark instances of the job-shop scheduling problem. Journal of Scheduling, 21(1), (2018),127–128.
• [47] P. J. M. van Laarhoven, E. H. L. Aarts and J. K. Lenstra: Job shop scheduling by Simulated Annealing. Operations Research, 40(1), (1992), 113–125.
• [48] T. Vredeveld and C. A. J. Hurkens: Experimental comparison of approximation algorithms for scheduling unrelated parallel machines. INFORMSJ. on Computing, 14(2) (2002), 175–189.
• [49] J. P. Watson: Empirical Modeling and Analysis of Local Search Algorithmsfor the Job-shop Scheduling Problem. PhD thesis, Fort Collins, CO, USA, 2003. AAI3114700.
• [50] J. P. Watson, A. E. Howe and L. D. Whitley: Deconstructing Nowicki and Smutnicki’s i-TSAB tabu search algorithm for the job-shop scheduling problem. Computers & Operations Research, 33(9), (2006), 2623–2644. Part Special Issue: Anniversary Focused Issue of Computers & Operations Research on Tabu Search.
• [51] C. Zhang, P. Li, Z. Guan and Y. Rao: A Tabu Search algorithm with a new neighborhood structure for the job shop scheduling problem. Computers & Operations Research, 34(11), (2007), 3229–3242.
• [52] C. Y. Zhang, P. Li, Y. Rao and Z. Guan: A very fast TS/SA algorithm for the job shop scheduling problem. Comput. Oper. Res., 35(1), (2008), 282–294.