网络计划模型计算机编号的逻辑运算方法

D0I:10.13374/j.iss1001-053x.1989.04.002 北京科技大学学报 第11卷第4期 Vol.II No.t 1989年：7月 Journal of University of Science and Technology Beijing Ju1y1989 网络计划模型计算机编号的逻辑运算方法 俟运炳 熊国华 (采矿系系统工坠室) 摘要：本文研究了网络计划模型让算机编号的逻拼运算方法，设计了非带的便的 树路模型工小关系表计算机输人方式，使得二作效事提高了10倍以上。 关键词：网路计划，计算机方法，泛#运京 The Computer Method for Numbering the Events of Network Planning Model Hou Yunbing Xiong Guohua ABSTRACT:A computer method for numbering the cvents of nctwork planning model is discussed in this paper,A simple technique for the inputing the data is given here.Thesc have raised the efficency of work by 10 times or more than befor. KEY WORDS:nctwork,computer method,logical operation 网络计划技术是50年代中期发展起来的一种重要的科学计划管理技术，目前在很多行业 得到了广泛的应用，在矿山企业也有着广阔的应用前景(，1。 运用网络计划技术，传统的方法是首先按一定规则进行工网络编号，其中常用的编号 方法为双代号法，即给出道工序的始点编号和终点编号，必要时还要增设虚工序；然后画 出网络图，构造侧铬模型；收后把网络编号和其它参数输人计算机，为计算机求解作准备， 或者准备人工手算【3。这些工作不仅费时费力需要一定技巧才能完成，而且极易出错。同 时，修改网络模型也很州难，不易快速改变计划方案。这些州难在一定程度上限制了网络 技术的进一步推应用。 为了克服这些附准，作者在研制某铁矿采掘生产计划网络优化系统时【」，设计了网络 1988一09-05收腐 302

第 卷第 期 。 年 少 京 科 技 大 学 学 报 。 、 ， ， 网络计划模型计算机编号的逻辑运算方法 侯运炳 熊 国华 采句 ‘ 系 系统 工 程室 摘 要 本 之研 究 ’ 闷络 计划 模 型 计算机编 廿的 逻辑 运 算 方法 ， 设 计 了 作 常 简便 的 网络 校 型 序 关系表 算机 输 人 方式 ， 使 得 作效率提 高 犷 告以上 。 关键词 网 络 计 划 ， 计 算机 方法 ， 逻 扰 运 算 夕 夕 赵 “ 、 、 。 ， ， 、 。 。 。 。 认 厂 ’ 。 、 、 「 ， 一 ， 网络 计划 技术 是 。 年代 中期 发 展 起来 的 一 种 重要 的科 学 计划管理技 术 ， 目前在很 多 行业 得到 了广 泛 的应 川 ， 在 矿 山 企业 也 有着广 阔 的应川 前景 〔 ” “ 」。 运 用 网络 计划 技术 ， 传 统 的 方法 是首先 按 一定规 则 进 行工 序 网络编号 ， 其 中常 用 的编号 方法 为双 代号 法 ， 即给 出桩道工 序 的始点 编号 和 终点 编号 ， 必 要时还 要增设 虚 工 序 然 后 画 出网络 图 ， 构造 网络模 型 竣 后把 网络 编 一 号和其它 参数输入 计算机 ， 为计算机 求解作准 备 ， 或 者淮备人工 手算 〔 。 这 些工 作 不仅 费时 费力需要 一定技 巧才能 完成 ， 而 且极 易出错 。 同 时 ， 修改 网络模 型 也很 困难 ， 不 易 二快 速 改 变 计划 方案 。 这 咋 困难 在 一 定程 度 上限 制 了网络 技术 的进 一 步 推广 应 川 。 为 了克服 这 咦 困难 ， 作 者在研 制某铁矿 采掘 生 产 · 划网 络优 化 系统 时 」 ， 设 一 卜了网络 一 一 收 稿 DOI ：10．13374／j ．issn1001－053x．1989．04．002

计划模型的“工序关系表”计算机输人法，并研究了网络模型计算编号的逻辑运算方法，根 据这些方法，编制了计算机程序。 1网络模型工序关系表输入法 工序关系表是以工序的紧前工序的工程序号来表示工序逻辑关系的一种表格。如图1所 示，4号工序的紧前工序工程序号是1,2和3，因此它们之间的关系可由表1表示。 表1工序关系表 Table 1 The table to show the relation- ships between the events 上程序号 紧前亡序工程序号 图1工序关系图 1,2,3 Fig.1 Diagram of the events 有了工序关系表给出的逻辑关系，计算机就可按照网络双代号编号原则进行工序的始点 和终点编号运算，并增设必要的虚工序。 工序关系表极大地方便了网络模型的建立、修改和计算机数据管理工作。工序的工程序 号可任意给定（但不能重复），可根据需要增加或减少某一工序的紧前工序。不太了解网络 计划技术的人也可以通过这种工序关系表使用网络技术。 2计算机网络编号逻辑运算方法 为了叙述方便，作下约定： (1)工序用A、B、K表示； (2)W4x表示A工序的一个紧前工序，用{W4}表示A工序所有的紧前工序，{WAx} 表示A工序的部分紧前工序子集，在特例情况下{W:}={W4x}; (3)任何工序的起点用“I”表示，终点用“J”表示，I(A)是A工序的起点，J(A)是 A工序的终点： (4)M表示工序编号状况，M(A)=1表示工序的起点已编号，M(A)=2表示工序的终 点已编号，M(A)=0表示工序尚未编号； (5)符号“入”表示逻辑和，“V”表示逻辑或，“≠”表示逻辑非，“{}”表示集 合，“∈”表示属于，“年”表示不属于。 此外，还应简单地提到网络模型双代号编号应遵循的原则： (1)事件1表示任务开始，从事件1出发的工序没有其它紧前工序； (2)工序A在事件I(A)开始，在事件J(A)结束； (3)对每道工序A来说，I(A)<J(A): (4)(I(A),J(A))表示且.仅能表示工序A。 编号分两步进行。 303

计 划模型 的 据 这些 方法 ， “ 工 序关 系表 ” 计算机输入 法 ， 并 研究 了网络模 型 计算编号 的逻辑 运 算方法 ， 根 编制 了计 算机程 序 。 网络模型工 序关系 表输入 法 工 序关 系表是以工 序的紧前 工 序 的工 程 序号 来表示工 序逻 辑 关 系 的一种表 格 。 如 图 所 示 ， 号工序 的紧前工 序工程 序号是 ， 和 ， 因此它 们之 间的关 系 可由表 表 示 。 表 工 序 关系表 比 叭 己 工 程 序 号 紧 自犷自 卜工 程序 号 图 工 序 关 系 图 一 、 有 了工 序关 系表给 出 的逻 辑 关 系 ， 计 算 机就 可按 照 网络双 代号编 号原则进行工 序 的始点 和 终点 编 号运算 ， 并增设 必要 的虚工 序 。 工 序关 系表极 大 地方 便 了网络模 型 的建 立 、 修改 和 计 算机数据管理 工作 。 工 序的工程 序 号 可 任意给 定 但 不能 重 复 ， 可根据需要 增 加或减 少某 一工 序 的紧前工 序 。 不 太 了解 网络 计划技术 的人 也 可以通过这 种工 序关 系表使 用 网络技术 。 计算机网络编号逻辑运 算方法 为 了叙 述 方 便 ， 作如 下约 定 工 序 用 、 、 表 示 才 ， 二 表示 工序 的一个 紧 前工 序 ， 用 ， 表 示 工 序所有 的紧前工 序 ， 砰 ， 二 表示 工 序 的部 分 紧前 工 序 子 集 ， 在特 例情况下 牙 ， ， 任何工序 的起点 用 “ ” 表示 ， 终点 用 “ ” 表 示 ， 是 工序 的起点 ， 是 工序 的终点 表 示工 序编号状况 ， 表 示工 序的 起 点 已编号 ， 对 表 示工 序 的 终 点 已编 号 ， 二 表示工 序 尚未编 号 符号 “ 八 ” 表示逻辑和 ， ，’ ” 表示逻辑或 ， “ 并 ” 表 示逻轼非 ， “ ” 表示集 合 ， “ 乏 ” 表 示属于 ， “ 去 ” 表示不 属 于 。 此外 ， 还 应简单 地提到 网 络摸型双 代号编号 应遵循 的原 则 事件 表示 任 务开 始 ， 从事件 出发 的工 序没 有其它 紧前工 序 工 序 在事件 开始 ， 在事件 结 束 对每道 工 序 来说 ， 姓 ， 表 示 且仅 能表 示工 序 。 编号 分两步 进行

步骤1首先令E=1 （1)始点事件编号 没有紧前工序的工序始点编号显然是始点事件编兮。检查序，凡满足公式 {W、}=中（中为空集） 的工序A令I(A)=E,M(A)=1。 (2)中间事件编号 给中间事件编号的思路是从始点事件编号入手，按紧前工序提供的逻#关系，循序推 进。 首先令E=E+1,然后检查上序编号状态。 )满足公式 M(A)≠UVM(WAx)=0 的工序A现在不其备编兮条件或暂时不必多虑。 2:如果工序A满足 {M(Wa)}={1} 即所有紧前工序的始点（也仅仪是始点）都已编号，这时： (a)给工序A始点编号，令I(A)=E,M(A)=1, (b)给工序A的紧前工序WAx终点编号，分两种不同情况： ⑧如果WAr满足 I(W,)=I(WA,)∧J(WA,)=EAWAx≠WAy (1) 则增设虚」K,令 I(K)=E+1,J(K)=E,M(K)-2 J(WAx)=E+1,M(W4x)=2, 增设虚广序后，虚上序K的紧前上序为W4,而A1序原来的紧前工序W4x则应更换为 K工序，问时，对于满足 WBx=W4A八M(B)产0 的工序B,也应把W。x换成K。以斤碰到！与此类以情况，同样道理改变紧前工序，不冉赞 述。 ⑤对手不满足(1)式的W,令J(W4x)=I(A),M(Wx)=2。 :}如果序A满足 {M(W4r)}={2; 即所有的紧前序终均心编号，这时： (a)如果所行紧前工序终点编号相同，即 304

步一 首先令 始点 事件编号 没 有 紧前工 序 的工 序始 点编号 显然 是 始 点 事件编 皆 。 检 查 二 一 犷 ， 儿满 足公 式 笼甲 、 二 必 功为空 集 的工 序 令 二 ， 。 中间事件编 号 给 中间事件编号 的思路是从 始点 事件编 号入 手 ， 按 紧前工序 提 洪 的 逻 辑 关 系 ， 循 序推 首先 令 二 十 ， 然 后 检查 工序编号 状 态 。 』 满 足 公 式 升 冲 ‘ 才 、 、 二 的工 序 现 在 不其 备编号 条 件或 暂” · 上不必 考虑 。 勺 如 果工 序 满 足 附 人 即所有 紧前工 序 的始 点 也 仪仪是始 点 都已 编号 ， 这 时 给工 序 始点 编 号 ， 令 ， ， 给工 序 的紧 前 工序 甲 二 终点 编号 ， 分 两种 不 同情况 如 果 牙 、 满 足 邵 、 、 二 才 人 ， 八 附 ， 二 八 津、 ， 笋 甲 ， 则增设 虚工序 ， 令 “ 斗 一 ， 砰 ， ， 二 甲 ， 名 增设虚 二序后 ， 虚工 序兀 的紧 前工序 为 才 ， 、 ， 而 一 子原来 的 紧 前工 序 甲 ‘ 、 则应 更 换为 工 序 ， 司 」 · ， 对于满 足 邵 。 的工 犷 ， 述 。 国 也应 把 附 ， 、 换 成 。 二 于 ， 产 以后碰 到 ’ 此 类 吐情况 ， 川同样道理改变 紧前工 序 ， 不 再赞 对 ， 叮满 足 式 的 甲 ， ， 令 牙 ， 月 ， 甲 月 。 如 果 序 满 足 牙 ， 、 傀 即所 有 的紧 前工 序 终 点 均 已编 号 ， 这 时 如 果所了 紧 ’上 子终点编号 相同 ， 即

{JW)}-{C}(C为常数) 则有 3如果行工序B满她 J(B)=J(W4x)八B{H:} (2) 则令1(A)=E,M(A)=1·增设虚工序K,令I(K)=J(TW4x),J(K)=I(A),M(K)=2, 改变W4x的终点编号，令{J(F4x)}={E}。 ⑤如果没有二序B满(2）式，则令 1(A)=J(下s),M(A)=1 (b)如果在4x,形满足 J(WMx)≠J(W4) 这需要逐个检含：个紧前序的情况。 首光令I(A)=E,M(A)=1:然后改变{：}的终点编号，按下列步骤逐个检查 个W4x: a令U=J(I4r); 5对于满足 J(B)=UB∈{W4} 的]序B,令J(B)=E+1,同时增设虚工序K,K+1,令 I(K)=J(B),J(K)=E,M(K)=2 I(K+1)=J(B),J(K+1)=U,M(K+1=2 同时令E=E+2,K=K+2; ©检查下一个W4x,如果W4x的终点编号已经被改动过则检查另外的Wx,否则按上 述步骤重新进行编号，直至所有的W4x处理元毕。 ④如果工序A满足 {M(Wax)}={1}八{M(W4y)}={2} 即一部分紧前工序的终点已经编号，另一部分紧前工宁终点尚未编号，这时 (a)令I(A)=E,M(A)=1, (b)检查每一个紧前工序Wx: @如果M(W4x)=2,则按照(2)一3一(b)中类似方法改变W4x的终点编号； 直 D如果M(W4x)=1,则按照(2)一②中类似方法给W4x终点编号， ©重复以上过程，将A工序的所有紧前工序处理完毕。 ⑤令E-E12,重复以上步骤，直至所有的T序A满足M(A)>0 (3)终点事件编号 显然，M(A)=1的工序，其终点尚未编号，它们的汇合点即为终点事件。 (a)令U=E+1,E=E+1 305

丈 冲 过 二 一 丈 为 常数 少 如 果 有」二序召 满 足 牙 咬 八 之 付 厂 理 则令 ， ， 增 设 虚 工 序 ， 令 ， ， ， 之 改 变牙 。 的终点 编号 ， 令 ， 、 。 ⑥ 如 果没 有工 序 满 足 式 ， 贝令 不于 一 、 ， 五 〕 如 果 在拜产 ， 丁于 ，。 ， 满 足 牙 ， 乙了 不不厂 、 。 这 时 需 要逐 个检查 每个紧前 几序的情况 。 首 先令 ， 二 ， 然 后 改 变 不厂 的 终点编 一 号 ， 按 下 列步 骤 逐个检 查 每 个 砰 月 ‘ 令 冲 ‘ 对 」三满 过 四， 召 二 八 任 牙 汉 的工 序刀 ， 令 牛 ， 同时增设 虚工 序 ， 十 ， 令 ， ， ， 二 ， 同时令 十 已 ， 二 ⑨ 检查下 一个 牙 刁 ， 如 果 ，汗勺终点 编 号已经 被改动过 则检查另 外 的牙 ， 二 ， 否则 按上 述步骤 重新 进 行编号 ， 直 至 所有 的 班 ， 处理 完毕 。 ④ 如 果工序 满 足 环 ， 二 王 八 班 ， ， 即 一部分 紧前工 序 的终点 已经编号 ， 另 一部分 紧前工 序终点 尚未编号 ， 这时 令 ， ， 检查每 一 个紧前 工 序 砰 ，、 ④ 如 果 牙 ， ， 则按 照 一 各一 中类 似 方法 改 变 才 ，二 飞勺终点编号 回 如 果 力 ， 则 按 照 一② 中类 似方 法给 过 终点 编号 。 重 复 以 上过程 ， 将 工 序 的所有 紧前工 序处理 完毕 。 ⑤ 令 一 一 一 ， 吸复以 土 步骤 ， 直 至 所 有 的 一 自 卜 满 足 终点事件编号 显 然 ， 的工 序 ， 其终点 尚未 编号 ， ‘ 己们 的汇 合点 即力终 点事件 。 令 ， 君

(b)设M(A)=1,如果有L序B满足 I(A)=I(B)∧J(B)=U 则令J(A)=E+1,M(A)=2,同时增设虚工FK,令1(K)=E+1,J(K)=U,M(K) =2。否则，令J(A)=U,M(A)=2, (c)令E-E+1,按(b)中所述方法处理所有M(A)=1的)序A。 步骤2以上编号方法会出现I(A)>J(A)的情况，这不符合树络编号原则，下面根据 上述方法所编的号，重新以由小到大连续性的数码确定事件的编号。 首先令所有工序编号状态M(A)=0,令E=2。 (1)始点事件编号 由上述方法产生的始点事件编号为1，因此不必重新编号。检查上？A,果(A)= 1,则令M(A)=1。 (2)中间事件和终点事件的重新编号 I首先要从M(A)=1的工序A开始，令U=J(A); 兰然寻找有没有其它的工序满足J(B)=J(A)； ()如米没有这样的汇序B,则令J(A)=E,M(A)=2,E=E+1,并子找满足I(K) =U的工序K,令I(K)=J(A),M(K)=1。 (b)如果有这样的工序B,检查工序B的始点是否已经重新编号，如果已经重新编号， 则令(A)=E,J(B)=E,M(A)=2,M(B)=2,E=E+1寻找满足I(K)=U的L序 K,令I(K)=J(A),M(K)=1。如果1工序B的始点没有重新编号，则上序A不具备编号条 件。 3在寻找过程中，如果M(A)=2,则表示该工序的编号已经完成。如果所有的工序 状态都满足M(A)=2,则整个网络模型编号全部完成。 3结论 根据上述的逻#运算方法编制的BM微机程序，经过多种方案运算检验，果完全止 确。作者编制的某矿采据生产网络计划软件包采用了此程序(2)。 实践表明，利用工序关系表和这种计算机编号方法建立网络模型，可以便」作效节提高 10倍以上【」。更重要的是，它能缩短网络计划技术与实际生产计划编制者之间的距离，对 树络计划技术的普及应用起推动作用。山于过去矿山应用网络计划的经验较少，因此该方法 意义更为重大。 参考文献 1 Glews K M.World Mining Equipment.1984;(7) 2俟运州.熊国华.金属矿山.988，(10) 3丁上：.算法语吉与网络计划程序设计。北京：中国建筑广业出版社。1983 4佚运州.北尔科技火学硕士论文，1987 306

设 ， 如 果有工序 满足 八 则 令 二 ， ， 同时增设 虚 上 序 ， 令 二 ， ， 。 否则 ， 令 ， ， 令 一 ， 按 ， 中所述 方法 处 理 所有 的 犷 。 步 骤 以 仁编 号方法 会出现 的 情 况 ， 这 不符 合 网络 编 一 号原 则 ， 「面根 据 上述 方法 所编 的号 ， 重 新以 由小 到大 连 续性 的数码 确 定 事 件的编号 。 首先令所 有工 序编号状态 ， 令 。 始点 事件 编号 由 卜述 方法产 生 的始点 事件编号 为 ， 因此 不必 重 新 编 号 。 检查 工 芥 ， 如 果 ， 则令 。 中间事 件和 终 点 事件的重新 编 号 首先 要从 二 的工序 开始 ， 令 然 后 一 寻找 有 没 有其 它 的工序满 足 ， 。 如 果没 有这样 的 一 〔 序 ， 则令 ， ， 二 ， 一 ， 井 子 找 满 足 二 的工 序 ， 令 ， 。 如 果有 这 样 的 工序 ， 检查 工序 的始点是否已经重新编号 ， 如 果 已经 重新编号 ， 则令 ， ， ， 材 ， 二 十 寻 找满 足 的工 序 ， 令 ， 。 如 果 工序 的始点 没有重 新编号 ， 则 上 序 不具 备编号 条 件 。 营 在寻找过 程 中 ， 如 果 二 ， 则表示该工序 的编号 己经完成 。 如果所 有 的 工序 状 态都满 足 刁 ， 则整个 网络模 型编号 全 部完成 。 结 论 根据 上 述 的逻 排运 算方法 编 制 的 微 机 程 犷 ， 经 过 多种方案达 算检验 ， 结 果完 全 确 。 作者编 制的某 矿采 掘 生产 网络 计划软 件 包采 用 此 程 序 〔 么 ’ 。 实践表 明 ， 利 用 工 序 关系表和 这种 计 算机 编号 方法建 立网 络模 型 ， 丁以 使」二作效 率提 高 倍以上 〔 咭 」 。 更 重 要的是 ， ‘ 已能缩短 网络 计划技术 与实际 生产 计划编 制 者之 间 的距 离 ， 对 网 络 计划 技术 的普 及应 用 起推动作 用 。 山于 过 去矿 山应 用 网络计划 的经验 较少 ， 因此 该方法 意义更 为 重大 。 参 考 文 献 、、 、 为 。 牙 ” 夕 优 侯运烟 熊 国 华 金 属矿 山 以 丁 昭 算法 语言 ’， 网 络 计 划程序 设 计 北 京 侠运炳 北 京科 技大 学硕士 沦 文 咬 中国建筑 伙出版 于