关于带运输的单机调度在线问题的研究

本文研究了带运输机的单机在线调度问题。问题假设工件实时在线到达，系统中有一台运输机，该运输机每次最多运输$k$个工件，每个工件需要先在单机上完成加工，然后再被运输机运往目的地，问题的优化目标为最小化完工时间，即所有工件被加工完并且运往目的地的时间最短。针对该问题，作者研究了工件满足一致性条件的模型，并且基于贪心思想给出了竞争比为$frac{sqrt{5}+1}{2}$的在线算法，并且证明该算法是最优在线算法。

Online single machine scheduling problem with transportation

This paper studies the single machine online scheduling problem with transporters. The problem assumes that the jobs arrive online over time, and there is only a single transporter in the system, which transports up to $k$ jobs each time. Each job needs to be processed on a single machine, and then transported to the destination by the transporter. The objective of the problem is to minimize the makespan, that is, the shortest time for all jobs to be processed and transported to the destination. For this problem, this paper studies the agreeable model, and proposes an online algorithm with the competitive ratio of $frac{sqrt{5}+1}{2}$ based on the greedy strategy, in the end, the algorithm is proved to be the optimal online algorithm.