加工时间和尺寸成正比单机排序和工件运输的最小化最大完工时间问题

在单机排序和工件运输的最小化最大完工时间问题中,工件首先在一台机器上加工,然后被一辆有容量限制的汽车运送到一个顾客．当工件的加工时间和尺寸无关时, Chang和Lee已经证明该问题是强NP困难的．他们也给出了一个启发式算法,它的最差执行比为5／3,并且这个界是紧的．本文考虑工件的加工时间和尺寸成正比的情形,证明了Chang和Lee的算法有更好的最差执行比53／35,并提供了一个新的启发式算法,它的最差执行比是3／2,并且这个界是最好的．     

Effective Heuristics for the GPS Survey Network of Malta: Simulated Annealing and Tabu Search Techniques

A GPS network can be defined as a set of stations, co-ordinated by a series of sessions formed by placing receivers on the stations. This paper shows how to search for the best order in which to observe these sessions giving the cheapest schedule. The complexity of observing GPS networks increases with their size and become highly difficult to solve effectively. To obtain good methods to solve this problem a new area of research is implemented. This area is based on developed heuristic techniques that provide an optimal or near optimal solution for large networks. Comparing their outcome in terms of solution quality and computational effort proves the performance of the developed techniques.     

Wrap-Around L2-Discrepancy of Random Sampling, Latin Hypercube and Uniform Designs

For comparing random designs and Latin hypercube designs, this paper con- siders a wrap-around version of the L₂-discrepancy (WD). The theoretical expectation and variance of this discrepancy are derived for these two designs. The expectation and variance of Latin hypercube designs are significantly lower than those of the corresponding random designs. We also study construction of the uniform design under the WD and show that one-dimensional uniform design under this discrepancy can be any set of equidistant points. For high dimensional uniform designs we apply the threshold accepting heuristic for finding low discrepancy designs. We also show that the conjecture proposed by K. T. Fang, D. K. J. Lin, P. Winker, and Y. Zhang (2000, Technometrics) is true under the WD when the design is complete.     

基于不同奖惩机制项目支付进度优化:双重视角

奖惩机制会对合同双方的收益产生重大影响,本文基于承包商和业主的双重视角,对不同奖惩机制下项目支付进度优化问题进行了研究。首先对所研究问题进行界定,并分别基于承包商和业主视角构建了不同奖惩机制下的优化模型;基于模型的属性设计了模拟退火启发式算法;最后通过一个实例对比了承包商和业主在四种不同奖惩机制下收益的优化结果,并对其中的关键参数进行了敏感性分析。结果显示:不同的奖惩机制对承包商和业主的收益有较大影响;不同的奖惩强度也会影响承包商和业主的收益。通过对奖惩机制类型及强度的分析,可以为项目中奖惩机制的设置提供定量化决策支持。     

空中加油问题的递推模型与调度策略

首先对空中加油问题进行了分析,提取了相关性质,在此基础上建立了问题的递推模型.根据该模型,提出了一种启发式搜索算法.该算法计算复杂度低,适用性好.对应于辅机是否可以多次起飞,该算法分为两子算法.对这两种不同情况下的具体问题,设计了相关的优化函数.所有算法都在计算机中运行,并得到了相应结果.值得指出的是,提出的启发式搜索算法十分高效.对于问题1和问题2,该算法所得解是约束条件下的最优调度策略.对于问题3,问题4,问题5,该算法所得解逼近最优调度策略.     

校车站点及线路的优化设计

以高校新校区教师校车站点及线路安排为对象,首先针对乘车站点建立了双目标非线性规划模型,其中目标函数包括乘客到达站点的距离偏差最小与所有乘客到达站点的总的距离最小两个方面;站点确定后针对车辆数最少、车辆行驶的总距离最短、各辆车的运行距离均衡及各辆车的负荷均衡这4个目标建立针对线路优化的多目标非线性规划模型,并给出了解决这类问题的启发式优化算法.与目前国内外研究相比较,该模型与算法更实际,更具体的给出了问题的解答.     

基于改进遗传算法的集合覆盖问题

集合覆盖问题是组合优化中的典型问题,在日常生活中有着广泛的应用.提出了一种改进遗传算法来解决集合覆盖问题.算法对标准遗传算法的改进主要表现在:1)结合启发式算法和随机生成,设计了新的产生初始种群的方法;2)引入修补操作处理不可行解使其转换成可行解;3)对重复个体进行处理再利用;4)对多点交叉进行推广,提出了新的交叉算子;5)针对可行解和不可行解,采取两种自适应多位变异操作.数值实验结果表明该算法对于解决规模较大的集合覆盖问题是有效的.     

汽车4S店维修车间的优化调度分析

调度研究的问题是将稀缺资源分配给在一定时间内的不同任务,它是一个决策过程,其目的是优化一个或多个目标。对实际问题的优化调度可以帮助企业提高资源利用率,减少客户等待时间,提升竞争力,对汽车4S维修服务站的优化调度问题进行研究,剖析这一实际应用问题的调度目标、机器环境、加工特征和约束等细节,提出了优化调度模型,设计了调度算法。然后,通过实例,简要分析了模型及算法的可行性.     

一类多对多物流系统的运送频率选择优化问题研究

多供应商多客户物流系统的周期运送库存决策问题是一个非常复杂的问题,但它在供应链管理中又极其重要.本文主要考虑一个由多个供应商、一个联运中心和多个客户组成的三级物流系统的运送频率选择优化问题.假定两级库存均采用周期补货策略,且补货周期满足二次幂(POT)策略,每个客户处的产品需求为确定性需求.假设给定一套可行频率的情况下,选择使整个系统总的长期平均成本最小化的联运中心的补货策略和联运中心到各客户的配送策略.分为单频率配送和多频率配送两种情况分别建立了数学模型,并设计了相应的近似算法——基于支配性的邻域搜索启发式算法和基于饱和性的邻域搜索启发式算法.计算试验显示,本文所设计的近似算法对于求解多对多配送这样的大型组合优化问题是有效的.     

Accelerating the convergence in the single-source and multi-source Weber problems

The modified Weiszfeld method [Y. Vardi, C.H. Zhang, A modified Weiszfeld algorithm for the Fermat-Weber location problem, Mathematical Programming 90 (2001) 559-566] is perhaps the most widely-used algorithm for the single-source Weber problem (SWP). In this paper, in order to accelerate the efficiency for solving SWP, a new numerical method, called Weiszfeld-Newton method, is developed by combining the modified Weiszfeld method with the well-known Newton method. Global convergence of the new Weiszfeld-Newton method is proved under mild assumptions. For the multi-source Weber problem (MWP), a new location-allocation heuristic, Cooper-Weiszfeld-Newton method, is presented in the spirit of Cooper algorithm [L. Cooper, Heuristic methods for location-allocation problems, SIAM Review 6 (1964) 37-53], using the new Weiszfeld-Newton method in the location phase to locate facilities and adopting the nearest center reclassification algorithm (NCRA) in the allocation phase to allocate the customers. Preliminary numerical results are reported to verify the evident effectiveness of Weiszfeld-Newton method for SWP and Cooper-Weiszfeld-Newton method for MWP.