加工时间离散可控的分批排序问题

摘要

分批排序和可控排序是两类重要的现代排序模型,该文中把这两类排序模型相结合,讨论加工时间离散可控的单机分批排序问题:对于所有工件具有相同的可控加工时间和控制费用这一情形,分别考虑机器容量有限及无限两种情况下,分别使最大完工时间和总完工时间加上加工时间可控所需费用的总和为最小作为优化的目标,讨论了这四个问题的最优解的性质,并在此基础上提出了相应的多项式时间最优算法.