Minimising total weighted completion time for semi-online single machine scheduling with known arrivals and bounded processing times
研究半在线单机调度问题，已知未来到达时间和加工时间下界，提出最优半在线算法，其竞争比与理论下界匹配。
This paper addresses the semi-online scheduling problem of minimising the total weighted completion time on a single machine, where a combination of information on jobs release dates and processing times is considered. In this study, jobs can only arrive at known future times and a lower bound on jobs processing times is known in advance. A new semi-online algorithm is presented and is shown to be the best possible for the considered problem. In order to make this statement, a new lower bound on the competitive ratio of any semi-online algorithm for the problem is developed and, using competitive analysis, the proposed semi-online algorithm is shown to have a competitive ratio that matches the lower bound.