hoch@ipsi.UUCP (Rainer Hoch) (02/12/91)
I am interested in the following 2-dimensional bin packing prob-
lem:
The problem requires to pack n rectangular items into a minimal
number of rectangular unit capacity bins. I am interested in the
case when the length and the width of the items are not too
weird. In fact I can assume that the ratio of the length (resp.
width) of
the unit and the length (resp. width) of an item is
equal to 1,2,3,4 or 5 (i.e. it is integral).
A possible application would be the problem of how to place n ar-
ticles on a minimal number of pages in a newspaper.
Any hints, solutions or pointers to algorithms in the literature
are welcome.
Thanks Volker Turau
Adress: e-mail hoch@darmstadt.gmd.dbp.de or
turau@darmstadt.gmd.dbp.de
ean-address: s=hoch;ou=darmstadt;p=gmd;a=dbp;c=de or
s=turau;ou=darmstadt;p=gmd;a=dbp;c=dexanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) (02/14/91)
hoch@ipsi.UUCP (Rainer Hoch) writes: > I am interested in the following 2-dimensional bin packing problem: > The problem requires to pack n rectangular items into a minimal number > of rectangular unit capacity bins. I am interested in the case when > the length and the width of the items are not too weird. In fact I can > assume that the ratio of the length (resp. width) of the unit and the > length (resp. width) of an item is equal to 1,2,3,4 or 5 (i.e. it is > integral). > A possible application would be the problem of how to place n ar- > ticles on a minimal number of pages in a newspaper. > Any hints, solutions or pointers to algorithms in the literature are > welcome. > Thanks Volker Turau > Address: e-mail hoch@darmstadt.gmd.dbp.de or > turau@darmstadt.gmd.dbp.de ean-address: > s=hoch;ou=darmstadt;p=gmd;a=dbp;c=de or > s=turau;ou=darmstadt;p=gmd;a=dbp;c=de Considering where I encountered this problem, what a strange place (comp.text.sgml) to find it again! A very similar problem is studied under the names "floor space control", "shop floor control", "floor space scheduling", and "platten scheduling"; in each case, what is being scheduled is rectangular work areas in which major mechanical equipment is constructed. The problem in its full blown nature is very complex. Plattens, for example, are the outdoor areas on which major component pieces of ships are welded up. In this case, you are actually working in four dimensions, as you try to schedule not only the flat space, but also clearances at particular points in time to lift the finished pieces out over other, under-construction pieces with a limited vertical clearance bridge crane. "Floor space" is more usually such items as massive trucks and other earth moving equipment being constructed in parts within a shelter; the scheduling concerns are similar to those for plattens (my own research interest). At any rate, eight years back, there were commercial heuristic schedulers for such uses. Consult journals and trade publications for the earthmoving, shipbuilding, and oil exploration industries for ads or articles under the above topics. A generalization of your problem which may prove useful also is "nesting", the science of cutting the most parts out of the least material. In the two dimensional case, this is interesting in the metal fabrication and garment cloth layout tasks. Again, all the work I know is in the area of heuristics; the problem is considered too difficult for a closed solution. I hope these rather general hints will provide a direction to your search. Kent, the man from xanth. <xanthian@Zorch.SF-Bay.ORG> <xanthian@well.sf.ca.us>