单机分批排序问题1|B，rj，sj| Lmax近似算法研究

"这篇论文探讨了单机分批排序问题1|B，rj，sj| Lmax，其中工件具有到达时间、加工时间和尺寸，目标是最小化最大延误时间。当机器容量B为常数时，即使在B=2且工件的到达时间和尺寸相同的情况下，该问题也被证明为强NPC。论文基于问题1|B，rj| Lmax的PTAS算法，设计了一个新的多项式时间近似算法，其最差性能比为2+ε，ε为任意小的正数。作者包括陈俊和吴翠连，发表在2012年的《曲阜师范大学学报》上，涉及的领域是自然科学和论文研究。" 正文: 本文深入研究了分批排序问题的一个变种，即1|B，rj，sj| Lmax问题。在这个问题中，每个工件不仅有加工时间和到达时间，还有尺寸的限制，而优化目标是尽可能地减少所有工件的最大延误时间。论文指出，当机器的容量B为常数时，即使简单情况如B=2且所有工件的到达时间和尺寸相同，该问题也属于强NPC（非确定性多项式时间完全难问题），意味着没有已知的多项式时间精确解法。 作者们借鉴了针对问题1|B，rj| Lmax的多项式时间近似解决方案——PTAS算法，该算法在最坏情况下的性能比最优解好。PTAS算法通常在寻找近似解时非常有效，尤其是在处理NP难问题时。在此基础上，他们提出了一种新的近似算法，允许工件按照尺寸进行拆分。新算法能够在多项式时间内完成，且分析表明其最差性能比为2+ε，这里的ε是任意小的正数，这意味着它能保证接近最优解的效率。 分批排序问题在现实世界中有广泛的应用，比如半导体制造、航空工业、钢铁铸造和制鞋业等。由于其复杂性和实用性，吸引了大量的研究者进行理论和应用上的探索。历史上，经典的排序问题如1|1| Lmax已经有了O(nlogn)的最优算法，但对于更复杂的情况，如1|B，rj，sj| Lmax，通常需要采用近似算法来寻求可接受的解决方案。 Leslie A. Hall和David B. Shmoys在1992年为1|η| Lmax问题设计了两个PTAS算法，它们的时间复杂度分别是O(n^4/ε log n / e^4)和O(n log n + n^(4/ε) / e^8)，这些算法为处理类似问题提供了理论基础。而吴翠连、张玉忠等人的工作则进一步扩展了这一领域的研究，提供了针对1|B，rj，sj| Lmax问题的新方法，为实际应用中的排序优化提供了理论支持。 这篇论文的关键贡献在于开发了一个新的近似算法，它在保持高效计算的同时，能够有效地降低最大延误时间，对于处理具有到达时间、加工时间和尺寸约束的工件排序问题具有实际价值。通过这样的算法，可以在不完全解决强NPC问题的前提下，获得接近最优解的方案，从而优化生产计划和调度，提高效率。