论文标题
改进了与常见的相同平行机上的早期工作计划的近似方案
Improved approximation schemes for early work scheduling on identical parallel machines with common due date
论文作者
论文摘要
我们研究相同并行机器上的早期工作调度问题，以最大程度地提高早期工作的总工作，即在共同截止日期之前执行的非抢先工作的部分。通过预处理和构建具有多个良好属性的辅助实例，我们提出了一种有效的多项式时间近似方案，其中包括运行时间$ o（n）$，从而改善了[Györgyi，P.，Kis，T。（2020）的结果。早期工作，晚期工作和资源级别问题的常见近似框架。 {\ IT欧洲运营研究杂志}，286（1），129-137]，以及一个完全多项式的时间近似方案，具有运行时间$ O（n）$的完全多项式时间近似方案，当机器数为固定数字时，改善了[Chen，X.，X.，X.，Liang，Y.完全多项式时间近似方案，以最大程度地提高平行机的早期工作，该机器具有共同的截止日期。 {\ IT欧洲运营研究杂志}，284（1），67-74]，其中$ n $是工作数，隐藏的常数取决于所需的准确性。
We study the early work scheduling problem on identical parallel machines in order to maximize the total early work, i.e., the parts of non-preemptive jobs executed before a common due date. By preprocessing and constructing an auxiliary instance which has several good properties, we propose an efficient polynomial time approximation scheme with running time $O(n)$, which improves the result in [Györgyi, P., Kis, T. (2020). A common approximation framework for early work, late work, and resource leveling problems. {\it European Journal of Operational Research}, 286(1), 129-137], and a fully polynomial time approximation scheme with running time $O(n)$ when the number of machines is a fixed number, which improves the result in [Chen, X., Liang, Y., Sterna, M., Wang, W., Błażewicz, J. (2020b). Fully polynomial time approximation scheme to maximize early work on parallel machines with common due date. {\it European Journal of Operational Research}, 284(1), 67-74], where $n$ is the number of jobs, and the hidden constant depends on the desired accuracy.
