三机单位作业调度的多项式时间算法
A Polynomial-Time Algorithm for Three-Machine Unit-Job Scheduling
OpenAI 数学仓库收录的研究手稿。展开查看英文摘要，或标记后让我进一步解释。
具体内容
稿件研究三台同型并行机上带任意优先约束的单位长度作业调度。作者声称给出统一的确定性多项式时间算法，能构造最小完工时间的调度，并精确判定所有作业能否在给定截止期前完成。证明将可行调度重组为区间，其作业集具有有界大小的描述；动态规划搜索含多项式多个此类描述的族，并通过全局边界条件与继承信息化简保持描述有界。
- 作者声称给出三机单位作业调度的统一确定性多项式时间算法
- 算法构造最小完工时间调度并判定截止期可行性
- 证明基于有界描述区间的动态规划与信息化简
AI 产生的研究手稿；收录不表示已完成独立审查或同行评议。
英文原始摘要
We give a uniform deterministic polynomial-time algorithm for scheduling unit-length jobs with arbitrary precedence constraints on three identical parallel machines. The algorithm constructs a schedule of minimum makespan and decides exactly whether all jobs can finish by a specified deadline. The proof reorganizes feasible schedules into intervals whose job sets have descriptions of bounded size. A dynamic program searches a family containing polynomially many such descriptions. Global boundary conditions and simplification of inherited information keep the descriptions bounded throughout the decomposition.
用户标记：未标记
固定编号：f95f401fd5aa482c
原文来源