重复性项目时间费用权衡模型及其扩展研究

发布时间：2018-01-02 10:05

本文关键词：重复性项目时间费用权衡模型及其扩展研究　出处：《华北电力大学(北京)》2016年博士论文　论文类型：学位论文

【摘要】：时间费用权衡是一类在项目调度领域广泛研究且具有重要应用价值的优化问题,旨在满足给定截止日期条件下最小化项目的总费用。重复性项目是指施工场所可划分为若干独立的单元,部分或全部工序需要在多个单元上重复执行的项目。常见的例子有高层建筑、高速公路、管道工程和住宅开发等。本文的研究目的是为重复性项目时间费用权衡问题(TCTPRP问题)建立可计算的数学模型。又因为TCTPRP问题属于NP-hard问题(即,不存在多项式时间可解的算法),因此本文还将研究能解决较大规模问题的近似模型或者启发式方法。与非重复性项目相比,重复性项目调度的复杂性主要表现在决策变量的多样化上,即它可能需要计算工序的执行模式、工作队的雇佣数量、单元间的逻辑顺序和单元的分配方案等。理论上,一个完美的TCTPRP模型或算法需要具备同时处理多工作队、多模式和非固定逻辑顺序(也称为软逻辑)的能力。但是,实际工程中并不是所有的项目都能够或者有必要雇佣多个工作队、考虑多种执行模式或者随意改变单元间的逻辑顺序。因此,从迎合实际的角度,本文同已有研究一样考虑不同类型限制条件下的TCTPRP问题。本文的主要研究内容和研究成果如下：(1)在单模式和固定逻辑条件下研究多工作队TCTPRP问题,目标是确定所有工序最优的工作队雇佣数量及其在各单元上的开始时间。我们提出了基于混合整数线性规划的精确模型,并在考虑工序进度不变假设条件下,建立了能在短时间内处理较大规模问题的近似模型。数值实验表明,精确模型在限定的时间(1小时)内能解决的最大规模问题包含50个工序、100个单元和10个工作队；近似模型计算结果的平均偏差不超过1%,并且能在短时间内处理包含100个工序的项目。然后,我们将上述精确模型推广至非典型项目(即,工序在不同单元上的工期可以不相同的项目),并提出了能计算工序最优单元分配方案的扩展模型。(2)在单工作队和固定逻辑条件下研究多模式TCTPRP问题,目标是确定所有工序最优的执行模式及其在各单元上的开始时间。我们同样提出了基于混合整数线性规划的精确模型,并定义了两种模式消除规则,它们能有效识别并删除不可行或者非最优的工序执行模式,从而降低模型的求解难度。对于较大规模的问题,我们提出了基于线性规划松弛思想的两阶段的启发式算法。数值实验表明,精确模型在可接受的时间内能处理的最大规模问题包含60个工序、40个单元和20种执行模式；启发式算法计算结果的平均偏差不超过4%并且有能力解决更大规模的问题。(3)研究单工作队多模式软逻辑TCTPRP问题,目标是确定单元间的最优逻辑顺序,以及所有工序最优的执行模式及其在各单元上的开始时间。我们分析了软逻辑对重复性调度可能产生的影响,并在此基础上给出了用于描述该问题的混合整数非线性规划模型。考虑到模型的求解难度,我们提出了基于遗传算法和线性规划的启发式方法。已有文献只对典型项目下多工作队TCTPRP问题以及单工作队和固定逻辑下的多模式TCTPRP问题进行了研究,并且它们均采用智能算法作为求解工具,不能保证解的最优性。我们的工作在一定程度上弥补了已有文献的不足,并且数值实验的结果还能作为参考用于评价其他启发式方法的性能。
[Abstract]:Time cost trade-off is a kind of optimization in the field of project scheduling and extensive research has important application value, to meet the given deadline under the condition of minimizing the total cost of the project. The repetitive project refers to the construction sites can be divided into several independent units, all or part of the process shall be repeated in multiple unit project. Common examples of high-rise buildings, highway, pipeline engineering and residential development. The purpose of this study is to balance the time cost of repetitive project (TCTPRP) model can be calculated. Because the TCTPRP problem belongs to NP-hard (i.e., there is no algorithm solvable in polynomial time), so this paper the research can solve the problem of large scale approximation or heuristic method. Compared with the non recurring items, the complexity of repetitive project scheduling is mainly reflected in the decision variable The amount of diversification, that it may be necessary to calculate process execution mode, hiring team, logical and unit of the distribution plan. In theory, a perfect TCTPRP model or algorithm requires simultaneous processing of multiple teams, multi mode and non fixed logical order (also known as soft logic) ability. However, in the actual project and not all items can or need to hire a team, considering the multiple mode or change the logical order between the units at random. Therefore, from catering to the practical point of view, the same as the existing research to account for TCTPRP of different types of constraints. This the main research contents and results are as follows: (1) study on the TCTPRP work team in the single mode and fixed logic conditions, the goal is to determine the number of teams employ all processes and in the single best The starting time of yuan. We propose a precise model based on mixed integer linear programming, and considering the process progress assumption conditions, established the approximate model can deal with larger scale problems in a short period of time. Numerical experiments show that the model is accurate in a limited time (1 hours) the biggest problem can be resolved include 50 steps, 100 units and 10 teams; the average deviation of the calculation results of the approximate model is less than 1%, and can handle the procedure contains 100 projects in a short time. Then, we will be the exact model is extended to the non typical project (i.e., time in different units on the same process can not project), and puts forward the extended model can calculate process unit optimal allocation scheme. (2) in a single team and fixed logic is studied under the condition of multi mode TCTPRP problem, the goal is to determine the optimal execution of all processes Mode and start time in each unit. We also propose a precise model based on mixed integer linear programming, and defines two modes of elimination rules, they can effectively identify and remove infeasible or non optimal process execution mode, thereby reducing the difficulty of solving the model. For the large scale problems, we put forward the two stage of the linear programming relaxation heuristic algorithm based on the idea. Numerical experiments show that the accurate model contains 60 processes in time to deal with the biggest scale acceptable, 40 units and 20 execution modes; the average deviation of the heuristic algorithm results is less than 4% and have the ability to solve large-scale problem (. 3) multi mode soft logic TCTPRP single work team, the goal is to determine the optimal logical order between units, and all process optimal execution mode and in each unit The starting time. We analyzed the effect of soft logic may be generated for repetitive scheduling, and on this basis are presented for mixed integer nonlinear programming model to describe the problem. Considering the difficulty of solving the model, we propose a heuristic method based on genetic algorithm and linear programming. The existing literature studied just TCTPRP multi mode TCTPRP multi typical project team and single team and fixed logic problems, and they are used as a tool for solving intelligent algorithm, can not guarantee the optimality of the solutions. We work to make up for the lack of existing literature to a certain extent, and the numerical results can be used as a reference for performance evaluation the other heuristic methods.

【学位授予单位】：华北电力大学(北京)
【学位级别】：博士
【学位授予年份】：2016
【分类号】：F285

【相似文献】