模糊环境下的生产计划最小风险模型

基于可信性理论和两阶段模糊优化方法,提出一类新的模糊生产计划模型．同时设计一个基于模糊模拟和遗传算法的启发式算法来求解模糊生产计划问题,并且给出一个数值例子来证明所提出算法的可行性．     

两类单机成组排序的问题

讨论了单机成组排序问题的加权总完工时间和最大延迟时间的极小化问题.并分别给出了算法.对于单杌成组排序误工总数问题,通过构造函数,利用动态规划方法给出其算法.     

转盘上单机排序问题的可解情形

文献（１）中证明,即使只有一台加工机器,带有转盘的流水作业问题的加工全长问题Ｔ１也是强ＮＰ困难的。本文讨论问题Ｔ１的几个多项式时间的可解情形。     

工件带拒绝费用的单机排序问题

在经典排序模型中,我们往往假定机器必须加工所有的工件,并且它们的加工时间都是给定的。但是在许多现实的应用中,若某个工件的加工时间或者加工费用很大,我们就会考虑是否要加工该工件,我们既可以选择付出一定的费用而拒绝加工该工件也可以选择不付费而加工它。这时目标函数不再是传统的最大总完工时间,极小化最大完工时间,最大延迟等,而是要同时考虑费用,我们把这种排序称为可拒绝排序[1][2]。本文研究了工件带拒绝费用的单机分族分批排序问题。主要证明了问题1,sfg|family-jobs,rej|Cmax+∑j∈sej和1,sfg|family-jobs,rej,b|Cmax+jisej是NP-难的,给出了它们的近似算法。     

工件可拒绝的单机无界平行批排序

首次考虑了目标函数为极小化最大延误与被拒绝工件的惩罚费用之和的单机无界平行批排序问题.证明了问题1｜B≥n,rej｜ Tmax+ TCP为NP-困难的,针对该问题给出了基于动态规划的伪多项式时间算法.     

有限重启的单机在线分批排序问题

研究了单机批容量b=3时有限重启且工件长度丰H同的情形,给出了一个竞争比为4/3的最好可能的在线算法.     

带学习效应的单机成组排序问题

考虑了在工件具有学习效应的条件下,目标函数为最大完工时间和总完工时间的单机成组排序问题.对这两个问题分别给出了多项式时问算法并证明了其算法的最优性.     

“合成链”算法与一类链优先约束的单机分批排序问题

讨论问题1| chains,B|Cmax具体可描述为:有m条链,其中一条链上有n个工件,其余的m-1条链上的工件数之和为常数k,且工件的加工时间不限制,目标函数为最大完工时间.我们对该问题B=2的情况进行了深入的探讨,在研究过程中首次提出“合成链“算法,给出了时间复杂性为O(nk)的多项式时间算法.     

带有霸王工件的单机在线分批排序

研究了一个带有霸王工件且允许重启的单机在线分批排序,其目标函数值为求时间表长．对于批容量无限的情况,给出了一个最坏竞争比为2的在线算法．     

配送时间有学习效应的单机排序问题

提出一种带有配送时间的单机排序问题,配送时间具有学习效应,目标为极小化总配送完成时间.证明了两个特殊情形下的最优序;分析一般情形下排序问题的性质,并由此得到一致性条件下该问题的最优序.     

一致性条件下的一类排序问题的算法研究

这篇文章研究了在一致性条件下,具有一般学习效应的一类超前有奖延误受罚的排序问题.由于1‖∑nj=1(αjTj-βjEj)是NP-困难的,这篇文章研究了该模型的3类多项式时间可解的特例,并给出了相应的算法.     

一类排序问题的最优化算法

本文讨论了具有调整时间的多类工件单机排序问题I|MCS|∑Ci|尽.管该问题是强NP—完全的,但本文证明了一个最优解的必要条件,由此给出了一个复杂性为O(M~2(n/M 1)~M)的动态规划算法.这是一个相当满意的结果.本文还对表现测度为加权完工时间和的情况做了一些讨论,在权为类权时得到了与上述同样的结果.     

具有学习效应且交货期可指派的单机排序问题

探讨了工件具有CON/SLK交货期指派且机器具有与位置有关的学习效应目标为极小化交货期指派费用、无误工工件的提前费用以及误工工件的惩罚费用之和排序问题.所探讨的问题在无误工工件数确定的情况下可以转化为指派问题,由于误工工件数最多有n种可能且指派问题能在O(n3)时间内解决,故排序问题是多项式时间可解的,并给出最优算法;在恶化工件具有CON/SLK交货期指派的基础上同时考虑了机器具有学习效应的排序,并给出了两种问题的多项式时间最优算法.     

基于量子遗传算法的一类非线性lp问题的求解方法

文章构造了求解非线性lp问题的新方法——量子遗传法。给出了具体的量子遗传算法步骤,并且结合文献[6]相关算例,将用量子遗传算法求解出的结果与其对比分析,结果显示量子遗传算法求在解非线性lp问题是十分有效和实用的。     

排序位移法证明一类离散不等式

文章给出一种证明一类离散不等式的新方法──排序位移法．     

一类特殊图关于Merrifield-Simmons指标的排序

以m阶圈Cm与n+1阶扇Fn+1为组成部分,利用两次单点重合连接方式定义了一种特殊平面图类CFk(m,n+1),并研究了该图类关于Merrifield-Simmons指标的排序问题,得到了不同k值图类CFk(m,n+1)关于Merrifield-Simmons指标的排序结果.     

有界模糊数的比较与排序

利用两模糊数之间的距离公式,将模糊数之间的比较转换为模糊数与纵轴距离之间的比较。在此基础之上定义了模糊数空间上的序关系,并证明了它们的一些性质。这种方法的排序效果与人们的直觉是一致的且不悖逆于实数的自然序。利用距离方法定义的序关系,便于理解与计算机实现。     

多类工件单机排序中具有多项式时间可解的子问题

本文讨论了NP—完全问题1|MCS|∑W_iC_i的子问题找到了两个多项式可解的情形.本文还给出了其它两种情形的最优性条件,由此得到的算法可使复杂性大大降低.     

工件有优先约束和尺寸的单机分批排序问题

研究了工件有优先约束和尺寸大小关系的分批排序问题,这里目标函数为工件的极大完工时间,这类问题是NP—完备的.对工件加工时间相同和有特殊到达时间的情况给出了它的近似算法,并证明其最差性能比不超过2.     

加工时间与位置有关的一类排序问题

研究单机具有递减率的加工时间成组排序问题,目标函数为超前有奖延迟受罚排序问题.研究了该问题的3种特殊情形,给出了相应的最优算法和计算复杂性的分析.