基于位置权重的窗口指派单机排序问题

研究了基于位置权重的窗口指派排序问题,机器限定为一台,其目的是在准时制环境下极小化窗口指派的窗口开始时间、窗口大小以及总延误的加权之和,以找到其最优工件加工序列以及窗口开始时间d_(k)^(1)(结束时间d_(k)^(2)),其中权重只和位置有关,而与工件无关。在共同、松弛和不同窗口指派下,通过相应最优解性质,证明此问题能够多项式时间可解。对于共同以及松弛窗口指派,算法的复杂度为O(n^(2)log n),而对不同窗口指派,问题可在O(n log n)时间内求解,其中n为给定工件数量。

奖励-收集Steiner树问题的精确算法

奖励-收集Steiner树问题是图的Steiner最小树问题的衍生,同时也是组合优化中的NP-hard问题。首先,提出该问题的数学性质并给出证明,利用数学性质能降低该问题的规模;其次,基于该问题的数学性质设计出上下界子算法、降阶子算法和回溯子算法,通过上下界子算法和降阶子算法可以降低该问题解空间的规模,从而缩短回溯子算法的搜索时间,进而降低求解该问题最优解的时间;最后,应用案例分析、算例分析以及算法分析与对比表明,所设计的算法不仅可以求出该问题的最优解,而且比没有考虑该问题数学性质的一般回溯算法的时间复杂度更低。

最小连通顶点覆盖问题的降阶回溯算法

本文从最小连通顶点覆盖问题的求解算法出发,提出一种基于该问题本身的数学性质的降阶回溯算法来求解。通过基于问题的数学性质来设计精确算法,不仅能够克服使用启发式算法求解该问题在一般情形下都无法求得最优解的缺点,也改善了该问题使用传统精确算法时最坏时间复杂度高的缺点。本文首先研究该问题的数学性质,部分数学性质可成批确定某些顶点在或不在最小连通顶点覆盖集中,从而降低该问题的规模,提高精确算法的求解速度。其次,在数学性质的基础上,设计出上下界子算法、降阶子算法、回溯子算法来求解该问题的最优解。最后,时间复杂度分析以及无线网络设计的实例分析表明,该算法不仅能求得该问题的最优解,且相对一般精确算法,本文算法的时间复杂度更低。

考虑模具约束和开机成本的并行机调度问题研究

受企业实际的注塑排产问题启发,本文研究了一类考虑模具约束和开机成本的相同并行机调度问题,目标是最小化加权延迟成本、换模成本和开机成本之和。构建了混合整数规划模型,证明了问题必定存在无机器空闲的最优解,提出了新的工作分配规则以确保产生的解都无机器空闲。在此基础上,设计了修改的ATCS算法(ATCS-MOD)和基于列表调度的遗传算法(GA-LS)两种算法。大规模数值实验证明GA-LS求解效果优于CPLEX和ATCS-MOD,更显著优于传统ATCS算法,同时也证明了新工作分配规则相比传统ATCS规则的优越性。

到达时间服从泊松分布的平行机队列的最优随机排序问题

论文考虑多个分布下,根据每类加工时间函数最小化目标函数的不同类别的随机排序问题。这个问题常出现在分布式系统、网络和应用程序方面。模型中,最优排序策略在每台机器上是一个简单的静态优先策略。在这种排序策略下,排序问题可以寻找到最佳路径矩阵。考虑一个非线性规划问题,证明了任何局部最优即为全局最优,大大简化了,优化问题的解决方案。在到达时间为泊松分布的情形下,论文提供了一个最佳的排序策略,能够最小化每类时间函数。对一般各种静态实例应用此方法,可得到简单的近似算法。

考虑退化效应的钢箱梁小节段在线生产调度研究

钢箱梁小节段作为桥梁组装的基础构件,需求量非常大,其生产方案的优化对制造商有着很大的影响,针对钢箱梁小节段的在线生产调度研究就显得愈发迫切与重要。本文研究工件具有退化效应的钢箱梁小节段单机在线生产问题,建立了的两个不同的退化加工模型,以最小化最大加权完工时间为优化目标。首先,对所研究的两个问题,都证明了最优排序应具有的性质。然后,对加工时长模型为pj=αjt(t>0)的问题,给出了一个竞争比为1+αmax最好可能的在线算法,其中αj为工件Jj的退化因子;同样,对加工时长模型为pj=αj(A+Bt)(A>0)的问题,也给出了一个竞争比为2+Bαmax最好可能的在线算法。最后,对文中的两个在线模型都进行了数据模拟,验证了在线算法的有效性与正确性,也为制造商的生产管理提供了有效参考。

具有依赖时间学习效应的资源分配排序问题

研究工件加工时间具有依赖时间学习效应的单机资源分配排序问题,其中工件的实际加工时间不仅依赖于分配给它的不可再生资源数量,还依赖于该工件所排位置之前工件的基本加工时间之和。该问题研究的目标是确定工件的最优排序和最优的资源分配,使最大完工时间(即所有工件的时间表长)和消耗资源的线性加权和最小。对给定的排序,最优的资源分配能够得到,从而目标函数转化为只和工件的基本加工时间有关。通过实例说明经典的最小加工时间优先(SPT)规则和最大加工时间优先(LPT)规则都不是最优解。猜测此问题是NP-难的,为了求解此问题,分析了问题满足的性质,给出了上界和下界,从而给出分支定界算法,并用实例说明该算法是如何求解的。

工件具有权重和服务等级约束的平行批在线排序算法

探讨两台机器上工件具有权重和服务等级约束的平行批在线排序问题。根据工件和机器的特性,有相应的等级约束。工件只能在服务等级不高于自身等级的机器上加工。工件按时在线释放,具有权重和相同的加工时间。机器可以平行批处理工件,在不超过批容量的情形下,多个工件可以用一台机器在一批中同时进行加工。目标函数是最小化所有工件的最大加权完工时间。讨论该问题的时间在线排序算法,给出了在线算法竞争比的下界,并设计了与下界√5+1/2匹配的最好可能的在线算法。

基于直觉模糊集对集结方法的隐私风险决策

针对隐私风险的不确定性决策问题,在直觉模糊和集对分析理论基础上,对隐私确定-不确定建立信息权重的集对关系,给出了直觉模糊集对(IFSPA:Intuitionistic Fuzzy Set Pair Analysis)算子,定义了直觉模糊集对的相关概念、运算、性质、期望值、大小排序和几种直觉模糊集对信息集结算子:直觉模糊集对加权平均(IFSPAWA:Intuitionistic Fuzzy Set Pair Analysis Weighted Average)算子、直觉模糊集对加权几何(IFSPAWG:Intuitionistic Fuzzy Set Pair Analysis Weighted Geometric)算子、直觉模糊集对有序加权(IFSPAOWA:Intuitionistic Fuzzy Set Pair Analysis Ordered Weighted Average)算子、直觉模糊集对有序加权几何(IFSPAOWG:Intuitionistic Fuzzy Set Pair Analysis Ordered Weighted Geometric)算子、直觉模糊集对混合集结(IFSPAHA:Intuitionistic Fuzzy Set Pair Analysis Hybrid Aggregation)算子、直觉模糊集对混合几何(IFSPAHG:Intuitionistic Fuzzy Set Pair Analysis Hybrid Geometric)算子及这些算子相关性质。在此基础上,分析了隐私风险多属性决策的直觉模糊集对信息集结方法,并通过算例验证了该方法的可行性和合理性。

考虑软时间窗的同时送取货随机旅行时间车辆路径问题

考虑车辆总旅行时间约束和车辆载重限制以及客户对服务时间窗的要求,研究带有软时间窗的同时送取货随机旅行时间车辆路径问题(STT‒VRPSPD),建立机会约束规划模型。将禁忌搜索算法与分散搜索算法相结合,构建混合分散禁忌搜索(HSTS)算法,并采用C‒W节约算法生成初始解。基于经典的Dethloff算例和Solomon时间窗生成方法,分别生成包括50个客户、200个客户各20组算例,算例测试结果验证了混合分散禁忌搜索算法的有效性。

关于梯形模糊数排序的新方法

关于模糊数排序的问题一直是模糊决策研究的热点。随着研究的深入,研究对象由区间模糊数发展到三角模糊数,进而又发展到梯形模糊数。文章提出一种新的梯形模糊数排序方法,该方法是基于两个梯形模糊数减法法则,通过定积分的运算给出可能度的概念,再利用可能度大小和布尔矩阵法对多个模糊数进行排序。最后通过算例显示该方法的可行性,并通过与近期文献的方法比较,显示其有效性和优效性。研究结果表明,该方法不仅能够比较不同类型的模糊数次序,而且计算简单、区分度强,所以应用范围广泛。

基于数值分布的激励型毕达哥拉斯模糊集成算子及其应用

针对毕达哥拉斯模糊环境下的多指标评价问题,根据决策信息的实际分布,提出一种基于数值分布的毕达哥拉斯模糊数等级划分方法,根据不同等级区间发展度及等级规模确定指标权重和密度权重,结合密度算子的思想,提出基于数值分布的激励型毕达哥拉斯模糊密度加权平均算子(incentive Pythagorean fuzzy density weighted average operator,I-PFDWA).将基于I-PFDWA算子的多指标评价方法运用于航空服务评价问题的结果证实了该方法的可行性和有效性.

具有位置相关权重的工期分配排序问题研究

针对具有位置相关权重的工期分配排序问题进行了研究,其目标是在共同工期分配/松弛工期分配两种模式下,找到最优的工件加工序列以极小化工件工期与工件延误的线性加权和,其中权重是与位置相关的权重。通过证明一系列性质得到工期的计算方法,进而将所要研究的两类工期分配问题转换为与工件加工时间有关的函数。根据每个工件对应的系数来给出具体求解算法从而得到最优的工件序列,以及对应的最优共同工期/最优松弛工期。通过具体的算例验证了此算法可在多项式时间内求解。

基于改进TOPSIS的三角直觉模糊多属性群决策方法

针对属性值为三角直觉模糊数,决策者权重已知的多属性群决策问题,提出基于灰色关联度的TOPSIS多属性群决策方法。首先根据决策者对各个属性的打分评级结果,将模糊的语言变量转化为三角直觉模糊数,集结决策者评价信息矩阵,基于属性值离差最大化求出各属性的权重向量,计算备选方案加权决策矩阵;其次,引入灰色关联度,基于模糊正理想点和模糊负理想点计算每个备选方案的灰色关联度,计算每个备选方案的相对贴近度,从而确定每个备选方案的顺序;最后,通过实例分析,验证该方法的有效性。

基于分区优化的无人机全自动机场选址研究

自2019年末新冠疫情爆发以来,人们对于自身安全及卫生问题尤为重视,一种以无人机全自动机场为零接触点的即时配送模式应运而生。针对研究无人机全自动机场选址中出现的分区局部最优的问题,首先考虑无人机运行特征构建全自动垂直机场选址模型,其次基于天津市和平区商家的实际数据,采用改进式网格分区方法进行区域的划分及预选址;并通过泰森多边形法对划分区域进行优化,使得选址机场分区范围内需求点分布更加均衡,达到了全局最优的目标。最后以天津市和平区即时配送的商家数据为例进行模型应用及结果分析。结果表明无人机全自动机场的覆盖范围与选址数量及需求均衡分布情况存在相关关系。通过分区优化的方法可以使得选址的无人机机场服务范围更合理,为未来城市区域中无人机全自动机场的规划提供建设性建议。

基于模糊过滤排序法的复球形犹豫模糊多属性群决策方法

为有效分析属性值的概率分布对决策结果的影响,基于模糊过滤排序法提出属性权重和决策成员权重完全已知的复球形犹豫模糊多属性群决策方法。首先,定义复球形犹豫模糊集以及集结算子和满意度;其次,根据模糊过滤排序法构建复球形犹豫模糊多属性群决策模型;最后,运用算例验证所提方法的合理性和有效性。

球型模糊环境下基于前景理论和VIKOR的多属性群决策方法研究

研究了模糊多属性群决策问题。首先,在属性权重已知的情况下,通过建立评价属性,专家打分构建球型模糊评价矩阵。其次,考虑专家的有限理性行为,基于前景理论构建了前景值决策矩阵,并运用VIKOR方法,在可接受优势和决策过程稳定的条件下对方案进行择优。最后,通过算例与3种方法对比,说明了方法的有效性和可行性。

基于前景理论和LOWA算子的概率语言LEC风险评估方法

考虑到作业条件危险性评价法(LEC)存在的评价信息遗漏、风险量化分析能力弱、忽略决策者有限理性特征等缺陷,提出一种基于前景理论和语言有序加权平均(LOWA)算子的概率语言LEC风险评估方法。首先,该方法采用概率语言术语集(PLTS)代替精确的非连续性数值来刻画决策者评价信息的不确定性;其次,利用概率语言连乘层次分析法(PL-MAHP)和正、负理想点双向投影贴近度最小偏差模型确定指标的主、客观权重,并基于博弈论的思想对主、客观权重进行组合优化;然后,考虑到风险评估过程中决策者的损失规避和参照依赖等心理行为,在前景理论决策视角下,引入LOWA算子确定前景参照点以提升参照点选取的科学性,进而实现安全隐患的风险排序;最后,通过危化品运输安全隐患的风险评估算例,验证了该方法的合理性和有效性。

基于遗传算法的装配线平衡与物料超市规划协同优化

近年来,企业开始广泛运用新型的物料超市来代替传统的中央仓库,以保证装配线上零件的准时化供应。在装配线设计阶段,装配线平衡方案会限定物料超市的布置,而物料超市的规划会影响装配线的物流效率和成本。目前大部分研究运用分阶段的方法将两者分开考虑,从而造成总成本的增加。本文提出了装配线平衡与物料超市规划协同优化的模型与算法。根据问题描述和相关假设构建了以工作站建设成本、物料超市建设成本与运输成本最小化为目标的混合整数规划模型。为求解大规模问题,提出了一种改进遗传算法对其进行优化。最后通过算例验证了所提协同优化方法的有效性。

基于物料超市的混流装配线准时化物料配送调度

针对混流装配线物料配送优化问题,结合新型的物料超市配送模式,提出了区别于传统周期性配送的准时化配送方法。首先,根据问题描述和相关假设构建了以线边库存最小化为目标的混合整数规划模型。然后,考虑到实际生产的连续性和复杂性,为求解大规模问题,设计出适用于问题的启发式算法,并与遗传算法进行比较,启发式算法能在更短时间内获得满意解。最后,在不同牵引拖车容量下,通过实例分析,与广泛应用的周期性配送进行比较,算例求解结果表明,准时化配送模型能够获得更低的库存水平,减少工作站的空间占用。