TSP Race: Minimizing completion time in time-sensitive applications

ÇAVDAR B., Sokol J.

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, cilt.244, sa.1, ss.47-54, 2015 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 244 Sayı: 1
  • Basım Tarihi: 2015
  • Doi Numarası: 10.1016/j.ejor.2014.12.022
  • Dergi Adı: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.47-54
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

In this paper, we present an approach for parallelizing computation and implementation time for problems where the objective is to complete the solution as soon after receiving the problem instance as possible. We demonstrate the approach on the TSP. We define the TSP race problem, present a computation-implementation parallelized (CIP) approach for solving it, and demonstrate CIP's effectiveness on TSP Race instances. We also demonstrate a method for determining a priori when CIP will be effective. Although in this paper we focus on TSP, our general CIP approach can be effective on other problems and applications with similar time sensitivity. (C) 2014 Elsevier B.V. All rights reserved.