SOLVING THE BI-DIMENSIONAL TWO-WAY NUMBER PARTITIONING PROBLEM WITH HEURISTIC ALGORITHMS

被引：0

作者：

Hacibeyoglu, Mehmet ^{[1
]}

Tongur, Vahit ^{[1
]}

Alaykiran, Kemal ^{[2
]}

机构：

[1] Necmettin Erbakan Univ, Dept Comp Engn, Konya, Turkey

[2] Necmettin Erbakan Univ, Dept Ind Engn, Konya, Turkey

来源：

2014 IEEE 8th International Conference on Application of Information and Communication Technologies (AICT) | 2014年

关键词：

Greedy algorithm; genetic algorithm; two-way number partitioning problem; combinatorial optimization;

D O I：

暂无

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The two-way number partitioning problem is to divide set of numbers into two subsets. As a result of the dividing process the sums of numbers in subsets must be as nearly equal as possible. The two-way number partitioning problem problem is NP-complete. The bi-dimensional two-way number partitioning problem is a kind of number partitioning problem. The sets have only two coordinates and the aim is minimized the differences of the sum of the numbers for both coordinates. This work presents two heuristic algorithm for solving bi-dimensional two-way number partitioning problem. Fist algorithm is best known and most used greedy algorithm. The other one is a novel genetic algorithm approach. These algorithms are analyzed, implemented and tested on randomly different 20 datasets.

引用

页码：73 / 77

页数：5

共 10 条

[1] Randomized methods for the number partitioning problem [J].

Arguello, MF ;

Feo, TA ;

Goldschmidt, O .

COMPUTERS & OPERATIONS RESEARCH, 1996, 23 (02) :103-111

[2]

Berretta P. M. Regina, 2004, METAHEURISTICS COMPU, P65

[3]

Holland J.H., 1968, Hierarchical descriptions, universal spaces and adaptive systems

[4] OPTIMIZATION BY SIMULATED ANNEALING - AN EXPERIMENTAL EVALUATION .1. GRAPH PARTITIONING [J].

JOHNSON, DS ;

ARAGON, CR ;

MCGEOCH, LA ;

SCHEVON, C .

OPERATIONS RESEARCH, 1989, 37 (06) :865-892

[5] A complete anytime algorithm for number partitioning [J].

Korf, RE .

ARTIFICIAL INTELLIGENCE, 1998, 106 (02) :181-203

[6]

Korf RE, 1995, INT JOINT CONF ARTIF, P266

[7] Two metaheuristic approaches for solving multidimensional two-way number partitioning problem [J].

Kratica, Jozef ;

Kojic, Jelena ;

Savic, Aleksandar .

COMPUTERS & OPERATIONS RESEARCH, 2014, 46 :59-68

[8]

Kumar M, 2010, Genetic algorithm: review and application, DOI [10.2139/ssrn.3529843, DOI 10.2139/SSRN.3529843]

[9]

Narenda K., 1998, DIFFERENCING METHOD, V82, P181

[10]

Pop P. C., 2013, LECT NOTES COMPUT SC, V7997, P81

← 1 →