کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6895245 1445939 2018 34 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Heuristics for the stochastic dynamic task-resource allocation problem with retry opportunities
ترجمه فارسی عنوان
اکتشافات برای مسئله تخصیص منابع وظیفه دینامیکی تصادفی با فرصتهای مجدد
کلمات کلیدی
تخصیص وظیفه منابع، برنامه ریزی پویا تقریبی اهریمنی، فرصت های دوباره امتحان کنید
ترجمه چکیده
این مقاله با یک مسئله تخصیص منابع کار چند مرحلهای تصادفی است. یک تیم از عوامل با مجموعه ای از منابع باید در یک مأموریت چند دوره ای مستقر شود و هدف آن موفقیت کامل وظایف بسیاری باشد. احتمال موفقیت یک نماینده اختصاص یافته به یک کار بستگی به منابع موجود برای عامل دارد. وظایف ناموفق را می توان دوباره در دوره های بعدی مورد آزمایش قرار داد. در حالی که این مشکل می تواند در اصل توسط برنامه نویسی دینامیک حل شود، در عمل این امر به جز محاسبات کمی کوچک، قابل قبول است. برای مقابله با مشکلات بزرگتر، ما یک اکتشاف ساختمانی را پیشنهاد می دهیم که منابع و وظایف را برای وظایف به ترتیب بر اساس ابزار حاشیه ای تخمین زده می شود. بر اساس این اکتشافی، ما علاوه بر این، روش های مختلف برنامه ریزی پویا تقریبی و الگوریتم تکاملی را پیشنهاد می کنیم. همه رویکردهای پیشنهادی تجربی در مقایسه با تعدادی از نمونه های مشکل به طور تصادفی تولید شده مقایسه شده است. ما نشان می دهیم که اکتشافی ساخت و ساز بسیار سریع است و نتایج خوبی دارد. برای نتایج حتی بهتر، در هزینه های زمان محاسباتی طولانی، برنامه ریزی پویا تقریبی به نظر می رسد یک جایگزین مناسب است.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش مقاله
اکتشافات برای مسئله تخصیص منابع وظیفه دینامیکی تصادفی با فرصتهای مجدد
چکیده انگلیسی
This paper deals with a stochastic multi-period task-resource allocation problem. A team of agents with a set of resources is to be deployed on a multi-period mission with the goal to successfully complete as many tasks as possible. The success probability of an agent assigned to a task depends on the resources available to the agent. Unsuccessful tasks can be tried again at later periods. While the problem can in principle be solved by dynamic programming, in practice this is computationally prohibitive except for tiny problem sizes. To be able to tackle also larger problems, we propose a construction heuristic that assigns agents and resources to tasks sequentially, based on the estimated marginal utility. Based on this heuristic, we furthermore propose various Approximate Dynamic Programming approaches and an Evolutionary Algorithm. All suggested approaches are empirically compared on a number of randomly generated problem instances. We show that the construction heuristic is very fast and provides good results. For even better results, at the expense of longer computational time, Approximate Dynamic Programming seems a suitable alternative.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 266, Issue 1, 1 April 2018, Pages 291-303
نویسندگان
, , ,