DOI: 10.1142/S0129054111008271

March 30, 2011 14:17 WSPC/INSTRUCTION FILE S0129054111008271

International Journal of Foundations of Computer Science

Vol. 22, No. 3 (2011) 639–656 c© World Scientific Publishing Company

APPROXIMATING THE DISCRETE RESOURCE SHARING

SCHEDULING PROBLEM

MARIN BOUGERET∗, PIERRE-FRANC¸OIS DUTOT†,

ALFREDO GOLDMAN‡, YANIK NGOKO§ and DENIS TRYSTRAM

LIG, Grenoble University, 51 avenue J. Kuntzmann 38330 Montbonnot, France †Pierre-Francois.Dutot@imag.fr

Received 20 July 2009

Accepted 2 March 2010

Communicated by Jacir L. Bordir

The goal of this work is to study the portfolio problem which consists in finding a good combination of multiple heuristics given a set of a problem instances to solve.

We are interested in a parallel context where the resources are assumed to be discrete and homogeneous, and where it is not possible to allocate a given resource (processor) to more than one heuristic. The objective is to minimize the average completion time over the whole set of instances. We extend in this paper some existing analysis on the problem. More precisely, we provide a new complexity result for the restricted version of the problem, then, we generalize previous approximation schemes. In particular, they are improved using a guess approximation technique. Experimental results are also provided using a benchmark of instances on SAT solvers.

Keywords: Resource allocation; combining algorithms; approximation schemes; oracleguess approximation; SAT solver. 1. Introduction 1.1. Description of the Portfolio problem

We are interested in this work in solving hard computational problems like the satisfiability problem SAT [11]. It is well-established that a single algorithm cannot solve efficiently all the instances of such problems. In most cases, the algorithms are characterized by the great variability of their execution time depending on the considered instances. Thus, a good effective solution is to consider several heuristics and combine them in such a way to improve the mean execution time when solving a large set of instances. In this paper, we are interested in designing adequate combination schemes. ∗Marin Bougeret has a PhD grant from DGA-CNRS. ‡Alfredo Goldman has been partially supported by the MINALOGIC project SCEPTRE funded by Region Rhone-Alpes in France. §Yanik Ngoko was sponsored by the international exchange program EGIDE. 639

March 30, 2011 14:17 WSPC/INSTRUCTION FILE S0129054111008271 640 M. Bougeret et al.

The suggested solution is based on the portfolio problem, introduced in the field of finance many years ago [14]. This problem can be informally recalled as follows: given a set of opportunities, an amount of possible investments on the set of opportunities and the payoff obtained when investing an amount on each opportunity, what is the best amount of investment to make on each opportunity in order to maximize the sum of the payoffs? Using the vocabulary of Computer Science, we assume that there exists a benchmark composed of a finite set of instances and some heuristics which solve these instances. The expected execution times of heuristics on all the instances is known. The objective is to determine the best possible resource allocation for the heuristics in order to minimize the mean execution time of the set of instances. The execution time of an instance given a resource allocation is taken here as the shortest execution time of a heuristic when executing simultaneously all the heuristics on this instance.

This formulation of the problem as a portfolio is motivated by the fact that we may not know which is the best suited heuristic to solve an instance before actually solving it. The interest of this sharing model is that in practice if the benchmark of instances is representative over the set to be solved, we can expect a better mean execution time than using only one heuristic. 1.2. Related works

There exist many studies focusing on the construction of automated heuristic selection process. For a given problem, the approaches usually proceed first by identifying the set of features which characterize its instances. A matching is then built between types of instances and heuristics in order to determine an efficient heuristic for any instance.

An et al. [2], for example, introduce a generic framework for heuristic selection in a parallel context and apply it to several classical problems including sorting and parallel reductions. Weerawarana et al. [21] suggest a model for the heuristics selection in the case of the resolution of partial differential equations. The SALSA project (Self Adapting Large-scale Solver Architecture) uses statistical techniques for solver selection [8]. Bhowmick et al. [3] study the construction of a selection process for solving linear systems. The construction of automated selection process requires the identification of a representative set of features. This can be very difficult depending on the targeted problems [8].

There exist other alternative works based on heuristic portfolio that can be used in these cases. A portfolio of heuristics is a collection of different algorithms (or algorithms with different parameters) running in an interleaved scheme. In [12, 13], the authors have demonstrated the interest to use heuristic portfolio on randomized heuristics. The concurrent use of heuristics for solving an instance has also been suggested in [7, 20] with the concept of asynchronous team. Streeter et al. [19] studied how to interleave the execution of various heuristics in order to reduce the execution time of a set of instances.

March 30, 2011 14:17 WSPC/INSTRUCTION FILE S0129054111008271

Approximating the Discrete Resource Sharing Scheduling Problem 641

Sayag et al. [15] have also studied a related problem, namely the time switching problem. This problem considers a finite set of instances and assumes a finite set of interruptible heuristics. To solve instances, the execution of the various heuristics are interleaved in a fixed pattern of time intervals. The execution ends as soon as one heuristic solves the current instance. As previously, the goal in the task switching problem is to find a schedule which minimizes the mean execution time on the set of instances. This approach is interesting in a single resource problem and has also been studied by Streeter et al. [19]. Sayag et al. [15] proved that to each resource sharing schedule corresponds a time switching with a lower execution time, which means that if there is no overhead on context switching, it is always better to use time slicing on the heuristics on the whole resources instead of applying resource sharing. Even if the time switching approach produces theoretically schedules with constant approximation ratio, it assumes that the heuristics can be interrupted at any moment. However, all the interrupted states have to be stored, leading to a prohibitive memory cost on multiple resources.