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

Approximation Algorithms for Multiprocessor scheduling with testing to Minimize the Total Job Completion Time

ALGORITHMICA 2024年第5期86卷 1400-1427页

作者： Gong, Mingyang Chen, Zhi-Zhong Hayashi, Kuniteru Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada Tokyo Denki Univ Div Informat Syst Design Saitama Japan

In offline scheduling models, jobs are given with their exact processing times. In their online counterparts, jobs arrive in sequence together with their processing times and the scheduler makes irrevocable decisions on how to execute each of them upon its arrival. We consider a semi-online variant which has equally rich application background, called scheduling with testing, where the exact processing time of a job is revealed only after a required testing operation is finished, or otherwise the job has to be executed for a given possibly over-estimated length of time. For multiprocessor scheduling with testing to minimize the total job completion time, we present several first approximation algorithms with constant competitive ratios for various settings, including a 2 phi-competitive algorithm for the non-preemptive general testing case and a (0.0382 +2.7925(1- 1/2m ))-competitive randomized algorithm, when the number of root machines m > 37 or otherwise 2.7925-competitive, where phi = (1+ 5)/2 < 1.6181 is the golden ratio and m is the number of machines, a (3.5 - 2 3m )-competitive algorithm allowing job preemption when m > 3 or otherwise 3-competitive, and a (phi + phi+1 2 (1 - 1m))-competitive algorithm for the non-preemptive uniform testing case when m > 5 or otherwise (phi + 1)-competitive. Our results improve three previous best approximation algorithms for the single machine scheduling with testing problems, respectively.

关键词： scheduling Multiprocessor scheduling with testing Total job completion time Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第1期44卷 877-893页

作者： Gong, Mingyang Goebel, Randy Lin, Guohui Miyano, Eiji Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada Kyushu Inst Technol Dept Artificial Intelligence Iizuka Fukuoka Japan

Multiprocessor scheduling, also called scheduling on parallel identical machines to minimize the makespan, is a classic optimization problem which has been extensively studied. scheduling with testing is an online variant, where the processing time of a job is revealed by an extra test operation, otherwise the job has to be executed for a given upper bound on the processing time. Albers and Eckl recently studied the multiprocessor scheduling with testing;among others, for the non-preemptive setting they presented an approximation algorithm with competitive ratio approaching 3.1016 when the number of machines tends to infinity and an improved approximation algorithm with competitive ratio approaching 3 when all test operations take one unit of time each. We propose to first sort the jobs into non-increasing order of the minimum value between the upper bound and the testing time, then partition the jobs into three groups and process them group by group according to the sorted job order. We show that our algorithm achieves better competitive ratios, which approach 2.9513 when the number of machines tends to infinity in the general case;when all test operations each takes one time unit, our algorithm achieves even better competitive ratios approaching 2.8081.

关键词： Multiprocessor scheduling scheduling with testing Non-preemptive Makespan Competitive ratio Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved Approximation Algorithms for Multiprocessor scheduling with testing 15th

Improved Approximation Algorithms for Multiprocessor Schedul...

引用

15th International Frontiers of Algorithmics Workshop (FAW) / Game Theory in Blockchain Track Conference / 2nd International Joint Conference on Theoretical Computer Science (IJTCS)

作者： Gong, Mingyang Lin, Guohui Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada

ISBN: (纸本)9783030970994;9783030970987

Multiprocessor scheduling, also called scheduling on parallel identical machines to minimize the makespan, is a classic optimization problem that has received numerous studies. scheduling with testing is an online variant where the processing time of a job is revealed by an extra test operation, or otherwise the job has to be executed for a given upper bound on the processing time. Albers and Eckl recently studied the multiprocessor scheduling with testing;among others, for the non-preemptive setting they presented an approximation algorithm with competitive ratio approaching 3.1016 when the number of machines tends to infinity and an improved approximation algorithm with competitive ratio approaching 3 when all test operations take a time unit. We propose to first sort the jobs into the non-increasing order of the minimum value between the upper bound and the testing time, then partition the jobs into three groups and process them group by group according to the sorted job order. We show that our algorithm achieves improved competitive ratios, which approach 2.9513 when the number of machines tends to infinity in the general case;when all test operations take a time unit, our algorithm achieves even better competitive ratios approaching 2.8081.

关键词： Multiprocessor scheduling scheduling with testing makespan non-preemptive competitive ratio approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Load Balancing with Job-Size testing: Performance Improvement or Degradation?

引用

ACM TRANSACTIONS ON MODELING AND PERFORMANCE EVALUATION OF COMPUTING SYSTEMS 2024年第2期9卷 1-27页

作者： Anselmi, Jonatha Doncel, Josu Univ Grenoble Alpes CNRS Inria Grenoble INPLIG 700 Ave Cent F-38400 St Martin Dheres France Univ Basque Country UPV EHU Barrio Sarriena S-N Leioa 48940 Spain

In the context of decision making under explorable uncertainty, scheduling with testing is a powerful technique used in the management of computer systems to improve performance via better job-dispatching decisions. Upon job arrival, a scheduler may run some testing algorithm against the job to extract some information about its structure, e.g., its size, and properly classify it. The acquisition of such knowledge comes with a cost because the testing algorithm delays the dispatching decisions, though this is under control. In this article, we analyze the impact of such extra cost in a load balancing setting by investigating the following questions: does it really pay off to test jobs? If so, under which conditions? Under mild assumptions connecting the information extracted by the testing algorithm in relationship with its running time, we show that whether scheduling with testing brings a performance degradation or improvement strongly depends on the traffic conditions, system size and the coefficient of variation of job sizes. Thus, the general answer to the above questions is non-trivial and some care should be considered when deploying a testing policy. Our results are achieved by proposing a load balancing model for scheduling with testing that we analyze in two limiting regimes. When the number of servers grows to infinity in proportion to the network demand, we show that job-size testing actually degrades performance unless short jobs can be predicted reliably almost instantaneously and the network load is sufficiently high. When the coefficient of variation of job sizes grows to infinity, we construct testing policies inducing an arbitrarily large performance gain with respect to running jobs untested.

关键词： Load balancing dispatching policies size-based routing scheduling with testing explorable uncertainty

来源：评论

学校读者我要写书评

暂无评论

testing in scheduling problems for information retrieval

Testing in scheduling problems for information retrieval

引用

作者： Ioannis Samaras Vrije Universiteit Amsterdam

学位级别：硕士

This thesis focuses on the two machine flow shop problem with unknown delays. This a problem often found in the design of manufacturing facilities, where the equipment can be ordered only after its specifications are known with one-hundred-percent confidence. In this industry, the man- agement uses the approach of Critical Path Method (CPM), which, given the stochastic nature of the problem, can lead to undesired prolongation of the project duration. For this reason, the idea of testing some of the jobs is proposed as an exploration through exploitation concept.

关键词： Two-machine flow shop with unknown delays scheduling with testing unknown time lags exploration through exploitation information retrieval

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：