algorithm - Variation of Bin packing- with bin and object classes and mutual constraints -



algorithm - Variation of Bin packing- with bin and object classes and mutual constraints -

i'm working on problem variation of bin-packing, bit more general form constraints. problem definition follows-

we have objects of varying sizes, can grouped object classes. have bins of differing capacities, grouped bin classes (all bins within same class have same capacity). object classes have constraints on bins may placed into- example, object of class 'a' can placed in either of bin classes 'x' or 'y'. objective find minimum number of bins in each class, can yield optimal packing of given set of objects.

is there mathematical formulation of problem, , solution methods have come across? extension of bin-packing problem same methods can applied? understand np hard. unable find much how tackle problem, quite helpful if can point me in right direction.

finding exact solution np-hard. finding optimal solution easy.

since objective minimize number of bins each class this.

from input constraints generate map stores object classes each bin class can pack. e.g. constraint "object of class 'a' can placed in either of bin classes 'x' or 'y'. "

m[x] = {a}; m[y] = {a};

generate map processing through constraints. start bin class has minimum number of objects , start packing , mark objects packed[object_a] = true;

now repeat above step bin classes in map in decreasing order of count.

after left objects has no constraints , bin classes has 0 or more objects.

we can extend first fit algorithm solve part. sort bin classes based on object count in them in increasing order. run loop on left on objects set first fit bin class. in each iteration need reorder bin classes based on object count.

i hope helps.

algorithm optimization np bin-packing

Comments

Post a Comment

Popular posts from this blog

xslt - DocBook 5 to PDF transform failing with error: "fo:flow" is missing child elements. Required content model: marker* -

xslt - DocBook 5 to PDF transform failing with error: "fo:flow" is missing child elements. Required content model: marker* - i've inherited doc publishing process takes docbook , builds html , pdf output, using apache fop both. project had been started, never completed. lots of tweaking, i've able of doc sets build (20+), except handful, , fail severe code 1 of these 2 conditions: "fo:flow" missing kid elements. required content model: marker* "fo:block" not valid kid of "fo:root" the xml output comes out of docbook , docbook-fop checks out well-formed. the fop error in 1 book, "endecagloss", example, points end of string: <fo:flow flow-name="xsl-region-body" start-indent="4pc" end-indent="0pt"/> here’s log output in case: [java] severe: javax.xml.transform.transformerexception: file:/scratch/publishing/hudson/jobs/build-main-endeca-documentation/workspace/serverdoc/w...
Read more

mediawiki - How do I insert tables inside infoboxes on Wikia pages? -

mediawiki - How do I insert tables inside infoboxes on Wikia pages? - i want insert tables in infoboxes. example, have proteinbox i've developed using infobox template (http://health-and-medicine.wikia.com/wiki/template:proteinbox), , fasta field big fit comfortably in proteinbox. hence collapsible table within box. this tried: {{infobox | row 1 = {| class = "mw-collapsible mw-collapsed wikitable" |- | <!-- table content --> |} }} your problem is, putting nested table within template. pipe characters ( | ) in table syntax collides pipe usage in templates. the commonly used hack around create template called template:! , containing pipe character, , utilize when need set tables, parser functions or other stuff using pipe characters, within templates. table (with every | replaced {{!}} ): {{{!}} {{!}}- {{!}} a1 {{!}} b1 {{!}}- {{!}} a2 {{!}} b2 {{!}}} ...the equivalent of {| |- | a1 | b1 |- | a2 | b2 |} furthermore, hav...
Read more

Local Service User Logged into Windows -

Local Service User Logged into Windows - i created windows service tracks app server user connected through load balancer. it retrieves user logged windows on machine, cross references active directory (ad) business relationship homecoming first name, lastly name , e-mail (for notification through website created project) there 1 scheme on network users remote system, vista system, reason returning values "local service" logged machine, it's weird , security guys impossible "local service" business relationship logged windows. here how user logged windows managementscope ms = new managementscope("\\\\.\\root\\cimv2"); objectquery query = new objectquery("select * win32_computersystem"); managementobjectsearcher searcher = new managementobjectsearcher(ms, query); foreach (managementobject mo in searcher.get()) { _username = mo["username"].tostring(); } // remove domain part username string[] usernameparts = _...
Read more