Approximating the Optimal Algorithm for Online Scheduling Problems via Dynamic Programming

作者：Chen, Lin; Ye, Deshi; Zhang, Guochuan^*

来源：Asia Pacific Journal of Operational Research, 2015, 32(1): 1540011.

DOI：10.1142/S0217595915400114

• Competitive analysis
• online scheduling
• dynamic programming

Very recently Gunther et al. [E. Gunther, O. Maurer, N. Megow and A. Wiese (2013). A new approach to online scheduling: Approximating the optimal competitive ratio. In Proc. 24th Annual ACM-SIAM Symp. Discrete Algorithms (SODA).] initiate a new systematic way of studying online problems by introducing the competitive ratio approximation scheme (simplified as competitive schemes in this paper), which is a class of algorithms {A(is an element of)vertical bar is an element of> 0} with a competitive ratio at most rho*(1 + is an element of), where rho* is the best possible competitive ratio over all online algorithms. Along this line, Gunther et al. [E. Gunther, O. Maurer, N. Megow and A. Wiese (2013). A new approach to online scheduling: Approximating the optimal competitive ratio. In Proc. 24th Annual ACM-SIAM Symp. Discrete Algorithms (SODA).] provide competitive schemes for several online over time scheduling problems like Qm vertical bar r(j), (pmtn)vertical bar Sigma w(j)c(j), while the running times are polynomial if the number of machines is a constant. In this paper, we consider the classical online scheduling problems, where jobs arrive in a list. We present competitive schemes for Rm parallel to C-max and Rm parallel to Sigma(i) C-i(p), where the running times are polynomial if the number of machines is a constant. Specifically, we are able to derive a competitive scheme for P parallel to C-max which runs in polynomial time even if the number of machines is an input. Our method is novel and more efficient than that of Gunther et al. [E. Gunther, O. Maurer, N. Megow and A. Wiese (2013). A new approach to online scheduling: Approximating the optimal competitive ratio. In Proc. 24th Annual ACM-SIAM Symp. Discrete Algorithms (SODA).] Indeed, by utilizing the standard rounding technique for the off-line scheduling problems, we reformulate the online scheduling problem into a game on an infinite graph, through which we arrive at the following key point: Assuming that the best competitive ratio is rho*, for any online algorithm there exists a list of a polynomial number of jobs showing that its competitive ratio is at least rho* - O(is an element of). Interestingly such a result is achieved via a dynamic programming algorithm. Our framework is also applicable to other online problems.

• 出版日期2015-2
• 单位浙江大学