TY - JOUR

T1 - Approximating the optimal algorithm for online scheduling problems via dynamic programming

AU - Chen, Lin

AU - Ye, Deshi

AU - Zhang, Guochuan

N1 - Publisher Copyright:
© 2015 World Scientific Publishing Co. & Operational Research Society of Singapore.

PY - 2015/2/25

Y1 - 2015/2/25

N2 - Very recently Günther et al. [E. Günther, 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ε| ε > 0} with a competitive ratio at most ρ∗(1 + ε), where ρ∗is the best possible competitive ratio over all online algorithms. Along this line, Günther et al. [E. Günther, 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|rj, (pmtn)| ε jcj, 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 Cmax and Rm∑Pi Cpi , 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∥Cmax which runs in polynomial time even if the number of machines is an input. Our method is novel and more efficient than that of Günther et al. [E. Günther, 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 ρ∗, for any online algorithm there exists a list of a polynomial number of jobs showing that its competitive ratio is at least ρ∗- O(ε). Interestingly such a result is achieved via a dynamic programming algorithm. Our framework is also applicable to other online problems.

AB - Very recently Günther et al. [E. Günther, 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ε| ε > 0} with a competitive ratio at most ρ∗(1 + ε), where ρ∗is the best possible competitive ratio over all online algorithms. Along this line, Günther et al. [E. Günther, 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|rj, (pmtn)| ε jcj, 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 Cmax and Rm∑Pi Cpi , 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∥Cmax which runs in polynomial time even if the number of machines is an input. Our method is novel and more efficient than that of Günther et al. [E. Günther, 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 ρ∗, for any online algorithm there exists a list of a polynomial number of jobs showing that its competitive ratio is at least ρ∗- O(ε). Interestingly such a result is achieved via a dynamic programming algorithm. Our framework is also applicable to other online problems.

KW - Competitive analysis

KW - dynamic programming

KW - online scheduling

UR - http://www.scopus.com/inward/record.url?scp=84928494458&partnerID=8YFLogxK

U2 - 10.1142/S0217595915400114

DO - 10.1142/S0217595915400114

M3 - Article

AN - SCOPUS:84928494458

SN - 0217-5959

VL - 32

JO - Asia-Pacific Journal of Operational Research

JF - Asia-Pacific Journal of Operational Research

IS - 1

M1 - 1540011

ER -