مقاله سال ۲۰۱۷

 مجله امگا – Omega

In BIN PACKING, a set J of n items of distinct sizes must be assigned to a minimum number of identical bins, so that the size of the items assigned to any bin never exceed its capacity. In the (orthogonal) s-dimensional problem, items and bins are closed intervals of IRs , and the former must be placed into the latter with no overlap. Items can or cannot be rotated before placement: in the latter case, the edge lengths of each interval can be normalized, and bins become unit s-cubes.

One can interpret the s-dimensional BIN PACKING as a scheduling problem with n jobs of unit time length: when scheduled, job j consumes some fraction of a discretized resource, the bin, available in one unit per time unit. In general, applications include all those cases (e.g., ads scheduling in sponsored internet search [1]) in which the resource used has both a geometric and a time dimension. Here are other popular applications: in s-dimensional cutting, jobs are parts to be produced, and the resource is a stock of standard size from which smaller items must be cut [2, 5–۷,۱۴,۱۷, ۲۱, ۳۱]; in telecommunication channel scheduling, jobs are packets of known length, and the resource is a frame able to host packets up to a given total length [4,11].