赶工问题的一个新的最优算法.pdfVIP

赶工问题的一个新的最优算法 钟 巍殷志文彭斌 (复旦大学统计运筹系，上海，200433) 摘要 我们在本文中针对文献[1]中培出的一十赶工同垣的算=|击，指出该算=|击并不是 一十量忱算法，在进行一定的改进之后，我们将其改造成为一十量恍算法。 关量词 罔培计捌技术，赶工问题 1问题的提出 网培计划技术是组织生产计划的方法。它用罔络图来表达生产和工程的进度，计算各项 活动的有关时间参敷，使管理者对全局有一个比较完整的了解，可以得到完工期、资源和成 本的优化方案。在某些工程问题中，在编制网络图、计算有关时间参数并确定总工期以后，常 常需要对某些工序考虑赶工的措施(例如增加人员或添加设备等方法)，以缩短这些工序的 施工时间，从而使总工期缩短。此时，虽然用于赶工的工序成本增加了，但由于总工期的缩 短，从整体来说经济效盏反而可能会更好些。在本文中，我们考虑如何将一些工序的施工时 闻减少，从而使总工期缩短一定的天数，并使所增加的赶工成本最小。 这个问题曾经已有许多算法提出，如FulkersonⅡ]在60年代就提出过一个最忱算法。国 内也有魏国华等人在文献[1]提出的一个算法。但从以下舶分析中，我们可以看到文献1-13中 提出的算法并不是一个最优算法，其能得到一个近似解。我们在本文中将文献[1]中的算法 进行一定的修改，使其成为～个最优算法。与文献[2]中的算法比较，我们给出的算法更为直 观、简便。 在本文中，我们考虑工序的赶工成本与工序的赶工时间有着线性关系，把为了缩短一个 单位时间所需要增加的费用称为赶工成本斜率。因此我们考虑如下的一个问题，每道工序 “，j)的正常工序时间为”o赶工时间限度为吨，赶工成本斜率为西(如果wo，记毛一M)。如 果每道工序时间为正常时间下，总工期为71e，那么应该在哪些工序上赶工、并且赶工时间 为多少，才能将总工期缩短为Tz(即缩短△TE=Tz一于z)，并使所增加的赶工时间为最小。 2原始算法 在叙述文献[1]中的原始算法之前，我们先引进两个记号。R(i，j)表示工期为71。时(即 正常工期下)，工序(i，J)的最晚开工时间与最早开工时间差，即工序(i，J)的完工时间的机 动时间。令 R(i，J)=R“，J)一△了1￡ 印表示工期为亍z的条件下，工序(i，J)的完工时间的机勋时间。所以，当矗(i，j)O时，对 赶工问题的一十新的最优算法 207 工序(i，j)进行赶工，可能有助于工期于z的实现。 文献[1]中给出的算法，在每个阶段中，将所有j乏(i，j)o的工序(i，j)构成一个辅助网 络，求出其中赶工成本斜率为最小的割集，将割集上的工序尽可能地赶工一定的时间，反复 运用以上的原则，求出一个解。具体的算法分析和步骤参见文献[1]。我们在这里只用一个 倒子说明该算法。网络图如图1所示； 19 f 19 l 三人(6’6．M 25 —— 7．4}邕 25 刭(10 = 6 5 8