转盘上的Flow-shop排序问题的复杂性

讨论转盘上的Flow-shop排序问题,当运送不相等且只有一台机器的情况下,转盘上的Flow-shop排序问题是强NP-困难的.

广义Flow-Shop排序问题的分析和优化

本文研究一类特殊的Job-Shop问题——广义Flow-Shop问题。首先给出了“广义Flow-Shop”的定义,然后提出了一种求解这类问题的启发式算法——逐机排序法。理论上和仿真中证明,用该方法求解广义Flow-Shop问题与一般Job-shop启发式算法等价,但计算大为简化和省时。

城市物流无人机起飞时刻排序问题研究

文中基于动态优先级计算了无人机起飞的时刻及起飞顺序.选取货物价值、收货点距离和最晚收货时间作为影响排序的主要因素,根据熵权法判断不同影响因素对物流订单优先级的影响程度,结合模糊聚类与三维优先级表调度规则判定物流订单的任务优先水平.并根据订单优先级设定延误成本系数,以最小总延误成本为目标构建物流无人机起飞时刻排序模型;提出相应的改进遗传算法对模型进行求解.数值仿真实验结果表明:所提方法可以安全高效地安排无人机起飞队列顺序,降低无人机配送的总延误成本.

同顺序(Flow-shop)排序问题的模拟退火求解

本文为Ｆｌｏｗ－ｓｈｏｐ问题的求解一般地构造了一类随机方法─—模拟退火算法。基于６种不同的随机抽样方式，分析表明求解算法渐近收敛于全局最优解集且具有多项式计算复杂特性。以不同实例规模的ＵＩＳ、ＦＩＳ和ＮＩＳ的Ｍａｋｅｓｐａｎ最小Ｆｌｏｗ－ｓｈｏｐ排序问题为例，计算结果表明模拟退火求解Ｆｌｏｗ－ｓｈｏｐ排序问题是有效的．

带广义偏序约束的Flow-Shop排序问题

本文研究了一种新的排序问题:带‘广义偏序”约束的flow-shop排序问题.如工件Jj与工件.。之间有广义偏序,则Jj→Jk,且Jj的完工时间与Jk的开工时间的间隔不小于ljk和不大于ujk,0ljkujk.问题的目标函数是最大完工时间.我们证明了:具有比较简单的广义偏序约束的两台机器的flow-shop问题亦是NP-hard.我们给出了相应的启发式算法.对于单位加工时间,证明了一种较复杂的广义偏序约束的flow-shop问题是多项式可解的.

三台带两个服务等级的平行机排序问题算法研究

研究了带两个服务等级的平行机排序问题,其中等级为1的机器有2台,等级为2的机器只有1台。每个工件和每台机器等级均为1或2,只有当工件等级不低于机器等级时,才能将工件安排到机器上加工,目标为极小化最大完工时间。针对该NP-难问题,设计了一个近似比严格小于3/2的新算法,改进了已知结果。同时,在加工时间满足2的幂次方条件下,设计了一个新算法,并证明了该算法总能得到一个最优分配。

关于企业多项目管理中的优先排序问题研究

随着我国社会经济的快速发展,城市化规模不断扩大,各大企业想要在激烈的竞争环境中生存下来,需要不断完善内部的管理工作。随着大数据时代的来临,生活节奏不断加快,企业不会像以往一个时间段只维护一个项目,所以,多项目运营管理是企业发展的必然趋势。多项目管理无论对于项目执行者还是公司管理者来说都是一大挑战,多个项目共同推进势必会出现资源需求重叠的情况,这也会导致项目之间出现资源抢夺的问题。所以多个项目实施过程中,优先解决管理问题是企业在发展过程中的重要问题,也是直接决定企业经济效益的关键因素。首先,企业需要对多个项目进行排序,此项工作是企业管理中的重要问题,只有对多项目进行优先级的排序,才能从根本上促进企业发展,为此创造更多经济效益,企业多项目管理的优先排序工作对企业长期发展具有重要意义。

混合流水作业的排序问题

研究了一类混合流水作业的排序问题,设置了2个处理中心,第1个处理中心含1台机器,第2个处理中心含m台机器.当作业在第2个处理中心加工时,需要多台机器同时加工.目标函数为最小化最大完工时间.讨论了3种情况,得到了以下结论:对于问题HF(1,P_(2))|M_(j)|C_(max)提出了3/2-近似算法,对于问题HF(1,P_(3))|M_(j)|C_(max),提出了3-近似算法,对于问题HF(1,P_(m))|M_(j)|C_(max),可以得到目标函数与最优解的比值为1+2 m.

考虑碳排放的危险品运输异构车辆路径问题研究

为满足危险品运输异构车辆路径问题(HVRP)的低碳需求,对易爆危险品运输过程中的总风险、总成本和总碳排放量进行最优化处理。首先,在模型构造阶段,改进总成本与总风险的度量方式,包括建立爆炸事故场景下考虑危险品装载量的风险量化模型,并设计一种用于惩罚成本计算的软时间窗函数,该函数可以优先减少装载量较大的车辆在客户处的等待时间;然后,在算法改良阶段从2方面改进非支配排序遗传算法(NSGA-Ⅱ),设计一种带有改良交叉算子的混合交叉方法来提升全局搜索效率,并通过包含2个阶段的变邻域搜索(VNS)算法来提高局部搜索能力;最后,通过算例验证模型和算法的有效性。研究结果表明:相较于原始NSGA-Ⅱ,改进的算法收敛曲线下降更快,使总成本、总风险和总碳排放量3个优化目标的平均值进一步减少3.36%、12.16%和6.96%;在车辆数目有限的车队中,承运人可以通过选择不同的车辆类型对各目标产生不同程度的影响。

折扣{0-1}背包问题之分段排序贪心核算法研究

折扣{0-1}背包问题(D{0-1}KP)的贪心核算法是一种近似解算法,常通过估算核区间划分子问题,采用分治算法设计求解算法,算法性能与核区间估计准确性密切相关,核区间估算优化是算法改进的主要途径。在研究{0-1}KP核概念基础上,提出D{0-1}KP核区间的修正定义,构建分段排序策略以缩减核区间规模,改进了D{0-1}KP贪心核算法,设计了修复贪心核动态规划加速算法(RGCADP)、分段排序贪心核动态规划加速算法(RGCADP_PS)。两个算法在D{0-1}KP标准数据集上的实验结果表明:与基本动态规划算法(BDP)相比,RGCADP、RGCADP_PS算法平均求解时间提升率为71.3%、77.2%;RGCADP、RGCADP_PS算法平均解误差率低于粒子群贪心修复算法(PSO-GRDKP)0.5个百分点,低于贪心核加速动态规划(GCADP)算法4.7个百分点;RGCADP_PS时间性能提升率高于RGCADP算法5.9%。

基于问题分类分级农村配电网项目精准投资策略研究

农村配电网供区地域分散、地形复杂,运行环境呈现差异化、多元化等特点,本文通过对农村配电网“低电压”、重过载、安全隐患等问题分析,采取多维度对问题进行量化评价,建立以供电分区、乡村振兴、电网现状问题等级、经济发展等指标为评价维度的项目排序体系,切实提升农村配电网精准投资管理水平。

《用排序算法进行数据整理》教学案例

课程核心素养目标①根据学习与生活需要,有意识地选用排序算法处理信息,对于简单问题,确定解决问题的需求和数据,使用排序整理数据,解决问题。(信息意识)②通过生活中的实例,了解排序算法的原理,对于给定的问题,能将其分解为一系列的实施步骤,使用顺序、分支、循环三种基本控制结构简单描述排序算法实施过程,通过编程验证该过程。(计算思维)

解决多目标Flow-shop问题的生物免疫调度算法

生产调度是车间自动化的关键问题之一 ,生产调度的优劣对制造系统的运行影响极大。通常的确定性优化方法往往不适合生产调度这类NP完全问题的求解。文章基于生命科学中的免疫概念与理论 ,构造了基于生物免疫机理的生产调度模型 ,并研制了用于求解目标Flowshop问题的智能调度系统 ,克服了当前遗传算法用于求解此类问题时 ,易于出现早熟、搜索效率低及不能很好保持个体多样性等不足 ,大大改进了搜索效率 ,对复杂的多约束、大规模及多目标生产调度问题 ,算法效果显著 ,并且可以轻松地获得满足要求的多个优化解。文章讨论了模型的建立、算法的实现和应用实例 ,测试情况表明 。

基于多目标猫群算法的混流装配线排序问题

针对现实混流装配线上各工作站内设备闲置/超载的成本不同的问题,在传统的最小化闲置/辅助工作总成本目标的基础上,考虑不同工作站内设备闲置/超载成本的差异,建立了以改进的最小化工作站闲置/超载总成本、产品变化率和产品切换总时间为目标的多目标优化模型,并设计一种改进多目标猫群优化算法进行求解。提出一种基于线性混合比率的猫行为模式选择方法,以提高算法前期的全局搜索能力和后期的局部寻优能力;提出能生成分布广泛的候选个体、基于多样化搜寻算子的改进搜寻模式,拓展算法的搜索空间,提高算法的全局搜索能力。运用基准实例对所提算法与第二代非支配排序遗传算法、多目标粒子群算法、第二代强度Pareto进化算法进行比较,结果表明所提算法在解的收敛性、分布性和Pareto解的搜索能力上均具有优势。将该算法用于求解某实例企业的混流装配线排序问题,为车间调度人员的决策提供了多样化的选择,且优于车间已有方法的求解结果。

基于蚁群系统的工件排序问题的一种新算法

工件排序问题中如何使加工效率最高 ,一直是一个非常重要而且又非常困难的问题 .特别是问题的规模很大时 ,目前各种算法计算就非常困难 ,有的甚至无法得到合理的方案 .蚁群系统是近年来发展起来的解决组合优化问题的一种有效方法 .根据工件排序问题的特点 ,建立了在不同种类的并行机上加工一批不同种类工件的优化数学模型 .在蚁群算法的基础上对其进行了改进 ,成功地把改进的蚁群算法用于工件排序问题的优化中 .通过与其他算法的仿真比较 ,表明基于蚁群系统的算法是有效的 。

模糊Flow-shop问题及其遗传优化

研究模糊生产环境下的Ｆｌｏｗ－ｓｈｏｐ调度问题．针对实际生产中加工时间的不确定性，应用模糊加工时间参数替代传统的清晰参数表示方法，引入了一种新的模糊数比较方法——面积补偿法，构造了一种解模糊Ｆｌｏｗ－ｓｈｏｐ问题的有效遗传算法．最后给出计算实例及仿真结果．

基于单机排序问题的降落飞机分组排序方法

为使单跑道降落飞机排序结果在实际操作时可行、简单,首先限制同一航路段上的飞机按照先来先服务的原则排序,在最终的排序中,其拓扑次序不变;其次提出了将飞机分组排序的思想,对同一航路段上刚好满足最小安全间隔的飞机做为一个飞机组参与排序。使用1|chains|∑wjcj做为排序模型,通过求解各飞机链的ρ因子可以快速得到排序结果。将本方法用于对双流国际机场和其它几个机场的实际航迹数据进行计算,得到的排序序列完全符合实际管制需要,具有很高的推广应用价值。

利用DNA遗传算法求解Flow-Shop调度问题

由于经典遗传算法在求解调度问题尤其是处理复杂的、混淆的和多任务问题时不够灵活且计算速度慢,论文引入DNA技术借助生物学理论对其进行改进。DNA遗传算法继承了遗传算法全局搜索的能力,同时利用DNA双螺旋结构和碱基互补配对原则进行编码运算,提高了算法的有效性和收敛速度,从而很好地解决了NP-hard性质的Flow-Shop调度问题。

企业多项目管理中的优先排序问题研究

企业在执行多项目管理时,由于其资源的限制,不能够将所有的项目机会都同时付诸实施。本文首先从企业的战略角度研究了如何对项目机会进行优先排序,选择优势项目;其次对企业的多项目实施过程中的项目优先排序问题提出了新的定量方法,并用实例进行了验证。

Job Shop排序问题解空间定量分析

讨论 Job shop排序问题不可行解的构造情况 ,给出了不可行解的一个充要条件以及 2台机器n个加工工件的 Job shop问题不可行解和可行解的计算公式 ,并由此得到一种概率模型的计算方法。通过计算发现 ,Job