文件名称：极小化加权完工时间和的调度问题 (2003年)
文件大小：638KB
文件格式：PDF
更新时间：2024-05-30 15:37:40
自然科学 论文
讨论目标函数为极小化加权完工时间和的调度问题。对于这类问题,平行机问题是 NP-难的。基于对问题的分析,对工件的加工时间相等的恒速平行机问题,给出了多项式最优算法。 Open shop问题是强 NP-难的。给出了工序的加工时间相等的无等待 Open shop问题与工件的加工 时间相等的同速平行机问题的联系。根据这种联系,对工序的加工时间相等的无等待 Open shop问 题,给出了多项式最优算法。算法的复杂性均为 O(nlogn+mn)。