基于免疫遗传算法和列生成的多项目人力资源调度研究

主要研究列生成法求解带有人力资源约束的多项目多模式进度管理问题。首先根据问题建立了相应的数学模型,模型中考虑了多种约束,如项目对人员能力、水平的不同要求,目标为满足约束的条件下成本最小化,其中包含固定和可变两类成本。模型分解后,按照列生成法流程求解。由于问题的复杂性,采用启发式算法求解每个子问题:首先由基于优先原则的启发式方法给出问题的初始解,再由免疫遗传算法寻优。通过数值实验分析了算法性能、模型改进情况,不同优先原则组合对目标成本和各项目间时间分配的影响。     

多项目人力资源调度实证研究

针对某公寓大修项目,建立有关人力资源约束下的多项目进度管理问题混合整数规划模型。其中考虑了多种约束,如项目对人员能力、水平的不同要求,而人员又具有多种能力及水平;目标为满足约束的条件下总成本最小化,其中包含按时间计费的工资,和福利等的固定费用。为了简化计算,采用列生成法把复杂的多项目模型分解为一个主问题和多个子问题并协调主问题和子问题求解。同时由于子问题的复杂性难以精确求解,采用启发式算法求解:首先由基于优先原则的启发式方法给出问题的初始解,再由遗传算法寻优。最后通过该实际案例的应用,表明此方法能够快速有效的解决实际问题,给决策者提供信息,帮助指导实践。     

考虑延误因素的机组排班模型研究

机组排班是航空公司运营计划的重要环节。传统对机组排班问题的研究,通常不考虑延误对排班的影响,导致机组排班的鲁棒性较差。本文在传统机组排班模型的基础上考虑延误成本,以最小化各项任务成本和延误成本为目标,提出了考虑随机延误因素的机组排班数学规划模型。然后提出求解此模型的启发式列生成算法,该算法可有效缩小问题规模,减少求解过程中的迭代次数并提高求解质量。利用航空公司真实飞行数据进行测试,证明算法可在短时间内求解大规模机组排班问题。最后,通过仿真试验证实考虑延误的机组排班模型可有效提升排班的鲁棒性。     

带有一致性规范约束的航空机组排班问题研究

航空机组人员排班是航空公司运营调度过程中的重要环节,现有文献对该问题的研究主要集中在排班成本的最优化以及排班结果的鲁棒性等方面,但排班计划对机组人员工作状态的影响尚未在已有的研究中得到充分的讨论与重视。因此,本文借鉴了最早提出于车辆路径规划等问题中的一致性概念,通过对华东地区某大型民营航空公司真实航班数据的分析,提出一类新型的、具有重要价值的一致性规范约束。该类约束具体体现在生成排班计划过程中,对人员工作班次的一致性与人员过夜城市的一致性做出要求。基于我国民航规定与真实航班数据,本文构建了航空公司机组人员排班的基础模型以及包含一致性约束的拓展模型。求解算法采用了列生成算法框架,并且在针对该框架中复杂子问题的求解提出了一种新的基于动态规划的启发式算法。数值实验结果表明,该求解算法可在短时间内求解大规模的机组排班问题,求解结果显著地提升了机组排班计划的一致性,这对航空公司实际机组排班计划的制定具有重要的价值。     

求解大规模生产批量问题的启发式算法

企业资源优化模型是多物料、多层、受多种能力约束、有启动时间和启动成本的生产批量问题,该问题是NP完全问题,求解十分困难。为此我们提出了一个新的启发式方法,通过交互求解线性规划松弛问题并应用改进的Silver-Meal方法处理批量来近似求解生产批量问题,并第一次将影子价格引入Silver-Meal方法的批量决策,数值实验表明新算法在不同规模问题上的有较好的表现。     

基于持续运营机会约束的竞争设施点选址研究——一种有效的实数编码遗传求解算法

竞争设施点选址是空间经济、区域发展、组合优化和系统工程的重要课题之一。本文以市场份额最大化为目标,研究了基于持续运营机会约束的竞争设施点选址问题,并给出了一种有效的实数编码遗传求解算法。在求解模型方面,首先假定运营成本是竞争设施点规模大小的函数,并对设施点持续运营概率进行机会约束,借鉴引力模型建立竞争设施点选址-设计问题的非线性混合整数规划模型。其次,考虑到选址变量和规模变量的数值类型,以及编码变换问题,设计了一种实数编码遗传求解算法。通过数值实验表明,对不同规模问题的实际计算结果,该算法可以在较短时间内获得最优解,可行解和精确解之间误差小于0.5%,相关比较分析也讨论了该算法的优越性和实用性,为竞争设施点选址问题的研究提供了不同的视角和实用求解算法。     

基于图的广度搜索的进度生成机制

启发式算法是解决资源受限的项目调度问题的经典方法之一，通常用来生成元启发算法初始解，传统的串行（SSGS）和并行（PSGS）是生成项目调度方案的经典机制，本文基于图的广度优先搜索算法，提出了一种考虑任务节点位置因素的广度生成机制（BSSGS），并验证了算法的效果。借鉴广度搜索算法定义进度生成机制中的当前任务集合C、候选任务集合D以及阶段变量g等，对各任务节点进行层次划分并定义任务调度秩序；结合优先规则选择候选任务j^*并进行资源R_k（t）调度更新，进而生成完整的调度方案；案例分析表明新机制在满足优先规则和资源约束的同时兼顾了任务节点在网络中位置因素，拥有对于局部复杂网络不回避，对关键节点及时调度等明显优势；选择PSPLIB中算例，在不同优先规则下对新机制进行了测试，测试结果表明新的进度生成机制在LPT、SPT、MTS和MIS等优先规则下，在平均最短工期、平均资源利用率及最优调度方案率等方面优于串行和并行进度生成机制，且算法时间复杂度与传统机制相比并未增加，仍为O（J²，K）。     

考虑零件三维装载约束带时间窗的循环取货路径问题研究

为提高车辆的可装载性,对考虑三维装载约束带时间窗的循环取货路径问题进行研究.在给定假设与约束条件的前提下,建立该问题的多目标数学模型,并设计用于问题求解的基于改进策略的启发式算法.数值实例的计算结果表明,该算法可有效求解考虑零件三维装载约束带时间窗的循环取货路径问题;且与时间窗优先法的求解结果相比,可大幅提高车辆的可装载性,并能有效减少不同车型车辆的投入数量.     

计及软逻辑的重复性项目离散时间费用权衡及其约束规划模型研究

在重复性项目中,如果一个工序适用软逻辑,则其在所有单元上的子工序可以任意改变施工顺序;当雇佣额外工作队后,同一工序中的多个子工序甚至可以同时执行。考虑软逻辑的重复性项目离散时间费用权衡问题(DTCTP-RPSL)旨在确定每个工序的执行模式、工作队分配方案和单元间的施工顺序,从而在满足给定截止日期条件下最小化项目总费用。已有研究均采用遗传算法求解此问题。但是,遗传算法属于启发式方法,不能保证解的最优性。本文首先建立了描述DTCTP-RPSL的混合整数线性规划(MILP)模型,然后从约束规划(CP)角度提出了求解此问题的CP模型。该模型以区间变量定义每个子工序,并利用CP表达式强迫所有变量在可行域内取值。与MILP模型相比,CP模型在保证解最优性的同时,减少了变量和约束的规模,提升了求解效率。数值实验表明,CP模型的性能优于MILP模型和遗传算法,能够在短时间内求出小规模和中等规模问题的最优解,以及较大规模问题的高质量解。     

大规模客运专线网络运营优化模型与求解算法

本文在分析铁路运营优化模型的研究进展的基础上,提出了一个适合大规模客运专线网络运营的优化模型,并提出了求解此模型的列生成算法和启发式快速算法。目的是将客运专线网路的开行方案优化与动态收益优化问题结合起来,解决更大、更复杂的客运网络运营优化问题。模型以列车运营总收益最大化为目标。用随机生成数据进行的模型试验表明,模型及算法可以在较短的时间内求解较大规模的收益管理优化问题。     

Robust multi-sensor scheduling for multi-site surveillance

This paper presents mathematical programming techniques for solving a class of multi-sensor scheduling problems. Robust optimization problems are formulated for both deterministic and stochastic cases using linear 0–1 programming techniques. Equivalent formulations are developed in terms of cardinality constraints. We conducted numerical case studies and analyzed the performance of optimization solvers on the considered problem instances.     

A chance constrained optimization model for risk

Choice among risky investments has been described using a chance constrained programming model with a finite number of states of nature. This paper presents a simple combinational algorithm for solving this model which, at worst, requires solving a number of linear programming problems.     

A unifying framework for duality and modeling in robust linear programs

In this paper, our major theme is a unifying framework for duality in robust linear programming. We show that there are two pair of dual programs allied with a robust linear program; one in which the primal is constructed to be “ultra-conservative” and one in which the primal is constructed to be “ultra-optimistic.” Furthermore, as one would expect, if the uncertainly in the primal is row-based, the corresponding uncertainty in the dual is column-based, and vice-versa. Several examples are provided that illustrate the properties of these primal and dual models.A second theme of the paper is about modeling in robust linear programming. We replace the ordinary activity vectors (points) and right-hand sides with well-known geometric objects such as hyper-rectangles, parallel line segments and hyper-spheres. In this manner, imprecision and uncertainty can be explicitly modeled as an inherent characteristic of the model. This is in contrast to the usual approach of using vectors to model activities and/or constraints and then, subsequently, imposing some further constraints in the model to accommodate imprecision and uncertainties. The unifying duality structure is then applied to these models to understand and interpret the marginal prices. The key observation is that the optimal solutions to these dual problems are comprised of two parts: a traditional “centrality” component along with a “robustness” component.     

An improved MIP heuristic for the intermodal hub location problem

Optimization methods have been commonly developed for the intermodal hub location problem because it has a broad range of practical applications. These methods include exact methods (limited on solving large-size problems) and heuristics (no guarantee on solution quality). In order to avoid their weakness but to leverage their strength, we develop an improved MIP heuristic combining branch-and-bound, Lagrangian relaxation, and linear programming relaxation. In the heuristic, we generate a population of initial feasible solutions using the branch-and-bound and Lagrangian relaxation methods and create a linear-relaxed solution using the linear programming relaxation method. We combine these feasible and linear-relaxed solutions to fix a portion of hub location variables so as to create a number of restricted hub location subproblems. We then combine the branch-and-bound method to solve these restricted subproblems for iteratively improving solution quality. We discuss in detail the application of the method to the intermodal hub location problem. The discussion is followed by extensive statistical analysis and computational tests, where the analysis shows statistical significance of solutions for guiding the heuristic search and comparisons with other methods indicate that the proposed approach is computationally tractable and is able to obtain competitive results.     

Exact methods in optimum disassembly sequence search for problems subject to sequence dependent costs

Disassembling complex products is formally approached via network representation and subsequent mathematical modeling, aimed at selecting a good or optimum sequence of disassembly operations. This is done via heuristics, metaheuristics or mathematical programming. In contrast with heuristics and metaheuristics, which select a near-optimum solution, mathematical programming guarantees the selection of the global optimum. This problem is relatively simple if the disassembly costs can be assumed sequence independent. In practice, however, sequence dependent disassembly costs are frequently encountered, which causes NP-completeness of the problem. Although methods, e.g., based on the two-commodity network flow approach, are available to solve this constrained asymmetric Traveling Salesperson problem rigorously, this requires the introduction of integer variables. In this paper, a modification of the two-commodity network flow approach is proposed, which reduces the number of integer variables. This is applied to product structures that can be represented by a disassembly precedence graph. It is demonstrated that use of integer variables is completely avoided by iteratively solving a binary integer linear programming problem. This appears to be more efficient than solving the corresponding integer linear programming problem. It is demonstrated, on the basis of some cases, that this method might provide the exact solution of problems with increased complexity compared to those discussed so far in the literature. This appears particularly useful for evaluating heuristic and metaheuristic approaches.     

Mathematical Programming Formulations for the Discriminant Problem: An Old Dog Does New Tricks*

In recent years, much research has been done on the application of mathematical programming (MP) techniques to the discriminant problem. While promising results have been obtained, many of these techniques are plagued by a number of problems associated with the model formulation including unbounded, improper, and unacceptable solutions as well as solution instability under linear transformation of the data. In attempting to solve these problems, numerous formulations have been proposec involving additional variables and/or normalization constraints. While effective, these models can also become quite complex. In this paper we demonstrate that a simple, well-known special case of Hand's [13] original formulation provides an implicit normalization which avoids the problems for which various complicated remedies have been devised. While other researchers have made use of this formulation, its properties have not previously been fully recognized.     

An efficient heuristic procedure for solving the layout design problem

The limited ability of schematic procedures, constraints of linear programming techniques, inflexibility of construction methods and inadequacy of dynamic programming approaches to provide acceptable solutions to realistic size layout design problems has led to an ever increasing interest in heuristic procedures. Comparative studies have shown that heuristic procedures can satisfy more desirable qualities in an ‘ideal algorithm’ to a greater extent than competitive techniques. Excessive computational effort, which has been one of the main criticisms levelled against heuristic approaches in the past, proves to be less of a problem in relation to layout design. By utilizing unique attributes associated with real-life problems and using small incisive modifications it is demonstrated how a heuristic procedure can be significantly improved.     

Linear programming approach to solve interval-valued matrix games

Matrix game theory is concerned with how two players make decisions when they are faced with known exact payoffs. The aim of this paper is to develop a simple and an effective linear programming method for solving matrix games in which the payoffs are expressed with intervals. Because the payoffs of the matrix game are intervals, the value of the matrix game is an interval as well. Based on the definition of the value for matrix games, the value of the matrix game may be regarded as a function of values in the payoff intervals, which is proven to be non-decreasing. A pair of auxiliary linear programming models is formulated to obtain the upper bound and the lower bound of the value of the interval-valued matrix game by using the upper bounds and the lower bounds of the payoff intervals, respectively. By the duality theorem of linear programming, it is proven that two players have the identical interval-type value of the interval-valued matrix game. Also it is proven that the linear programming models and method proposed in this paper extend those of the classical matrix games. The linear programming method proposed in this paper is demonstrated with a real investment decision example and compared with other similar methods to show the validity, applicability and superiority.     

A Dynamic Disaggregation Approach to Approximate Linear Programs for Network Revenue Management

The linear programming approach to approximate dynamic programming has received considerable attention in the recent network revenue management (RM) literature. A major challenge of the approach lies in solving the resulting approximate linear programs (ALPs), which often have a huge number of constraints and/or variables. Starting from a recently developed compact affine ALP for network RM, we develop a novel dynamic disaggregation algorithm to solve the problem, which combines column and constraint generation and exploits the structure of the underlying problem. We show that the formulation can be further tightened by considering structural properties satisfied by an optimal solution. We prove that the sum of dynamic bid‐prices across resources is concave over time. We also give a counterexample to demonstrate that the dynamic bid‐prices of individual resources are not concave in general. Numerical experiments demonstrate that dynamic disaggregation is often orders of magnitude faster than existing algorithms in the literature for problem instances with and without choice. In addition, adding the concavity constraints can further speed up the algorithm, often by an order of magnitude, for problem instances with choice.     

Semidefinite Programming Relaxations for the Quadratic Assignment Problem

Semidefinite programming (SDP) relaxations for the quadratic assignment problem (QAP) are derived using the dual of the (homogenized) Lagrangian dual of appropriate equivalent representations of QAP. These relaxations result in the interesting, special, case where only the dual problem of the SDP relaxation has strict interior, i.e., the Slater constraint qualification always fails for the primal problem. Although there is no duality gap in theory, this indicates that the relaxation cannot be solved in a numerically stable way. By exploring the geometrical structure of the relaxation, we are able to find projected SDP relaxations. These new relaxations, and their duals, satisfy the Slater constraint qualification, and so can be solved numerically using primal-dual interior-point methods.For one of our models, a preconditioned conjugate gradient method is used for solving the large linear systems which arise when finding the Newton direction. The preconditioner is found by exploiting the special structure of the relaxation. See e.g., Vandenverghe and Boyd (1995) for a similar approach for solving SDP problems arising from control applications.Numerical results are presented which indicate that the described methods yield at least competitive lower bounds.