Almost Sure Asymptotic Optimality for Online Routing and Machine Scheduling Problems

作者：Jaillet Patrick^*; Wagner Michael R

来源：Networks, 2010, 55(1): 2-12.

DOI：10.1002/net.20309

• online algorithms
• routing
• traveling repairman problem
• machine scheduling

In this article, we study algorithms for online routing and machine scheduling problems. The problems are "online" because the problem instances are revealed incrementally. We first study algorithms for the online Traveling Repairman Problem (TRP), where a single server is to visit a set of locations in a network with the objective of minimizing the sum of weighted completion times. We then analyze well-known online algorithms for a variety of machine scheduling problems, which are appropriate models for many network optimization problems; in the scheduling notation of Graham et al. [18], we consider 1 vertical bar r(j), pmtn vertical bar Sigma(j)w(j)C(j), 1 vertical bar r(j)vertical bar Sigma(j)w(j)C(j), Q vertical bar r(j), pmtn vertical bar Sigma(j)C(j), P vertical bar r(j)vertical bar Sigma(j)C(j), Q vertical bar r(j), pmtn vertical bar Sigma(j)w(j)C(j) and Q vertical bar r(j)vertical bar Sigma(j)w(j)C(j). We introduce general probabilistic assumptions about the problem data as a tool to study the online algorithms for these online combinatorial problems. The algorithms do not utilize the underlying probabilistic assumptions in any way. We prove that these online algorithms are almost surely asymptotically optimal.

• 出版日期2010-1