Exactly Solving Hard Permutation Flowshop Scheduling Problems on Peta-Scale GPU-Accelerated Supercomputers

References

• Anstreicher K, Brixius N, Goux JP, Linderoth J (2002) Solving large quadratic assignment problems on computational grids. Math. Programming 91(3):563–588. http://dx.doi.org/10.1007/s101070100255.Crossref, Google Scholar
• Asanovic K, Bodik R, Demmel J, Keaveny T, Keutzer K, Kubiatowicz J, Morgan N, Patterson D, Sen K, Wawrzynek J, Wessel D, Yelick K (2009) A view of the parallel computing landscape. Commun. ACM 52(10):56–67. http://dx.doi.org/10.1145/1562764.1562783.Crossref, Google Scholar
• Bader DA, Hart WE, Phillips CA (2005) Parallel Algorithm Design for Branch and Bound (Springer, New York). http://dx.doi.org/10.1007/0-387-22827-6_5.Crossref, Google Scholar
• Cappello F (2009) Fault tolerance in petascale/exascale systems: Current knowledge, challenges and research opportunities. Internat. J. High Perform. Comput. Appl. 23(3):212–226.Crossref, Google Scholar
• Carneiro T, Muritiba A, Negreiros M, de Campos GL (2011) A new parallel schema for branch-and-bound algorithms using GPGPU. Sympos. Comput. Architecture High Performance Comput. (IEEE Computer Society, Los Alamitos, CA), 41–47. http://dx.doi.org/10.1109/SBAC-PAD.2011.20.Google Scholar
• Chakroun I, Melab N (2015) Toward a heterogeneous and adaptive parallel Branch-and-Bound algorithm. J. Comput. System Sci. 81(1):72–84. http://dx.doi.org/https://doi.org/10.1016/j.jcss.2014.06.012.Crossref, Google Scholar
• Chakroun I, Melab N, Mezmaz M, Tuyttens D (2013) Combining multi-core and GPU computing for solving combinatorial optimization problems. J. Parallel Distributed Comput. 73(12):1563–1577. http://dx.doi.org/https://doi.org/10.1016/j.jpdc.2013.07.023.Crossref, Google Scholar
• Crainic TG, Le Cun B, Roucairol C (2006) Parallel Branch-and-Bound Algorithms, Chapter 1 (John Wiley & Sons, Ltd, Hoboken, NJ), 1–28. http://dx.doi.org/https://doi.org/10.1002/9780470053928.ch1.Crossref, Google Scholar
• Date K, Nagi R (2019) Level 2 reformulation linearization technique-based parallel algorithms for solving large quadratic assignment problems on graphics processing unit clusters. INFORMS J. Comput. 31(4):771–789. http://dx.doi.org/10.1287/ijoc.2018.0866.Link, Google Scholar
• de Bruin A, Kindervater GAP, Trienekens HWJM (1995) Asynchronous parallel branch and bound and anomalies. Ferreira A, Rolim J, eds. Parallel Algorithms for Irregularly Structured Problems (Springer Berlin Heidelberg, Berlin, Heidelberg), 363–377. ISBN 978-3-540-44915-7.Crossref, Google Scholar
• Deroussi L, Gourgand M, Norre S (2006) New effective neighborhoods for the permutation flow shop problem. Technical Report LIMOS/RR-06-09, LIMOS, Université Clermont Auvergne. https://hal.archives-ouvertes.fr/hal-00678053/.Google Scholar
• Dubois-Lacoste J, Pagnozzi F, Stützle T (2017) An iterated greedy algorithm with optimization of partial solutions for the makespan permutation flowshop problem. Comput. Oper. Res. 81:160–166. http://dx.doi.org/https://doi.org/10.1016/j.cor.2016.12.021.Crossref, Google Scholar
• Fonlupt C, Marquet P, Dekeyser JL (1994) A data-parallel view of the load balancing experimental results on MasPar MP-1. Gentzsch W, Harms U, eds. High-Performance Computing and Networking (Springer Berlin Heidelberg, Berlin, Heidelberg), 338–343. ISBN 978-3-540-48408-0.Crossref, Google Scholar
• Garey MR, Johnson DS, Sethi R (1976) The complexity of flowshop and jobshop scheduling. Math. Oper. Res. 1(2):117–129.Link, Google Scholar
• Gendron B, Crainic TG (1994) Parallel branch-and-bound algorithms: Survey and synthesis. Oper. Res. 42(6):1042–1066.Link, Google Scholar
• Gmys J (2017) Heterogeneous cluster computing for many-task exact optimization—Application to permutation problems. Ph.D. thesis, Université de Mons/Université de Lille. https://hal.inria.fr/tel-01652000.Google Scholar
• Gmys J (2021) Permutation Flow-shop: Best-known makespans and schedules for Taillard and VRF benchmarks [Data Set]. Accessed February 16, 2021, http://doi.org/10.5281/zenodo.4542886.Google Scholar
• Gmys J, Mezmaz M, Melab N, Tuyttens D (2016) A GPU-based Branch-and-Bound algorithm using Integer-Vector-Matrix data structure. Parallel Comput. 59:119–139, http://dx.doi.org/10.1016/j.parco.2016.01.008.Crossref, Google Scholar
• Gmys J, Mezmaz M, Melab N, Tuyttens D (2017) IVM-based parallel branch-and-bound using hierarchical work stealing on multi-GPU systems. Concur. Comput. Pract. Exp. 29(9):e4019. http://dx.doi.org/https://doi.org/10.1002/cpe.4019.Crossref, Google Scholar
• Gmys J, Mezmaz M, Melab N, Tuyttens D (2020) A computationally efficient Branch-and-Bound algorithm for the permutation flow-shop scheduling problem. Eur. J. Oper. Res. 284(3):814–833. http://dx.doi.org/https://doi.org/10.1016/j.ejor.2020.01.039.Crossref, Google Scholar
• Grabowski J, Skubalska E, Smutnicki C (1983) On flow shop scheduling with release and due dates to minimize maximum lateness. J. Oper. Res. Soc. 34(7):615–620. http://dx.doi.org/10.1057/jors.1983.142.Crossref, Google Scholar
• Grama A, Kumar V (1995) Parallel search algorithms for discrete optimization problems. ORSA J. Comput. 7(4):365–385. http://dx.doi.org/10.1287/ijoc.7.4.365.Link, Google Scholar
• Hoefler T, Lumsdaine A (2008) Message progression in parallel computing—To thread or not to thread? 2008 IEEE Internat. Conf. Cluster Comput., 213–222. http://dx.doi.org/10.1109/CLUSTR.2008.4663774.Google Scholar
• Ignall E, Schrage L (1965) Application of the branch and bound technique to some flow-shop scheduling problems. Oper. Res. 13(3):400–412. http://dx.doi.org/10.1287/opre.13.3.400.Link, Google Scholar
• Jenkins J, Arkatkar I, Owens JD, Choudhary A, Samatova NF (2011) Lessons learned from exploring the backtracking paradigm on the GPU. Jeannot E, Namyst R, Roman J, eds. Euro-Par 2011 Parallel Processing (Springer Berlin Heidelberg, Berlin, Heidelberg), 425–437. ISBN 978-3-642-23397-5.Crossref, Google Scholar
• Johnson SM (1954) Optimal two- and three-stage production schedules with setup times included. Naval Res. Logist. 1(1):61–68. http://dx.doi.org/10.1002/nav.3800010110.Crossref, Google Scholar
• Karypis G, Kumar V (1994) Unstructured tree search on SIMD parallel computers. IEEE Trans. Parallel Distrib. Syst. 5:1057–1072.Crossref, Google Scholar
• Kizilay D, Tasgetiren MF, Pan QK, Gao L (2019) A variable block insertion heuristic for solving permutation flow shop scheduling problem with makespan criterion. Algorithms (Basel). 12(5):100.Crossref, Google Scholar
• Knuth D (1997) The Art of Computer Programming, volume 2: Seminumerical Algorithms (Addison-Wesley Professional, Reading, MA).Google Scholar
• Lageweg BJ, Lenstra JK, Kan AHGR (1978) A general bounding scheme for the permutation flow-shop problem. Oper. Res. 26(1):53–67. http://dx.doi.org/10.1287/opre.26.1.53.Link, Google Scholar
• Libralesso L, Focke PA, Secardin A, Jost V (2022) Iterative beam search algorithms for the permutation flowshop. Eur. J. Oper. Res. 301(1):217–234.Google Scholar
• Lomnicki ZA (1965) A “branch-and-bound” algorithm for the exact solution of the three-machine scheduling problem. J. Oper. Res. Soc. 16(1):89–100. http://dx.doi.org/10.1057/jors.1965.7.Crossref, Google Scholar
• Melab N, Gmys J, Mezmaz M, Tuyttens D (2018) Multi-core vs. many-core computing for many-task Branch-and-Bound applied to big optimization problems. Future Gen. Comput. Syst. 82:472–481. http://dx.doi.org/https://doi.org/10.1016/j.future.2016.12.039.Crossref, Google Scholar
• Mezmaz M, Melab N, Talbi E (2007) A grid-enabled branch and bound algorithm for solving challenging combinatorial optimization problems. 2007 IEEE Internat. Parallel Distributed Processing Sympos., 1–9, URL http://dx.doi.org/10.1109/IPDPS.2007.370217.Google Scholar
• Mezmaz M, Leroy R, Melab N, Tuyttens D (2014) A multi-core parallel branch-and-bound algorithm using factorial number system. 2014 IEEE 28th Internat. Parallel Distributed Processing Sympos., 1203–1212. http://dx.doi.org/10.1109/IPDPS.2014.124.Google Scholar
• Nowicki E, Smutnicki C (1996) A fast tabu search algorithm for the permutation flow-shop problem. Eur. J. Oper. Res. 91(1):160–175. http://dx.doi.org/https://doi.org/10.1016/0377-2217(95)00037-2.Crossref, Google Scholar
• Ożejko W (2009) Solving the flow shop problem by parallel programming. J. Parallel Distributed Comput. 69(5):470–481. http://dx.doi.org/https://doi.org/10.1016/j.jpdc.2009.01.009.Crossref, Google Scholar
• Pan QK, Tasgetiren MF, Liang YC (2008) A discrete differential evolution algorithm for the permutation flowshop scheduling problem. Comput. Ind. Eng. 55(4):795–816.Crossref, Google Scholar
• Pessoa TC, Gmys J, Melab N, de Carvalho FH Jr, Tuyttens D (2016) A GPU-based backtracking algorithm for permutation combinatorial problems. Carretero J, Garcia-Blas J, Ko RK, Mueller P, Nakano K, eds. Algorithms and Architectures for Parallel Processing (Springer International Publishing, Cham, Switzerland), 310–324. ISBN 978-3-319-49583-5.Crossref, Google Scholar
• Potts C (1980) An adaptive branching rule for the permutation flow-shop problem. Eur. J. Oper. Res. 5(1):19–25. http://dx.doi.org/https://doi.org/10.1016/0377-2217(80)90069-7.Crossref, Google Scholar
• Pruul E, Nemhauser G, Rushmeier R (1988) Branch-and-bound and parallel computation: A historical note. Oper. Res. Lett. 7(2):65–69. http://dx.doi.org/https://doi.org/10.1016/0167-6377(88)90067-3.Crossref, Google Scholar
• Rao VN, Kumar V (1987) Parallel depth first search, Part I: Implementation. Internat. J. Parallel Program 16(6):479–499. http://dx.doi.org/10.1007/BF01389000.Crossref, Google Scholar
• Ravetti MG, Riveros C, Mendes A, Resende MG, Pardalos PM (2012) Parallel hybrid heuristics for the permutation flow shop problem. Ann. Oper. Res. 199(1):269–284.Crossref, Google Scholar
• Reinefeld A, Schnecke V (1994) Work-load balancing in highly parallel depth-first search. Proc. IEEE Scalable High Performance Comput. Conf. (IEEE), 773–780.Google Scholar
• Rocki K, Suda R (2010) Parallel minimax tree searching on GPU. Wyrzykowski R, Dongarra J, Karczewski K, Wasniewski J, eds. Parallel Processing and Applied Mathematics (Springer Berlin Heidelberg, Berlin, Heidelberg), 449–456.Crossref, Google Scholar
• Ruiz R, Stützle T (2007) A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. Eur J. Oper. Res. 177(3):2033–2049. http://dx.doi.org/https://doi.org/10.1016/j.ejor.2005.12.009.Crossref, Google Scholar
• Taillard E (1993) Benchmarks for basic scheduling problems. Eur J. Oper. Res 64(2):278–285.Crossref, Google Scholar
• Taillard E (2015) Summary of best known lower and upper bounds of Taillard’s instances. Accessed March 11, 2022, http://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/flowshop.dir/best_lb_up.txt.Google Scholar
• Vaidyanathan K, Kalamkar DD, Pamnany K, Hammond JR, Balaji P, Das D, Park J, Joó B (2015) Improving concurrency and asynchrony in multithreaded MPI applications using software offloading. SC ’15: Proc. Internat. Conf. High Performance Comput. Networking Storage Anal. 1–12. http://dx.doi.org/10.1145/2807591.2807602.Google Scholar
• Vallada E, Ruiz R, Framinan JM (2015) New hard benchmark for flowshop scheduling problems minimising makespan. Eur J. Oper. Res. 240(3):666–677. http://dx.doi.org/https://doi.org/10.1016/j.ejor.2014.07.033.Crossref, Google Scholar
• Vu TT, Derbel B (2016) Parallel Branch-and-Bound in multi-core multi-CPU multi-GPU heterogeneous environments. Future Gen. Comput. Syst. 56:95–109. http://dx.doi.org/https://doi.org/10.1016/j.future.2015.10.009.Crossref, Google Scholar