Random Placement Problem (RPP)

Hana Rudová
hanka@fi.muni.cz
  and   Kamil Veømiøovský
xvermir@fi.muni.cz

Specification

The random placement problem (RPP) seeks to place a set of randomly generated rectangles (called objects) of different sizes into a larger rectangle (placement area) in such a way that no objects overlap and all object borders are parallel to the border of the placement area. In addition, a set of allowable placements is randomly generated for each object.

The ratio between the size of the placement area and the total area of all objects is called the filled area ratio. The higher the filled area ratio is, the more constrained (possibly over-constrained) the problem is. For problems with the filled area ratio greater than one (or any over-constrained problem instance with a smaller filled area ratio), we seek for a solution with the maximum placed objects.

Relation with Timetabling

We have proposed the RPP because it allows us to generate various instances of the problem similar to a trivial timetabling problem: each course must fit into a classroom of sufficient capacity.

The object corresponds to a course to be timetabled - the x-coordinate to its time, the y-coordinate to its classroom. For example, a course taking three time hours corresponds to an object with dimensions 3x1 (course should be taught in one classroom only). Each course can be placed only in a classroom of sufficient capacity - each object will have a randomly generated lower y-bound.


Back to RPP main page.