【作者】 陈欢；

【导师】 闻振卫；

【作者基本信息】 苏州大学 ， 运筹学与控制论， 2014， 硕士

【摘要】 在工程项目的实施管理中,人们首先要关心的问题是,如何合理的安排和调度工程内部各项工序的施工,使整个工程尽可能快而省地完成。网络计划技术(CPM／PERT)是项目管理中最为基础和广泛应用的管理方法。A-PERT问题是网络计划问题与分配问题的一种综合表现形式,在工程项目的管理和生产调度等许多方面有着重要的应用。本文研究A-PERT问题的一个方面—时间模式分配问题(简称模式分配问题)：设有一个由内部存在先后关系的n个工序所组成的工程项目以及有一个含有n个离散时间模式的集合。现要对工序的施工方式进行模式分配,每个工序的施工必须在模式集合中选取恰一个模式,且不同的两个工序不能选取同一个模式。模式分配的目的是使工程的总工期尽可能小。本文第二章建立了模式分配问题的数学模型,证明了该问题是NP-困难的,但对于几个特殊的情形给出了多项式时间算法。第三章提出了求解模式分配问题的一个近似算法：基于路长调整的模式分配算法,并分析了算法复杂性。我们还对最优总工期给出了一个较好的下界(LB)。第四章对这个模式分配问题提出另一个近似算法：基于时差调整的模式分配算法,并分析了算法复杂性。虽然后一个算法在计算精度上通常不如前一个,但它在计算速度上远优于前者,从而弥补了前者在算法复杂性方面的不足。因此,在针对不同规模的模式分配问题时,这两个算法在计算精度和速度上互为补充,从而给管理者提供了更多的选择。更多还原

【Abstract】 In the implementation of the project management, the first thing people concern is how to arrange and schedule the activity reasonably so that the whole project is completed as quickly and economically as possible.Network planning (CPM/PERT) is the most fundamental and the most widely used management method for the project management. A-PERT problem is a comprehensive form of it which is associated with CPM/PERT and assignment problem. It has important applications in many areas such as project management, production scheduling and so on. In this paper, we study one aspect of the A-PERT problem-a time-node assignment problem (or the mode assignment problem for short):There is a project of n activities with precedence constraints and a time-mode set with n discrete time-modes. We need to assign the modes to the activities such that each activity must select exactly one mode in the mode set, and two distinct activities must not select the same mode. The purpose of the mode assignment is to make the total duration of the project as short as possible. In the second chapter, a mathematical model of the mode assignment problem is established, and then we prove that the mode assignment problem is NP-hard. For some special cases of the mode assignment problem polynomial time algorithms are given. The third chapter proposes an approximation algorithm to solve the mode assignment problem:the algorithm based on paths length adjustment. We analyze the complexity of the algorithm and give a fairly good lower bound for the optimal total duration of the assignment scheme. Chapter four presents another approximation algorithm the algorithm based on floats adjustment, and we analyze the complexity of the algorithm. Although the latter algorithm is worse than the former one on accuracy, it is superior to the former one on computation speed. So it makes up for the lack of computational complexity of the former one. As the two algorithms help each other on accuracy and velocity, so the project managers will have more choices while facing problems with different sizes.更多还原