项目调度中的时间-费用权衡问题研究综述

项目管理中,通过增加额外费用来加速执行项目的某些活动,以此达到缩短项目工期的目的,这就是在项目调度文献中被广泛研究的时间-费用权衡问题.这篇文章将时间-费用权衡问题分为两类来研究:第一类是活动的执行时间和费用之间有连续函数关系的连续时间-费用权衡;第二类为时间和费用之间没有函数关系的离散时间-费用权衡.详细介绍离散时间-费用权衡问题近10年的研究进展,包括问题的求解算法、模型改进等.从更贴近实际项目实施的角度,介绍了具有时间转换约束的离散时间-费用权衡问题.最后,指出了时间-费用权衡问题需要进一步研究的几个方向.     

基于DSM的复杂研发项目价值流优化

针对传统设计结构矩阵(DSM)优化研发项目的不足,本文采用基于价值要素的DSM价值流优化方法,提出了活动的"费用时间比"参数和返工因子DSM矩阵,以综合反映活动的费用、时间及返工风险等价值要素对复杂研发项目活动排序优化的影响。进一步,将活动的"费用时间比"参数和返工因子作为优化参数,构建了相应的DSM价值流优化目标函数。对某案例优化计算表明,与传统方法相比,采用本文提出的价值流优化方法能明显降低由于返工而引起的项目费用增加值。     

带工期指派的产品服务系统订单随机调度问题研究

针对由一个制造工厂和多个区域服务中心组成的服务型制造企业，研究了考虑生产时间和服务时间均具有随机性且工期可指派的产品服务系统（PSS）订单调度问题。首先以最小化订单提前、误工和工期指派费用的期望总额为目标构建问题的优化模型，然后分析目标函数近似值的最优性条件，据此提出加权最短平均生产时间排序规则，并结合该规则与插入邻域局部搜索设计了启发式算法对问题进行求解，最后通过数值仿真验证算法的可行性和有效性。研究表明，提前费用偏差对PSS订单调度与工期指派决策的影响很小，因此企业管理者无需准确估计库存费用也能制定出比较有效的PSS订单调度策略；而工期指派费用偏差对决策结果的影响非常大，因此企业管理者在决策时必须谨慎估计该项费用。     

基于MDE资源分时段与活动平移并行的均衡优化

本文以资源均方差作为衡量工程网络计划资源均衡性的评价函数,基于非关键活动资源可以分段使用的状态,提出了对非关键活动机动时间及其各个时段的资源强度同时动态并行调整的优化策略,以弥补非关键活动平移幅度因受时差的限制而对均衡效果产生的影响,并以此构建了网络计划资源均衡优化模型;并针对网络计划均衡优化模型是一多峰值的非线性优化函数的特点,对基于种群的全局搜索策略的差分进化算法进行了改进和进行全局最优解的寻优,以优化各个非关键活动起止时间,求出各个非关键活动最优的安排;最后,通过实例分析,并与其它算法进行了对比分析,验证明了所提出的均衡优化方法的优越性和实用性.     

运输问题时间优化算法

运输问题是线性规划中的一类特殊问题。适用于求解目标函数符合线性叠加关系的费用或距离问题,对于实际运输问题中的运输时间优化问题则难以给出优化解。本文结合科研实践提出了运输问题中有关时间优化的迭代算法模型,此模型可给出整体运输时间最优的运输方案。通过实际检验证明,此算法简便、稳定、计算结果符合实际情况。     

差价合约下电网公司购电费用最小化的离散优化模型

以购电费用最小化为目标函数,构建了差价合约下电网公司在合约市场、现货市场、备用市场和可中断负荷交易市场上的最优购电模型,并利用启发式算法给出了该模型的求解算法,最后,通过算例分析了差价合约及合约电量比重对电网公司购电费用的影响。     

基于遗传算法的设计结构矩阵优化方法研究

分析了DSM(Design Structure Matrix)优化方法的研究现状及不足,接着以耦合强度为基础,提出了数字化的设计结构矩阵。以此矩阵为基础,以遗传算法为优化工具,经过目标函数的设立,编码、交叉算子、变异算子等的设计,提出了一个新的DSM优化方法。以飞机某一部件的设计过程为例,实现了设计的时间、费用及过程优化,并与现有算法作了对比分析,验证了新优化方法在寻优效率、目标函数、及最优化结果等方面的优越性能。     

供电企业中电力设备全寿命周期费用模型研究

全寿命周期费用(LCC)分析是成本管理发展的重要方向。本文针对供电企业的实际情况,建立了电力设备全寿命周期费用定量模型。将所有费用分为一次投资费用和运行维护费用两部分。针对一次投资费用的特点,建立了基于时间分摊的一次投资费用模型;针对运行维护费用长期发生的特点,建立了基于灰色关联度确定分布类型的运行维护费用模型,即假定每次发生故障的时间分布函数是几种典型费用分布函数之一,用参数估计法求取各分布参数及分布概率,根据关联度最大原则确定最佳拟合分布函数。将两部分费用模型综合考虑,可建立总的费用模型,由此可计算最小费用和最佳使用寿命。以某变电站综合自动化项目为例,验证了该方法的有效性。     

电子商务下基于改进两阶段算法的有时间窗车辆调度优化

为满足电子商务下的物流配送需求,将传统车辆调度模型进行修改,将目标函数改为基于费用最小,在约束条件中增加时间约束、货物容积约束、车辆最大工作时间、多种车型、载重量限制和最大行驶距离等,以提高模型的适用性和通用性。由于有时间窗的车辆调度问题是NP难问题,采用改进两阶段算法进行求解。即第一阶段用模糊分层聚类法将客户群分成若干区域,在每个区域又用扫描算法分解成若干符合约束条件的小规模子集;第二个阶段对各个分组内客户点,就是一个个单独TSPTW模型的线路优化问题,因此,采用改进混合遗传算法进行优化求解,最后的算例仿真表明了算法的有效性和可行性。     

时间依赖型多配送中心带时间窗的开放式车辆路径问题研究

本文研究了时间依赖型多配送中心带时间窗的开放式车辆路径问题,基于道路通行情况,建立车辆行驶速度时间函数;考虑车辆载重、里程限制与客户点服务时间窗的约束,建立混合整数规划模型,目标函数为最小化车辆总成本,具体包括车辆行驶时间成本和车辆固定发车成本;提出了一种二维编码方式的混合遗传算法,针对混合遗传算法设计了多分区段单点交叉策略、动态插入算子及局部搜索策略;最后,基于Solomon VRPTW基准数据集生成27个测试算例,使用混合遗传算法进行求解。数值实验结果表明,考虑道路通行情况,选择合理的出发时间,避免拥堵时段进行配送服务,能明显减少车辆的总行驶时间,且验证了混合遗传算法能够获得问题的满意解。     

具有时间转换约束的离散时间-费用权衡问题研究

离散时间-费用权衡问题(DTCTP)是项目进度中研究最多的双目标优化问题,它通常以三种形式出现:(1)P1:截止日期问题,在项目截止日期约束下使完成项目的总费用最小;(2)P2:预算问题,在费用预算约束下使项目工期最短;(3)P3:工期-费用曲线问题,找出全部有效的工期-费用模式集合。然而,考虑时间转换约束(TSC)的DTCTP却很少被关注。本文首先介绍时间转换约束的问题描述,在此基础上,建立具有活动类型时间转换约束的DTCTPTSC-P2模型;从实用角度出发,设计求解模型的遗传算法;最后,用一个真实项目实例说明模型的合理性和算法的有效性,对算例分析结果表明,该模型对承包商更准确地进行项目工期-费用权衡决策具有借鉴意义。     

基于工序异质性的关键链项目缓冲监控

通过关键链项目缓冲监控可以防止缓冲在项目执行阶段被浪费,并保证项目的工期,有效的监控方法有利于提升项目的整体绩效。为了克服统一缓冲监控方法的不足,在保证项目工期的基础上,本文考虑成本因素对项目的影响,提出了一种基于工序成本和工期敏感度的差别动态缓冲监控模型。该模型考虑工序异质性将工序划分为成本敏感型工序和工期敏感型工序,根据工序的综合感知效用进行缓冲监控分配,并结合敏感度对不同类型的工序设置不同的监控基准点和纠偏措施。仿真结果表明,差别监控相对于统一的监控模式有利于实现项目工期和成本的双优化,验证了本文方法的有效性。     

On step fixed-charge transportation problem

The fixed-charge problem is a nonlinear programming problem of practical interest in business and industry. One of its variations is the fixed-charge transportation problem (FCTP) where fixed cost is incurred for every route that is used in the solution, along with the variable cost that is proportional to the amount shipped. That cost structure causes the value of the objective function Z to also behave like a step function. Each time we open or close a route the objective function jumps a step. The step fixed-charge transportation problem (SFCTP) is a variation of the FCTP where the fixed cost is in the form of a step function dependent on the load in a given route. While the value of the objective function Z in the FCTP is a step function, the introduction of the step fixed cost in the SFCTP results in the objective function Z being itself a step function with many more steps. Fixed-charge problems are usually solved using sophisticated analytical or computer software. This paper discusses the theory of SFCTP and presents a computationally simple heuristic algorithm for solving small SFCTPs.     

Modeling External Risks in Project Management

To ascertain the viability of a project, undertake resource allocation, take part in bidding processes, and other related decisions, modern project management requires forecasting techniques for cost, duration, and performance of a project, not only under normal circumstances, but also under external events that might abruptly change the status quo. We provide a Bayesian framework that provides a global forecast of a project's performance. We aim at predicting the probabilities and impacts of a set of potential scenarios caused by combinations of disruptive events, and using this information to deal with project management issues. To introduce the methodology, we focus on a project's cost, but the ideas equally apply to project duration or performance forecasting. We illustrate our approach with an example based on a real case study involving estimation of the uncertainty in project cost while bidding for a contract.     

Single machine scheduling problems with subcontracting options

In this paper, we study a scheduling model as follows: there are n jobs which can be processed in house on a single machine or subcontracted to a subcontractor. If a job is subcontracted, its processing cost is different from the in-house cost and its delivery lead time is a stepwise function of the total processing time of outsourced jobs. Two objective functions are studied (1) to minimize the weighted sum of the maximal completion time and the total processing cost and (2) to minimize the weighted sum of the number of tardy jobs and the total processing cost. For the first problem, we prove that it is NP-hard and get a pseudo-polynomial time algorithm. For the second problem, we prove that it is NP-hard and get a pseudo-polynomial time algorithm for a special case.     

Exact approaches for the pickup and delivery problem with loading cost

In this paper, we propose a branch-and-cut algorithm and a branch-and-price algorithm to solve the pickup and delivery problem with loading cost (PDPLC), which is a new problem derived from the classic pickup and delivery problem (PDP) by considering the loading cost in the objective function. Applications of the PDPLC arise in healthcare transportation where the objective function is customer-centric or service-based. In the branch-and-price algorithm, we devise an ad hoc label-setting algorithm to solve the pricing problem and employ the bounded bidirectional search strategy to accelerate the label-setting algorithm. The proposed algorithms were tested on a set of instances generated by a common data generator in the literature. The computational results showed that the branch-and-price algorithm outperformed the branch-and-cut algorithm by a large margin, and can solve instances with 40 requests to optimality in a reasonable time frame.     

Cost/quality tradeoffs for control procedures in information systems

An analytical framework is presented to study the cost/benefit tradeoffs of alternative internal control scenarios designed to ensure quality of outputs from information systems. A mathematical model is used to evaluate the impact that various alternatives have on system performance and cost. The model can be used to compare the benefits gained from enhanced processing with those arising from more effective internal control procedures. Model variables under the control of system designers include placement and effectiveness of internal control procedures, cost and quality of processing activities, both manual and computerized, and cost and quality of correction procedures. The model incorporates a penalty cost incurred by failure to detect and correct errors. The analytical process is illustrated through application to a specific information system.     

跨企业组织协同产品开发中供应商早期参与策略研究

在跨企业组织的协同产品开发中,供应商的参与时间和设计活动间的信息交流是影响整个产品开发时间和供应商开发成本的重要因素之一。基于对设计活动的技术创新程度和下游制造商信息对上游供应商的重要程度,扩展了知识累积函数和设计返工函数。针对供应商的参与时间和信息交流次数,建立了供应商参与协同产品开发模型,通过构造考虑产品开发时间和供应商开发成本权衡的全局收益变量,证明了全局收益极大值的存在性。在此基础上,分别给出了供应商最优参与时间和最优的信息交流次数的计算公式以及供应商参与协同产品开发策略选择的判定条件。最后通过实例验证了该结论的适用性。     

Iterative Converging Algorithms for Computing Bounds on Durations of Activities in Pert and Pert-Like Models

Since its invention in 1958, Program Evaluation and Review Technique (PERT) has been widely used during the planning, design, and implementation of projects. Pert models the activities of a project as a single source-single sink directed acyclic graph where nodes represent events (end or beginning of activities) and arcs activities. The maximum amount by which an activity can be delayed without delaying the overall project is called the slack. Critical tasks have zero slack whereas all noncritical tasks have positive slacks. Pert is a valuable tool in the management of large projects since it allows to compute the slack of each activity of the project. Such information may be crucial in avoiding cost overruns that would be caused by delays to critical activities and/or excessive delays to noncritical activities. What Pert fails to provide is how one should go about distributing remaining slack on noncritical activities while taking into consideration properties of the activities as well as precedence relationships among them, so as to have reasonable upper bounds on duration of all activities, critical or noncritical. In this paper we propose several algorithms for the distribution of slack on non-critical activities. We show that if one desires to distribute the remaining slack proportionally to the initially assigned activity durations then the problem is in P, and propose an algorithm of linear time complexity. However if one desires to use distribution functions other than the initial durations of activities, then the problem of slack distribution becomes NP-complete. Finding the maximal bounds corresponding to zero-slack solution at the sink requires iterative application of exponential algorithm. For that case we introduce an approximation algorithm of linear time complexity on each iteration. The algorithm iteratively increases bounds on durations of activities and converges to the zero-slack solution on all paths from the source node to the sink node in the Pert-like graph. The algorithms described in this paper were successfully applied to solving timing bounds problems in VLSI design.