حداقل سازی حداکثر تاخیر در bin packing تک بعدی Maximum lateness minimization in one-dimensional bin packing
- نوع فایل : کتاب
- زبان : انگلیسی
- ناشر : Elsevier
- چاپ و سال / کشور: 2017
توضیحات
رشته های مرتبط مهندس کامپیوتر
گرایش های مرتبط رایانش ابری
مجله امگا – Omega
دانشگاه گروه علوم / مهندسی ‘اطلاعات و ریاضیات، یتالیا
نشریه نشریه الزویر
گرایش های مرتبط رایانش ابری
مجله امگا – Omega
دانشگاه گروه علوم / مهندسی ‘اطلاعات و ریاضیات، یتالیا
نشریه نشریه الزویر
Description
1. Introduction 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–7,14,17, 21, 31]; 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].
