加工时间为线性增函数有上界的排序问题

本文讨论工件的加工时间是其开工时间的一类线性增加函数有上界的单机排序问题1|pj(t)(t0,T1,T2)|Cmax:设工件集J=J1,J2,…,Jn中的每个工件需要在一台机器上得到加工;工件集J被划分成两组J=Ω1+Ω2;机器上第一个被加工的工件在时刻t00开始加工;Ω1中工件的加工时间为pj(t)=ajt(当tT1)或pj(t)=ajT1(当t≥T1),Ω2中工件的加工时间为pj(t)=ajt(当tT2)或pj(t)=ajT2(当t≥T2),其中T2T1t0均是给定的常数,t表示对应工件的开工时刻;排序的目的是极小化时间表长(最大完工时间)Cm ax。在所得的引理2和引理3的基础上,本文给出一个复杂度为nlogn的多项式时间算法,从而也证明了所讨论的问题是多项式时间可解得的。     

一类具有维护和共同工期的单机排序问题

主要讨论了带有维护和共同工期的单机排序问题.工件的实际加工时间是与该工件在排序中的加工位置相关的.目标函数是共同工期相关的费用、提前完工的工件存储费用和不能在工期内完成的工件的惩罚费用之和.最后给出了多项式动态规划算法.     

具有学习效应和非线性安装时间的单机排序问题

讨论了加工工件具有学习效应和安装时间的单机排序问题。文中工件的加工时间不是固定不变的,不仅与工件的加工位置有关,同时还与已加工完成工件的加工时间有关。安装时间分为线性安装时间和非线性安装时间,本文主要讨论的是具有非线性安装时间的情况。工件的安装时间是依赖于已加工完的工件的实际加工时间和工件所排列位置的函数形式。在文中主要证明了极小化最大完工时间,极小化完工时间总和问题是多项式可解的,另外还证明了满足一定条件下的极小化加权完工时间和,极小化最大延误问题是多项式可解的。     

有安装时间的单机排序问题

工件具有安装时间的排序问题最近几年受到越来越多的关注,主要讨论了一类有安装时间且与加工位置有关的单机排序模型。在该模型中,所有工件在机器上加工时,一次只能加工一个工件,工件的相邻加工工序之间不允许出现空闲,工件的实际加工时间不是一成不变的,它不仅与工件的基本加工时间有关,同时还与工件所处的加工位置有关,工件的安装时间是依赖于已加工工件的实际加工时间的简单函数,即p-s-d形式。对目标函数为极小化最大完工时间,极小化完工时间和以及极小化总完工时间差等问题进行讨论,分别给出了多项式算法和算法复杂性。还证明了对于目标函数为完工时间,提前完工时间以及误工时间的加权和最小化问题是多项式可解的。     

具有空间对照结构渐近解的构造(Ⅰ)

对具有快慢变量非线性方程组的边值问题(μ是小参数) (du)/(dx)=g(x,u,v,w) μ(dv)/(dx)=F(x,u,w) μ(dw)/(dx)=G(x,u,v) u(0,μ)=v(0,μ)=v(1,μ)=0 本文讨论了产生空间对照结构时的渐近解构造,“啪”型内部层解位置的确定及给出了渐近解的误差估计。     

同时带有安装时间和送出时间的单机排序问题

在实际生产,如钢铁和冶金工业生产过程中,工件在加工之前需要预热或安装必要的夹具和固定装置,在加工之后工件需要进行冷却处理等,也就是工件在进行加工时常常带有安装时间和送出时间。讨论带有学习效应、安装时间和送出时间的单机排序问题。在这一模型中,工件的实际加工时间是与工件的基本加工时间和工件的实际加工位置相关的一般函数。工件的安装时间和送出时间均依赖于已加工完的工件的实际加工时间,即p-s-d形式。目标函数分别为最大完工时间、总完工时间、加权总完工时间、总延误时间、最大延误时间和最大延迟时间,提出了上述问题的最优排序规则。     

加工时间与位置相关的最小化最大完工时间两人合作排序博弈

【目的】针对加工时间与加工位置相关的两人合作排序博弈问题开展研究。【方法】工件加工时间与加工位置相关可以描述为工件加工时间随着加工序列中工件加工位置的改变而呈现出递增或递减的函数变化。两个人必须合作加工一批工件,两人各自都有一台机器可用于加工这批工件,且他们的加工成本定义为各自的最小完工时间。目标是使得他们的合作收益最大化,为了使这两个人的合作总收益最大化,需对这批工件进行一个划分,把工件分配给两台机器。【结果】提出了该问题有正整数解的充分必要条件。【结论】证明了该问题是多项式可解的。     

加工时间可控的单机排序问题

研究带有学习效应和恶化效应的单机排序问题。在此模型中,工件的学习效应是与工件加工位置相关的减函数,工件的恶化效应是与其开始加工时间相关的线性函数。在无资源约束的情况下,分别讨论了目标函数为最大完工时间、总完工时间及总完工时间的绝对差之和的排序问题,证明了这些问题都是多项式时间可解的。对于带有资源约束问题,若分配一定的资源,工件加工时间会减少。讨论了在线性资源分配情况下,带有学习效应、恶化效应和资源分配量的交货期排序问题,其中所有工件有一个共同的交货期。目的是确定最优交货期、资源分配及工件的加工顺序,使交货期、提前、延误和资源分配量之和最小,通过将其转化为指派问题,证明问题是多项式时间可解的。     

基于一般时间相关和位置相关的单机排序问题研究

【目的】研究了工件加工时间、开工时间与所在位置相关的单机排序问题,以扩展这类问题的研究范围。【方法】工件加工时间是开工时间和所在位置的一般非增函数。工件开工时间越晚,加工位置越靠后,实际加工时间则越短。受相关论文的启发,对此问题用经典算法进行了讨论。【结果】目标函数为极小化最大完工时间和总完工时间的问题证明了SPT算法仍是最优算法。对极小化加权总完工时间问题分析了最坏竞争比;在正常加工时间和权重或工期存在特殊关系时对加权总完工时间和最大延迟问题证明了经典算法是最优的。【结论】对所研究的单机排序问题给出了若干结果。     

加工时间依赖工件位置的树约束单机排序问题

讨论了工件的加工时间依赖于工件位置的树约束单机排序问题,给出了目标函数为最大完工时间的多项式算法.结果表明,最大家庭树中的工件优先于其它家庭树中的工件加工,并且其工件要连续加工所得到的排序为最优排序.     

稳态吊桥方程耦合系统正解的存在性

本文研究了二阶和四阶常微分方程耦合系统u~((4))(t)=λf(t,v(t)),t∈(0,1),-v″(t)=λg(t,u(t)),t∈(0,1),u(0)=u(1)=u″(0)=u″(1),v(0)=v(1)正解的存在性,其中λ0为参数,f,g∈C([0,1]×[0,∞),R).当f,g满足适当的条件时,本文证明了λ充分大时方程一个正解的存在性.主要结果的证明基于Schauder不动点定理.     

一类三阶周期边值共振问题解的存在性

本文研究了三阶周期边值共振问题{v'(t)=f(t,v(t)),t∈[0,T],v~(i)(0)-v~(i)(T)=0,i=0,1,2解的存在性,其中函数f:[0,T]×R→R连续且有界.当非线性项f满足适当条件时,本文发展了上下解方法并得到其解的存在性.主要结果的证明基于Lyapunov-Schmidt过程和解集连通理论.     

有序 Banach 空间非线性四阶边值问题的正解

讨论有序Banach 空间E中非线性四阶边值问题 $ \left\{\begin{array}{ll} u^{(4)}(t)=f(t,u(t),u'(t)),\qquad 0\leqslant t\leqslant 1, \ u(0)=u(1)=u'(0)=u'(1)=\theta, \ \end{array} \right. $ 正解的存在性, 其中\ $f:[0, 1]\times E\times E\rightarrow E$ 连续. 在较一般的非紧性测度条件与序条件下运用凝聚映射的不动点指数理论获得了该问题正解的存在性.     

带有导数项的~Neumann~问题正解

本文研究了带有导数项的非线性~Newmann~问题 $$ \left\{\begin{array}{ll} u''(t)+ku(t)=f(t,u(t),u''(t)),\quad t\in (0,1),\\[2ex] u''(0)=u''(1)=0 \\[2ex] \end{array}. \right.\eqno $$ 其中~$0相似文献   

流水作业由二台柔性机器组成时的极小完工时间之和问题

该文考虑下述由2台机器组成的流水作业问题:n个相同工件需依相同次序在机器1、2上共进行3次加工.工件j的第一次加工在机器1上进行,所需时间为p1;其第二次加工或单独在机器1上或单独在机器2上进行,当工件j的第二次加工在机器1上进行时,所需时间为p12,当工件j的第二次加工在机器2上进行时,所需时间为p21;其第三次加工需在机器2上进行,所需时间为p2.要求适当安排这n个工件的加工方式以使它们的完工时间之和达到极小.对该问题作者对应不同情况给出了不同的最优解法.     

关于具有正比权值完工时间与公共交货期偏差最小化单机调度问题的注记

讨论了工件权值与加工时间成正比、完工时间与公共交货期绝对偏差权和最小化单机调度问题(简记为PTD问题).1997年,Alidaee和Dragan证明了PTD问题LPT(LargestProcessingTime)调度最优.并给出一个简单证明;还讨论了加工时间随机的情形,指出依加工时间似然比单减得到的工件调度最优.     

带有学习效应和加工时间可控的排序问题

考虑了带有学习效应和加工时间可控的交货期窗口的单机排序问题。工件的加工时间是关于所分配资源的线性函数或凸函数。其中每一个工件均有一个交货期窗口且窗口大小相同,若工件在窗口之前或之后完工则会产生相应的惩罚,若工件在窗口中完工则无惩罚,目标是通过极小化包括提前,误工工件数、窗口的开始时间、窗口大小和资源消耗的总惩罚函数确定工件的最优排序、最优加工时间和最优资源分配量。在加工时间是线性资源函数的情况下,通过将问题转化为一系列指派问题,构造一个多项式时间算法;在加工时间是凸资源函数的情况下,构造了一个在多项式时间内可解的动态规划算法。     

退化条件下的工期指派的单机排序问题

研究退化条件下的工期指派的单机排序问题。每个工件均有一个关于工期的连续非减的惩罚函数。工件的加工时间是退化的,即工件的加工时间是其开始加工时间的一个线性增函数,所有工件都有一个相同的退化率。目标是确定工件的最优加工顺序、最优工期和最优开始加工时间,使总工期、误工工件数及总完工时间之和最小。工件在工期之后完成则称为误工工件,工件在工期之前完成则是提前工件。工期指派分两种情况,一种是所有的工件工期都相等,另一种是不同的工件有不同的工期。对于上述两种情况分别给出了最优解的3个性质,并且证明了这个问题是多项式时间可解的。     

一致性条件下带磨损因子的排序问题

考虑下述带磨损因子的排序问题：n个工件需在同台机器上依次加工，工件j,j=1，2，…，n,所需的加工时间同它被开始加工的时间有关，当工件j开始被加工的时间为t时其所需的加工时间为Pj=bjt，其中bj可视作与工件j有关的一个磨损因子．要求适当排列这n个工件的加工顺序，使某目标函数值达最小．对最大迟后、最大延误、加权完工时间之和这三个目标函数，文中给出了相应条件下的最优算法．