具有线性减少加工时间的资源约束单机排序问题

讨论具有连续资源的单机排序问题.在这一模型中,工件的准备时间是所消耗资源的非负严格减少连续函数,工件的加工时间是开工时间的严格减少线性函数.考虑两类问题,第一类问题的目标函数是在满足最大完工时间限制条件下极小化资源消耗总量.第二类问题的目标函数是在满足资源消耗总量限制条件下极小化最大完工时间.对两类问题讨论了最优排序的某些特征.基于对问题的分析,分别给出了求解最优资源分配的方法.结果表明,加工时间为常数情况的结论对于加工时间是开工时间线性函数的情况仍然成立.     

机会约束下不允许无风险借入的均值-VaR投资组合模型

在投资组合回报率服从正态分布的前提下,建立了允许无风险借出但不允许无风险借入的具有投资机会约束的均值-VaR投资组合模型,讨论了模型最优解的存在唯一性,并指出了最优解的位置.     

资源约束下的投资优化模型

资源约束下的投资问题在决策中很常见.本文提出运用边际净现值比较的思想来解决资源约束下多项目多地区投资决策问题的观点,并且尝试用"区域影响力系数"来衡量区域经济规模对投资项目的影响.在此基础上建立了资源约束下的投资优化模型,并给出解决此类问题的方法.     

恶化率与工件无关的线性加工时间调度问题

讨论恶化率与工件无关的线性加工时间调度问题 .对于工件间具有平行链约束 ,目标函数为极小化最大完工时间的单机问题 ,分别就链不允许中断和链允许中断两种情况给出了最优算法 .对于工件间没有优先约束 ,目标函数为极小化完工时间和的平行机问题 ,证明了工件按基本加工时间不减排列可以得到最优调度 .     

一种部分约束满足车辆路线问题及其求解算法

描述了一类过度约束车辆路线问题，其中可用车辆数较少而时间窗口等其它约束又不允许放松，因而导致不存在满足所有约束的可行解。此时问题求解可以转化为一类部分约束满足问题来处理，相应的优化目标是最小化未访问顾客的损失和。本给出了求解这类特殊问题的一种禁忌搜索算法设计，并通过规模不同的几个算例与其它常用方法进行了比较。最后分析了模型和算法的实用意义。     

资源受限下森林火灾应急救援多目标调度优化

许多森林火灾由于救援资源受限而不能在第一时间扑灭,导致火灾扩大蔓延,进而造成更大的森林资源损失。因此,在救援资源受限情形下,如何对消防救援车辆进行合理的调度安排以快速和低成本地扑灭火灾已成为亟待解决的现实问题。本文研究了一类资源受限下森林火灾应急救援多目标调度优化问题,为该问题构建了多目标混合整数非线性规划模型,优化目标为同时最小化总灭火救援时间和救援车辆总行驶距离。为有效求解该问题,首先将上述非线性模型等价转化为线性模型。然后提出ε-约束法和模糊逻辑相结合的算法对问题进行求解。最后,以大兴安岭山发生的火灾案例和随机生成仿真算例对模型和算法有效性进行验证,结果表明所提出的模型和算法能够有效解决资源受限下森林火灾应急救援问题,并为决策者提供最优的消防调度方案。     

平衡约束优化问题可行的充分条件

提出了平衡约束优化问题可行的一个充分性条件,该类优化问题中除平衡约束以外的关联约束中允许同时出现状态变量和设计变量.     

破产控制约束下组合投资:两阶段MiniMax模型

以绝对偏差函数作为风险测度,考虑不允许卖空约束条件下基于MiniMax的多期证券组合选择问题。为了避免在投资周期内破产事件的发生,增加了风险控制约束。利用动态规划和拉格朗日乘子法,给出了两阶段MiniMax投资组合模型最优解析策略。本文所提出策略可以为需要同时资产管理和破产控制的投资者提供决策依据。     

短期维度下手术排程优化问题的数学模型研究

在国内医院手术室的运作管理中,普遍存在护士加班时间长和资源利用不均衡的问题.短期维度下的手术排程优化关注手术时间的确定和优化配置完整手术流程中所需的各类手术资源,考虑到手术排程优化问题的复杂性和实用性,本研究中我们从基本的择期手术排程优化模型,而后引入全面的护士资源的排班约束,再进一步将单目标的数学模型扩展到多目标,较为系统、完整地研究了医院手术室的短期手术排程模型.我们通过仿真算例、文献算例和医院实际调度算例结果进行比较,验证结果发现基于所研究的系列排程数学模型的优化排程解在均衡手术室和护士工作时间、减少护士最大加班时间和总加班时间上具有较大程度的改善,多目标模型较单目标模型总体优化效果更为明显.由于医院管理水平不同,数学模型的约束条件也有不同,医院管理者可以使用对应的数学模型进行手术排程.研究成果可为医院管理形成新的优化决策手段,可以用来提升手术室各类资源的利用率,最终达成医院增加日开放手术台数,缩短平均住院日的手术室管理目标,在优化医院服务管理实践上有普遍意义.     

极小化最大提前完工费用的可中断排序问题

讨论了带截止期限的$n$个工件在单机上加工,工件间存在优先约束,在允许机器空闲的条件下,确定一个工件的可中断排序,极小化最大提前完工费用.首先考虑两种特殊情形:(1)截止期限相同,存在优先约束;(2)截止期限任意,不存在优先约束.针对两种情形分别给出了时间复杂度为$O(n^2)$的算法.在此基础上,考虑普遍情形,即截止期限任意,存在优先约束,也给出了一个时间复杂度为$O(n^2)$的算法.由于工件不允许延迟,问题可能会无可行排序,需先对问题的可行性进行讨论.     

一类稀疏约束非线性规划的约束规格

研究一类带有闭凸集约束的稀疏约束非线性规划问题,这类问题在变量选择、模式识别、投资组合等领域具有广泛的应用.首先引进了限制性Slater约束规格的概念,证明了该约束规格强于限制性M-F约束规格,然后在此约束规格成立的条件下,分析了其局部最优解成立的充分和必要条件.最后,对约束集合的两种具体形式,指出限制性Slater约束规格必满足,并给出了一阶必要性条件的具体表达形式.     

A General Approach for Constraint Solving by Local Search

In this paper, we present a general approach for solving constraint problems by local search. The proposed approach is based on a set of high-level constraint primitives motivated by constraint programming systems. These constraints constitute the basic bricks to formulate a given combinatorial problem. A tabu search engine ensures the resolution of the problem so formulated. Experimental results are shown to validate the proposed approach. This revised version was published online in August 2006 with corrections to the Cover Date.     

基于动态列生成算法的飞机排班问题研究

飞机排班是航空运输生产计划的重要环节,对航空公司的正常运营和整体效益有着决定性影响;飞机排班通常构建为大规模整数规划问题,是航空运筹学研究的重要课题,构建的模型属于严重退化的NP-Hard问题.在考虑对多种机型的飞机进行排班时,大大增加了问题的复杂性.针对航空公司实际情况,建立多种机型的飞机排班模型;为实现模型的有效求解,提出了基于约束编程的动态列生成算法;即用约束编程快速求解航班连线(航班串)并计算航班串简约成本,动态选择列集并与限制主问题进行迭代.最后,利用国内某航空公司干线航班网络实际数据验证模型和算法的有效性.     

A mixed variational formulation of a contact problem with adhesion

A mathematical model describing the contact between a viscoplastic body and a deformable foundation is analyzed under small deformation hypotheses. The process is quasistatic and in normal direction the contact is with adhesion, normal compliance, memory effects and unilateral constraint. We derive a mixed-variational formulation of the problem using Lagrange multipliers. Finally, we prove the unique weak solvability of the contact problem.     

Optimal insurance under the insurer’s risk constraint

In this paper, we impose the insurer’s risk constraint on Arrow’s optimal insurance model. The insured aims to maximize his/her expected utility of terminal wealth, under the constraint that the insurer wishes to control the expected loss of his/her terminal wealth below some prespecified level. We solve the problem, and it is shown that when the insurer’s risk constraint is binding, the solution to the problem is not linear, but piecewise linear deductible. Moreover, it can be shown that the insured’s optimal expected utility will increase if the insurer increases his/her risk tolerance.     

An FPTAS for scheduling with resource constraints

We study a basic scheduling problem with resource constraints: A number of jobs need to be scheduled on two parallel identical machines with the objective of minimizing the makespan, subject to the constraint that jobs may require a unit of one of the given renewable resources during their execution. For this NP-hard problem, we develop a fully polynomial-time approximation scheme (FPTAS). Our FPTAS makes a novel use of existing algorithms for the subset-sum problem and the open shop scheduling problem.     

On Constraint Qualification in Multiobjective Optimization Problems: Semidifferentiable Case

Some versions of constraint qualifications in the semidifferentiable case are considered for a multiobjective optimization problem with inequality constraints. A Maeda-type constraint qualification is given and Kuhn–Tucker-type necessary conditions for efficiency are obtained. In addition, some conditions that ensure the Maeda-type constraint qualification are stated.     

基于外包决策的并行调度随机模型

在传统的并行机器调度问题基础上引入了不确定随机变量,同时考虑了以产品外包为能力拓展形式的现代生产模式,建立了基于外包决策的并行调度随机模型.模型以带有拖期惩罚函数的最大化利润为目标,以遗传算法这种进化的启发式计算方法寻找最优解.同时引入虚拟机器的概念,实现了对外包情形下机器调度问题的有效处理和简化.实例证明,该模型更符合现代生产模式,极大地提高了企业的工作效率和经济效益.     

基于时间约束的生产过程优化问题研究

本文提出一个实际的生产过程优化问题:基于时间约束的生产过程优化问题。客户要求企业在规定时间内完成指定批量工件的生产任务,该问题便是从中引出的。该问题的目标是在满足生产时间的条件下最小化总生产成本。本文为该问题建立了整数规划模型。然后以某厂工作缸生产过程为例,采用数学规划软件Cplex 9.0求解模型。     

一类受时间约束的广义运输问题的求解

研究一类受时间约束的广义运输问题,将时间约束转化为容量约束,并将该问题转化为标准的最小费用流问题进而求解.该方法能够较快地找到最优运输方案.