The Markov Model Based Algorithm to Predict Networking Load on the Computational Grid

The computational Grid is currently gaining in popularity, and it enables computers scattered all over the world to be connected by the Internet as if they are part of a large computational infrastructure. While the computational Grid gathers more and more computational resources and the number of the applications for the computational Grid is increasing, load balancing for the computational Grid is still not effective enough. Because the computers are connected by a wide area network on the computational Grid, the significant communication latency and the frequency of large wave throughputs make it difficult to achieve effective load balancing. Thus, in this paper, we propose an algorithm to predict networking loads on the computational Grid to make the use of computational resources more efficient. The proposed algorithm based on the Markov model is evaluated using an actual networking load. As a result, the Markov model based algorithm offers the most accurate predictions compared with the related work. This revised version was published online in July 2006 with corrections to the Cover Date.     

An approximation result for the interval coloring problem on claw-free chordal graphs

We study the problem of finding an acyclic orientation of an undirected graph, such that each (oriented) path is covered by a limited number k of maximal cliques. This is equivalent to finding a k-approximate solution for the interval coloring problem on a graph. We focus our attention on claw-free chordal graphs, and show how to find an orientation of such a graph in linear time, which guarantees that each path is covered by at most two maximal cliques. This extends previous published results on other graph classes where stronger assumptions were made.     

P‖Cmin随机算法研究

本文研究了P‖Cmin的随机算法及其最坏情况界，我们给出了Pm‖Cmin在线排序问题新的随机上界，并给出了P2‖Cmin的最好随机算法，其最坏情况界为2／3。对P2‖Cmin已知工件加工时间递减半在线模型，我们给出了一最坏情况界为6／7的随机算法并证明了它为最好的。     

On optimal polling policies

In a single-server polling system, the server visits the queues according to a routing policy and while at a queue, serves some or all of the customers there according to a service policy. A polling (or scheduling) policy is a sequence of decisions on whether to serve a customer, idle the server, or switch the server to another queue. The goal of this paper is to find polling policies that stochastically minimize the unfinished work and the number of customers in the system at all times. This optimization problem is decomposed into three subproblems: determine the optimal action (i.e., serve, switch, idle) when the server is at a nonempty queue; determine the optimal action (i.e., switch, idle) when the server empties a queue; determine the optimal routing (i.e., choice of the queue) when the server decides to switch. Under fairly general assumptions, we show for the first subproblem that optimal policies are greedy and exhaustive, i.e., the server should neither idle nor switch when it is at a nonempty queue. For the second subproblem, we prove that in symmetric polling systems patient policies are optimal, i.e., the server should stay idling at the last visited queue whenever the system is empty. When the system is slotted, we further prove that non-idling and impatient policies are optimal. For the third subproblem, we establish that in symmetric polling systems optimal policies belong to the class of Stochastically Largest Queue (SLQ) policies. An SLQ policy is one that never routes the server to a queue known to have a queue length that is stochastically smaller than that of another queue. This result implies, in particular, that the policy that routes the server to the queue with the largest queue length is optimal when all queue lengths are known and that the cyclic routing policy is optimal in the case that the only information available is the previous decisions.This work was supported in part by NSF under Contract ASC-8802764.     

Analysis of a queueing system with a general service scheduling function,with applications to telecommunication network traffic control

In this paper we analyze a queueing system with a general service scheduling function. There are two types of customer with different service requirements. The service order for customers of each type is determined by the service scheduling function α_k(i, j) where α_k(i, j) is the probability for type-k customer to be selected when there are i type-1 and j type-2 customers. This model is motivated by traffic control to support traffic streams with different traffic characteristics in telecommunication networks (in particular, ATM networks). By using the embedded Markov chain and supplementary variable methods, we obtain the queue-length distribution as well as the loss probability and the mean waiting time for each type of customer. We also apply our model to traffic control to support diverse traffics in telecommunication networks. Finally, the performance measures of the existing diverse scheduling policies are compared. We expect to help the system designers select appropriate scheduling policy for their systems.     

Coal bank scheduling using a mathematical programming model

Coals are extracted from mines and upgraded on the surface for customers. The upgraded coals must be aged at least four weeks in a bank before being supplied to customers. Different sizes of banks are required for different lengths of time at different points in time. Bigger banks increase the floor space capacity and reduce handling costs. The proper location of banks reduces the total space requirement and bank movement after building. In this paper, we address the bank size and location problem and solve it by using a mathematical programming approach.     

A scheduling policy with maximal stability region for ring networks with spatial reuse

A slotted ring that allows simultaneous transmissions of messages by different users is considered. Such a ring network is commonly called ring withspatial reuse. It can achieve significantly higher throughput than standard token rings but it also raises the issue of fairness since some nodes may be prevented from accessing the ring for long time intervals. Policies that operate in cycles and guarantee that a certain number (quota) of packets will be transmitted by every node in every cycle have been considered before to deal with the fairness issue. In this paper we address the problem of designing a policy that results in a stable system whenever the end-to-end arrival rates are within the stability region of the ring with spatial reuse (the stability region of the ring is defined as the set of end-to-end arrival rates for which there is a policy that makes the ring stable). We provide such a policy, which does not require knowledge of end-to-end arrival rates. The policy is an adaptive version of the quota policies and can be implemented with the same distributed mechanism. We use the Lyapunov test function technique together with methods from the theory of regenerative processes to derive our main results.This research was primarily done while the author was visiting INRIA in Rocquencourt, France. The author wishes to thank INRIA (projects ALGO, MEVAL and REFLECS) for a generous support. Additional support was provided by NSF Grants NCR-9206315 and CCR-9201078 and INT-8912631, and by Grant AFOSR-90-0107, and in part by NATO Grant 0057/89.The research of this author was supported in part by NSF under Grants NCR-9211417 and NCR-9406415, and by the New York State Center for Advanced Technology in Telecommunications, Polytechnic University.     

Dual decomposition of a single-machine scheduling problem

We design a fast ascent direction algorithm for the Lagrangian dual problem of the single-machine scheduling problem of minimizing total weighted completion time subject to precedence constraints. We show that designing such an algorithm is relatively simple if a scheduling problem is formulated in terms of the job completion times rather than as an 0–1 linear program. Also, we show that upon termination of such an ascent direction algorithm we get a dual decomposition of the original problem, which can be exploited to develop approximative and enumerative approaches for it. Computational results exhibit that in our application the ascent direction leads to good Lagrangian lower and upper bounds.     

Heuristics Based on Partial Enumeration for the Unrelated Parallel Processor Scheduling Problem

The classical deterministic scheduling problem of minimizing the makespan on unrelated parallel processors is known to be NP-hard in the strong sense. Given the mixed integer linear model with binary decision variables, this paper presents heuristic algorithms based on partial enumeration. Basically, they consist in the construction of mixed integer subproblems, considering the integrality of some subset of variables, formulated using the information obtained from the solution of the linear relaxed problem. Computational experiments are reported for a collection of test problems, showing that some of the proposed algorithms achieve better solutions than other relevant approximation algorithms published up to now.     

A branch and bound algorithm for scheduling trains in a railway network

The paper studies a train scheduling problem faced by railway infrastructure managers during real-time traffic control. When train operations are perturbed, a new conflict-free timetable of feasible arrival and departure times needs to be re-computed, such that the deviation from the original one is minimized. The problem can be viewed as a huge job shop scheduling problem with no-store constraints. We make use of a careful estimation of time separation among trains, and model the scheduling problem with an alternative graph formulation. We develop a branch and bound algorithm which includes implication rules enabling to speed up the computation. An experimental study, based on a bottleneck area of the Dutch rail network, shows that a truncated version of the algorithm provides proven optimal or near optimal solutions within short time limits.