Through recent technical advances, multiple resources can be connected to provide a computing grid for processing computationally intensive applications. We build on an approach, termed sequential grid computing, that takes advantage of idle processing power by routing jobs that require lengthy processing through a sequence of processors. We present two models that solve the static and dynamic versions of the sequential grid scheduling problem for a single job. In the static and dynamic versions, the model maximizes a reward function tied to the probability of completion within service-level agreement parameters. In the dynamic version, the static model is modified to accommodate real-time deviations from the plan. We then extend the static model to accommodate multiple jobs. Extensive computational experiments highlight situations (a) where the models provide improvements over scheduling the job on a single processor and (b) where certain factors affect the quality of solutions obtained.

Modern applications are built using object-oriented (OO) principles. Unfortunately, OO technologies, though they add tremendous functionality and flexibility to applications, require significant computational power, which greatly affects the performance and scalability of the applications. Caching objects in memory is a popular way to solve this problem, but the available memory in systems is limited and not sufficient to store each instance of every enterprise application object. Deciding which instances of which objects should be cached is a two-stage process. The first stage is selecting the objects, and the second stage is selecting the object instances. The second stage, typically referred to as a replacement policy, occurs at run-time and has been widely studied. The focus of this paper is the first stage: selecting objects whose instances are candidates for caching at run-time. In current systems, this critical step is performed in an ad hoc manner. We build a nonlinear mathematical model for this problem, develop a feasible solution procedure based on genetic algorithms, and demonstrate its effectiveness by comparing the solution quality to lower bounds obtained using a Lagrangian-relaxation-based method.

In this paper, we study the problem of the design of telecommunication access networks with reliability constraints. These networks form an important part of the telecommunications infrastructure of large organizations, such as banks. Using data patterned after an actual bank network in the U.S., we formulate an optimization model for this problem which specifically takes into account the various cost, and discount structures offered by telecommunication carriers. We then develop dedicated solution procedures for obtaining solutions. Starting from a cluster solution, we then use perturbation techniques which we developed specifically for this problem within an overall simulated annealing solution algorithm. We show how to make the solution procedure more efficient by implicitly determining the values for many variables. We then report the results of our computational testing for a variety of problems. We compare our solution to a lower bound obtained using a linear programming relaxation. We show that substantial cost savings can be realized with our model, and solution procedure. Finally, we discuss which types of annealing steps in the simulated annealing algorithm are important.

Push-based information delivery technology is commonly expressed as a broadcast solution where the information is pushed to a channel where all receivers can tap into. In this context, prior work has explored how to broadcast and what to broadcast. However, one problem not addressed so far is providing secure access control in broadcast schemes. Furthermore, existing broadcast work does not consider a subscription-based access scheme which is conceivable for most commodities. In this paper, we present existing secure access control schemes and adapt them to the broadcasting scenario, and outline their limitations in this environment. We propose a new protocol, single encoding multiple decoding (SEMD), to handle secure access and subscription services for broadcast. The superior performance of SEMD is demonstrated via a a simulation study of existing protocols and our protocol in a mobile computing environment.

The problem of database allocation incorporating a specific concurrency control mechanism and queuing delays is addressed in this paper. A mathematical model is presented to aid designers in the development of distributed database systems. The model takes into account the pattern of usage of the databases, communication costs in the network, costs for maintaining consistency among the various copies of a database, and storage costs. A solution procedure based on the principle of Lagrangian relaxation is proposed to solve the model. Some analysis of the model is reported along with several useful observations. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

This paper addresses the problem of selecting primary and secondary routes for every pair of communicating nodes in a backbone computer network. A primary route and a secondary route constitute a route pair. The secondary route is node-disjoint (and hence also link-disjoint) from the primary route. A mathematical programming model is developed whose objective is to select routes to minimize the mean delay faced by messages. The model captures situations where a single link or node failure would divert traffic to the appropriate secondary routes. A solution procedure based on a relaxation of the problem is presented. Computational results indicate the effectiveness of the solution procedure. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

A model is developed that assigns primary and secondary (backup) concentrator coverage to each terminal site. The objective is to minimize communications costs as well as costs for setting up and operating the concentrators subject to capacity constraints. A relaxation of the problem is studied, and an effective solution procedure that makes the use of this relaxation is developed. Experimental results over a wide range of problem structures show that this solution procedure is very effective. It is also found to be significantly faster than a state-of-the-art commercial integer programming package.>