2026-09-18T20:41:35Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/116108 2023-07-11 col_2142_5131 col_2142_16359 com_2142_5130 com_2142_16358 com_2142_234

Nagi, Rakesh 2022-08 application/pdf en text Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2024-08-01 The student, Mohit Mahajan, accepted the attached license on 2022-07-14 at 17:01. The student, Mohit Mahajan, submitted this Thesis for approval on 2022-07-14 at 17:08. This Thesis was approved for publication on 2022-07-19 at 13:48. DSpace SAF Submission Ingestion Package generated from Vireo submission #18320 on 2022-11-15 at 21:40:27 GPU accelerated transportation simplex algorithm Mahajan, Mohit 2022-07-19 Parallel Algorithms Transportation Problem Operations Research Simplex GPU CUDA Transportation Problem (TP) is a popular mathematical model for optimally matching several supply centers to several demand centers at the smallest transportation cost. Recent disruptions in the physical supply chains and the growth of internet marketplaces such as ride-sharing, doorstep delivery, and expedited shipping have engendered a need for efficient algorithms to solve fundamental TP in near real-time. The traditional ways to solve TP are unsuitable for some of these systems because their run-time causes latency issues. The evolution of accelerated computing using Graphics Processing Units (GPUs) has recently attracted some interest in solving optimization problems. In this research, an attempt has been made to solve TP in an accelerated way using a GPU. The Transportation Simplex Algorithm (TSA) is one of the efficient ways to solve the TP. A detailed study has been conducted to expose the underlying parallelism in the iterative steps of TSA. The parallel design proposed improves runtime through simultaneously executing multiple independent iterations. The results show that the accelerated algorithm performs up to 5 times faster on an average compared to the known sequential algorithm and up to 3 times faster on an average compared to the state-of-the-art commercial Linear Programming solver. Thesis eng https://hdl.handle.net/2142/116108 Copyright 2022 Mohit Mahajan M.S. Thesis Industrial Engineering University of Illinois at Urbana-Champaign Industrial&Enterprise Sys Eng