带有交货期和加工时间可控的单机排序问 (运筹学与控制论)

讨论了带有交货期和工件的加工时间可控的单机排序问题。本文首先根据最优排序的性质确定了最优资源的分配方法，并将问题转化为指派问题，通过构造多项式时间算法确定最优排序。然后，本文将学习效应与加工时间可控问题结合，分别讨论了加工时间是线性资源函数和凸资源函数两种情况，证明了该类问题是多项式时间可解的。最后，讨论了一种特殊情况（学习因子是常数，加工时间是凸资源函数），给出了复杂性为Onlogn的算法，通过运行此算法确定最优资源分配量和工件的最优排序。