Call for Paper

CAE solicits original research papers for the May 2023 Edition. Last date of manuscript submission is April 30, 2023.

Read More

Bin Packing Algorithms with Applications to Passenger Bus Loading and Multiprocessor Scheduling Problems

SocButtons v1.5

Taiwo O. Ojeyinka. Published in Algorithms.

Bin Packing Algorithms with Applications to Passenger Bus Loading and Multiprocessor Scheduling Problems
Communications on Applied Electronics
Year of Publication: 2015
Publisher: Foundation of Computer Science (FCS), NY, USA
Series: Volume 2 Number 8
Authors: Taiwo O. Ojeyinka
10.5120/cae2015651851
Download full text

Taiwo O Ojeyinka. Article: Bin Packing Algorithms with Applications to Passenger Bus Loading and Multiprocessor Scheduling Problems. Communications on Applied Electronics 2(8):38-44, September 2015. Published by Foundation of Computer Science (FCS), NY, USA. BibTeX

@article{key:article,
	author = {Taiwo O. Ojeyinka},
	title = {Article: Bin Packing Algorithms with Applications to Passenger Bus Loading and Multiprocessor Scheduling Problems},
	journal = {Communications on Applied Electronics},
	year = {2015},
	volume = {2},
	number = {8},
	pages = {38-44},
	month = {September},
	note = {Published by Foundation of Computer Science (FCS), NY, USA}
}

Abstract

The problem of arranging items into bins in order to minimize the overall number of used bins was implemented and evaluated using the online and offline bin packing heuristics. The study implemented the fill function to evaluate the performance of both the online and offline variants of bin packing heuristics. The algorithms were applied to some commonly occurring NP-hard problems whose solutions require optimisation e.g. the passenger-bus scheduling and the multiprocessor job scheduling problems. The results of the evaluation show that the minimisation function varied w.r.t. the sizes of the items and also of the bins. Results further shows that a minimised resource allocation and makespan are feasible for the passenger-bus scheduling and the multiprocessor job allocation respectively.

References

  1. Albers, S., Charikar, M., & Mitzenmacher, M. 1998. Delayed information and action in on-line algorithms. In Foundations of Computer Science, November 1998. Proceedings. 39th Annual Symposium on (pp. 71-80). IEEE.
  2. Alvim, A. C. F., Ribeiro, C. C., Glover F. and Aloise, D. J. 2004. A Hybrid Improvement Heuristic for the One-Dimensional Bin Packing Problem, Journal of Heuristics, Vol. 10, No. 2, 205-229.
  3. American Mathematical Society 2010. Feature Column from the AMS http://paginas.fe.up.pt/~mac/ensino/docs/DS20102011/Bin_Packing.pdf.
  4. Ayachi, I., Kammarti, R., Ksouri, M., & Borne, P. 2013. A Genetic algorithm to solve the container storage space allocation problem. arXiv preprint arXiv:1303.1051.
  5. Bansal, N., Caprara, A., & Sviridenko, M. 2009. A new approximation method for set covering problems, with applications to multidimensional bin packing. SIAM Journal on Computing, 39(4), 1256-1278.
  6. Coffman E. G, Galambos G, Martello S. & Vigo D. 1998. Bin packing approximation algorithms: Combinatorial analysis, pp. 151–208 in Du D-Z & Pardalos PM (Eds), Handbook of combinatorial optimization, Kluwer Academic Publishers, Boston MA.
  7. Coffman E. G, Garey. M. R. & Johnson, D. S. 1978. An Application of Bin-Packing to Multiprocessor Scheduling.. SIAM J. Comput., 7, 1-17.
  8. Corcoran A. L, Wainwright R. L. 1995. Using LibGA to Develop Genetic Algorithms for Solving Combinatorial Optimization Problems. Published in The Application Handbook of Genetic Algorithms, Volume I, Lance Chambers, editor, pages 143-172, CRC Press, 1995.
  9. Fleszar, K., and Hindi K. S., 2002. New heuristics for one-dimensional bin packing, Computers and Operations Research, Volume 29, Issue 7, pp. 821-839.glewood. Cliffs, N.J.
  10. Francq P. 2012. Optimization Problems. January, 2012 http://www.otlet-institute.org/wikics/Optimization_Problems.html
  11. Garey M. R. and Johnson D. S. 1979. Computer and Intractability: A guide to the Theory of NP-Completeness by Publisher: W. H. Freeman 1979.
  12. Gupta, J. N. D., and J. C. Ho. 1999. A new heuristic algorithm for the one-dimensional bin-packing problem, Production Planning and Control, Volume 10, Issue 6, pp. 598-603.
  13. Janković M., 2013. Genetic Algorithm for Bin Packing Problem. http://www.codeproject.com/Articles/633133/g
  14. Silberschatz A., Gagne G., and Galvin P. B. 2008, "Operating System Concepts, Eighth Edition ". John Wiley & Sons. July 2008. ISBN: 9780470128725.
  15. Zapata, O. U. P., & Alvarez, P. M. 2005. EDF and RM multiprocessor scheduling algorithms: Survey and performance evaluation. Seccion de Computacion Av. IPN, 2508.

Keywords

Bin packing, resource allocation, heuristics, NP-hard, passenger-bus, multiprocessor