کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
459512 696257 2015 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Cost-aware demand scheduling for delay tolerant applications
ترجمه فارسی عنوان
برنامه ریزی تقاضای هزینه برای آگاهی از برنامه های کاربردی تحمل پذیر
کلمات کلیدی
برنامه ریزی تقاضا، کاهش منابع قله، کمینه شدن زمان تکمیل
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر شبکه های کامپیوتری و ارتباطات
چکیده انگلیسی

In this paper, we study the problem of demand scheduling for delay tolerant applications. With regard to the time-varying resource cost per unit size of the demand, we study two optimization problems: (1) how to minimize the peak resource usage, while making sure that each demand is served before the deadline; (2) how to minimize the longest completion time of all the demands under a given maximum allowable resource constraint. For the first problem, we prove that it is NP-hard, under the general setting that the demands are of different sizes and require several continuous time slots to complete. We then provide an integer linear programming solution, and propose an efficient heuristic algorithm. For a special case of the same size demand and single serving time slot, the proposed algorithm is proved to be optimal. We further study a special case that all the demands have the same deadline, and prove that the proposed algorithm can achieve three times the optimal solution if the number of serving time slots required for each demand is at most two. For the second problem, we also prove it to be NP-hard and formulate it into an integer linear programming. An efficient polynomial-time algorithm is then proposed, whose completion time is proved to be at most two times the optimal minimum completion time under a specific setting. Finally, simulation results demonstrate the superiorities of the proposed schemes.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Network and Computer Applications - Volume 53, July 2015, Pages 173–182
نویسندگان
, , , , ,