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

An Algorithm for Minimum Vertex Cut Set of Partially Ordered Sets and the Problem of Minimum Cost of Crashed Tasks

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

In the PERT network, a project is composed of many tasks. There is a precedence relationship between tasks. Each task has its own normal working time and crashed working time. Each task has its own cost per day of working faster. Let us assume that the normal time limit for the project is T days and the shortest time by fast working is S days. The problem in this paper is, given any integer t(St<T), how to choose some tasks and how many days we work faster on them so that the project time limit is t and the total cost of crashed tasks is the minimum. A convenient, easy and effective method is provided to solve this problem. The computing of the time limit (and other indexes) for the project is realized on the vertex diagram instead of on the arrow diagram of the partially ordered set representing the project, which overcomes the difficulty of constructing the optimal arrow diagram of the partially ordered set.