We consider online competitive algorithms for the problem of collecting weighted items from a dynamic queue S . The content of S varies over time. An update to S can occur between any two consecutive time steps, and it consists in deleting any number of items at the front of S and inserting other items into arbitrary locations in S . At each time step we are allowed to collect one item in S . The objective is to maximize the total weight of collected items. This is a generalization of bounded-delay packet scheduling (also known as buffer management). We present several upper and lower bounds on the competitive ratio for the general case and for some restricted variants of this problem.

We consider the problem of collecting weighted items from a dynamic queue . Before each step, some items at the front of can be deleted and some other items can be added to at any place. An item, once deleted, cannot be re-inserted — in other words, it “expires”. We are allowed to collect one item from per step. Each item can be collected only once. The objective is to maximize the total weight of the collected items. We study the online version of the dynamic queue problem. It is quite easy to see that the greedy algorithm that always collects the maximum-value item is 2-competitive, and that no deterministic online algorithm can be better than 1.618-competitive. We improve both bounds: We give a 1.89-competitive algorithm for general dynamic queues and we show a lower bound of 1.632 on the competitive ratio. We also provide other upper and lower bounds for restricted versions of this problem. The dynamic queue problem is a generalization of the well-studied buffer management problem, and it is an abstraction of the buffer management problem for network links with intermittent access.

In queue-based scheduling systems jobs are executed according to a predefined sequential plan. During exe- cution, faults may occur that cause jobs to re-execute, thus delaying the whole schedule. It is thus important to determine (in real-time) whether the given set of pre- ordered jobs is fault-tolerant, that is, if all jobs will al- ways meet their deadlines. This allows, for instance, to decide online whether to admit a new urgent job into the queue while still guaranteeing that the whole sched- ule remains fault-tolerant. Our goal in this work is to design efficient algorithm for testing fault tolerance of sequenced jobs in the presence of transient faults. We consider different fault models that specify which fault patterns are allowed to occur and how soon failed jobs can be restarted. For each fault model we provide ef- ficient algorithms that determine the feasibility of all jobs in the schedule. Our algorithms are exact and run in time linear in the number of jobs (deterministically, or with very high probability, depending on the fault model), and thus can be used to make real-time deci- sions.