带有学习效应的加工时间可控退化工件单机排序问题

摘要

讨论了带有学习效应、加工时间可控的退化工件的单机排序问题.工件的实际加工时间是一个关于所排位置、开始加工时间和所分配资源的函数.加工时间可控是指工件的实际加工时间是一个依赖资源分配量的函数.目标是确定工件的最优排序、最优加工时间和最优资源分配量、极小化最大完工时间、总完工时间、完工时间差和资源消耗的总费用.考虑了2种情形:学习因子与工件有关的线性资源函数;将学习效应与工件的实际加工时间、依赖开始时间结合在一起的凸资源函数.通过分析最优解的一些重要性质,将这2个问题分别转化为指派问题,给出了2个计算复杂性为O(n3)的最优算法,证明了该问题是多项式时间可解的.