Scheduling Web Advertisements: A Note on the Minspace Problem

Free services to internet users are commonly available on many web sites e.g., Hotmail and Yahoo. For such sites, revenue generated from advertisements (hereafter also called ads) placed on the web pages is critical for survival. An effective way to schedule ads on web pages to optimize certain performance measures is an important problem that these sites need to address.In this note, we report improved approximation algorithms for the following problem: ads from a set of n ads A = {A_i,...,A_n} are to be placed on a web page during a planning horizon that is divided into N time intervals. In each time interval, ads are shown in a rectangular space called a slot. An ad A_i is specified by its size s_i and frequency w_i and is to be scheduled in exactly w_i slots. We are required to find a schedule that minimizes the maximum fullness among all the slots, where the fullness of a slot is the sum of the sizes of ads scheduled in that slot. Our results include (i) the first online algorithm with a performance bound of , and (ii) two offline algorithms with performance guarantees of and , respectively. These bounds are significant improvements over those for previously known algorithms presented in Adler, Gibbons, and Matias (2002) and Dawande, Kumar, and Sriskandarajah (2003).     

Approximation Algorithms for Average Stretch Scheduling

We study the basic problem of preemptive scheduling of a stream of jobs on a single processor. Consider an on-line stream of jobs, and let the ith job arrive at time r(i) and have processing time p(i). If C(i) is the completion time of job i, then the flow time of i is C(i) − r(i) and the stretch of i is the ratio of its flow time to its processing time; that is, . Flow time measures the time that a job is in the system regardless of the service it requests; the stretch measure relies on the intuition that a job that requires a long service time must be prepared to wait longer than jobs that require small service times. We present the improved algorithmic results for the average stretch metric in preemptive uniprocessor scheduling. Our first result is an off-line polynomial-time approximation scheme (PTAS) for average stretch scheduling. This improves upon the 2-approximation achieved by the on-line algorithm srpt that always schedules a job with the shortest remaining processing time. In a recent work, Chekuri and Khanna (Proc. 34th Ann. Symp. Theory Comput., 297–305, 2002) have presented approximation algorithms for weighted flow time, which is a more general metric than average stretch; their result also yields a PTAS for average stretch. Our second set of results considers the impact of incomplete knowledge of job sizes on the performance of on-line scheduling algorithms. We show that a constant-factor competitive ratio for average stretch is achievable even if the processing times (or remaining processing times) of jobs are known only to within a constant factor of accuracy.     

Utilization Bounds for EDF Scheduling on Real-Time Multiprocessor Systems

The utilization bound for earliest deadline first (EDF) scheduling is extended from uniprocessors to homogeneous multiprocessor systems with partitioning strategies. First results are provided for a basic task model, which includes periodic and independent tasks with deadlines equal to periods. Since the multiprocessor utilization bounds depend on the allocation algorithm, different allocation algorithms have been considered, ranging from simple heuristics to optimal allocation algorithms. As multiprocessor utilization bounds for EDF scheduling depend strongly on task sizes, all these bounds have been obtained as a function of a parameter which takes task sizes into account. Theoretically, the utilization bounds for multiprocessor EDF scheduling can be considered a partial solution to the bin-packing problem, which is known to be NP-complete. The basic task model is extended to include resource sharing, release jitter, deadlines less than periods, aperiodic tasks, non-preemptive sections, context switches, and mode changes.     

网格任务调度算法研究

网格任务调度算法是影响网格成功与否的关键技术之一。本文总结了网格计算系统的体系结构和特征,分析了网格任务调度算法的基本原理和性能指标,并对各种调度策略和算法进行了分类和比较。本文为网格任务调度的研究提供了很好的参考。     

Microchoice Bounds and Self Bounding Learning Algorithms

A major topic in machine learning is to determine good upper bounds on the true error rates of learned hypotheses based upon their empirical performance on training data. In this paper, we demonstrate new adaptive bounds designed for learning algorithms that operate by making a sequence of choices. These bounds, which we call Microchoice bounds, are similar to Occam-style bounds and can be used to make learning algorithms self-bounding in the style of Freund (1998). We then show how to combine these bounds with Freund's query-tree approach producing a version of Freund's query-tree structure that can be implemented with much more algorithmic efficiency.     

元计算系统的批模式启发式任务调度算法研究

元计算系统是通过网络连接的地理上分散的主机、数据库和文件等资源。使用这些资源、可以运行用户的应用程序。研究元计算环境下的批模式启发式任务调度算法,论述Wade系统的应用任务的调度模型,比较4种调度算法的性能。     

Fundamentals of Scheduling and Performance of Video Tape Libraries

Robotic tape libraries are popular for applications with very high storage requirements, such as video servers. Here, we study the throughput of a tape library system, we design a new scheduling algorithm, the so-called Relief, and compare it against some older/straightforward ones, like FCFS, Maximum Queue Length (MQL) and an unfair one (Bypass), roughly equivalent to Shortest Job First. The proposed algorithm incorporates an aging mechanism in order to attain fairness and we prove that, under certain assumptions, it minimizes the average start-up latency. Extensive simulation experiments show that Relief outperforms its competitors (fair and unfair alike), with up to 203% improvement in throughput, for the same rejection ratio.     

New Algorithms for Disk Scheduling

Abstract. Processor speed and memory capacity are increasing several times faster than disk speed. This disparity suggests that disk I/ O performance could become an important bottleneck. Methods are needed for using disks more efficiently. Past analysis of disk scheduling algorithms has largely been experimental and little attempt has been made to develop algorithms with provable performance guarantees. We consider the following disk scheduling problem. Given a set of requests on a computer disk and a convex reachability function that determines how fast the disk head travels between tracks, our goal is to schedule the disk head so that it services all the requests in the shortest time possible. We present a 3/2 -approximation algorithm (with a constant additive term). For the special case in which the reachability function is linear we present an optimal polynomial-time solution. The disk scheduling problem is related to the special case of the Asymmetric Traveling Salesman Problem with the triangle inequality (ATSP-Δ ) in which all distances are either 0 or some constant α . We show how to find the optimal tour in polynomial time and describe how this gives another approximation algorithm for the disk scheduling problem. Finally we consider the on-line version of the problem in which uniformly distributed requests arrive over time. We present an algorithm related to the above ATSP-Δ .     

Semi-Online Algorithms for Parallel Machine Scheduling Problems

This paper considers two semi-online versions of scheduling problem P2||C_max where one type of partial information is available and one type of additional algorithmic extension is allowed simultaneously. For the semi-online version where a buffer of length 1 is available and the total size of all jobs is known in advance, we present an optimal algorithm with competitive ratio 5/4. We also show that it does not help that the buffer length is greater than 1. For the semi-online version where two parallel processors are available and the total size of all jobs is known in advance, we present an optimal algorithm with competitive ratio 6/5.The second author is supported by TRAPOYT of China, National Natural Science Foundation of China (10271110). Corresponding author: Y. He.     

Polynomial Algorithms for a Two-Class Multiprocessor Scheduling Problem in Mobile Telecommunications Systems

In Universal Mobile Telecommunications Systems radio access, information packets of different services and users are sent across the air interface organized into radio frames. A radio frame is divided into a fixed number of time slots, different packets can share the same time slot and exactly one slot must be assigned to each packet. The packets of different services have divisible sizes and the slot capacity is limited. Quality of Service requirements set time intervals within which each packet must be scheduled. In this work, we address the problem of scheduling packets related to two different services to the time slots of a radio frame. The problem is a variant of the High-Multiplicity Multiprocessor Scheduling Problem in which there are two classes of jobs with divisible sizes, and the jobs must satisfy assignment restrictions. Two polynomial—time scheduling algorithms, maximizing the number of scheduled packets, and the weighted throughput, are provided.     

实时系统中的调度算法分类研究

本文叙述了实时系统中调度算法的分类、各类算法的研究成果和近期研究状况。     

网络RAID存储系统边界性能研究

目前针对网络存储系统性能的研究大都集中在定性研究方面,缺乏有效的定量分析方法和模型.在有限容量闭合排队网络理论的基础上,提出了网络RAID存储系统性能的定量分析模型.并提出了一种新的计算有限容量闭合排队网络系统边界性能的分析方法-APBA法,和其他近似分析方法相比,APBA法的计算时间复杂度更低.测试结果表明,通过利用APBA方法,由网络RAID存储系统的性能定量分析模型获得的系统性能值,可以有效反映网络RAID存储系统在轻载区、重载区和过载区的性能边界,以及系统的最大负载量.     

基于遗传算法的均热炉群装炉出炉调度

提出了基于遗传算法的均热炉装炉出炉调度的方法,并在调度目标中增加了对装炉优先级和过均热禁忌度等因素的考虑。仿真结果表明,该调度结果优于目前普遍使用的调度方法。这种方法能减轻调度人员劳动强度,并在一定程序上改善均热炉生产调度的性能。     

Framework for Task Scheduling in Heterogeneous Distributed Computing Using Genetic Algorithms

An algorithm has been developed to dynamically schedule heterogeneous tasks on heterogeneous processors in a distributed system. The scheduler operates in an environment with dynamically changing resources and adapts to variable system resources. It operates in a batch fashion and utilises a genetic algorithm to minimise the total execution time. We have compared our scheduler to six other schedulers, three batch-mode and three immediate-mode schedulers. Experiments show that the algorithm outperforms each of the others and can achieve near optimal efficiency, with up to 100,000 tasks being scheduled     

基于遗传算法的半导体生产线调度方法研究

在介绍遗传算法及其在流水车间调度(flow shop)应用现状的基础上,针对半导体生产线可重入的特性,研究了基于遗传算法的半导体生产线调度算法,并用一个例子给出了算法的计算过程。     

多媒体服务器混合磁盘调度策略

基于多媒体服务器的性能要求，提出了一种自适应的混合磁盘调度策略DRT-window．它既能满足实时请求对实时性的要求，根据实时请求的截止期动态选择窗口大小；又能在其松弛度内尽努力(best-effort)地服务非实时请求，从而减少非实时请求的响应时间。DRT-window采用了两级层次调度方案：第一层为不同类型的请求采用各自适合的调度策略；第二层为混合请求调度嚣，混合调度第一层中的不同类型的请求。通过性能比较和理论证明，表明此混合磁盘调度策略能在保证实时请求无抖动执行的同时，尽量地减少非实时请求的响应时间。     

用于VOD系统的块重组策略及分组调度算法

1 引言随着存储子系统、数据压缩技术、网络带宽各方面技术的发展,视频点播(VOD)得到了极大的推动。VOD的本质是用户根据自己的需求去主动选择所感兴趣的信息,这种主动性和选择性使得它在广告宣传、信息查询、娱乐、教育等领域变得前景广阔。国内外一些知名大学和公司已在这方面进行了深入的研究。     

Bounds on the largest singular value of a matrix and the convergence of simultaneous and block-iterative algorithms for sparse linear systems

We obtain the following upper bounds for the eigenvalues of the matrix A ^† A . For any a in the interval [0, 2] let and c_a and r_a the maxima of the c_aj and r_ai , respectively. Then no eigenvalue of the matrix A ^† A exceeds the maximum of over all i , nor the maximum of over all j . Therefore, no eigenvalue of A ^† A exceeds c_ar_a .
Using these bounds, it follows that, for the matrix G with entries no eigenvalue of G ^† G exceeds one, provided that, for some a in the interval [0, 2], we have and
Using this result, we obtain convergence theorems for several iterative algorithms for solving the problem Ax = b , including the CAV, BICAV, CARP1, SART, SIRT, and the block-iterative DROP and SART methods.     

并行设计子任务调度的遗传算法原理与实现方法

建立了设计子任务调度的目标模型,提出了一种针对并行设计子任务调度的遗传算法．应用结果表明,在满足子任务间偏序关系条件下,文中算法能够得到设计子任务的最优调度方案．     

求解Flow-shop调度问题的HSGATS算法研究

通过研究流程企业典型生产加工方式的Flow-shop加工调度问题,分析了求解这一调度问题的各种算法的性能,特别是混合遗传算法中的混合策略,进而提出了一种以启发式搜索算法为前置算法、遗传算法为主体算法、禁忌搜索算法为后置算法的新的混合遗传算法-HSGATS算法,并针对置换Flow-shop调度问题提出了具体的算法设计和实现方法;通过对大量置换Flow--ShopBenchmark问题进行实验求解和其他算法的比较分析,验证了此算法是十分有效的。