Solving the Bin-Packing Problem by Means of Tissue P System with 2-Division

Abstract

The ability of tissue P systems with 2-division for solving NP problems in polynomial time is well-known and many solutions can be found in the literature to several of such problems. Nonetheless, there are very few papers devoted to the Bin-packing problem. The reason may be the difficulties for dealing with different number of bins, capacity and number of objects by using exclusively division rules that produce two offsprings in each application. In this paper we present the design of a family of tissue P systems with 2 division which solves the Bin-packing problem in polynomial time by combining design techniques which can be useful for further research.