Multi-processor Search and Scheduling Problems with Setup Cost

被引:0
|
作者
Spyros Angelopoulos
Diogo Arsénio
Christoph Dürr
Alejandro López-Ortiz
机构
[1] Sorbonne Universités,CNRS and Institut de Mathématiques
[2] UPMC Univ Paris 06,School of Computer Science
[3] CNRS,undefined
[4] LIP6,undefined
[5] Université Paris Diderot,undefined
[6] University of Waterloo Canada,undefined
来源
Theory of Computing Systems | 2017年 / 60卷
关键词
Online search; Scheduling; Linear programming; Anytime algorithms;
D O I
暂无
中图分类号
学科分类号
摘要
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.
引用
收藏
页码:637 / 670
页数:33
相关论文
共 50 条
  • [21] Workload and Variation Aware Thread Scheduling for Heterogeneous Multi-processor
    Lee, Seungwon
    Ro, Won Woo
    18TH IEEE INTERNATIONAL SYMPOSIUM ON CONSUMER ELECTRONICS (ISCE 2014), 2014,
  • [22] Heuristic techniques: Scheduling partially ordered tasks in a multi-processor environment with tabu search and genetic algorithms
    Lin, M
    Karlsson, L
    Yang, LTR
    SEVENTH INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED SYSTEMS: WORKSHOPS, PROCEEDINGS, 2000, : 515 - 523
  • [23] Shared-Memory Multi-Processor Scheduling Algorithms for CCSP
    Ritson, Carl G.
    WOTUG-30: COMMUNICATING PROCESS ARCHITECTURES 2007, 2007, 65 : 509 - 509
  • [24] Photovoltaic-Aware Multi-Processor Scheduling - A Recipe for Research
    Koch, Peter
    TOWARDS GREEN ICT, 2010, 9 : 211 - 228
  • [25] Dynamic Measurement of Task Scheduling Algorithm in Multi-Processor System
    Xie Y.
    Wu J.
    Chen J.
    Cui M.
    Journal of Shanghai Jiaotong University (Science), 2019, 24 (03): : 372 - 380
  • [26] An improved genetic algorithm for task scheduling in multi-processor environment
    Lin, M
    DCABES 2002, PROCEEDING, 2002, : 43 - 46
  • [27] MULTI-PROCESSOR SYSTEMS
    HUGHES, P
    DOONE, T
    MICROELECTRONICS AND RELIABILITY, 1977, 16 (04): : 281 - 293
  • [28] Multi-fold Scheduling Algorithm for Multi-core Multi-Processor Systems
    Gautam, Savita
    Umar, M. Sarosh
    Samad, Abdus
    PROCEEDINGS OF THE 2020 5TH INTERNATIONAL CONFERENCE ON COMPUTING, COMMUNICATION AND SECURITY (ICCCS-2020), 2020,
  • [29] Task scheduling and management in single-chip multi-processor system
    Hu Yue-li
    Wang Yao-ming
    Xuan Xiang-guang
    2008 INTERNATIONAL CONFERENCE ON ELECTRONIC PACKAGING TECHNOLOGY & HIGH DENSITY PACKAGING, VOLS 1 AND 2, 2008, : 382 - +
  • [30] Partitioned scheduling policies on multi-processor mixed-criticality systems
    Gu, Chuan-Cai
    Guan, Nan
    Yu, Jin-Ming
    Wang, Yi
    Deng, Qing-Xu
    Ruan Jian Xue Bao/Journal of Software, 2014, 25 (02): : 284 - 297