Design of Scheduling Algorithms Using Game Theoretic Ideas

Scheduling a set of jobs over a collection of machines to optimize a certain quality-of-service measure is one of the most important research topics in both computer science theory and practice. In this thesis, we design algorithms that optimize {\em flow-time} (or delay) of jobs for scheduling problems that arise in a wide range of applications. We consider the classical model of unrelated machine scheduling and resolve several long standing open problems; we introduce new models that capture the novel algorithmic challenges in scheduling jobs in data centers or large clusters; we study the effect of selfish behavior in distributed and decentralized environments; we design algorithms that strive to balance the energy consumption and performance.

The technically interesting aspect of our work is the surprising connections we establish between approximation and online algorithms, economics, game theory, and queuing theory. It is the interplay of ideas from these different areas that lies at the heart of most of the algorithms presented in this thesis.

The main contributions of the thesis can be placed in one of the following categories.

1. Classical Unrelated Machine Scheduling: We give the first polygorithmic approximation algorithms for minimizing the average flow-time and minimizing the maximum flow-time in the offline setting. In the online and non-clairvoyant setting, we design the first non-clairvoyant algorithm for minimizing the weighted flow-time in the resource augmentation model. Our work introduces iterated rounding technique for the offline flow-time optimization, and gives the first framework to analyze non-clairvoyant algorithms for unrelated machines.

2. Polytope Scheduling Problem: To capture the multidimensional nature of the scheduling problems that arise in practice, we introduce Polytope Scheduling Problem (\psp). The \psp problem generalizes almost all classical scheduling models, and also captures hitherto unstudied scheduling problems such as routing multi-commodity flows, routing multicast (video-on-demand) trees, and multi-dimensional resource allocation. We design several competitive algorithms for the \psp problem and its variants for the objectives of minimizing the flow-time and completion time. Our work establishes many interesting connections between scheduling and market equilibrium concepts, fairness and non-clairvoyant scheduling, and queuing theoretic notion of stability and resource augmentation analysis.

3. Energy Efficient Scheduling: We give the first non-clairvoyant algorithm for minimizing the total flow-time + energy in the online and resource augmentation model for the most general setting of unrelated machines.

4. Selfish Scheduling: We study the effect of selfish behavior in scheduling and routing problems. We define a fairness index for scheduling policies called {\em bounded stretch}, and show that for the objective of minimizing the average (weighted) completion time, policies with small stretch lead to equilibrium outcomes with small price of anarchy. Our work gives the first linear/ convex programming duality based framework to bound the price of anarchy for general equilibrium concepts such as coarse correlated equilibrium.

Superresolution: an ill-posed problem in Fourier optics

info:eu-repo/semantics/published

The Superresolution Problem in Doppler Difference Laser Anemometry

info:eu-repo/semantics/published

Equilibrium structure of the hydrogen bonded dimer H2O ⋯ HF

The equilibrium structure of the hydrogen bonded complex H2O HF has been calculated ab initio using the CCSD(T) method with basis sets up to sextuple- quality with diffuse functions and taking into account the basis set superposition error correction. The calculations carried out confirm the importance of diffuse functions and of counterpoise correction to obtain an accurate geometry. The most important point is that the basis set convergence is extremely slow and, for this reason an accurate ab initio structure requires a very large basis set. Nevertheless, the ab initio structure is significantly different from the experimental r0 and rm structures. Analysis of the basis set convergence and of the approximations used for the determination of the experimental structures indicates that the ab initio structure is expected to be more reliable.

Comparison of the experimental, semi-experimental and ab initio equilibrium structures of acetylene: Influence of relativisitic effects and of the diagonal Born-Oppenheimer corrections

The equilibrium structure of acetylene (also named ethyne) has been reinvestigated to resolve the small discrepancies noted between different determinations. The size of the system as well as the large amount of available experimental data provides the quite unique opportunity to check the magnitude and relevance of various contributions to equilibrium structure as well as to verify the accuracy of experimental results. With respect to pure theoretical investigation, quantum-chemical calculations at the coupled-cluster level have been employed together with extrapolation to the basis set limit, consideration of higher excitations in the cluster operator, inclusion of core correlation effects as well as relativistic and diagonal Born-Oppenheimer corrections. In particular, it is found that the extrapolation to the complete basis set limit, the inclusion of higher excitations in the electronic-correlation treatment and the relativistic corrections are of the same order of magnitude. It also appears that a basis set as large as a core-valence quintuple-zeta set is required for accurately accounting for the inner-shell correlation contribution. From a pure experimental point of view, the equilibrium structure has been determined using very accurate rotational constants recently obtained by a global analysis (that is to say that all non-negligible interactions are explicitely included in the Hamiltonian matrix) of rovibrational spectra. Finally, a semi-experimental equilibrium structure (where the equilibrium rotational constants are obtained from the experimental ground state rotational constants and computed rovibrational corrections) has been obtained from the available experimental ground-state rotational constants for ten isotopic species corrected for computed vibrational corrections. Such a determination led to the revision of the ground-state rotational constants of two isotopologues, thus showing that structural determination is a good method to identify errors in experimental rotational constants. The three structures are found in a very good agreement, and our recommended values are rCC 120.2958(7) pm and rCH 106.164(1) pm. © 2011 American Institute of Physics.

Description of a procedure to identify strategies: The case of the tiles problem

In this paper we present a procedure to describe strategies in problems which can be solved using inductive reasoning. This procedure is based on some aspects of the analysis of the specific subject matter, concretely on the elements, the representation systems and the transformations involved. We show an example of how we used this procedure for the tiles problem. Finally we present some results and conclusions.

Nested heuristic methods for the location-routeing problem

The concept of 'nested methods' is adopted to solve the location-routeing problem. Unlike the sequential and iterative approaches, in this method we treat the routeing element as a sub-problem within the larger problem of location. Efficient techniques that take into account the above concept and which use a neighbourhood structure inspired from computational geometry are presented. A simple version of tabu search is also embedded into our methods to improve the solutions further. Computational testing is carried out on five sets of problems of 400 customers with five levels of depot fixed costs, and the results obtained are encouraging.

The open shop scheduling problem with a given sequence of jobs on one machine

The paper considers the open shop scheduling problem to minimize the make-span, provided that one of the machines has to process the jobs according to a given sequence. We show that in the preemptive case the problem is polynomially solvable for an arbitrary number of machines. If preemption is not allowed, the problem is NP-hard in the strong sense if the number of machines is variable, and is NP-hard in the ordinary sense in the case of two machines. For the latter case we give a heuristic algorithm that runs in linear time and produces a schedule with the makespan that is at most 5/4 times the optimal value. We also show that the two-machine problem in the nonpreemptive case is solvable in pseudopolynomial time by a dynamic programming algorithm, and that the algorithm can be converted into a fully polynomial approximation scheme. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 705–731, 1998

The many-to-many location-routing problem

In this paper the many to many location routing problem is introduced, and its relationship to various problems in distribution management is emphasised. Useful mathematical formulations which can be easily extended to cater for other related problems are produced. Techniques for tackling this complex distribution problem are also outlined.

Analysis of species hyper-diversity in the tropical rain forests of Indonesia: the problem of non-observance

The main interest in the assessment of forest species diversity for conservation purposes is in the rare species. The main problem in the tropical rain forests is that most of the species are rare. Assessment of species diversity in the tropical rain forests is therefore often concerned with estimating that which is not observed in recorded samples. Statistical methodology is therefore required to try to estimate the truncated tail of the species frequency distribution, or to estimate the asymptote of species/diversity-area curves. A Horvitz-Thompson estimator of the number of unobserved (“virtual”) species in each species intensity class is proposed. The approach allows a definition of an extended definition of diversity, ( or generalised Renyi entropy). The paper presents a case study from data collected in Jambi, Sumatra, and the “extended diversity measure” is used on the species data.

Existence, recurrence and equilibrium properties of Markov branching processes with instantaneous immigration

Attention has recently focussed on stochastic population processes that can undergo total annihilation followed by immigration into state j at rate αj. The investigation of such models, called Markov branching processes with instantaneous immigration (MBPII), involves the study of existence and recurrence properties. However, results developed to date are generally opaque, and so the primary motivation of this paper is to construct conditions that are far easier to apply in practice. These turn out to be identical to the conditions for positive recurrence, which are very easy to check. We obtain, as a consequence, the surprising result that any MBPII that exists is ergodic, and so must possess an equilibrium distribution. These results are then extended to more general MBPII, and we show how to construct the associated equilibrium distributions.

Heuristics for the two-stage job shop scheduling problem with a bottleneck machine

The paper considers the job shop scheduling problem to minimize the makespan. It is assumed that each job consists of at most two operations, one of which is to be processed on one of m⩾2 machines, while the other operation must be performed on a single bottleneck machine, the same for all jobs. For this strongly NP-hard problem we present two heuristics with improved worst-case performance. One of them guarantees a worst-case performance ratio of 3/2. The other algorithm creates a schedule with the makespan that exceeds the largest machine workload by at most the length of the largest operation.

Group technology approach to the open shop scheduling problem with batch setup times

This paper studies the problem of scheduling jobs in a two-machine open shop to minimize the makespan. Jobs are grouped into batches and are processed without preemption. A batch setup time on each machine is required before the first job is processed, and when a machine switches from processing a job in some batch to a job of another batch. For this NP-hard problem, we propose a linear-time heuristic algorithm that creates a group technology schedule, in which no batch is split into sub-batches. We demonstrate that our heuristic is a -approximation algorithm. Moreover, we show that no group technology algorithm can guarantee a worst-case performance ratio less than 5/4.