Project Title : High-Performance Computing for Logistics Optimization

Supervisor : Asst Prof. Malcolm Low Yoke Hean

Degree Registered : Doctor of Philosophy

Starting Date : 26/07/2007

Keywords: Logistics, Operational Research, Optimization Algorithms, High-Performance Computing

Project Description :

Logistics is the art and science of managing and controlling the flow of goods, energy, information and other resources like products, services, and people, from the source of production to the marketplace. It is difficult to accomplish any marketing or manufacturing without logistical support. It involves the integration of information, transportation, inventory, warehousing, material handling, and packaging. The operating responsibility of logistics is the geographical repositioning of raw materials, work in process, and finished inventories where required at the lowest cost possible [1].

There are several conventions in logistics: Just In Time ( JIT), as an example, is an inventory strategy implemented to improve the return on investment of a business by reducing in-process inventory and its associated costs [2]. The Just in Time philosophy is also applied to other segments of the supply chain in several types of industries. In the commercial sector, it means eliminating one or all of the warehouses in the link between a factory and a retail establishment which is called Cross-docking. Cross-docking is a practice in logistics of unloading materials from an incoming semi-trailer truck or rail car and loading these materials in outbound trailers or rail cars, with little or no storage in between [2]. In this regard, achieving operational performance is greatly dependent upon good planning and dynamic scheduling. This necessitates developing optimization policies and real-time scheduling algorithms for cross-docking operations.

All of this introduces the concept of Operational Research which is an interdisciplinary branch of mathematics that uses methods like mathematical modeling, statistics, and algorithms to arrive at optimal or good decisions in complex problems which are concerned with optimizing the maxima (profit, faster assembly line, greater crop yield, higher bandwidth, etc) or minima (cost loss, lowering of risk, etc) of objective functions [3]. The eventual intention behind using Operations Research is to arrive at a best possible solution to a problem mathematically, which improves or optimizes the performance of the system. Some of the primary tools used by operational researchers are statistics, optimization, stochastic, queuing theory, game theory, graph theory, decision analysis, and simulation.

Optimization, already mentioned as an important tool in Operational Research, is the use of specific techniques to determine the most cost effective and efficient solution to a problem or design for a process. There are two subcategories in the category of optimization algorithms: combinatorial optimization and evolutionary algorithms [4]. We can name Local Search, Simulated Annealing, Genetic Algorithms, and Ant colony Optimization. These are used in different application domains such as manufacturing, maritime and aerospace applications, and biological problems.

These algorithms are normally subsuming “arithmetic intensity,” i.e. with large ratio of mathematical operations [5]. Some of them are inherently data parallel computational problems which can be executed a piece at a time on many different processing devices, and then put back together again at the end to get the correct result; some are inherently serial algorithms in which each step or iteration requires the result of the previous one and some require a mix of sequential and data-parallel computation.

However, regardless of the nature of these algorithms, it is very important to shorten their run times while they are finding the optimal solution. In this regard, parallel algorithms are highly valuable because it is faster to perform large computing tasks via a parallel algorithm than it is via a serial (non-parallel) algorithm. Moreover, due to the way modern processors work, it is far more difficult to construct a computer with a single fast processor than one with many slower processors with the same throughput [6]. That is why data-parallel programming is here to stay.

The proposed research will be going to address this issue in the area of high-pesrformance computing systems through exploiting parallel-programming models mapped on multi-core processors [7] and the recently-introduced “streaming” computational model mapped on Graphics Processing Units (GPUs) [5] - a dedicated graphics rendering device comprising several functional units, capable of parallel processing - for optimizing some common applications used in logistics industry.

References :

[1] Gianpaolo Ghiani, Gilbert Laporte, Roberto Musmanno, Introduction to Logistics Systems Planning and Control, Wiley Interscience Series in Systems and Optimization, January 2004.

[2] Kevin R. Gue, “Cross-docking: Just-In-Time for Distribution,” Teaching Notes-Naval Postgraduate School, Monterey, CA, May 2001.

[3] Frederick S. Hillier, Gerald J. Lieberman, Frederick Hillier, Gerald Lieberman, MP Introduction to Operations Research, McGraw-Hill Science/Engineering/Math; 8 th edition, July 2004.

[4] Edwin K. P. Chong, Stanislaw H. Żak, An Introduction to Optimization, Wiley-Interscience Series in Discrete Mathematics and Optimization; 2 nd edition, July 2001.

[5] Matt Pharr, Randima Fernando, GPU Gems 2: Programming Techniques for High-Performance Graphics and General-Purpose Computation, Addison-Wesley Professional; Har/Cdr edition, March 2005.

[6] Ananth Grama, George Karypis, Vipin Kumar, Anshul Gupta, An Introduction to Parallel Computing: Design and Analysis of Algorithms, Addison Wesley; 2 nd edition, January 2003.

[7] Shameem Akhter, Jason Roberts, Multi-Core Programming: Increasing Performance through Software Multi-threading, Intel Corporation (2006), ISBN 0-9764832-4-6.

Publications :

• Nil