一类排序问题的最优解

本文讨论了将多个零件分派给多台机床加工的一类排序问题,机床的工效可以不一样,但假设零件在不同机床上的加工时间成比例.给出了使总花费时间最小的计算方法,这是一种多项式算法.当零件在所有机床上的加工时间与在其中某一机床上的加工时间之比均 为正整数时,进一步给出一种更为简便的算法——标号法.     

分派问题保持最优解不变的充分必要条件

进一步讨论了在保持分派问题最优解不变的情况下,效率矩阵元素的变化范围.这些变化范围是保持分派问题最优解不变的充要条件.     

分派问题的灵敏度分析及其应用

讨论分派问题的效率矩阵的元素发生变化时,对最优解的影响;在保持分派问题最优解不变的情况下,效率矩阵的元素的变化范围;及当分派问题的最优解发生变化后,如何用简单的方法求得新的最优解等.     

灰色分派问题

在分派问题中,总假设被分派工作的人(或机器)做各项工作的效率(或所费时间)都是确定的值.但实际上,对于以往未做过的工作,或做过但情况变化较大的工作都难以定下确切的工作效率,而只能估计出一个大概范围.这也就是说工作效率是有理灰数.我们把这一类分派问题称为灰色分派问题.本义给出了灰色分派问题的有关定义和求解方法.     

军用飞机维修质量管理的最优线性分派评估

在军机维修工作中,科学有效的管理,对及时完成维修任务,保障训练作战计划至关重要.在建立适合我军军机维修质量评估指标体系的基础上,定义了理想方案和贴近度,给出了排序频数的计算方法,进而将军机维修质量评估问题转化为最优线性分派问题来处理,从而为军机维修质量管理提供了一种科学、可靠的决策方法.     

赛程中裁判分派问题的研究

应用图的边着色和全着色理论,研究了赛程中的单循环比赛的裁判分派问题,给出了最优分派结果.     

城市配送车辆路径优化集束式算法的客户点归并策略

VRP问题的研究起步较早,求解方法也非常丰富,然而,面对客户规模庞大,交通网络复杂的多约束车辆优化调度问题,现有算法显得无能为力.为有效解决需求点规模庞大的城市配送车辆优化调度问题,提出一种新的两阶段启发式算法——集束式算法,采用"集中后分派,分派后扩展"的思想,对末梢客户和同路段客户进行客户点合并,从全局上降低搜索范围,并提出相关客户点归并算法.     

带强制工期的可中断平行机排序问题

讨论了在m台同型平行机上,加工带强制工期的n个可中断工件,在机器可空闲条件下,确定一个工件排序,使得提前完工时间和最小.先考虑了问题的复杂性,通过3-划分问题归约,证明了其是强NP-hard的.而后,讨论了强制工期相等的特殊情形,由于工件不允许延迟,问题可能会无可行排序.先讨论了可行性,接着针对可行问题,提出一个算法在多项式时间内获得最优排序.     

极小化最大提前完工时间的两平行机排序问题

讨论了在两台同型平行机上,加工带截止期限的n个工件,在机器可空闲条件下,确定一个工件排序,使得最大提前完工时间最小.由于工件不允许延迟,问题可能会无可行排序.先讨论问题的可行性,通过子集和问题归约,证明了判定问题的可行性是NP-complete的.如果问题可行,接着讨论了问题的复杂性,通过划分问题归约,证明了其是NP-complete的.最后,考虑了工件加工时间相等的特殊情形,提出了一个算法在多项式时间内获得最优排序.     

排序在数学解题中的作用

有些数学问题中涉及多个元素,在解题时若能按照某种关系将它们排序,使它们之间的数量关系明朗化,那么就给解题带来方便.     

带强制工期的双机开放车间排序问题

讨论了强制工期相等的n个工件在双机开放车间加工.在允许机器空闲的条件下,寻找一个工件排序,使得最大提前完工时间最小.由于工件不允许延迟,同题可能会无可行排序.先讨论了问题的可行性.如果问题可行,找出一个可行序列作为预排序列,并提出了一个算法计算每个工件尽可能迟的开工时间.而后,提出了一个多项式时间最优算法,在预排序列的基础上,通过调整两台机器上最先加工的工件来获得最优排序.     

基于可能度排序法的区间信息指派方法

针对具有区间数信息的多目标指派问题,利用区间数可能度排序方法,给出了一种新的指派方法.该方法充分利用实际所给的区间信息进行求解,克服了以往这类指派问题最后由多目标问题转换为单目标问题时权数确定主观性大的缺陷.最后给出了该方法的一个算例.     

保险管理决策中的两个问题

本文运用风险决策理论建立了分保限额与红利分派两个保险管理决策问题的数学模型,从理论和实践两个方面讨论了最优管理策略,并给出了计算实例。     

一类加工时间依赖资源的单机排序问题

讨论了一类有准备时间且任务的加工时间依赖资源的单机排序问题.目标函数为最大完工时间与分配给各任务资源消耗量的加权线性组合.给出了问题的若干相关性质.在此基础上,对于任务之间无优先约束和有任意优先约束的情况.分别给出了最优排列算法和最优资源分配方法.并用数值例子作了说明.     

分批排序的"转换引理"及其应用

本文首次对同类机分批排序问题进行了研究,讨论极小化最大完工时间和极小化最大延迟两类问题.首先揭示了分批排序问题与经典排序问题之间的联系,得到了有趣的“转换引理”,提出了近似算法并用“转换引理”分析了这些算法的最差性能,改进了前人的诸多结果.     

层次分析法应用过程中的若干问题

层次分析法是处理多准则决策的一种系统化、层次化的分析方法,在经济、管理、工程和社会诸多领域中有着广泛的应用.通过若干案例对层次分析法应用过程中关于权重度量的相对量测与绝对量测、比例尺度的分配模式与理想模式、方案的排序保持与排序逆转以及与线性规划的结合等问题给以讨论.     

数学规划与约束规划整合下的多目标分组排序问题研究

分组排序问题属于NP-难题, 单纯的数学规划模型或约束规划模型都无法在有效时间内解决相当规模的此类问题. 控制成本、缩短工期和减少任务延迟是排序问题的三个基本目标, 在实际工作中决策者通常需要兼顾三者, 并在 三者之间进行权衡. 多目标分组排序问题 的研究增强了排序问题的实际应用价值, 有利于帮助决策者处理复杂的多目标环境. 然而, 多目标的引入也增加了问题求解难度, 针对数学规划擅长寻找最优, 约束规划擅长排序的特点, 将两类方法整合起来, 提出一个基于Benders分解算法, 极大提高了此类问题的求解 效率.     

联系数的自对应点及在方案综合排序中的应用

针对多方案综合评价排序中应用集对分析联系数的势函数a/c进行排序时零不能作除数的问题,提出联系数的自对应点概念,讨论了自对应点的性质,举例说明了联系数的自对应点的具体应用,拓广了联系数的应用范围,也为集对分析联系数中的i取值提供了一种新思路.     

灰色分派问题及其应用

在分派问题中，总假设被分派工作的人（或机器等）做各项工作的效率（或所费时间）都是确定的值．但实际上．对于以往未做过的工作，或做过但情况变化较大的工作都难以定下确切的工作效率，而只能估计出一个大概的范围．这也就是说有些工作效率是有理灰数．我们把这一类分派问题称为灰色分派问题．木文给出了灰色分派问题有关定理的证明以及一个应用实例．     

排序问题的定义、分类和在国内的某些研究进展

排序问题是组合最优化中的一个重要分支。然而,由于使用术语混淆,问题表述不清楚,给学习和交流带来困难。本文从国际公认的有关定义出发,提出序列、整序、排序、时间表和排时(安排时间表)等术语的汉语译名和相关定义,阐述目前国际上使用的三参数分类法,回顾国内排序研究的动向,介绍上海地区研究生和青年教师排序问题讨论班的情况、成果和打算。一、排序、排时和整序若干个工件要在一些机器上进行加工,如何安排机器和工件,使得某些要求(目标函数)达到最优,这就是所谓排序问题。排序问题最早是在机器制造中提出,因此沿用机器制造的术语是理所当然的。然而,这并不意味着排序问题仅仅在机器制造中得以应用。事实上,排