Open Access Open Access  Restricted Access Subscription or Fee Access

Optimizing Deployment- Scheme System Using the Concept of Bin Packing Algorithm

Arogundade O. Tale, Ikotun A. Motunrayo, Akinwale A. Taofik, Ogunnowo Olubunmi

Abstract


Deployment scheme is a variant of bin packing problem which is known to be an NP-complete problem. The deployment scheme problem asks for the minimum number k of identical bins (states) of capacity C needed to store a finite collection of weights (corps members) w1, w2, w3, ... , wn so that no bin has weights stored in it whose sum exceeds the bin's capacity. Traditionally, the capacity C is chosen to be 1 and the weights are real numbers which lie between 0 and 1, but here, for convenience of exposition, the consideration will be a situation where C is a positive integer and the weights are positive integers which are less than the capacity. The bin packing concepts was modified by adding some other soft and hard constraints. The algorithm was tested with real life data of graduate from Nigerian tertiary institutions who are to be deployed for the National Youth Service Corps (NYSC) Scheme and interesting results were obtained.

Keywords


Bin Packing Algorithm, Hard and Soft Constraints, NP Problem, Optimization.

Full Text:

PDF

References


G. Ausiello, M. Lucertini and P. Serafine, Algorithm Design for Computer System Design : Springer-Verlag, 1984.

E. G. Coffman Jr., M. R Garey and D. S. Johnson, Approximation Algorithms for Bin-Packing—An Updated Survey: PWS Publishing, Boston (1997), pp. 46-97.

D.S. Johnson, Near Optimal Bin-Packing Algorithms, :Massachusetts Institute of Technology, Cambridge, 1973,

D. S. Johnson et al, ―Worst-case Performance Bounds for Simple one Dimensional Packing Algorithms‖, SIAM J. COMPUT, vol. 3,no. 4, pp. 299-325, Dec.1974

S. Fadal, ―Why NYSC should be abolished now‖ in Nigeria Matters, Feb. 2004.

D. S. Johnson, A Theoretician‘s Guide to the Experimental Analysis of Algorithms: AT&T Laboratory, Nov. 2001.

Leung, Phillips et al 2003, Algorithmic Support for Commodity-based Parallel Computing: Sandia National Laboratories, SAND2003-3702, Oct. 2003.

M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979

Miyazawa, Wakabayashi, ―Parametric On-Line Algorithms for Packing Rectangles and Boxes‖, European Journal of Operational Research, Vol. 150, No. 2, pp. 281-292, Oct. 2003.

O. Soseleipirim, Appraisal of the National Youth Service Corps Scheme

S. Owomero, National Youth Service Scheme Incorporating UBE into National Unity

E. W. Weisstein, Bin-Packing Problem: Math World, Wolfram Web Resource.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.