We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Multi-processor Search and Scheduling Problems with Setup Cost.
- Authors
Angelopoulos, Spyros; Arsénio, Diogo; Dürr, Christoph; López-Ortiz, Alejandro
- Abstract
We study two optimization problems in a multiprocessor environment in the presence of set-up costs. The first problem involves multiple parallel searchers (e.g., robots) that must locate a target which lies in one of many concurrent rays, and at an unknown position from their common origin. Every time a searcher turns direction, it incurs a turn cost. The objective is to derive a search strategy for locating the target as efficiently as possible. The second problem involves contract algorithms, namely algorithms in which the available computation time is specified prior to their execution. In particular, we seek a schedule of executions of contract algorithms for several different problems in identical parallel processors so as to efficiently simulate an interruptible algorithm, assuming that each execution incurs a given set-up cost. The performance of the search and scheduling strategies are evaluated by means of well-established measures, namely the competitive ratio and the acceleration ratio, respectively. In this paper we provide near-optimal strategies for the above problems, using an approach based on infinite linear-programming formulations. More precisely, we present a search strategy (resp. schedule) which is optimal when the number of rays (resp. problems) is a multiple of the number of searchers (resp. processors). For the general case, we show that the corresponding solutions are very close to optimal.
- Subjects
PRODUCTION scheduling; MATHEMATICAL optimization; ARRAY processors; LINEAR programming; MATHEMATICAL programming
- Publication
Theory of Computing Systems, 2017, Vol 60, Issue 4, p637
- ISSN
1432-4350
- Publication type
Article
- DOI
10.1007/s00224-016-9691-3