A Time-mode Assignment Problem For The Project Management

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.