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

online deadline scheduling with preemption penalties

COMPUTERS & INDUSTRIAL ENGINEERING 2011年第4期60卷 542-549页

作者： Zheng, Feifeng Xu, Yinfeng Poon, Chung Keung Zhang, E. Wu, Xiaoping City Univ Hong Kong Dept Comp Sci Kowloon Hong Kong Peoples R China Xi An Jiao Tong Univ Sch Management Xian 710049 Peoples R China State Key Lab Mfg Syst Engn Xian 710049 Peoples R China Shanghai Univ Finance & Econ Shanghai 200433 Peoples R China Xian Univ Posts & Telecommun Xian 710049 Peoples R China

This paper presents a study of the problem of online deadline scheduling under the preemption penalty model of Zheng, Xu, and Zhang (2007). In that model, each preemption incurs a penalty of rho times the weight of the preempted job, where rho >= 0 is the preemption penalty parameter. The objective is to maximise the total weight of jobs completed on time minus the total penalty. When the scheduler knows the ratio of longest to shortest job length, Delta, we show that the WAL algorithm of Zheng et al. (2007) is ((1 + rho)Delta + o(Delta))-competitive for sufficiently large Delta. This improves the bound shown in Zheng et al. (2007). When the scheduler only knows that Delta >= (k(1 + rho))(3) for some k > 1, we propose a ((k(1 + rho)Delta/(k - 1)) + o(Delta))-competitive algorithm. When rho = 0, we give an optimal, O(Delta/log Delta)-competitive algorithm that, unlike previous algorithms, does not require knowledge of Delta. This settles an open problem mentioned in Ting (2008). (C) 2011 Elsevier Ltd. All rights reserved.

关键词： Deadline scheduling online scheduling algorithms Competitive analysis Preemption penalty

来源：评论

学校读者我要写书评

暂无评论

Improved multi-processor scheduling for flow time and energy

引用

JOURNAL OF scheduling 2012年第1期15卷 105-116页

作者： Lam, Tak-Wah Lee, Lap-Kei To, Isaac K. K. Wong, Prudence W. H. Univ Liverpool Dept Comp Sci Liverpool Merseyside England Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China

Energy usage has been an important concern in recent research on online scheduling. In this paper, we study the tradeoff between flow time and energy (Albers and Fujiwara in ACM Trans. algorithms 3(4), 2007;Bansal et al. in Proceedings of ACM-SIAM Symposium on Discrete algorithms, pp. 805-813, 2007b, Bansal et al. in Proceedings of International Colloquium on Automata, Languages and Programming, pp. 409-420, 2008;Lam et al. in Proceedings of European Symposium on algorithms, pp. 647-659, 2008b) in the multi-processor setting. Our main result is an enhanced analysis of a simple non-migratory online algorithm called CRR (classified round robin) on ma parts per thousand yen2 processors, showing that its flow time plus energy is within O(1) times of the optimal non-migratory offline algorithm, when the maximum allowable speed is slightly relaxed. The result still holds even if the comparison is made against the optimal migratory offline algorithm. This improves previous analysis that CRR is O(log P)-competitive where P is the ratio of the maximum job size to the minimum job size.

关键词： online scheduling algorithms Multi-processor scheduling Competitive analysis Dynamic speed scaling Energy minimization

来源：评论

学校读者我要写书评

暂无评论

A Framework for Automated Competitive Analysis of On-line scheduling of Firm-Deadline Tasks 35

A Framework for Automated Competitive Analysis of On-line Sc...

引用

35th IEEE Real-Time Systems Symposium (RTSS)

作者： Chatterjee, Krishnendu Pavlogiannis, Andreas Koessler, Alexander Schmid, Ulrich IST Austria Inst Sci & Technol Austria Klosterneuburg Austria Vienna Univ Technol Embedded Comp Syst Grp Vienna Austria

ISBN: (纸本)9781479972876

We present a flexible framework for the automated competitive analysis of on-line scheduling algorithms for firm-deadline real-time tasks based on multi-objective graphs: Given a taskset and an on-line scheduling algorithm specified as a labeled transition system, along with some optional safety, liveness, and/or limit-average constraints for the adversary, we automatically compute the competitive ratio of the algorithm w.r.t. a clairvoyant scheduler. We demonstrate the flexibility and power of our approach by comparing the competitive ratio of several on-line algorithms, including D-over, that have been proposed in the past, for various tasksets. Our experimental results reveal that none of these algorithms is universally optimal, in the sense that there are tasksets where other schedulers provide better performance. Our framework is hence a very useful design tool for selecting optimal algorithms for a given application.

关键词： scheduling task analysis automated competitive analysis clairvoyant scheduler competitive ratio firm-deadline real-time tasks flexible framework labeled transition system limit-average constraints liveness multiobjective graphs online scheduling algorithms optimal algorithms optional safety Algorithm design and analysis Real-time systems Safety Schedules scheduling scheduling algorithms Vectors scheduling algorithms elastic frame Optimization algorithms Algorithm design and analysis task analysis real-time systems Consumer safety safety IN-LINE

来源：评论

学校读者我要写书评

暂无评论

Performance of work conserving schedulers and scheduling of some synchronous dataflow graphs

Performance of work conserving schedulers and scheduling of ...

引用

10th International Conference on Parallel and Distributed Systems (ICPADS 2004)

作者： Kanade, U Codito Technologies Pvt. Ltd.

ISBN: (纸本)0769521525

We know a lot about competitive or approximation ratios of scheduling algorithms. This, though, cannot be translated into direct bounds on the schedule produced by a scheduling algorithm, because often the optimal solution is intractable. We derive a methodology to find absolute bounds on the scheduling of jobs with precedence constraints on parallel identical machines. Our bounds hold for a large class of online and offline scheduling algorithms: the "work conserving" scheduling algorithms. We apply this methodology to prove that an important class of synchronous dataflow graphs - the parallelized pipelines has very good performance characteristics when scheduled by a work conserving scheduler Real time guarantees and granularity design for these dataflow graphs are discussed. We argue that parallelized pipelines should be dynamically scheduled on multiprocessor architectures.

关键词： parallel job scheduling online scheduling algorithms synchronous dataflow graphs real time systems performance analysis of parallel systems

来源：评论

学校读者我要写书评

暂无评论

Competitive Non-migratory scheduling for Flow Time and Energy 08

Competitive Non-migratory Scheduling for Flow Time and Energ...

引用

20th ACM Symposium on Parallelism in algorithms and Architectures

作者： Lam, Tak-Wah Lee, Lap-Kei To, Isaac K. K. Wong, Prudence W. H. Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China Univ Liverpool Dept Comp Sci Liverpool Merseyside England

ISBN: (纸本)9781595939739

Energy usage has been an important concern in recent research on online scheduling. In this paper we extend the study of the tradeoff between flow time and energy from the single-processor setting [8, 6] to the multi-processor setting. Our main result is an analysis of a simple non-migratory online algorithm called CRR (classified round robin) on m >= 2 processors, showing that its flow time plus energy is within O(i) times of the optimal non-migratory offline algorithm, when the maximum allowable speed is slightly relaxed. This result still holds even if the comparison is made against the optimal migratory offline algorithm (the competitive ratio increases by a factor of 2.5). As a special case, our work also contributes to the traditional online flow-time scheduling. Specifically, for minimizing flow time only, CRR can yield a competitive ratio one or even arbitrarily smaller than one, when using sufficiently faster processors. Prior to our work, similar result is only known for online algorithms that needs migration [21, 23], while the best non-migratory result can achieve an O(1) competitive ratio [14]. The above result stems from an interesting observation that there always exists some optimal migratory schedule S that can be converted (in an offline sense) to a non-migratory schedule S' with a moderate increase in flow time plus energy. More importantly, this non-migratory schedule always dispatches jobs in the same way as CRR.

关键词： online scheduling algorithms competitive analysis dynamic speed scaling energy minimization

来源：评论

学校读者我要写书评

暂无评论

The Power of Amortization on scheduling with Explorable Uncertainty 1

引用

21st International Workshop on Approximation and online algorithms (WAOA) part of ALGO Conference

作者： Liu, Alison Hsiang-Hsuan Liu, Fu-Hong Wong, Prudence W. H. Zhang, Xiao-Ou Univ Utrecht Utrecht Netherlands Univ Liverpool Liverpool Merseyside England

ISBN: (数字)9783031498152

ISBN: (纸本)9783031498145;9783031498152

In this work, we study a scheduling problem with explorable uncertainty. Each job comes with an upper limit of its processing time, which could be potentially reduced by testing the job, which also takes time. The objective is to schedule all jobs on a single machine with a minimum total completion time. The challenge lies in deciding which jobs to test and the order of testing/processing jobs. The online problem was first introduced with unit testing time [5,6] and later generalized to variable testing times [1]. For this general setting, the upper bounds of the competitive ratio are shown to be 4 and 3.3794 for deterministic and randomized online algorithms [1];while the lower bounds for unit testing time stands [5,6], which are 1.8546 (deterministic) and 1.6257 (randomized). We continue the study on variable testing times setting. We first enhance the analysis framework in [1] and improve the competitive ratio of the deterministic algorithm in [1] from 4 to 1+ root 2 approximate to 2.4143. Using the new analysis framework, we propose a new deterministic algorithm that further improves the competitive ratio to 2.316513. The new framework also enables us to develop a randomized algorithm improving the expected competitive ratio from 3.3794 to 2.152271.

关键词： Explorable uncertainty online scheduling algorithms Total completion time Competitive analysis Amortized analysis

来源：评论

学校读者我要写书评

暂无评论

Optimizing Dynamic Data Center Provisioning through Speed Scaling: A Primal-Dual Perspective 24

Optimizing Dynamic Data Center Provisioning through Speed Sc...

引用

36th ACM Symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Chen, Xiaosong Xu, Huanle Xu, ChengZhong Univ Macau Macau Peoples R China

ISBN: (纸本)9798400704161

A significant proportion of energy consumed in modern data centers and clouds is dedicated to provisioning idle servers for maintaining Quality of Service guarantees. Various studies have been conducted exploring dynamic provisioning in data centers with the objective of reducing overall energy consumption. However, many of these studies assume a fixed energy cost per operating server where each server can only handle one job within a given time slot. In this paper, we address a new and practical problem that involves speed scaling of multiple servers within a data center. Specifically, we consider a scenario where each server can handle multiple jobs simultaneously, and the energy consumed is a piece-wise convex function that depends on processing speed. In addition, turning on a server incurs a substantial energy cost. To tackle this problem, we develop a new online primal-dual fitting framework. By leveraging this framework, we have found that the straightforward LIF algorithm, which allocates new workloads to servers based on their minimal idle times, attains a bounded competitive ratio in comparison to the optimal offline solution. Building upon this finding, we have designed a novel algorithm called BDST. BDST dynamically updates server provisioning based on a long-term evaluation of the trade-off between the cost of maintaining high-speed for current servers and the cost of powering on additional servers. One critical aspect of BDST is its remarkable constant competitive ratio of less than three, regardless of the shape of the energy function.

关键词： online scheduling algorithms Capacity provisioning Energy efficiency

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：