论文标题
一个在线联合补货问题与单机调度相结合
An online joint replenishment problem combined with single machine scheduling
论文作者
论文摘要
本文考虑了联合补货问题与单个机器计划的结合。有一个资源，所有作业都需要，并且只有机器才能在$ t $上处理另一个作业，并且在发布日期和$ t $之间补充了资源，就可以在计算机上的时间点$ t $启动作业。每个补给都有一个成本，这与补充金额无关。目的是最大程度地降低总补货成本，加上工作的最大流动时间。 我们考虑了问题的在线变体，即随着时间的推移，在其中释放了作业，并且一旦将作业插入了时间表，就无法更改其启动时间。我们为一般输入提出了一种确定性的2竞争性在线算法。此外，我们表明，对于某些类别的输入（所谓的$ p $结合输入），算法的竞争比率倾向于$ \ sqrt {2} $，因为工作数量倾向于无限。在各种假设下，我们还可以得出几个确定性在线算法的最佳竞争比率。
This paper considers a combination of the joint replenishment problem with single machine scheduling. There is a single resource, which is required by all the jobs, and a job can be started at time point $t$ on the machine if and only the machine does not process another job at $t$, and the resource is replenished between its release date and $t$. Each replenishment has a cost, which is independent of the amount replenished. The objective is to minimize the total replenishment cost plus the maximum flow time of the jobs. We consider the online variant of the problem, where the jobs are released over time, and once a job is inserted into the schedule, its starting time cannot be changed. We propose a deterministic 2-competitive online algorithm for the general input. Moreover, we show that for a certain class of inputs (so-called $p$-bounded input), the competitive ratio of the algorithm tends to $\sqrt{2}$ as the number of jobs tends to infinity. We also derive several lower bounds for the best competitive ratio of any deterministic online algorithm under various assumptions.
