17449226
Approximation algorithms for scheduling multiple feasible interval jobs
Time-critical jobs in many real-time applications have multiple feasible intervals. Such a job is constrained to execute from start to completion in one of its feasible intervals. A job fails if the job remains incomplete at the end of the last feasible interval. This paper is concerned with how to find a schedule in which the number of jobs completed in one of their feasible intervals is maximized. We show that the maximization problem is NP-hard for both nonpreemptible and preemptible jobs. This paper develops two approximation algorithms for nonpreemptible and preemptible jobs. When jobs are nonpreemptible, algorithm LECF is with a 2-approximation factor; when jobs are preemptible, algorithm LEF is proved being a 3-approximation algorithm. We also show that our analysis on the two algorithms is tight by providing a set of input instances. Simulation results demonstrate that algorithms LECF and LEF not only guarantee the approximation factors but also outperform other multiple feasible interval scheduling algorithms.
30973700
Allocation cost minimization for periodic hard real-time tasks in energy-constrained DVS systems
12533129
Procrastination for leakage-aware rate-monotonic scheduling on a dynamic voltage scaling processor
As the dynamic voltage scaling (DVS) technique provides system engineers the flexibility to trade-off the performance and the energy consumption, DVS has been adopted in many computing systems. However, the longer a job executes, the more energy in the leakage current the device/processor consumes for the job. To reduce the energy consumption resulting from the leakage current, a system might enter the dormant mode. This paper targets energy-efficient rate-monotonic scheduling for periodic real-time tasks on a uniprocessor DVS system with non-negligible leakage power consumption. An on-line simulated scheduling strategy and a virtually blocking time strategy are developed for procrastination scheduling to reduce energy consumption. The proposed algorithms derive a feasible schedule for real-time tasks with worst-case guarantees for any input instance. Experimental results show that our proposed algorithms could derive energy-efficient solutions.
5871408
Leakage-Aware Energy-Efficient Scheduling of Real-Time Tasks in Multiprocessor Systems
This work targets energy-efficient scheduling of periodic real-time tasks over multiple DVS processors with the considerations of power consumption due to leakage current. A polynomial-time algorithm with a 1.283 approximation bound is proposed when the overheads in turning on/off a processor are negligible. When the overheads are non-negligible, we develop polynomial-time algorithms with a 2 approximation bound. A series of simulation experiments was done for the performance evaluation of the proposed algorithms. The simulation results show that the proposed algorithms could derive schedules very close to optimal solutions.
11672412
Dealing with Node Mobility in Ad Hoc Wireless Network
A Mobile “Ad hoc” wireless NETwork (MANET) is a network established for a special, often extemporaneous service customized to applications. The ad hoc network is typically set up for a limited period of time, in an environment that may change from application to application. As a difference from the Internet where the TCP/IP protocol suite supports a vast range of applications, in the MANET the protocols are tuned to a specific customer and application (eg, send a video stream across the battlefield; find out if there is a fire in the forest; establish a videoconference among several teams engaged in a rescue effort, etc). The customers move and the environment may change dynamically and unpredictably. For the MANET to retain its efficiency, the ad hoc protocols at various layers may need to self-tune to adjust to environment, traffic and mission changes. From these properties emerges the vision of the MANET as an extremely flexible, malleable and yet robust and formidable network architecture. Indeed, an architecture that can be deployed to monitor the habits of birds in their natural habitat, and which, in other circumstances, can be organized to interconnect rescue crews after a Tsunami disaster, or yet can be structured to launch deadly attacks onto unsuspecting enemies.
2221913
A Simple Linear-Time Approximation Algorithm for Multi-processor Job Scheduling on Four Processors
Multiprocessor job scheduling problem has become increasingly interesting, for both theoretical study and practical applications. Theoretical study of the problem has made significant progress recently, which, however, seems not to imply practical algorithms for the problem, yet. Practical algorithms have been developed only for systems with three processors and the techniques seem difficult to extend to systems with more than three processors. This paper offers new observations and introduces new techniques for the multiprocessor job scheduling problem on systems with four processors. A very simple and practical linear time approximation algorithm of ratio bounded by 1:5 is developed for the multi-processor job scheduling problem P4|fix|Cmax, which significantly improves previous results. Our techniques are also useful for multiprocessor job scheduling problems on systems with more than four processors.
41399976
Characterizing Parallel Hierarchies by Reducibilities
Abstract Parallel time bounded reducibilities are discussed. The important parallel hierarchies NC and AC are characterized using a parallel time bounded reducibility. From this point of view, a structural property of the hierarchies NC and AC is easily obtained.
47173629
A Polynomial Time Approximation Scheme for General Multiprocessor Job Scheduling
Recently, there have been considerable interests in the multiprocessor job scheduling problem, in which a job can be processed in parallel on one of several alternative subsets of processors. In this paper, a polynomial time approximation scheme is presented for the problem in which the number of processors in the system is a fixed constant. This result is the best possible because of the strong NP-hardness of the problem and is a significant improvement over the past results: the best previous result was an approximation algorithm of ratio $7/6 + \epsilon$ for 3-processor systems based on Goemans's algorithm for a restricted version of the problem.
42479552
A note on practical construction of maximum bandwidth paths
Constructing maximum bandwidth paths has been a basic operation in the study of network routing, in particular in the recent study of network QoS routing. In the literature, it has been proposed that a maximum bandwidth path be constructed by a modified Dijkstra's algorithm or by a modified Bellman-Ford algorithm. In this short note. we show that maximum bandwidth paths can be constructed by a modified Kruskal's algorithm. We demonstrate that this approach is simpler, easier in implementation, more flexible, and faster than the previously proposed algorithms.