基于MAS的多模式分布式资源约束多项目调度

针对实践中分布式多项目的活动往往具有多种执行模式,提出多模式分布式资源约束多项目调度问题。在项目动态到达环境下,考虑活动不同的执行模式,以工期最短和多项目延期成本最小为目标分别构建局部单项目调度模型和全局多项目决策模型,采用改进变邻域搜索算法求解初始局部调度计划,并设计基于模式调整的全局协商调度算法求解全局决策模型,通过双层算法实现分布式多项目调度中局部单项目调度与全局多项目调度系统性协调,减少项目中断和多项目延期成本。基于构建的多模式测试集进行的多项目数值实验表明：本文设计的双层算法可有效求解多模式分布式多项目调度问题,并且对不同规模问题求解具有良好的适应性。     

带时间窗取送货问题的混合算法

为解决带时间窗的取送货问题,建立了集合划分模型,设计列生成算法与启发式规则相结合的CGA混合算法进行求解。首先,放松约束构建主问题及受限主问题,运用单纯形法与分支定界进行求解;其次,建立时空网络以构建子问题,基于修正的Dijkstra's算法,设计包含算法A、B1、B2的求解算法;最后,通过启发式算法解决节点重复覆盖问题。为验证算法有效性,进一步构建了OPT近似最优解算法;并基于CGA提出三种求解策略C1、C2、C3,做单因素方差分析,采用算例分析算法的性能。实验结果表明,对于客户点数量小于30的小规模算例,CGA与OPT所得结果相近,但CGA求解效率更显著;针对客户点数量为600的大规模算例,CGA至多在20分钟内求得结果,可见本文算法的精度和效率较高。而针对不同类型及规模的客户点的单因素方差分析结果显示,C1、C2、C3在“平均行驶距离成本”、“平均车辆数”、“平均求解时间”三个维度上差异性显著,经营者可根据实际需求进行策略选择。     

Copula-CVaR下考虑随机成本和需求的单周期订货决策研究

不确定环境下的单周期最优订货量决策具有重要且广泛的应用价值。与传统的仅考虑需求不确定性的报童模型不同,本文考虑市场价格恒定,但成本和需求随机变化且相关联下的报童决策问题。为此,采用Copula函数构建成本和需求之间的关联,考虑决策者可能具有的风险态度,建立了相应的Copula-CVaR模型,证明了模型解的存在性和唯一性,并将模型离散化为易求解的线性规划问题。最后,通过不同的风险水平和多种Copula函数下的仿真,分析了随机成本与需求的相关性和波动性对最优决策结果影响,并得到相关结论,为相关企业决策提供依据。     

供应提前期和需求不确定下库存系统的随机比较

本文研究供应提前期和需求不确定下包含最小化成本和最大化利润的一致化报童问题中随机比较实现的充分条件,并通过随机比较定量刻画提前期和需求不确定性对库存系统决策和利润的影响。首先引入报童收益函数,给出其优化前后满足随机占优及拉普拉斯变换序的充分条件。进一步,在周期需求服从指数分布的情形下,定量刻画固定提前期与提前期服从几何分布两种情况的随机单调性。最后,将上述结论应用到报童模型中,得到提前期需求对一致化报童问题的随机单调性。     

随机模糊需求报童问题

考虑到需求的随机模糊性,建立了随机模糊需求报童的利润模型。利用可信性测度理论给出了其期望利润模型,并揭示了期望利润函数的凹性,证明了最优订货量的存在性和唯一性。结合随机模糊模拟技术和随机扰动近似算法设计了求解最优订货量的混合算法。最后,通过数值算例说明了算法的有效性。     

线状需求下的长江航道危险品应急中心选址优化

本文分析了长江航道危险品船舶对应急中心救援服务的线状需求特征,基于点状需求的设施选址模型,构建了全覆盖下的最小成本选址模型,实现了线状需求特性与最小成本的最优结合。将点状需求的设施选址研究延伸到线状需求的设施选址研究领域。并且针对模型设计了确定性规划算法和遗传算法。最后以长江航道为具体算例,对比了确定性规划算法和遗传算法对模型进行求解的效率及精度。实例表明,本文建立的基于线状需求的应急中心选址模型是符合实际的,确定性规划算法相对于遗传算法可以在更短时间内求得较稳定的最优解;遗传算法运行时间相对较长,且结果稳定性较差。     

可追加订购的报童问题

研究带有追加 (两次 )订购的报童模型 ,分析了此模型与经典 (一次订购 )报童模型的收益关系 ,服务水平评价 ,订购量与需求均值、方差、价格等的灵敏度及发现了在适当的条件下 ,最大追加订购量 M的最优解存在 ,且给出了求解的方法 .     

带冲突关系装箱问题的启发式求解算法

现实物流活动中大量存在的食品、药品和危险品等货物的分组包装问题属于带冲突关系的装箱问题(BPPC),其优化目标是在满足货物间冲突限制的前提下完成装箱操作,并最小化使用货箱的数量。本文从实际需求出发,基于货物之间的冲突关系、装箱顺序和货箱容量等约束建立相应的数学规划模型;随后设计了求解BPPC问题的启发式算法,算法通过迭代求解最大团结构实现货物间冲突关系的消去,根据当前货物最大团采用改进降序首次适应算法(FFD)完成货物装箱操作,并通过“洗牌”策略对已有装箱方案进行局部优化;最后,针对Iori算例数据,将以上算法与基于图着色的启发式算法进行比较分析,结果表明,本文算法是求解BPPC问题更为有效的方法。     

“供应侧”鲁棒报童模型

完全信息下的报童模型是研究单周期下企业运营的核心方法,制定不同情形下的订货决策是提高其运作效率的主要策略.Scarf在1958年构建了需求侧不确定时部分信息下的鲁棒报童模型,经过GallegoMoon更简便的证明后Worst-case的鲁棒订货方法得到了广泛的应用,供应侧不确定时的订货问题由于求解的困难性导致运作管理学者长期受其困扰.文章假设报童只知道供应商随机产出因子的均值和方差信息,建立了Worst-case的鲁棒订货模型,给出了订货决策的闭式最优解.研究表明:鲁棒报童模型能够恰当的描述供应侧信息缺失下的企业订货行为,鲁棒的订货策略能有效解决供应不确定的信息缺失环境下企业的订货决策问题.     

考虑空重箱转换的港口集装箱甩挂运输问题研究

针对港口堆场与内陆腹地客户之间的空重集装箱运输问题,本文结合甩挂运输的特点将客户的进出港需求拆分为相互关联的空箱和重箱任务,实现单个决策期内运输系统中集装箱的状态转换与回收工作。状态转换受集装箱货物装卸时间影响,因此需要合理调度牵引车路线,以满足前置任务约束。针对此类问题的特点,本文建立了空重箱运输任务整合的整数规划模型,并设计了基于集群选择的改进蚁群算法进行求解。最后,通过不同规模的仿真算例与现有数学模型及优化算法对比结果可知,本文所提出的改进蚁群算法在此类问题的最优解搜索中具有良好的稳定性和求解效率。     

价格数量折扣下多阶段报童问题的在线策略

价格数量折扣可以提高订购量, 是库存决策中的一个重要因素. 特别地, 当订购量达到一定水平时, 价格折扣才会发生. 应用理论计算机科学兴起的弱集成算法, 研究具有这种价格数量折扣的多阶段报童问题的在线策略. 弱集成算法是一种在线序列决策算法, 其主要特点是不对未来输入做任何统计假设, 克服了报童问题研究中需要对需求做概率假设的困难. 主要将弱集成算法应用到固定订购量的专家策略, 给出了价格数量折扣下多阶段报童问题的具体在线策略;得到了该在线策略相对于最优专家策略的理论保证. 进一步将回收价值和缺货损失费引入, 给出了推广的在线策略及其理论结果. 最后应用数值算例说明了给出的在线策略具有较好的竞争性能.     

Using separable programming to solve the multi-product multiple ex-ante constraint newsvendor problem and extensions

This paper provides an approximating programming technique to solve the multi-product newsvendor model in which product demands are independent and stocking quantities are subject to two or more ex-ante linear contraints, such as budget or volume constraints. Previous research has attempted to solve this problem with Lagrange relaxation techniques or by limiting the distribution of demand. However, by taking advantage of the separable nature of the problem, a close approximation of the optimal solution can be found using convex separable programming for any demand distribution in the traditional newsvendor model and extensions. Sensitivity analysis of the linear program provides managerial insight into the effects of parameters of the problem on the optimal solution and future decisions.     

A benchmark solution for the risk-averse newsvendor problem

In this paper, we derive the first order conditions for optimality for the problem of a risk-averse expected-utility maximizer newsvendor. We use these conditions to solve a special case where the utility function is any increasing differentiable function, and the random demand is uniformly distributed. This special case has a simple closed form solution and therefore it provides an insightful and practical interpretation to the optimal point. We show some properties of the solution and also demonstrate how it can be used for assessing the newsvendor utility function parameters.     

Multi-tier binary solution method for multi-product newsvendor problem with multiple constraints

This paper considers a multi-product newsvendor problem with multiple constraints. Multiple constraints in the problem make it more challenging to solve. Previous research has attempted to solve the problem by considering two-constraint case or/and using approximation techniques or active sets methods. The solution methods in literature for solving multi-constraint problem are limited or cumbersome. In this paper, by analyzing structural properties of the multi-constraint multi-product newsvendor problem, we develop a multi-tier binary solution method for yielding the optimal solution to the problem. The proposed method is applicable to the problem with any continuous demand distribution and more than two constraints, and its computational complexity is polynomial in the number of products. Numerical results are presented for showing the effectiveness of our method.     

基于网络流理论的非线性规划评价模型

针对既有的评价模型缺乏对评价结果保序性的讨论,以及难以有效处理缺失数据的问题,本文建立了一个新的评价模型用以解决以上问题。该模型建立在三个标准的基础上,这三个标准分别为“结果一致性”、“最小偏离性”和“最小差异性”,其为模型的建立提供了依据和理论基础;在已建立的非线性规划模型基础上,进行了模型的性质讨论,并将其归结为一类最小凸费用循环流的统一表述,这是解决模型的算法问题和揭示其蕴含的更为深刻的管理学意义的核心;最后,模型被用于一个示例分析和含有缺失数据的大规模数据集的实证分析,这些分析论证了该新模型的有效性。本文的模型提供了新的评价工具,扩展了运筹学和决策科学之间相互运用的案例,具有较好的保序性和处理缺失数据的能力,含有理论和实践的双重意义。     

A fuzzy newsvendor approach to supply chain coordination

In the absence of a clear command and control structure, a key challenge in supply chain management is the coordination and alignment of supply chain members who pursue divergent and often conflicting goals. The newsvendor model is typically used as a framework to quantify the cost of misalignment and to assess the impact of various coordination initiatives. The application of the newsvendor framework, however, requires the specification of some probability distribution for the sources of uncertainty, and in particular, for the market demand. The specification of an adequate demand distribution becomes difficult in the absence of statistical data. We therefore consider a fuzzy approach to the newsvendor problem. We use several fuzzy parameters in the model for the demand, the wholesale price, and the market sales price. We solve the fuzzy newsvendor problem to study three coordination policies: quantity discounts, profit sharing, and buyback. For each coordination policy, the optimal order quantity of the retailer is computed. The possible profits of the members in the supply chain are calculated with minimum sharing of private information. We further extend the fuzzy newsvendor model to a setting with a single manufacturer and multiple retailers under the assumption of ample capacity for the manufacturer. Detailed numerical examples are also provided.     

Robust optimization of uncertain multistage inventory systems with inexact data in decision rules

In production-inventory problems customer demand is often subject to uncertainty. Therefore, it is challenging to design production plans that satisfy both demand and a set of constraints on e.g. production capacity and required inventory levels. Adjustable robust optimization (ARO) is a technique to solve these dynamic (multistage) production-inventory problems. In ARO, the decision in each stage is a function of the data on the realizations of the uncertain demand gathered from the previous periods. These data, however, are often inaccurate; there is much evidence in the information management literature that data quality in inventory systems is often poor. Reliance on data “as is” may then lead to poor performance of “data-driven” methods such as ARO. In this paper, we remedy this weakness of ARO by introducing a model that treats past data itself as an uncertain model parameter. We show that computational tractability of the robust counterparts associated with this extension of ARO is still maintained. The benefits of the new model are demonstrated by a numerical test case of a well-studied production-inventory problem. Our approach is also applicable to other ARO models outside the realm of production-inventory planning.     

A two-bottleneck system with binomial yields and rigid demand

This study considers multistage production systems where production is in lots and only two stages have non-zero setup costs. Yields are binomial and demand, needing to be satisfied in its entirety, is “rigid”. We refer to a stage with non-zero setup cost as a “bottleneck” (BN) and thus to the system as “a two-bottleneck system” (2-BNS). A close examination of the simplest 2-BNS reveals that costs corresponding to a particular level of work in process (WIP) depend upon costs for higher levels of WIP, making it impossible to formulate a recursive solution.For each possible configuration of intermediate inventories a production policy must specify at which stage to produce next and the number of units to be processed. We prove that any arbitrarily “fixed” production policy gives rise to a finite set of linear equations, and develop algorithms to solve the two-stage problem. We also show how the general 2-BNS can be reduced to a three-stage problem, where the middle stage is a non-BN, and that the algorithms developed can be modified to solve this problem.     

航空器供油问题中完全逆序类中的多项式时间可解类

航空器供油问题是一类非线性组合优化问题,其目标函数为分式形式,该问题目前不存在多项式时间算法,也未被证明是NP完全问题。一般可以用置换来刻画n架飞机的一个供油顺序。该问题中有一类实例被称为“完全逆序类”,“完全逆序类”用动态规划算法求解计算时间为O(n2ⁿ),具有指数时间复杂度。本文通过对该“完全逆序类”问题做进一步分析,发现在“完全逆序类”中也存在着多项式时间可解的情况。定理1研究一类一次可解的情况,若问题满足定理1的条件,则求解一次即可找到其最优解;定理2研究一类多项式时间可解的情况,当问题满足定理2的条件时,其最优解可在多项式时间内获得。