ELISA: An Estimated Load Information Scheduling Algorithm for Distributed Computing Systems

In this paper, we present a decentralized dynamic load scheduling/balancing algorithm called ELISA (Estimated Load Information Scheduling Algorithm) for general purpose distributed computing systems. ELISA uses estimated state information based upon periodic exchange of exact state information between neighbouring nodes to perform load scheduling. The primary objective of the algorithm is to cut down on the communication and load transfer overheads by minimizing the frequency of status exchange and by restricting the load transfer and status exchange within the buddy set of a processor. It is shown that the resulting algorithm performs almost as well as a perfect information algorithm and is superior to other load balancing schemes based on the random sharing and Ni-Hwang algorithms. A sensitivity analysis to study the effect of various design parameters on the effectiveness of load balancing is also carried out. Finally, the algorithm's performance is tested on large dimensional hypercubes in the presence of time-varying load arrival process and is shown to perform well in comparison to other algorithms. This makes ELISA a viable and implementable load balancing algorithm for use in general purpose distributed computing systems.

Real-World Extensions To Scheduling Algorithms Based On Lagrangian Relaxation

Recently, efficient scheduling algorithms based on Lagrangian relaxation have been proposed for scheduling parallel machine systems and job shops. In this article, we develop real-world extensions to these scheduling methods. In the first part of the paper, we consider the problem of scheduling single operation jobs on parallel identical machines and extend the methodology to handle multiple classes of jobs, taking into account setup times and setup costs, The proposed methodology uses Lagrangian relaxation and simulated annealing in a hybrid framework, In the second part of the paper, we consider a Lagrangian relaxation based method for scheduling job shops and extend it to obtain a scheduling methodology for a real-world flexible manufacturing system with centralized material handling.

Optimal scheduling of hydro-thermal power systems under shortage

The problem of optimal scheduling of the generation of a hydro-thermal power system that is faced with a shortage of energy is studied. The deterministic version of the problem is first analyzed, and the results are then extended to cases where the loads and the hydro inflows are random variables.

Regional Differences in the Influence of Irrigation on Climate

A global climate model experiment is performed to evaluate the effect of irrigation on temperatures in several major irrigated regions of the world. The Community Atmosphere Model, version 3.3, was modified to represent irrigation for the fraction of each grid cell equipped for irrigation according to datasets from the Food and Agriculture Organization. Results indicate substantial regional differences in the magnitude of irrigation-induced cooling, which are attributed to three primary factors: differences in extent of the irrigated area, differences in the simulated soil moisture for the control simulation (without irrigation), and the nature of cloud response to irrigation. The last factor appeared especially important for the dry season in India, although further analysis with other models and observations are needed to verify this feedback. Comparison with observed temperatures revealed substantially lower biases in several regions for the simulation with irrigation than for the control, suggesting that the lack of irrigation may be an important component of temperature bias in this model or that irrigation compensates for other biases. The results of this study should help to translate the results from past regional efforts, which have largely focused on the United States, to regions in the developing world that in many cases continue to experience significant expansion of irrigated land.

Ways and Means for Disposal of Surplus Water in Storage Reservoirs and other Irrigation and Flood Protective Works

In the paper new way of classifying spillways have been suggested. The various types, merits and demerits or existing spillway devices have been discussed. The considerations governing the choice of a design of a spillway have been mention. A criteria for working out the economics of spillway design has been suggested. An efficient surplus sing device has next been described and compared with other devices. In conclusion it has been suggested that the most efficient and at the same time economical arrangement will be a combination of devices. In conclusion it has been suggested will be a combination of crest gate, volute siphons and high head gates. The appendix gives a list of devices used in dams in various parts of the world.

Bi-criteria single machine scheduling problem with a learning effect: Aneja-Nair method to obtain the set of optimal sequences

In this paper, we consider the bi-criteria single machine scheduling problem of n jobs with a learning effect. The two objectives considered are the total completion time (TC) and total absolute differences in completion times (TADC). The objective is to find a sequence that performs well with respect to both the objectives: the total completion time and the total absolute differences in completion times. In an earlier study, a method of solving bi-criteria transportation problem is presented. In this paper, we use the methodology of solvin bi-criteria transportation problem, to our bi-criteria single machine scheduling problem with a learning effect, and obtain the set of optimal sequences,. Numerical examples are presented for illustrating the applicability and ease of understanding.

Parallel processor scheduling for minimizing total weighted tardiness using ant colony optimization

In the modern business environment, meeting due dates and avoiding delay penalties are very important goals that can be accomplished by minimizing total weighted tardiness. We consider a scheduling problem in a system of parallel processors with the objective of minimizing total weighted tardiness. Our aim in the present work is to develop an efficient algorithm for solving the parallel processor problem as compared to the available heuristics in the literature and we propose the ant colony optimization approach for this problem. An extensive experimentation is conducted to evaluate the performance of the ACO approach on different problem sizes with the varied tardiness factors. Our experimentation shows that the proposed ant colony optimization algorithm is giving promising results compared to the best of the available heuristics.

Distributed Scheduling for Multi-Hop Wireless Networks

We study the performance of greedy scheduling in multihop wireless networks where the objective is aggregate utility maximization. Following standard approaches, we consider the dual of the original optimization problem. Optimal scheduling requires selecting independent sets of maximum aggregate price, but this problem is known to be NP-hard. We propose and evaluate a simple greedy heuristic. We suggest how the greedy heuristic can be implemented in a distributed manner. We evaluate an analytical bound in detail, for the special case of a line graph and also provide a loose bound on the greedy heuristic for the case of an arbitrary graph.

Experiences With WM: A Centralised Scheduling Approach for Performance Management of IEEE 802.11 Wireless LANs

In our earlier work ([1]) we proposed WLAN Manager (or WM) a centralised controller for QoS management of infrastructure WLANs based on the IEEE 802.11 DCF standards. The WM approach is based on queueing and scheduling packets in a device that sits between all traffic flowing between the APs and the wireline LAN, requires no changes to the AP or the STAs, and can be viewed as implementing a "Split-MAC" architecture. The objectives of WM were to manage various TCP performance related issues (such as the throughput "anomaly" when STAs associate with an AP with mixed PHY rates, and upload-download unfairness induced by finite AP buffers), and also to serve as the controller for VoIP admission control and handovers, and for other QoS management measures. In this paper we report our experiences in implementing the proposals in [1]: the insights gained, new control techniques developed, and the effectiveness of the WM approach in managing TCP performance in an infrastructure WLAN. We report results from a hybrid experiment where a physical WM manages actual TCP controlled packet flows between a server and clients, with the WLAN being simulated, and also from a small physical testbed with an actual AP.

Computer-model for vedavati groundwater basin .3. Irrigation potential

An estimate of the irrigation potential over and above the existing utilization was made based on the ground water potential in the Vedavati river basin. The estimate is based on assumed crops and cropping patterns as per existing practice in the various taluks of the basin. Irrigation potential was estimated talukwise based on the available ground water potential identified from the simulation study. It is estimated that 84,100 hectares of additional land can be brought under irrigation from ground water in the entire basin.

Multiobjective Analysis of Irrigation Planning in River Basin Development

A river basin that is extensively developed in the downstream reaches and that has a high potential for development in the upper reaches is considered for irrigation planning. A four-reservoir system is modeled on a monthly basis by using a mathematical programing (LP) formulation to find optimum cropping patterns, subject to land, water, and downstream release constraints. The model is applied to a fiver basin in India. Two objectives, maximizing net economic benefits and maximizing irrigated cropped area, considered in the model are analyzed in the context of multiobjective planning, and the tradeoffs are discussed.

Optimal irrigation planning in river basin development: The case of the Upper Cauvery river basin

The study deals with the irrigation planning of the Cauvery river basin in peninsular India which is extensively developed in the downstream reaches and has a high potential for development in the upper reaches. A four-reservoir system is modelled on a monthly basis by using a mathematical programming (LP) formulation to find optimum cropping patterns, subject to land, water and downstream release constraints, and applied to the Cauvery basin. Two objectives, maximizing net economic benefits and maximizing irrigated cropped area, considered in the model are analysed in the context of multiobjective planning and the trade-offs discussed.

Greedy Scheduling in Multihop Wireless Networks

We study the performance of greedy scheduling in multihop wireless networks where the objective is aggregate utility maximization. Following standard approaches, we consider the dual of the original optimization problem. Optimal scheduling requires selecting independent sets of maximum aggregate price, but this problem is known to be NP-hard. We propose and evaluate a simple greedy heuristic. Analytical bounds on performance are provided and simulations indicate that the greedy heuristic performs well in practice.

A strategy for scheduling tightly coupled parallel applications on clusters

Although various strategies have been developed for scheduling parallel applications with independent tasks, very little work exists for scheduling tightly coupled parallel applications on cluster environments. In this paper, we compare four different strategies based on performance models of tightly coupled parallel applications for scheduling the applications on clusters. In addition to algorithms based on existing popular optimization techniques, we also propose a new algorithm called Box Elimination that searches the space of performance model parameters to determine the best schedule of machines. By means of real and simulation experiments, we evaluated the algorithms on single cluster and multi-cluster setups. We show that our Box Elimination algorithm generates up to 80% more efficient schedule than other algorithms. We also show that the execution times of the schedules produced by our algorithm are more robust against the performance modeling errors.

Cross-Layer Scheduling with Infrequent Channel and Queue Measurements

The downlink scheduling problem in multi-queue multi-server systems under channel uncertainty is considered. Two policies that make allocations based on predicted channel states are proposed. The first is an extension of the well-known dynamic backpressure policy to the uncertain channel case. The second is a variant that improves delay performance under light loads. The stability region of the system is characterised and the first policy is argued to be throughput optimal. A recently proposed policy of Kar et al [1] has lesser complexity, but is shown to be throughput suboptimal. Further, simulations demonstrate better delay and backlog properties for both our policies at light loads.