A best possible algorithm for an online scheduling problem with position-based learning effect

In this paper, we focus on an online scheduling problem with position-based learning effect on a single machine, where the jobs are released online over time and preemption is not allowed. The information about each job \begin{document}$ J_j $\end{document} , including the basic processing time \begin{document}$ p_j $\end{document} and the release time \begin{document}$ r_j $\end{document} , is only available when it arrives. The actual processing time \begin{document}$ p_j' $\end{document} of each job \begin{document}$ J_j $\end{document} is defined as a function related to its position \begin{document}$ r $\end{document} , i.e., \begin{document}$ p_j' = p_j(\alpha-r\beta) $\end{document} , where \begin{document}$ \alpha $\end{document} and \begin{document}$ \beta $\end{document} are both nonnegative learning index. Our goal is to minimize the sum of completion time of all jobs. For this problem, we design a deterministic polynomial time online algorithm Delayed Shortest Basic Processing Time (DSBPT). In order to facilitate the understanding of the online algorithm, we present a relatively common and simple example to describe the execution process of the algorithm, and then by competitive analysis, we show that online algorithm DSBPT is a best possible online algorithm with a competitive ratio of 2.