دانلود ترجمه مقاله مسئله بسته بندی با جعبه (Bin Packing) توسط صف ها

قیمت خرید این محصول

۴۱,۰۰۰ تومان

دانلود رایگان نمونه دانلود مقاله انگلیسی

عنوان فارسی

مسئله بسته بندی با جعبه (Bin Packing) توسط صف ها

عنوان انگلیسی

Bin Packing With Queues

صفحات مقاله فارسی

29

صفحات مقاله انگلیسی

18

سال انتشار

2008

نشریه

(MIT (sloanreview

فرمت مقاله انگلیسی

PDF

فرمت ترجمه مقاله

ورد تایپ شده

رفرنس

دارد

کد محصول

4037

وضعیت فرمولها و محاسبات در فایل ترجمه

به صورت عکس، درج نشده است

رشته های مرتبط با این مقاله

مهندسی کامپیوتر

گرایش های مرتبط با این مقاله

مهندسی الگوریتم ها و محاسبات

مجله

مجله احتمال کاربردی

دانشگاه

آزمایشگاه سیستم های تصمیم و اطلاعات، MIT، کمبریج، ایالت متحده آمریکا

کلمات کلیدی

بسته بندی، صف بندی، ترافیک سنگین

فهرست مطالب

چکیده
۱ مقدمه
۱ ۱ مدل
۲ ۱ مقایسه با سایر مسائل ترکیبی پویا و تصادفی
۳ ۱ نتایج
۴ ۱ سازمان
۲ دو سیاست ناکافی
۱ ۲ دسته بندی
۲ ۲ سیاست های جفت محدود
۳ ۲ حد پائین برای سیاست های جفت محدود
۴ ۲ حد بالا
۳ سیاست نزدیک به حد بهینه
۱ ۳ سیاست
۲ ۳ پویایی صف
۳ ۳ اختلافات و ارتباط آنها با اندازه های صف
۴ ۳ اثبات حد بالا
۵ ۳ اثبات لم ۱ ۳
۶ ۳ بحث و توسعه
۴ حد پائین
۵ نتیجه گیری

نمونه چکیده متن اصلی انگلیسی

Abstract

We study the best achievable performance (in terms of the average queue size and delay) in a stochastic and dynamic version of the bin-packing problem. Items arrive to a queue according to a Poisson process with rate 2ρ, where ρ ∈ (0, 1). The item sizes are independent and identically distributed (i.i.d.) with a uniform distribution in [0, 1]. At each time unit, a single unit-size bin is available and can receive any of the queued items, as long as their total size does not exceed 1. Coffman and Stolyar (1999) and Gamarnik (2004) have established that there exist packing policies under which the average queue size is finite for every ρ ∈ (0, 1). In this paper we study the precise scaling of the average queue size, as a function of ρ, with emphasis on the critical regime where ρ approaches 1. Standard results on the probabilistic (but static) bin-packing problem can be readily applied to produce policies under which the queue size scales as O(h2), where h = 1 / (1 - ρ), which raises the question of whether this is the best possible. We establish that the average queue size scales as Ω(hlogh), under any policy. Furthermore, we provide an easily implementable policy, which packs at most two items per bin. Under that policy, the average queue size scales as O(hlog3/2h), which is nearly optimal. On the other hand, if we impose the additional requirement that any two items packed together must have near-complementary sizes (in a sense to be made precise), we show that the average queue size must scale as Θ(h2).

نمونه چکیده ترجمه متن فارسی

چکیده
در این مقاله بهترین عملکرد دست یافتنی (از لحاظ متوسط اندازه صف و تاخیر) در ورژن دینامیکی (پویا) و تصادفی مسئله بسته بندی را مطالعه می کنیم. آیتم ها برطبق فرایند پویسن با سرعت وارد صف می شود که . اندازه آیتم ها مستقل و دارای توزیع مشابهی (i.i.d) با توزیع یکنواخت در بازه [1و0] می باشد. در هر واحد زمانی، یک سطل با اندازه واحد موجود بوده و می تواند آیتم های صف بندی شده را دریافت نماید، این روند تا زمانی ادامه می یابد که اندازه کل آنها بیشتر از یک نشود. Coffman و Stolyar (1999) و Gamarnik (2004) مقرر کرده اند که سیاست های بسته بندی وجود دارد که تحت آنها متوسط اندازه صف برای هر محدود یا متناهی می باشد. در این مقاله ، مقیاس بندی دقیق متوسط اندازه صف را به شکل تابع مطالعه کرده و در این راستا بر رژیم بحرانی تاکید می کنیم که به 1 نزدیک می شود. ازنتایج استاندارد پیرامون مسئله بسته بندی احتمالی ( اما ایستایی) به راحتی می توان برای تولید سیاست هایی استفاده نمود که تحت آنها اندازه صف به شکل مقیاس بندی می شود، در اینجا که این سئوال مطرح می شود که آیا ممکن می باشد یا خیر. دراینجا نشان می دهیم که متوسط اندازه صف در هر سیاستی به شکل مقیاس بندی می شود. به علاوه، یک سیاست به راحتی قابل اجرا ارائه می دهیم که در بهترین حالت ممکن دو آیتم را در هر سطل بسته بندی می کند. تحت آن سیاست، متوسط اندازه صف به شکل مقیاس بندی می شود که تقریباً بهینه است. از طرف دیگر، در صورت تحمیل شرط دیگری مبنی براینکه دو آیتمی که باهم بسته بندی شده اند، بایستی دارای اندازه های نزدیک به مکمل باشند ( برای دقیق ظاهر شدن)، آنگاه نشان می دهیم که متوسط اندازه صف بایستی به شکل مقیاس بندی شود.

برچسب‌ها: دانلود رایگان مقالات انگلیسی مهندسی کامپیوتر