偏序集最小顶点割算法与最小费用赶工问题

摘要

在网络计划问题中,一项大的工程由许多工序合成.工序与工序之间存在着一定的前后关系,每个工序有着自己的正常加工时间和通过赶工所能达到的最短加工时间以及每赶工一天的赶工费用.设一项工程的正常工期为T天,通过对所有可能的工序赶工,整个工程能达到的最短工期为S天.本文的问题是,对于任意给定的t(St＜T),怎样确定所要赶工的工序及其赶工天数,在满足整个工程的完工时间恰为t天的条件下,使总的赶工费用最小.本文对这一问题给出了一个方便易行的有效算法,并将以往在(双代号)网络图上对工程工期的计算改为在工程的偏序图上进行,从而省去了烦琐的工程网络图(即偏序集的箭线图)的绘制.