دانلود مقاله ISI انگلیسی شماره 78949
ترجمه فارسی عنوان مقاله

معرفی یک الگوریتم سریع تر برای مساله تخصیص منابع با توابع هزینه محدب

عنوان انگلیسی
A faster algorithm for the resource allocation problem with convex cost functions
کد مقاله سال انتشار تعداد صفحات مقاله انگلیسی
78949 2015 10 صفحه PDF
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Journal of Discrete Algorithms, Volume 34, September 2015, Pages 137–146

فهرست مطالب ترجمه فارسی
چکیده

کلمات کلیدی

1.مقدمه

2 . الگوریتم ساده

3 . الگوریتم دو فازی

شکل 1: تصویر الگوریتم دو فازی

3.1 یک مثال ساده

4 . الگوریتم چندفازی

5 . مطالعات محاسباتی

5.1 مساله بازپرسازی مشترک

جدول 1: عملکرد الگوریتم چندفازی برای مساله بازپرسازی مشترک. زمان اجرا(T)، کاهش زمان(T_reduct) و مقدار هدف بهینه(OPT).

6 . نتیجه گیری پایانی
ترجمه کلمات کلیدی
الگوریتم های چندجمله ای؛ تجزیه و تحلیل پیچیدگی؛ ساختار داده ها؛ بهینه سازی ترکیبی غیر خطی
کلمات کلیدی انگلیسی
Polynomial-time algorithms; Complexity analysis; Data structure; Nonlinear combinatorial optimization
ترجمه چکیده
در اینجا، به بازنگری مساله تخصیص منابع کلاسیک با توابع هدف محدب عمومی و با در نظر گرفتن قید کوله پشتی عدد صحیح خواهیم پرداخت. این دسته از مسائل، پایه و اساس بهینه سازی گسسته را تشکیل می دهند و کاربردهای وسیع و گسترده ای دارند. در مقاله پیش رو، الگوریتم تقسیم-و-غلبه زمان چندجمله ای جدیدی به نام الگوریتم چندفازی را معرفی می نماییم و ثابت می کنیم که پیچیدگی محاسباتی این الگوریتم برابر با O(n log n lob N) می باشد، و عملکرد آن از شناخته شده ترین الگوریتم زمان چندجمله ای که دارای پیچیدگی محاسباتی O(n(log N)2) است بهتر خواهد بود.
ترجمه مقدمه
مساله تخصیص منابع کلاسیک را در نظر بگیرید که می توان آن را بصورت مساله برنامه ریزی خطی زیر نشان داد: در اینجا، معرف مجموعه اعداد صحیح غیر منفی است. فرض می کنیم که هر fi، یک تابع محدب با دامنه تعریف [0,N] می باشد و N عدد صحیح مثبت را نشان می دهد. مساله فوق الذکر، در زمانی که N خیلی خیلی بزرگتر از n است، یعنی تعداد واحدهای منبع خیلی بیشتر از تعداد بازیگران می باشد، اهمیت ویژه ای پیدا می کند. توصیف فیزیکی فشرده مساله عبارت است از تخصیص یک استخر همگن ثابت از N واحد منبع، به شیوه ای بهینه، به n بازیگر مجزا، به گونه ای که هزینه تخصیص کل به حداقل مقدار برسد. معمولا این مساله، در دسته مسائل "توزیع تلاش ها" قرار دارد. شاید بتوان این مساله را ساده ترین مساله بهینه سازی ترکیبی غیر خطی قلمداد نمود که مقالات زیادی در حوزه علوم رایانه و تحقیق در عملیات، به آن پرداخته اند. گراس (رفرنس 10)، اولین کسی بود که یک الگوریتم حریصانه ساده با پیچیدگی محاسباتی O(N g n) را جهت حل دقیق این مساله توسعه داد. پس از وی، سایر محققین از قبیل فاکس و شیه (رفرنس 20)، مجددا به همین نوع الگوریتم حریصانه رسیدند. در ادامه، کاتو و همکارانش(رفرنس 14)، الگوریتم مبتنی بر روش های ضریب لاگرانژ را پیشنهاد کردند که به زمان O(n2(log N)2) نیاز داشت. در حال حاضر، شناخته شده ترین الگوریتم زمان چندجمله ای برای این مساله، در O(n(log N)2) اجرا می شود که حاصل کار بدوی گالیل و مگیدو (رفرنس 8) است. تعداد زیادی از محققین نیز روی برخی انواع این مساله پایه متمرکز شدند(مثل دریفوس و لاو در رفرنس 4، واینستین و یو در رفرنس 23، دانستان در رفرنس 5). کار تئوری مهمی که در اینجا انجام داده ایم، پیشنهاد یک الگوریتم زمان چندجمله ای جدید، به نام الگوریتم چندفازی است که در O(n log n log N) اجرا می شود که نشان دهنده بهبود قابل توجه پیچیدگی محاسباتی نسبت به کارهای موجود قبلی می باشد. ایده مهم و کلیدی الگوریتم چندفازی پیشنهادی، یافتن پارتیشن بندی بهینه هزینه های نهایی در بین چندین گروه در هر فاز است، به گونه ای که بتوان به کیپ ترین کران پیچیدگی رسید. به نظر می رسد که تعداد بهینه پارتیشن ها در هر فاز، برابر با می باشد، که e تقریبا مساوی با 2.71828، مبنای الگوریتم طبیعی را نشان می دهد و تابع سقف ، معرف کوچکترین عدد صحیح بزرگترمساوی x است. الگوریتم ما از نظر مفهومی خیلی ساده می باشد و به راحتی می توان آن را در تعداد زیادی از کاربردها مورد استفاده قرار داد. مساله بهینه سازی پیشنهادی، کاربردهای عملی مختلفی دارد. در واقع، انگیزه اولیه نوشتن این مقاله را دسته مهمی از مسائل مدیریت موجودی و زنجیره تامین به نام مساله بازپرسازی مشترک(JRP) (به مقاله مروری بسیار عالی خوجا و گویال در رفرنس 15 مراجعه فرمایید) تشکیل می داد. در اینجا، مدیر انبار می خواهد مقدار بازپرسازی کل را مشخص کند و سپس این واحدهای سفارش شده را به چندین خرده فروش غیر مشابه تخصیص بدهد. مساله مطالعه شده در این مقاله، زیرروال مهمی از مساله توزیع و تخصیص بهینه است، با این فرض که مقدار بازپرسازی کل در هر چرخه بازپرسازی مشخص باشد. به بیان کوتاه، مدیر انبار بایستی نحوه تخصیص مقدار ثابتی از کالا در بین چندین خرده فروش را تعیین کند، به گونه ای که هزینه های نگهداری و پس افت به حداقل برسند(جهت کسب اطلاعات دقیق، به مدل بخش 5 مراجعه فرمایید). علاوه بر مثال فوق الذکر، مسائل تخصیص منابع، در حوزه های کاربردی زیاد دیگری نیز مورد استفاده قرار می گیرند(به مقالات مروری هوچ بام در رفرنس 11 و پاتریکسون در رفرنس 19 مراجعه فرمایید). گالینسکو و همکارانش(رفرنس 12)، کیفیت نتایج بررسی شان را با در نظر گرفتن برنامه ریزی بهینه منابع بهبود بخشیدند. وینوت (رفرنس های 21 و 22)، رویّه هایی را برای انتخاب مقادیر یک کالای منفرد جهت تولید در تعداد مشخصی از دوره های زمانی پیشنهاد نمود، به گونه ای که هزینه های تولید و جابجایی موجودی در طی این دوره ها به حداقل برسند. همچنین، جانسون (رفرنس 12) و کاروش (رفرنس 13) نیز روش هایی را جهت تعیین برنامه تولید بهینه نسبت به زمان یک کالای اساسی مشخص اختراع نمودند، به گونه ای که هزینه های کل به حداقل برسند. زیپکین (رفرنس 24)، الگوریتم های مختلفی را جهت یافتن تخصیص بهینه مسائل انتخاب پرتفوی پیشنهاد کرد. لی(Lee) و پایرسکالا (رفرنس 16)، یک برنامه غربالگری گروهی را جهت محاسبه انتخاب آزمون بهینه و غربالگری دوره ها در بین یک بودجه تست ثابت ترتیب دادند. این مدل بهینه سازی، در مساله تخصیص بهینه در نمونه گیری طبقه ای (به کار نیمن در رفرنس 17 رجوع کنید) و مساله تخصیص بهینه منابع تست نرم افزار(به کار اوترا و یامادا در رفرنس 18 مراجعه فرمایید) نیز مورد استفاده قرار گرفت. ادامه مقاله دارای چیدمانی به شرح زیر است. بخش 2، به مرور الگوریتم ساده دست می زند و کران پیچیدگی اش را نشان می دهد. در بخش 3، با ارائه یک لِم کلیدی، به معرفی و تحلیل یک الگوریتم دو مرحله ای خواهیم پرداخت که پایه و اساس الگوریتم چندفازی ما را تشکیل می دهد. در بخش 4، الگوریتم چندفازی را معرفی می کنیم و کران پیچیدگی محاسباتی آن را به دست می آوریم. بخش 5، به مطالعه عددی الگوریتم پیشنهادی اختصاص دارد. سرانجام در بخش 6، به جمع بندی مقاله و ارائه رهنمودهایی در مورد جهتگیری کارهای آتی خواهیم پرداخت. در سرتاسر این مقاله، مکررا از نمادهای و استفاده خواهیم کرد. در اینجا، بزرگترین مقدار صحیح کوچکترمساوی x را نشان می دهد و معرف کوچکترین مقدار صحیح بزرگترمساوی x است. علاوه بر این، x+=max{x,0}.
پیش نمایش مقاله
پیش نمایش مقاله  معرفی یک الگوریتم سریع تر برای مساله تخصیص منابع با توابع هزینه محدب

چکیده انگلیسی

We revisit the classical resource allocation problem with general convex objective functions, subject to an integer knapsack constraint. This class of problems is fundamental in discrete optimization and arises in a wide variety of applications. In this paper, we propose a novel polynomial-time divide-and-conquer algorithm (called the multi-phase algorithm) and prove that it has a computational complexity of O(nlog⁡nlog⁡N)O(nlog⁡nlog⁡N), which outperforms the best known polynomial-time algorithm with O(n(log⁡N)2)O(n(log⁡N)2).