货物运输车辆的调度算法

本文以上海煤炭公司为例,讨论了运煤车辆的计算机调度问题,提出一个数学模型及有效的近似算法。在算法实现中,采用了一些较为先进的数据结构,使运算速度及存储需求均有较大的改善。对实际算例计算结果表明,采用本算法进行运输车辆调度,经济效益比人工调度有明显的提高。     

三维布局的一种优化算法

分析了布局问题的特性，综合利用“爬山”策略思想和实体的八叉树操作语言，提出一种适合于三维实体布局的优化算法。实例表明，该算法能从任一初始布局方案快速收敛到一个局部最优的布局。此外，对实体八叉树旋转的操作语言进行了研究并给出相应的算法。     

基于空间分解的二维布局问题的启发式算法

一种基于空间分解的解决矩形物体布局问题的启发式方法。按照深度优先的原则将布局空间逐步分解，每次放入相对于当前布局空间来说是满足特定条件的最优布局块，并将该布局块定位于当前布局空间的左上角来不同大小矩形物体的布局方案。通过调整调序因子ＫＡ和ＫＢ的值，可得到满足不同要求的优化布局方案，所得布局方案均满足工业上一刀切的要求。实验结果及与其他算法的比较证明了该算法的灵活性和有效性。     

锁定初始调度的紧急工作单机重调度问题

对单机环境下紧急工作的重调度问题进行了研究.初始调度中工作带有到达时间,目标为最小化初始工作的等待时间和;重调度目标是在初始调度锁定的情况下,将紧急工作插入初始调度,最小化紧急工作的最长等待时间.建立了RRLS(reschedulingrushjobswithloadslockedonsinglemachine)问题模型,然后证明了RRLS问题是NP难问题.根据问题性质和特点提出了有效的启发式算法,并给出了算法的时间复杂度.通过实例证明了算法的最优性条件.     

求解带平衡约束矩形布局问题的混合算法

以卫星舱布局为背景,针对二维带平衡约束的矩形集在圆容器内的布局问题,提出了一种混合算法,即带压缩策略的动态匹配算法,并与粒子群优化算法结合起来.对于给定的圆容器,将整个布局过程分为4个阶段,相应地将圆容器分成8个区域.每次放置矩形时,动态匹配算法先根据系统质心动态选择装填区域,然后在该装填区域中根据排序函数选择待布矩形.压缩策略用来压缩圆容器,粒子群优化算法用来优化排序函数的参数.在测试集上的计算结果表明:相对于已有算法,提出的混合算法更加有效.     

基于构造的布局启发方法

布局问题属于ＮＰ完全问题已知被研究多年,关于它的求解方法多为启发式方法,本文在分析了布局问题特性的基础上,提出了一种基于构造的布局启发方法,该方法既考虑到布局总问题的不干涉的约束及又考虑了其它的布局约束,从而更加全面,准确地指导布局求解的进行,本文还首次提出了“虚容器”的概念,从而使定序函数和定位函数的计算易于进行。     

论矩形物体布局的启发式近似计算问题

针对待布局矩形物体在布局空间中可行位置，给出了其可行域的定义，并据此对待布局物体的摆放规则进行了讨论，提出了一种基于空间分解的启发式算法，实例计算表明了该算法是有效的。     

求解MAFS问题的归并算法的性能比研究

对M＋1台机器的MAFS排序问题，在该问题的启发式算法的基础上作了进一步的研究。用一实例证明，MAFS排序问题的归并算法的性能比是上界可达的。     

基于贪心算法的宏模块布局分析

为芯片上每个模块选择一个好的布图方案,采用合理的布图算法尤为重要.在NP完全理论的基础上,从问题的可计算性与复杂性出发,提出贪心算法的实现原理与实现过程.结合4个有代表性的实例,对该算法进行了实验测试与分析.计算结果对宏模块布局问题具有参考价值.     

一种求解多处理机调度问题的自适应蚁群算法

将蚁群算法应用于求解多处理机调度问题,提出一种自适应蚁群算法．算法以最小化makespan为调度目标,根据蚂蚁留下的信息素指导蚁群在解空间展开全局搜寻,将任务分配在恰当的机器上,并通过自适应调整阈值实现全局探索与精细查找的平衡．实验结果表明算法具有较好的优化性能．     

针对目标的布局启发式算法

为解决二维矩形布局问题，在广泛研究各种启发式方法的基础上，提出了基于目标的启发式算法．该算法在布局开始时确定布局目标，布局过程中综合运用多种策略，让每个局部最优解达到布局目标值，得到稳定的、可靠的全局解；并且简要分析了矩形正交布局的空间分解方法，提出了群组的基本策略以及布局的定序规则和定位规则、实验结果表明，算法具有较强实用性，布局效率提高2％以上．     

集合覆盖问题的一种启发式算法

给出了完备策略的概念，并提出了一个求解集合覆盖问题的启发式算法，对该算法的合理性、时间复杂性以及精度进行了分析。用该方法可以求解其它的NP困难问题。     

解不等圆 packing 问题拟物拟人算法初态选取

提出形式化了的人工经验方法,由此得出的算法可以极快速地为不等圆填装（ｐａｃｋｉｎｇ）问题求出初始近似解．将此初始近似解作为求解不等圆ｐａｃｋｉｎｇ问题的拟物拟人算法中的初态,可以提高这种拟物拟人算法的计算速度约１０倍．此种方法还有可能发展为关于求解ＮＰ难问题的不仅具有高速度而且具有高精确度高完整度的具有实用价值的纯粹拟人方法．     

有舍弃的装箱问题及其启发式算法

设计了一种启发式算法——RCF算法来解决有舍弃装箱问题.实验证明,该算法与RFF3算法相比,在物体个数比较少(<200)的情况下,由于数据的随机性会出现比RFF3算法较好;在物体个数大于200的情况下,RFF3算法具有绝对的优势.因此,提出的RCF算法在物体个数比较少的情况下,有一定的应用价值.     

出厂物流调度问题及其启发式算法

针对出厂物流调度问题,建立了一类出厂物流问题的调度理论模型,证明了该问题的强NP-hard特性.基于对问题的特征分析,提出求解问题的近似算法,证明了算法的最坏性能比为3且为紧界,并通过数值仿真验证了该算法的有效性.结果表明,所提出算法对两台流水作业机器的完工时间有一定的优化.     

Aheuristic Algorithm for Berth Scheduling Problem in Container Ports

In this paper,the berth scheduling problem is transformed into a special two-dimensional packing problem with some constraints.A nonlinear programming model for the problem is established,and a heuristic algorithm is proposed to solve the model.Simulation results show that the algorithm can improve the utilization of berths on discrete berth scheduling in the container port.     

箱子装载问题的算法研究

1　引言　　设有ｎ件物品 ,每件物品的体积分别为ｓ1,ｓ2 ,… ,ｓｎ,且 0 <ｓｉ≤ 1(ｉ =1,2 ,… ,ｎ) .现有一批箱子 ,每只箱子的容量为一个单位 ,现在的问题是能够容纳这ｎ件物品的箱子至少需多少只 ?此问题为著名的ＮＰ复杂问题 ,迄今在多项式时间内尚无求解的办法 .但可用近似算法求解 ,使结果接近最优解 .对于此问题 ,有 4种流行的求解算法 :( 1)最先匹配法 (ＦｉｒｓｔＦｉｔ ,ＦＦ) ;( 2 )最优匹配法 (ＢｅｓｔＦｉｔ ,ＢＦ) ;( 3)最先匹配递减法 (ＦＦＤ) ;( 4 )最优匹配递减法 (ＢＦＤ) .这 4种算法的时间复杂度均为Ｏ(ｎ×ｌｏｇ(…     

基于改进遗传算法的Flow Shop调度算法研究

给出了Flow Shop调度问题的数学模型,介绍了三种用于求解该问题的启发式算法,根据普通遗传算法与启发式算法的互补特性,提出了结合两者各自优势的改进遗传算法．通过两个不同规模的经典算例对算法的优化性能进行了对比分析,结果表明,采用了保优策略的改进遗传算法的搜索能力优于启发式算法及普通遗传算法,并具有较强的鲁棒性．     

基于启发式群聚算法的机器人全局任务调度策略

提出了一种基于启发式群聚算法的机器人全局任务调度策略，在任务划分阶段采用一种启发式群聚算法对随机划分的各子任务按能否使总的运行时间缩短进行各子任务间的聚合，以使各子任务粒度和相互之间的通讯量达到一种优化状态，并在此基础上对群聚之后的各子群任务采用集中式动态调度策略，在程序运行过程中实现各处理器的负载平衡，提高各处理器的利用率，缩短总的运行时间．在一个由5个DSP（digital signal processor）处理器组成的同构型松耦合MIMD（multi instruction multidata）并行处理平台上，对平面四自由度连杆机器人在关节锁定下的运动控制任务采用上述先随机划分，再聚合，最后集中式调度的方法进行了并行实时仿真实验，取得了满意的并行性能指标．     

一类复合并行机排序问题计算复杂性研究

研究确定性排序理论的一个新模型：考虑４台机器的集合Ｍ＝（Ｍ１，Ｍ２，Ｍ３，Ｍ４）和ｎ个零件的集合Ｊ＝（ｊ１，ｊ２，…，ｊｎ），每个零件同时被２ｉ＝（ｉ＝０，１，２）台机器同时加工。证明了在不允许间断，优化指标为作业排序长度的条件下，该问题是强ＮＰ－完全问题，没有多项式时间算法。