ترجمه مقاله محل تسهیلات آنلاین همراه با حرکت تسهیلات

توضیحات

عنوان فارسی: محل تسهیلات آنلاین همراه با حرکت تسهیلات

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

Online facility location with facility movements

چکیده

در مسئله محل تسهیلات آنلاین، نقاط تقاضا به طور همزمان وارد می­شوند و هدف تصمیم­گیری در مورد مکان و زمان بازگشایی یک تسهیل است. در این مقاله یک نسخه جدید از مسئله محل تسهیلات آنلاین را در نظر گرفته­ایم که الگوریتم اجازه حرکت تسهیلات باز در فضای متریک را فراهم می­کند. ما مورد یکنواخت را در نظر گرفتیم که هر مرکز هزینه ثابت یکسانی دارد.ما یک الگوریتم را ارائه دادیم که برای موارد عمومی 2- رقابتی است و ما ثابت کردیم که اگر فضای متریک خط باشد به صورت 2/3 – رقابتی می­باشد. همچنین ثابت می­کنیم که هیچ الگوریتمی با نسبت رقابتی کمتر از وجود ندارد. همچنین یک تحلیل تجربی را ارائه می­دهیم که نشان می­دهد الگوریتم نتایج خیلی خوبی در موارد متوسط ارائه می­دهد.

واژه­های کلیدی:محل تسهیلات، الگوریتم­های آنلاین، تحلیل رقابتی.

مقدمه

در مسئله محل تسهیلات یک فضای متریک همراه با مجموعه­ای از نقاط تقاضا(المان­ها و اجزای فضا) داده شده است. هدف پیدا کردن مجموعه­ای از مکان­های تسهیلات در فضای متریک است که مجموع هزینه تسهیلات و هزینه انتقال را به حداقل می­رسانند. نسخه آنلاین آن یک مسئله شناخته شده در بهینه­سازی ترکیبی است. در برخی از کاربردها (ساختن یک کامپیوتر یا شبکه سنسور، برخی از مسائل خوشه­ای) مجموعه­ای از تقاضاهای شناخته شده نیستند و نقاط تقاضا به یکباره و به طور همزمان وارد می­شوند و پس از ورود یک تقاضا، الگوریتم باید در مورد باز کردن تسهیلات بدون داشتن اطلاعات کافی پیرامون تقاضاهای بعدی تصمیم­گیری نماید. این نسخه آنلاین از محل تسهیلات در میرسون(2001) تعریف شده است. در میرسون اجازه حرکت تسهیلاتی که توسط الگوریتم باز شده­اند، داده نشده است اما در اینجا ما یک نسخه­ای را در نظر می­گیریم که می­تواند در کاربردهای مذکور مورد استفاده قرار گیرد. در این مدل، الگوریتم اجازه حرکت تسهیلات و مراکز به موقعیت­های جدید را پس از ورود نقاط تقاضا دارد. در فوتاکیس(2006) مدل مشابهی با محدودیت حرکت تنها یک مرکز مورد بررسی قرار گرفته است. در فوتاکیس(2006) یک الگوریتم بدون حافظه با نسبت رقابتی 66/13 برای هزینه یکنواخت تسهیلات ارائه شده است. هزینه تسهیلات غیریکنواخت نیز مورد بررسی قرار گرفته است و در این مورد عمومی یک الگوریتم بدون حافظه 6/48 برای آن ارائه شده است.

      به طور کلی، کیفیت یک الگوریتم آنلاین با استفاده از تحلیل رقابتی ارزیابی می­گردد. یک الگوریتم آنلاین برای مسئله بهینه­سازی c-رقابتی است اگر هزینه الگوریتم هیچ­گاه بیشتر از c برابر هزینه بهینه نباشد(جزئیات بیشتر در مورد تحلیل رقابتی را می­توانید در بورودین و ال-یانیف(1998)، فیات و وگینگر(1998) و امره(2007) بیایبد).

نتایج ما:

در این مقاله مسئله محل تسهیلات آنلاین همراه با حرکت آن­ها را در نظر گرفته­ایم. این بدین معنی است که به الگوریتم اجازه حرکت دادن تسهیلات به موقعیت­های دیگر پس از ورود نقاط تقاضا و بدون هزینه اضافی داده شده است. ما الگوریتمی به نان OFW برای حل ارائه داده­ایم و ثابت می­کنیم که در فضای متریک عمومی نسبت رقابتی 2 و برای فضای متریک خط نسبت رقابتی 2/3 است. ما همچنین گسترش زمان چندجمله­ای OFW با نام POFW را بررسی کرده و محدوده­ای برای نسبت رقابتی آن ارائه دادیم. علاوه بر این، ما ثابت کردیم که هیچ الگوریتم آنلاینی نمی­تواند نسبت رقابتی کمتر از  داشته باشد. این مسئله برای وقتی که فضای متریک خط است نیز صدق می­کند. همچنین نتایج تحلیل­های تجربی که به منظور بررسی رفتار OFW در موارد متوسط صورت گرفته­اند را ارائه می­دهیم.

کارهای مرتبط:

مسئله محل تسهیلات آنلاین بدون حرکت آن­ها در میرسون(2001) تعریف شده است. در آن مقاله یک الگوریتم تصادفی  -رقابتی برای هزینه تسهیلات یکنواخت پیشنهاد شده است و همچنین نشان داده شده است که الگوریتم در مقابل دنباله­های ورودی یکنواخت رقابتی ثابت است(این بیانیه نیز برای هزینه تسهیلات غیریکنواخت ارزیابی شده است). علاوه بر این، اثبات شده است که هیچ الگوریتم آنلاین رقابت-ثابتی برای حل این مسئله وجود ندارد. در فوتاکیس(2008) مسئله بیشتر بررسی شده است و یک الگوریتم   قطعی -رقابتی برای هزینه تسهیلات یکنواخت و غیریکنواخت ارائه شده است. همچنین ثابت شده است که هیچ الگوریتم تصادفی یا قطعی با نسبت رقابتی کمتر از  وجود ندارد. آناگنوستوپولوس و همکارانش(2004) یک الگوریتم  -رقابتی ساده ­تر با نام تقسیم برای هزینه تسهیلات یکنواخت و فضاهای اقلیدسی ارائه دادند. مقاله شامل تحلیل­های احتمالی و تجربی اولیه برای مسئله می­باشد. نشان داده شده است که تقسیم، یک الگوریتم Q-رقابتی با احتمال بالا برای ورودی با هر مرتبه است وقتی که مشتریان به طور یکنواخت توزیع شده باشند و یا وقتی که ئآن­ها از یک توزیع رضایت­بخش پیروی می­کنند. یک الگوریتم  -رقابتی برای هزینه تسهیل غیریکنواخت و فضاهای متریک اختیاری در فوتاکیس(2006) ارائه شده است.

      یک مقاله دیگر وجود دارد که چنین مسائل آنلاینی را بررسی کرده است که در آن فضاهای مربوط به تسهیلات باز به صورت غیرقابل جبران مقید نشده­اند. در محل تسهیلات افزایشی نقاط تقاضا به طور همزمان وارد می­شوند و باید به تسهیلات موجود و یا جدید اختصاص داده شوند. برای هر نقطه در زمان، الگوریتم می­تواند یک مرکز را با مرکز دیگر از طریق بستن اولی و تخصیص تمامی تقاضاهای موجود به مرکز دوم، ترکیب کند. در فوتاکیس(2006) یک الگوریتم رقابتی ثابت برای مسئله محل تسهیل افزایشی داده شده است.

توجه:

• برای دانلود فایل word کامل ترجمه لطفا اقدام به خرید فرمایید.
• پس از خرید بلافاصله لینک دانلود فایل برای شما ایمیل خواهد شد.