一种利用图形内角的多边形布尔运算新算法

现有的平面多边形布尔运算在一般情况下可以快速地获得正确结果,但如遇到奇异情况,则会产生错误。因此,采用图形内角概念分析奇异情况,并在原有交点遍历算法框架基础上给出一种全局化的奇异处理算法。与其他的多边形布尔运算算法相比,该算法对奇异的分析更为简洁有效,且具有高效性和鲁棒性。     

Preference Trade-Offs In Capital Budgeting Decisions

Capital budgeting analysis may be characterized as an attempt to satisfy a set of potentially conflicting objectives. Corporate managers may be faced with multiple and conflicting objectives. The wide-spread acceptance of prioritized objectives in capital budgeting has stimulated the adoption of pre-emptive goal programming models. This paper presents a procedure to model a goal programming based capital budgeting model as a polynomial expression where inter-and intra-goal trade-offs can be achieved subject to the marginal rates of substitution between preference levels.     

延时受限启发式组播路由算法

给出了一种带延时约束的组播路由算法，旨在确定组播路由，不仅要使网络通信的费用达到最小，而且要保证源节点到每个目的节点的延时满足给定约束。此算法具有易于实现、计算量小且所需传递信息量小等优点。仿真结果表明此算法性能良好。     

Capital Budgeting and Mixed Zero-One Integer Programming

The capital budgeting problem for a firm deals with the allocation of limited amounts of capital among a specified set of investment opportunities. In this article, we assume the investment opportunities are indivisible in nature and that the firm desires to make this allocation in such a way as to maximize the discounted sum of dividends paid to its shareholders. From a mathematical programming standpoint, the problem may be classified as a mixed zero-one integer programming problem. Special solution techniques based on Benders's partitioning procedure and Balas's zero-one algorithm are developed for this problem. The solution algorithm may be extended to general mixed-integer programming problems.     

A Heuristic Programming Algorithm for Warehouse Location

A new heuristic programming method of solving a particular type of warehouse location problem is presented. The problem is to allocate K or less facilities to N possible locations so as to service M demand centers at minimum cost. The algorithm presented is suitable for hand calculation of medium-size problems (50 × 50) or when computerized will readily solve large-scale problems of the order of (600 × 600); i.e., 600 demand centers and 600 possible locations.     

钢管冷区生产调度的一种启发式算法

基于国内大型钢铁公司的实际操作,运用离散化时间的方法把钢管冷区生产调度抽象为可中断Job-Shop问题.同时考虑前置库存限制、生产尽可能连续、部分人工调度等约束条件,以最小化中断次数和尽可能满足人工调度为目标,建立相应的数学模型.再依据约束条件的主次性设计生产调度规则(赋值规则和生产规则),根据实际生产流程设计启发式算法.运用该算法对该问题的大规模算例进行求解,其结果在满足了约束条件情况下达到比较理想的中断次数.     

钢管生产的合同组批优化算法

钢管生产的合同组批优化问题是一个典型的组合优化问题,对钢管生产企业的计划排程、生产效率及市场反应速度等有重要影响。以生产批量、热区分段长度为优化目标,考虑了多种约束条件,提出了一套解决该问题的算法,并已运用于生产实际中,具有推广价值。     

一种动态识别瓶颈机床的前向启发算法

为了解决作业车间调度问题中的瓶颈漂移和动态识别问题,提出了一种动态识别瓶颈机床的前向启发算法.该算法引入搜索空间的概率分析方法,通过工序开工概率、工序对机床的独立需求概率、机床累计需求概率和3个量化参数,构造了以竞争高峰时段的机床负荷量大小为判定依据的瓶颈机床识别启发规则.实验结果表明该方法能够有效识别瓶颈机床,使得大规模作业车间调度的求解复杂度显著降低.     

混合流程型企业主生产计划的启发式算法

提出了一个新的启发式算法,该启发式算法称为多目标主生产计划算法(MOMPS),用于解决混合流水线车间的主生产计划安排,该启发式算法主要有以下目标:最小化拖期惩罚,最小化完工时间,最小化装设和库存成本等.该算法先对所有的定单进行排序,然后根据最小生产成本树及其该树的最大生产能力进行定单的分配,如果定单数量超出了最大生产能力,对生产网络进行调整,通过比较次优生产成本树和拖期以后的最小生产成本决定定单是否该拖期.最后通过和一般的线性规划进行比较,得出该算法在解决混合流程型企业的多目标主生产计划的制定中十分有效,有时得到的结果和线性规划模型解出的解是一致的.     

一个实用的矩形件优化排样启发式算法

仔细研究了传统矩形件优化排样近似算法及存在的主要问题，提出一个新的启发式算法。该算法根据最后板材的实际排放情况，采用了多种排放策略，克服了原算法的在零件数较少时的缺陷。在此基础上用Visual C 6．0开发了一个实用的矩形件计算机辅助排样系统。实际应用表明，新算法可获得比原近似算法更好的优化排样结果。笔者给出了算法的具体实现方法和步骤．     

A Heuristic Algorithm for the Mixed Chinese Postman Problem

The Chinese Postman Problem (CPP) is to find a minimum-cost Eulerian tour in a given graph. CPP is efficiently solvable when the original graph is either undirected or directed. For a mixed graph consisting of both edges and arcs, the Mixed Chinese Postman Problem (MCPP) is known to be NP-complete. Many heuristics and optimal algorithms have been devised for solving MCPPs. A new heuristic is proposed. The heuristic finds the initial solution by using a Minimum Cost Flow algorithm; then it repeatedly uses the shortest path algorithm with slightly modified costs of the edges/arcs. The heuristic improves the solution by trying to find the correct direction of unoriented edges and simultaneously it deletes some of the additional edges/arcs. A number of previous heuristics are tested, analyzed, and compared with the proposed approach. Based upon computational results, the proposed heuristic on average outperforms all previous heuristics.     

A Parallel Heuristic Algorithm for Lot-Sizing in Multistage Production Systems

Existing studies on heuristic lot-sizing techniques for multistage production systems concentrate on optimizing the production operations of the individual stages. This approach induces a family of heuristics, in which the production plans for the individual stages are computed sequentially starting from the final stage. In this paper we introduce a parallel heuristic for the problem. The method, which may be considered as the generalization of the single stage Wagner-Whitin algorithm, attempts to optimize over all stages simultaneously, while building the production plans in a forward manner. In computational experiments the new algorithm performed extremely well.     

基于Project 2003的关键链启发式算法

介绍了关键链项目管理的基本方法;针对资源受限项目调度问题,提出了资源冲突时的资源分配原则;以项目工期最小化为目标,以Proiect 2003为辅助工具,提出了一个确定关键链的启发式算法,即在找出关键路径的基础上,从后往前遍历,对发生资源冲突的活动,依资源分配原则修改紧前关系,然后再确定关键链,进而得到了基于关键链项目管理方法的项目调度算法.对算法进行了验证,结果表明算法是有效的.     

Capital Budgeting and Mixed Zero-One Integer Programming, the Quadratic Case

The capital budgeting problem is treated as a part of the general theory of choice, where utility is to be maximized subject to the opportunities and constraints. The utility function is assumed to be quadratic to take care of any risk-averse behavior of the shareholders and a quadratic mixed zero-one integer programming model is developed. Special solution techniques for the resulting mixed zero-one integer quadratic programming model are discussed.     

A Heuristic Algorithm for the Multi-Item Lot-Sizing Problem with Capacity Constraints

A heuristic algorithm is presented for solving the scheduling of several items in parallel under capacity constraints with setup and carrying costs. The method is based upon finding a lower bound solution for these costs, securing the feasibility of the solution, and improving the feasible solution so obtained until no further improvements can be made. Comparison of the performance of the proposed heuristic algorithm to that of an exact mixed-integer programming model showed that best solution costs found by the heuristic deviated on an average by 1% from the optimal values, while the computing time was on an average 1/140 of that required by the exact method.     

Experimental Design for Pharmaceutical Process Characterisation and Optimisation Using an Exchange Algorithm

Abstract

Efficient experimental design may be used to maximise the information available from a given number of experiments (1, 2, 3, 4). In the development of new molecules the amount of drug available for formulation studies is often restricted. Thus in studying a given process the experiment is designed so that the necessary information is obtained given there is only enough material for a limited number of operations.

We have studied the effects of process variables on the characteristics of a conventional tablet formulation of a soluble drug; the factorial design was optimised by an exchange algorithm.     

基于启发式调度规则的能力需求计划算法

传统的能力需求计划方法不能准确地反映实际生产能力需求与负荷.为此设计了基于启发式调度规则的能力需求计划算法,该算法将基于启发式规则的调度算法作用于物料需求计划进行能力需求计算,并对设备负荷率、关键设备资源和关键任务等关键能力信息的计算方法进行了重新定义,以更加真实地反映计划期内计划的能力需求与设备负荷状态.该算法已应用...     

Some Problems in the Use of a Discount Rate for Constrained Capital Budgeting

Widely advocated mathematical programming models for constrained capital budgeting call for the maximization of total net present value of undertaken projects. However, very little attention has been given to the problem of choosing a suitable discount rate. Baumol and Quandt concluded that, if reference is limited to the model itself, a meaningful choice of rate cannot be made. Recent proposals of Mao and of Lusztig and Schwab contradict that conclusion. This paper supports Baumol and Quandt including their alternative of using externally specified utilities in the objective function. Using the dual model, it is shown that correct discounting factors cannot be specified independent of these external utilities.