Other Articles by Author(s)

Dimitris Varsamis
Fotios Chanlioglou

Author(s) and WSEAS

Dimitris Varsamis
Fotios Chanlioglou

WSEAS Transactions on Computers

Print ISSN: 1109-2750
E-ISSN: 2224-2872

Volume 17, 2018

Notice: As of 2014 and for the forthcoming years, the publication frequency/periodicity of WSEAS Journals is adapted to the 'continuously updated' model. What this means is that instead of being separated into issues, new papers will be added on a continuous basis, allowing a more regular flow and shorter publication times. The papers will appear in reverse order, therefore the most recent one will be on top.

A Parallel Approach of Best Fit Decreasing Algorithm

AUTHORS: Dimitris Varsamis, Fotios Chanlioglou

Download as PDF

ABSTRACT: : In this work we introduce a parallel approach of Best Fit Decreasing algorithm. The Best Fit Decreasing algorithm is heuristic and is used for optimal assignment problems, for example cutting stock problem, bin packing problem etc. The above problems for optimal assignment have very large computational complexity. For this reason have developed heuristic algorithms which aim at the reduction of computational time with disadvantage on solution. The Best Fit Decreasing compute, in most times, a approach of optimal solution. The purpose of the study is twofold: (a) to split the dataset of problem with representative manner so that at every sub-problem to Best Fit Decreasing algorithm is applied and the cost to the results to be the smallest and (b) to be implemented program in Matlab that will running every sub-problem with parallel techniques with the aim of reducing computational time

KEYWORDS: Linear Programming, Optimization, Bin Packing Problem, Parallel Processing


[1] M. R. Garey, D. S. Johnson, Computers and Intractability; A Guide to the Theory of NPCompleteness, W. H. Freeman & Co., New York, NY, USA, 1990.

[2] R. E. Korf, A New Algorithm for Optimal Bin Packing, Eighteenth National Conference on Artificial Intelligence, Edmonton, Alberta, Canada, (2012), 731-736.

[3] A. N. Zehmakan, Bin Packing Problem: Two Approximation Algorithms, CoRR, (2015), abs/1508.01376

[4] D. S. Johnson, A. J. Demers, J. D. Ullman, M. R. Garey, R. L. Graham, Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms, SIAM J. Comput., 4 (1974), 299- 325.

[5] P. Luszczek, Parallel Programming in MATLAB, International Journal of High Performance Computing Applications, 23 (2009), no. 3, 277-283.

[6] C. Moler, Parallel MATLAB: Multiple processors and multiple cores, The MathWorks News & Notes, (2007).

[7] G. Sharma, J. Martin, MATLAB : A Language for Parallel Computing, International Journal of Parallel Programming, 37 (2009), no. 1, 3-36.

[8] D. N. Varsamis, C. Talagkozis, P. A. Mastorocostas, E. Outsios, N. P. Karampetakis, The performance of the MATLAB Parallel Computing Toolbox in specific problems, Federated Conference on Computer Science and Information Systems (FedCSIS), Wroclaw, Poland, (2012), 587- 593.

[9] D. N. Varsamis, P. A. Mastorocostas, A. K. Papakonstantinou, N. P. Karampetakis, A parallel searching algorithm for the insetting procedure in Matlab Parallel Toolbox, Advanced Information Science and Applications Volume I, 18th Int. Conf. on Circuits, Systems, Communications and Computers (CSCC 2014), July 17-21, 2014, Santorini Island, Greece, (2014), 145-150.

WSEAS Transactions on Computers, ISSN / E-ISSN: 1109-2750 / 2224-2872, Volume 17, 2018, Art. #9, pp. 79-85

Copyright © 2018 Author(s) retain the copyright of this article. This article is published under the terms of the Creative Commons Attribution License 4.0

Bulletin Board


The editorial board is accepting papers.

WSEAS Main Site