Preemptive and Non-preemptive On-line Algorithms for Scheduling with Rejection on Two Uniform Machines

In this paper, we consider the problem of on-line scheduling a job sequence on two uniform machines. A job can be either rejected, in which case we pay its penalty, or scheduled on machines, in which case it contributes its processing time to the makspan of the constructed schedule. The objective is to minimize the sum of the makespan of the schedule for all accepted jobs and the penalties of all rejected jobs. Both preemptive and non-preemptive versions are considered. For the preemptive version, we present an optimal on-line algorithm with a competitive ratio for any s≥1, where s is the machine speed ratio. For the non-preemptive version, we present an improved lower bound. Moreover, as an optimal algorithm for s≥1.6180 is known, we present a modified version of the known algorithm, and show that it becomes optimal for any 1.3852≤s<1.6180 and has a smaller competitive ratio than that of original version for any 1≤s<1.3852. The maximum gap between its competitive ratio and the lower bound is 0.0534.     

Resource Constraints for Preemptive Job-shop Scheduling

This paper presents an experimental study of constraint propagation algorithms for preemptive scheduling. We propose generalizations of non-preemptive constraint propagation techniques (based on timetables, on disjunctive constraints, and on edge-finding) to preemptive and mixed problems, i.e., problems in which some activities can be interrupted and some cannot. Another approach relies on incremental flow-based techniques. We theoretically compare these approaches and present an experimental comparison based on a branch and bound procedure for the preemptive variant of the job-shop scheduling problem. We show that both edge-finding and flow-based techniques allow the resolution of hard problem instances, including the preemptive variant of the famous FT10.     

基于特定应用的可抢占与不可抢占任务调度算法

根据ASOS的特点和实际实时任务的特性,该文提出了一种建立在RM上的算法：NPT算法。它能很好地实现可抢占与不可抢占任务在单一处理器中的调度,并具有RM算法的一些良好的基本特性,还研究了这种算法的性质,给出并汪明了NPT算法的任务町调度性充分条件。此外,对NPT算法下的最坏响应时间计算也作了论述。     

Cache-Conscious Limited Preemptive Scheduling

In multi-tasking real-time systems, inter-task cache interference due to preemptions degrades schedulability as well as performance. To address this problem, we propose a novel scheduling scheme, called limited preemptive scheduling (LPS), that limits preemptions to execution points with small cache-related preemption costs. Limiting preemptions decreases the cache-related preemption costs of tasks but increases blocking delay of higher priority tasks. The proposed scheme makes an optimal trade-off between these two factors to maximize the schedulability of a given task set while minimizing cache-related preemption delay of tasks. Experimental results show that the LPS scheme improves the maximum schedulable utilization by up to 40\% compared with the traditional fully preemptive scheduling (FPS) scheme. The results also show that up to 20\% of processor time is saved by the LPS scheme due to reduction in the cache-related preemption costs. Finally, the results show that both the improvement of schedulability and the saving of processor time by the LPS scheme increase as the speed gap between the processor and main memory widens.     

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-Δ .     

New Algorithms for Disk Scheduling

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-Δ .     

Robust Algorithms for Object Localization

Model-based localization, the task of estimating an object's pose from sensed and corresponding model features, is a fundamental task in machine vision. Exact constant time localization algorithms have been developed for the case where the sensed features and the model features are the same type. Still, it is not uncommon for the sensed features and the model features to be of different types, i.e., sensed data points may correspond to model faces or edges. Previous localization approaches have handled different model and sensed features of different types via sampling and synthesizing virtual features to reduce the problem of matching features of dissimilar types to the problem of matching features of similar types. Unfortunately, these approaches may be suboptimal because they introduce artificial errors. Other localization approaches have reformulated object localization as a nonlinear least squares problem where the error is between the sensed data and model features in image coordinates (the Euclidean image error metric). Unfortunately, all of the previous approaches which minimized the Euclidean image error metric relied on gradient descent methods to find the global minima, and gradient descent methods may suffer from problems of local minima. In this paper, we describe an exact, efficient solution to the nonlinear least squares minimization problem based upon resultants, linear algebra, and numerical techniques. On a SPARC 20, our localization algorithm runs in a few microseconds for rectilinear polygonal models, a few milliseconds for generic polygonal models, and one second for generalized polygonal models (models composed of linear edges and circular arcs).     

Semi-Online Preemptive Scheduling: One Algorithm for All Variants

We present a unified optimal semi-online algorithm for preemptive scheduling on uniformly related machines with the objective to minimize the makespan. This algorithm works for all types of semi-online restrictions, including the ones studied before, like sorted (decreasing) jobs, known sum of processing times, known maximal processing time, their combinations, and so on. Based on the analysis of this algorithm, we derive some global relations between various semi-online restrictions and tight bounds on the approximation ratios for a small number of machines.     

无线调度算法

为满足无线应用中的Qos要求,调度算法是很重要的。由于无线网络变化的链路错误率和容量,因此为其设计调度算法非常有挑战性。近来提出了多种适合无线网络的调度算法。该文分析了3种基于TDD的调度算法。讨论了各种算法的实现过程和优缺点,最后对它们的性能进行比较．得出了有意义的结论。     

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.     

Approximation Algorithms for Time Constrained Scheduling

In this paper we consider the following time constrained scheduling problem. Given a set of jobsJwith execution timese(j)(0, 1] and an undirected graphG=(J, E), we consider the problem to find a schedule for the jobs such that adjacent jobs (j, j′)Eare assigned to different machines and that the total execution time for each machine is at most 1. The goal is to find a minimum number of machines to execute all jobs under this time constraint. This scheduling problem is a natural generalization of the classical bin-packing problem. We propose and analyse several approximation algorithms with constant absolute worst case ratio for graphs that can be colored in polynomial time.     

Barely Random Algorithms for Multiprocessor Scheduling

We consider randomized algorithms for on-line scheduling on identical machines. For two machines, a randomized algorithm achieving a competitive ratio of was found by Bartal et al. (1995). Seiden has presented a randomized algorithm which achieves competitive ratios of 1.55665, 1.65888, 1.73376, 1.78295, and 1.81681, for m=3,4,5,6,7, respectively (Seiden, 2000). A barely random algorithm is one which is a distribution over a constant number of deterministic strategies. The algorithms of Bartal et al. and Seiden are not barely random–in fact, these algorithms potentially make a random choice for each job scheduled. We present the first barely random on-line scheduling algorithms. In addition, our algorithms use less space and time than the previous algorithms, asymptotically.     

Optimal Scheduling Algorithms for Tertiary Storage

The ever growing needs of large multimedia systems cannot be met by magnetic disks due to their high cost and low storage density. Consequently, cheaper and denser tertiary storage systems are being integrated into the storage hierarchies of these applications. Although tertiary storage is cheaper, the access latency is very high due to the need to load and unload media on the drives. This high latency and the bursty nature of I/O traffic result in the accumulation of I/O requests for tertiary storage. We study the problem of scheduling these requests to improve performance. In particular we address the issues of scheduling across multiple tapes or disks as opposed to most other studies which consider only one or two media. We focus on algorithms that minimize the number of switches and show through simulation that these result in near-optimal schedules. For single drive libraries an efficient algorithm that produces optimal schedules is developed. Formultiple drives the problem is shown to be NP-Complete. Efficient and effective heuristics are presented for both single and multiple drives. The scheduling policies developed achieve significant performance gains over naive policies. The algorithms are simple to implement and are not restrictive. The study encompasses all types of storage libraries handling removable media, such as tapes and optical disks.     

Competitive Algorithms for Due Date Scheduling

We consider several online scheduling problems that arise when customers request make-to-order products from a company. At the time of the order, the company must quote a due date to the customer. To satisfy the customer, the company must produce the good by the due date. The company must have an online algorithm with two components: The first component sets the due dates, and the second component schedules the resulting jobs with the goal of meeting the due dates.     

基于启发式规则的混合遗传算法及其在生产计划优化中的应用

以最优或近似最优的作业顺序编制满足关键资源约束的生产计划优化问题一直是企业生产管理中重要的研究课题之一。文章提出了一种基于传统启发式规则的混合遗传算法。该算法将染色体分为两段,前段表示资源安排策略,后段表示为优先分配规则序列,并设计了一种新的交叉算子。最后,介绍了根据此算法编制的一个制造企业生产控制的软件系统。     

Approximation Algorithms for Multiprocessor Scheduling under Uncertainty

Motivated by applications in grid computing and project management, we study multiprocessor scheduling in scenarios where there is uncertainty in the successful execution of jobs when assigned to processors. We consider the problem of multiprocessor scheduling under uncertainty, in which we are given n unit-time jobs and m machines, a directed acyclic graph C giving the dependencies among the jobs, and for every job j and machine i, the probability p _ij of the successful completion of job j when scheduled on machine i in any given particular step. The goal of the problem is to find a schedule that minimizes the expected makespan, that is, the expected time at which all of the jobs are completed.     

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.     

Multicycle Polling Scheduling Algorithms for FieldBus Networks

The paper deals with the scheduling of periodic information flow in a FieldBus environment. The scheduling problem is defined from an analytical point of view, giving a brief survey of the most well-known solutions. One of these is called multicycle polling scheduling, which is based on the hypothesis that all the production periods of the periodic processes to be scheduled are harmonic. Although in some process control or manufacturing scenarios, this hypothesis may be acceptable, there are many real industrial processes to which it cannot be applied. The aim of the paper is to make a contribution towards solving the scheduling problem. It essentially concerns extension of the theory on which multicycle polling scheduling is based to a much more realistic and general scenario, where the periods of all the processes to be scheduled have arbitrary values. The authors present a new formulation of multicycle polling scheduling, called extended multicycle polling scheduling, and demonstrate that it comprises the scenario currently considered in the literature. Two algorithmic solutions for extended multicycle polling scheduling are then proposed, giving a computational complexity analysis which will highlight the capability of the algorithmic scheduling solutions to be performed on-line. The paper concludes by comparing the multicycle polling scheduling approach known in literature and the one presented in the paper. Comparison is performed by evaluating the use of available bandwidth to serve both periodic and asynchronous traffic in the two approaches.     

Performance of Channel-Aware Scheduling Algorithms for HDR-WPAN

In this paper, we consider the performances in terms of system throughput and response time of various channel-aware scheduling algorithms for both MPEG streams and non-MPEG flows in a high-data-rate (HDR) wireless personal area network (WPAN). The algorithms under investigation are the shortest remaining processing time rule, the exponential rule, the modified largest weighted delay first rule, the maximum rate rule, and the proportionally fair rule. Decodability issues are taken care of by means of the frame-decodability aware technique and the burst transfer eligibility decision mechanism. The impacts of a number of factors including deadline and interference-plus-noise level are also examined. The investigations are carried out through extensive ns-2 simulations. Based on the numerical results, we propose a heuristic scheduling algorithm for MPEG streams that outperforms the above algorithms in terms of system throughput. The findings are useful for system designers.