الفهرس 
Fundamental BackgroundOnly 14 pages are availabe for public view
 |  | from | 134 |  |  |
| | | from | 134 | | |
Abstract
Throughout the recent years, various parallel systems have been greatly developed and played a significant role in the computing field. The field of optimization problems is considered as one of the research fields that is noticeably affected by this technology. The main goals of using parallelism in the optimization field are speeding up the computation and being able to solve problems of large size.
The Multi-Way Number Partitioning (MWNP) problem is one of the NP-hard optimization problems, therefore it requires parallel processing. It aims to divide a multiset1 S of n numbers into k subsets such that the largest subset sum is minimized. The problem has many applications in various areas such as processors scheduling, public key encryption, and voting rules manipulation.
The main goal of this thesis is to study and discuss several sequen- tial algorithms for solving the MWNP problem which run in a very long time. This has motivated us to design a new parallel algorithm for solving the MWNP problem based on one of those algorithms in order to speed up the running time. In addition, the thesis addresses some different topics serving this goal.
1A multiset is a set in which an element can appear more than once.
xi
This thesis is organized into five chapters and a list of most impor- tant references relevant to its topics. In what follows, each chapter is briefly outlined.
Chapter 1 contains some fundamental concepts, a background, and algorithms related to the thesis’ topic like the complexity con- cepts of algorithms, an overview of optimization problems, and some examples of NP-hard optimization problems. Then, the MWNP prob- lem, which is the main problem of interest in this thesis, is introduced. In addition, some of its applications and a special case called the Two-Way Number Partitioning (TWNP) are given. At the end, the chapter focuses on some fundamentals, algorithms, techniques, and frameworks of parallel processing.
Chapter 2 presents most of the optimal and approximation algo- rithms for solving the MWNP problem. Nine algorithms are discussed in this chapter along with their related subroutines which assist in finding an optimal solution.
Chapter 3 includes a detailed description of the proposed parallel algorithm for solving the MWNP which is the main goal of the thesis and is based on the Improved Recursive Number Partitioning (IRNP) algorithm [21]. So, the chapter starts with detailed presentation of the latter sequential algorithm. After that, the chapter introduces
xii
the proposed parallel version, namely, the parallel IRNP (PIRNP) which made the running time for solving the problem at hand faster. While in Chapter 4, the performance of the proposed algorithm, PIRNP, is discussed. The detailed experimental configuration and parameter setting are given. Then, a comparison between PIRNP and the sequential version, IRNP, is presented. Finally, the scalability of
the proposed algorithm is discussed.
Finally, Chapter 5 contains the conclusion of the thesis that has presented the proposed parallel algorithm and its advantages. The chapter also points to some potential ideas for the future studies in this field.