论文部分内容阅读
具有资源约束的调度问题在实际的机械加工中具有很强的应用背景。这里讨论一类工件间具有平行链优先约束的单机调度问题，同时工件的加工时间受资源约束，目标函数在满足资源消耗总量限制条件下，极小化加权总完工时间。研究考虑了两种情况，即一种是中链不允许中断，给出了多项式时间的算法；另一种是中链允许中断，引入了关键工件和优先因子的概念。证明了首先选择优先因子最小的链，连续加工直至关键工件完工产生的调度为最优调度，同样对该种情况给出了多项式时间的算法，并引入数值算例，对算法的运行过程进行了说明，验证了算法的有效性。