检索结果-内蒙古大学图书馆

semi-online algorithms for Computational Task Offloading with Communication Delay

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2017年第4期28卷 1189-1201页

作者： Champati, Jaya Prakash Liang, Ben Univ Toronto Dept Elect & Comp Engn Toronto ON M5S 3G4 Canada

We study the scheduling of computational tasks on one local processor and one remote processor with communication delay. This problem has important application in cloud computing. Although the communication time to transmit a task can be inferred from the known data size of the task and the transmission bandwidth, the processing time of the task is generally unknown until it is processed to completion. Given a set of independent tasks with unknown processing times, our objective is to minimize makespan. We study the problem under two scenarios: 1) the communication times of the tasks to the remote processor are smaller than their corresponding processing times on the remote processor, and 2) the communication times of the tasks to the remote processor are larger than their corresponding processing times on the remote processor. For the first scenario we propose the semi-online Partitioning and Communication (SPaC) algorithm, and for the second scenario we propose the SPaC-Restart (SPaC-R) algorithm. Even though the offline version of this problem, with a priori known processing times, is NP-hard, we show that the proposed semi-online algorithms achieve O(1) competitive ratios for their intended scenarios. We also provide competitive ratios for both algorithms for more general communication times. We use simulation to demonstrate that SPaC and SPaC-R outperform online list scheduling and performs comparably well with the best known offline heuristics.

关键词： Computational offloading mobile cloud computing computation with communication semi-online algorithms

来源：评论

学校读者我要写书评

暂无评论

semi-online scheduling with non-increasing job sizes and a buffer

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2025年第4期49卷 1-23页

作者： Epstein, Leah Zebedat-Haider, Hanan Univ Haifa Fac Nat Sci Dept Math Haifa Israel Coll Sakhnin Dept Math Sakhnin Israel

This work considers a semi-online version of scheduling on m identical machines, where the objective is to minimize the makespan. In the variant studied here, jobs are presented sorted by non-increasing sizes, and a buffer of size k is available for storing at most k jobs. Every arriving job has to be either placed into the buffer until its assignment, or else it has to be assigned immediately to a machine. We prove a lower bound greater than 1 on the competitive ratio of the problem for any m and any buffer size. To complement this negative result, we design a simple algorithm for any m whose competitive ratio tends to 1 as the buffer size grows. Using those results, we show the best possible competitive ratio is 1+Theta(mk)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1+\Theta (\frac{m}{k})$$\end{document}. We provide additional bounds for small values of m. In particular, we show that for m=2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m=2$$\end{document} the case k=1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k=1$$\end{document} is not different from the case without a buffer, while k=2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k=2$$\end{document} admits an improved competitive ratio.

关键词： Multiprocessor scheduling semi-online algorithms Reordering buffers Competitive analysis

来源：评论

学校读者我要写书评

暂无评论

algorithms better than LPT for semi-online scheduling with decreasing processing times

引用

OPERATIONS RESEARCH LETTERS 2012年第5期40卷 349-352页

作者： Cheng, T. C. E. Kellerer, Hans Kotov, Vladimir Graz Univ Inst Stat & Operat Res A-8010 Graz Austria Hong Kong Polytech Univ Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China Belarusian State Univ Fac Appl Math & Comp Sci Minsk 220030 BELARUS

We consider the semi-online multiprocessor scheduling problem with m identical, parallel machines to minimize the makespan, where the jobs arrive in decreasing order of processing times. The famous Longest Processing Time (LPT) algorithm by Graham (1966) [4] for the classical offline multiprocessor scheduling problem schedules the jobs in decreasing order of processing times and has a worst-case bound of 4/3-1/(3m). So far, no algorithm with a better competitive ratio than the LPT algorithm has been given for the semi-online scheduling problem with decreasing processing times. In this note, we present a 5/4-competitive algorithm for m >= 3 and an algorithm that is the best possible for m = 3, i.e. an algorithm with competitive ratio (1 + root 37)/6. (C) 2012 Elsevier B.V. All rights reserved.

关键词： online algorithms semi-online algorithms Competitive ratio Multiprocessor scheduling

来源：评论

学校读者我要写书评

暂无评论

An optimal semi-online algorithm for a single machine scheduling problem with bounded processing time

引用

INFORMATION PROCESSING LETTERS 2010年第8-9期110卷 325-330页

作者： Tao, Jiping Chao, Zhijun Xi, Yugeng Tao, Ye Shanghai Jiao Tong Univ Dept Automat Shanghai 200030 Peoples R China

The single machine semi-online scheduling problem is considered with the assumption that the ratio of the longest processing time to the shortest one is not greater than gamma. The goal is to minimize the total weighted completion time. We design a semi-online algorithm and prove that it has a competitive ratio of 1 + root 4 gamma(2)+1-1/2 gamma, which is also shown to be the best performance achieved by any deterministic semi-online algorithm for the problem. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Analysis of algorithms semi-online algorithms Single machine scheduling Total weighted completion time Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

semi-online machine covering for two uniform machines

引用

THEORETICAL COMPUTER SCIENCE 2009年第47-49期410卷 5047-5062页

作者： Chen, Xingyu Epstein, Leah Tan, Zhiyi Univ Haifa Dept Math IL-31905 Haifa Israel Zhejiang Univ Dept Math State Key Lab CAD & CG Hangzhou 310027 Peoples R China

The machine covering problem deals with partitioning a sequence of jobs among a set of machines, so as to maximize the completion time of the least loaded machine. We study a semi-online variant, where jobs arrive one by one, sorted by non-increasing size. The jobs are to be processed by two uniformly related machines, with a speed ratio of q >= 1. Each job has to be processed continuously, in a time slot assigned to it on one of the machines. This assignment needs to be performed upon the arrival of the job. The length of the time slot, which is required for a specific job to run on a given machine, is equal to the size of the job divided by the speed of the machine. We give a complete competitive analysis of this problem by providing an algorithm of the best possible competitive ratio for every q >= 1. We first give a tight analysis of the performance of a natural greedy algorithm LPT for the problem. To achieve the best possible performance for the semi-online problem, we use a combination of LPT, together with two alternative algorithms which we design. The new algorithms attain the best possible competitive ratios in the two intervals q is an element of (1 . root 15) and q is an element of (2.4856, 1 + root 3). respectively, whereas the greedy algorithm has the best possible competitive ratio for any other q >= 1. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Two-machine scheduling semi-online algorithms

来源：评论

学校读者我要写书评

暂无评论

Delay and Cost Optimization in Computational Offloading Systems with Unknown Task Processing Times

引用

IEEE TRANSACTIONS ON CLOUD COMPUTING 2021年第4期9卷 1422-1438页

作者： Champati, Jaya Prakash Liang, Ben KTH Royal Inst Technol Sch Elect Engn & Comp Sci Div Informat Sci & Engn S-11428 Stockholm Sweden Univ Toronto Dept Elect & Comp Engn Toronto ON M5S 3G4 Canada

Computational offloading systems, where computational tasks can be processed locally or offloaded to a remote cloud, have become prevalent since the advent of cloud computing. The task scheduler in a computational offloading system decides both the selection of tasks to be offloaded to the remote cloud and the scheduling of tasks on the local processors. In this work, we consider the problem of minimizing a weighted sum of the makespan of the tasks and the offloading cost at the remote cloud. In contrast to prior works, we do not assume that the task processing times are known a priori. We show that the original problem can be solved by algorithms designed toward minimizing the maximum between the makespan and the weighted offloading cost, only with doubling of the competitive ratio. Furthermore, when the remote cloud is much faster than the local processors, the latter problem can be equivalently transformed into a makespan minimization problem with unrelated processors. For this case, we propose a Greedy-One-Restart (GOR) algorithm based on online estimation of the unknown processing times, and one-time cancellation and rescheduling of tasks that turn out to require long processing times. Given m local processors, we show that GOR has O(root m) competitive ratio, which is a substantial improvement over the best known algorithms in the literature. For the general case of arbitrary speed at the remote cloud, we extend GOR to a Greedy-Two-Restart (GTR) algorithm and show that it is O(root m)-competitive. Furthermore, where tasks arrive dynamically with unknown arrival times, we extend GOR and GTR to Dynamic-GOR (DGOR) and Dynamic-GTR (DGTR), respectively, and find their competitive ratios. Finally, we discuss how GOR can be extended to accommodate multiple remote processors. In addition to performance bounding by competitive ratios, our simulation results demonstrate that the proposed algorithms are favorable also in terms of average performance, in comparison with t

关键词： Computational offloading edge computing mobile cloud computing hybrid cloud offloading cost semi-online algorithms

来源：评论

学校读者我要写书评

暂无评论

online scheduling with a buffer on related machines

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2010年第2期20卷 161-179页

作者： Gyorgy Dosa Epstein, Leah Univ Haifa Dept Math IL-31905 Haifa Israel Univ Pannonia Dept Math Veszprem Hungary

online scheduling with a buffer is a semi-online problem which is strongly related to the basic online scheduling problem. Jobs arrive one by one and are to be assigned to parallel machines. A buffer of a fixed capacity K is available for storing at most K input jobs. An arriving job must be either assigned to a machine immediately upon arrival, or it can be stored in the buffer for unlimited time. A stored job which is removed from the buffer (possibly, in order to allocate a space in the buffer for a new job) must be assigned immediately as well. We study the case of two uniformly related machines of speed ratio s >= 1, with the goal of makespan minimization. Two natural questions can be asked. The first question is whether this model is different from standard online scheduling, that is, is any size of buffer K > 0 already helpful to the algorithm, compared to the case K = 0. The second question is whether there exists a constant K, so that a larger buffer is no longer beneficial to an algorithm, that is, increasing the size of the buffer above this threshold would not change the best competitive ratio further. Previous work (Kellerer et al., Oper. Res. Lett. 21, 235242, 1997;Zhang, Inf. Process. Lett. 61, 145-148, 1997;Englert et al., Proc. 48th Symp. Foundations of Computer Science (FOCS), 2008) shows that in the case s = 1, already K = 1 allows to design a 4/3-competitive algorithm, which is best possible for any K >= 1, whereas the best possible ratio for K = 0 is 3/2. Similar results have been show for multiple identical machines (Englert et al., Proc. 48th Symp. Foundations of Computer Science (FOCS), 2008). We answer both questions affirmatively, and show that a buffer of size K = 2 is sufficient to achieve the a competitive ratio which matches the lower bound for K --> infinity for any s > 1. In fact, we show that a buffer of size K = 1 can evidently be exploited by the algorithm for any s > 1, but for a range of values of s, it is still weaker than a buf

关键词： semi-online algorithms Scheduling Uniformly related machines

来源：评论

学校读者我要写书评

暂无评论

online bin stretching with three bins

引用

JOURNAL OF SCHEDULING 2017年第6期20卷 601-621页

作者： Bohm, Martin Sgall, Jiri van Stee, Rob Vesely, Pavel Charles Univ Prague Comp Sci Inst Prague Czech Republic Univ Leicester Dept Comp Sci Leicester Leics England

online bin stretching is a semi-online variant of bin packing in which the algorithm has to use the same number of bins as an optimal packing, but is allowed to slightly overpack the bins. The goal is to minimize the amount of overpacking, i.e., the maximum size packed into any bin. We give an algorithm for online bin stretching with a stretching factor of for three bins. Additionally, we present a lower bound of for online bin stretching on three bins and a lower bound of 19/14 for four and five bins that were discovered using a computer search.

关键词： online algorithms semi-online algorithms semi-online scheduling Bin stretching Bin packing Lower bounds for online algorithms Game tree search

来源：评论

学校读者我要写书评

暂无评论

Single Restart with Time Stamps for Parallel Task Processing with Known and Unknown Processors

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2020年第1期31卷 187-200页

We study the problem of scheduling n tasks on m + m ' parallel processors, where the processing times on m processors are known while those on the remaining m ' processors are not known a priori. This semi-online model is an abstraction of certain heterogeneous computing systems, e.g., with them known processors representing local CPU cores and the unknown processors representing remote servers with uncertain availability of computing cycles. Our objective is to minimize the makespan of all tasks. We initially focus on the case m ' = 1 and propose a semi-online algorithm termed Single Restart with Time Stamps (SRTS), which has time complexity O(nlogn). We derive its competitive ratio in comparison with the optimal offline solution. If the unknown processing times are deterministic, the competitive ratio of SRTS is shown to be either always constant or asymptotically constant in practice, respectively in cases where the processing times are independent and dependent on m. A similar result is obtained when the unknown processing times are random. Furthermore, extending the ideas of SRTS, we propose a heuristic algorithm termed SRTS-Multiple (SRTS-M) for the case m ' > 1. Finally, where tasks arrive dynamically with unknown arrival times, we extend SRTS to Dynamic SRTS (DSRTS) and find its competitive ratio. Besides the proven competitive ratios, simulation results further suggest that SRTS and SRTS-M give superior performance on average over randomly generated task processing times, substantially reducing the makespan over the best known alternatives. Interestingly, the performance gain is more significant for task processing times sampled from heavy-tailed distributions.

关键词： Computational offloading edge computing mobile cloud computing opportunistic computing unknown processing times task restart semi-online algorithms

来源：评论

学校读者我要写书评

暂无评论

A survey on makespan minimization in semi-online environments

引用

JOURNAL OF SCHEDULING 2018年第3期21卷 269-284页

作者： Epstein, Leah Univ Haifa Dept Math Haifa Israel

We discuss variants of online scheduling on identical and uniformly related machines, where the objective is to minimize the makespan. All variants are such that some information regarding the input is provided in advance, and therefore these models are known as semi-online problems. algorithms are analyzed with respect to the competitive ratio. We discuss the benefit arising from different kinds of available information and find that almost all variants allow one to reduce the competitive ratio significantly compared to the best possible competitive ratio for the corresponding pure online problem.

关键词： Competitive ratio semi-online algorithms Bin stretching Reassignment Known total size Reordering buffers

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：