检索结果-内蒙古大学图书馆

河南理工大学学报（自然科学版） 2016年第5期35卷 745-748页

作者：李文杰万龙洛阳师范学院数学科学学院河南洛阳471022 江西财经大学信息管理学院江西南昌330013

在单机区间排序环境中定义了一种新的半在线排序模型:区间是随着时间依次到达的,区间的一切信息,如到达时间、区间长度、权重等在区间的到达时刻才可获知;已知区间实例集中区间的最大权重与最小权重之比为Δ;目标是确定一个工件允许被... 详细信息

在单机区间排序环境中定义了一种新的半在线排序模型:区间是随着时间依次到达的,区间的一切信息,如到达时间、区间长度、权重等在区间的到达时刻才可获知;已知区间实例集中区间的最大权重与最小权重之比为Δ;目标是确定一个工件允许被终端抢先的排序最大化接收区间的总权重。用对手法给出了该问题的一个下界为2,接着用组合分析法设计了该问题的一个在线算法H,并用最小反例法证明其竞争比分别为(1+(4Δ+1)1/2)/2(1≤Δ≤12时)和4(Δ>12时)。表明当Δ=2时,算法H是一个最好可能的在线算法.

关键词：在线排序在线算法等长区间竞争比

来源：评论

学校读者我要写书评

暂无评论

一致机上最小化时间表长的在线排序问题

一致机上最小化时间表长的在线排序问题

引用

作者：曲晓慧郑州大学

学位级别：硕士

在离线排序问题中,机器的性质是多样的,其中研究比较多的主要为恒同机、一致机以及无关机.所谓恒同机是指机器的速度是一样的,工件的加工时间只与工件自身的长度有关,而与机器无关；一致机是指机器的速度是不同的,一个工件的加工时间既... 详细信息

在离线排序问题中,机器的性质是多样的,其中研究比较多的主要为恒同机、一致机以及无关机.所谓恒同机是指机器的速度是一样的,工件的加工时间只与工件自身的长度有关,而与机器无关；一致机是指机器的速度是不同的,一个工件的加工时间既与工件自身有关又与所排的机器速度有关；无关机是指机器的速度与所加工的工件也存在着联系.本文研究一致机上的在线排序问题,工件在到达之前的所有信息都是未知的.在线包括按时到达和按序列到达.按时到达即每个工件都有各自的到达时间,按序列到达即工件是一个接着一个到的,下一个工件只有在前一个工件排序之后才能到达.每个工件一旦到达,工件的所有信息就变成已知.在第二章中,研究了m台一致机上批容量无界的工件长度为1在线排序问题Qm|online, p-batch,b=∞,pj=1|Cmax(m≥2),其中前m—1台机器的速度为1,最后一台机器的速度为v(0在线指的是工件按时间到达,在工件到达之前,该工件的所有信息是未知的.每个工件的加工时间均为1.分批指的是一台分批机器可以一批同时加工至多b个工件.批的加工时长由该批中的最长工件决定.按照批的容量,可以分为两类平行分批排序：有界的情形和无界的情形.这里我们研究批容量无界的情形.我们给出竞争比为的最好可能的在线算法.其中a1满足等式(1+α)m=2+α;α2满足等式(1+α)(m+1)= (1/υ-1)(1+α)(m-1)+2+α.在第三章中,我们考虑2台一致机上的分层可中断在线排序问题Q2|online-list,g= 2,pmtn|Cmax,工件是按序列到达,即后一个工件的信息只有在前一个工件排序之后才能知道.第一台机器的速度为1,第二台机器的速度为υ.该问题所研究的工件分为两层,对于工件Jj来说,gj=1表示该工件只能在第一台机器上加工,gj=2表示该工件可以在任意一台机器上加工.进一步,排在速度为1的机器上的工件的实际加工时间为该工件自身的加工时间,而排在速度为υ的机器上的工件的加工时间等于该工件的标准加工时间与机器速度的比值.在任意时刻,每个机器最多只能加工一个工件,每个工件最多只能被一台机器加工.可中断即工件可以分成若干个片段在不重叠的时间内在不同的机器上加工.这里所研究的可中断是不允许有空闲时间的,后到达的工件必须紧着前面排好的工件去排.在实际应用中的一些情况下,可能不允许有空闲时间是必须的,这也使得本文有研究价值.本章对于当v≤1时给出竞争比的下界为1+υ/υ+1,当v≤1且满足v3+v2≥1时给出竞争比为1+1/υ2+υ的在线算法；当v≥1时给出了竞争比的下界为1+1/υ+1,并给出竞争比为1+v/v+1的在线算法.

关键词：一致机在线排序平行分批分层可中断空闲时间最大完工时间竞争比

来源：评论

学校读者我要写书评

暂无评论

带拒绝费用的平行机在线排序

引用

石家庄铁道大学学报（自然科学版） 2016年第2期29卷 107-110页

作者：荣建华侯丽英石家庄铁道大学四方学院基础部河北石家庄051132 南京农业大学理学院江苏南京210095

研究了工件带有拒绝费用的m台平行机在线算法,假定有m台平行机M_1,M_2,…,M_m,n个工件J_1,J_2,…,J_n,每个工件的加工时间与拒绝费用成固定的比例α(α≥0),即p_j=αt_j,当α较大时,即工件的拒绝费用相对于加工时间较大,则将此工件接收... 详细信息

研究了工件带有拒绝费用的m台平行机在线算法,假定有m台平行机M_1,M_2,…,M_m,n个工件J_1,J_2,…,J_n,每个工件的加工时间与拒绝费用成固定的比例α(α≥0),即p_j=αt_j,当α较大时,即工件的拒绝费用相对于加工时间较大,则将此工件接收加工;当α较小时,即每个工件的拒绝费用相对于其加工时间较小,此时将工件拒绝。文中设计出在线算法PRLS,并证明算法的竞争比为关于参数α的分段函数,且为紧界。

关键词：在线排序竞争比同型机拒绝费用不可中断运筹学

来源：评论

学校读者我要写书评

暂无评论

两台带服务等级的可拒绝同型机可中断在线排序问题的最优算法研究

引用

嘉兴学院学报 2016年第6期28卷 69-73页

作者：闵啸朱俊蕾嘉兴学院数理与信息工程学院浙江嘉兴314001

研究两台带服务等级的可拒绝同型机可中断在线排序问题.设有两台同型机M_1、M_2,速度一致,但具有不同的加工能力,用其服务等级表示,M_1的服务等级为1,M_2的服务等级为2.工件j按列表在线到达,每个工件带有三个参数:长度tj、等级gj=1或2... 详细信息

研究两台带服务等级的可拒绝同型机可中断在线排序问题.设有两台同型机M_1、M_2,速度一致,但具有不同的加工能力,用其服务等级表示,M_1的服务等级为1,M_2的服务等级为2.工件j按列表在线到达,每个工件带有三个参数:长度tj、等级gj=1或2、罚值pj.当j到达时,其可以被拒绝,但要付出相应的罚值pj,也可以被接受并分配给机器加工,但规定其只能安排给服务等级小于工件等级的机器加工,即等级为1的工件只能分给M_1加工,等级为2的工件可以分给任一台机器加工,加工允许中断,目标为极小化加工工件集的最晚完工时间和拒绝工件集的总罚值之和.本文对于该问题给出了一个最优在线算法,其竞争比为1.618.

关键词：在线排序同型机服务等级可中断可拒绝竞争比

来源：评论

学校读者我要写书评

暂无评论

一种特殊情形下的三台可拒绝同类机在线排序问题

引用

嘉兴学院学报 2016年第6期28卷 74-77,130页

作者：荣建华侯丽英石家庄铁道大学四方学院河北石家庄051132 南京农业大学理学院江苏南京210095

研究了工件带有拒绝费用的三台同类机在线算法:假定有三台同类机,速度分别为s_1=s_2=1,s_3=s(s≥1).n个工件J_1,J_2,…,J_n,每个工件的加工时间与拒绝费用成固定的比例α(α≥0),即p_j=αt_j.当α较大时,即工件的拒绝费用相对于加工时... 详细信息

研究了工件带有拒绝费用的三台同类机在线算法:假定有三台同类机,速度分别为s_1=s_2=1,s_3=s(s≥1).n个工件J_1,J_2,…,J_n,每个工件的加工时间与拒绝费用成固定的比例α(α≥0),即p_j=αt_j.当α较大时,即工件的拒绝费用相对于加工时间较大,则将此工件接收加工;当α较小时,即每个工件的拒绝费用相对于其加工时间较小,此时将工件拒绝.目标函数为使被加工工件的最大完工时间与被拒绝工件的总罚值之和最小.工件的加工不可中断.设计了在线算法URL,并证明算法的竞争比为关于参数α的分段函数,且为紧界.

关键词：在线排序同类机拒绝费用不可中断竞争比

来源：评论

学校读者我要写书评

暂无评论

平行机上带有前瞻区间的不相容工件组在线排序问题

引用

运筹学学报 2015年第4期19卷 121-126页

作者：李文华柴幸袁航杨素芳郑州大学数学与统计学院郑州450001 浙江大学经济学院杭州310027

研究当不相容工件组的个数与机器数相等时，具有前瞻区间的单位工件平行机无界平行分批在线排序问题工件按时在线到达，目标是最小化最大完工时间．具有前瞻区间是指在时刻t，在线算法能预见到时间区间（t，t＋β[]内到达的所有工件的... 详细信息

研究当不相容工件组的个数与机器数相等时，具有前瞻区间的单位工件平行机无界平行分批在线排序问题工件按时在线到达，目标是最小化最大完工时间．具有前瞻区间是指在时刻t，在线算法能预见到时间区间（t，t＋β[]内到达的所有工件的信息．不可相容的工件组是指属于不同组的工件不能被安排在同一批中加工．当β≥1时，提供了一个最优的在线算法；当0≤p〈1时，提供了一个竞争比为1＋α的最好可能的在线算法，其中＆是方程OL0＋（1＋β）α＋β-1=0的一个正根．最后，给出了当β=0时稠密算法竞争比的下界，并提供了达到该下界的最好可能的稠密算法．

关键词：在线排序平行分批不相容工件组最大完工时间竞争比

来源：评论

学校读者我要写书评

暂无评论

最大化接收工件个数的在线分批排序问题研究

引用

郑州大学学报（理学版） 2016年第2期48卷 24-28页

作者：李文杰马冉洛阳师范学院数学科学学院河南洛阳471022 河南理工大学数学与信息科学学院河南焦作454000

研究m台批处理机上的等长工件在线排序问题.在该问题中,工件是随着时间依次到达的,每个工件J具有一个共同的加工时间p>0,一个释放时间rj≥0,一个必须交货期dj>0.一台机器可以同时加工b个工件(b个工件构成一批),b=∞表示批容量无界... 详细信息

研究m台批处理机上的等长工件在线排序问题.在该问题中,工件是随着时间依次到达的,每个工件J具有一个共同的加工时间p>0,一个释放时间rj≥0,一个必须交货期dj>0.一台机器可以同时加工b个工件(b个工件构成一批),b=∞表示批容量无界.每一批的加工时间由该批中工件的最长加工时间来决定.同一批中的所有工件均具有相同的开工时间和完工时间,目标是确定一个工件可以被中断重启的在线排序最大化接收工件总个数.首先,当m=2、3时分别给出了问题的下界为2和6/5.其次,设计出了问题的一个在线算法H并证明其竞争比分别为3(当m=2时)、4(当m=3或m≥4为偶数时)和5(当m≥5为奇数时).

关键词：在线排序在线算法批处理机竞争比

来源：评论

学校读者我要写书评

暂无评论

工件具有恶化效应的分批排序问题

工件具有恶化效应的分批排序问题

引用

作者：王嘉和曲阜师范大学

学位级别：硕士

排序问题是一类典型的组合优化问题,随着社会的发展,排序问题被广泛的应用到运输调度、计算机系统和管理科学等许多领域.在经典的排序问题中,工件的加工时间是固定不变的.然而在现实的工业生产中,由于受到机器的老化磨损、加工环境以及... 详细信息

排序问题是一类典型的组合优化问题,随着社会的发展,排序问题被广泛的应用到运输调度、计算机系统和管理科学等许多领域.在经典的排序问题中,工件的加工时间是固定不变的.然而在现实的工业生产中,由于受到机器的老化磨损、加工环境以及工件本身特性等影响,工件的加工时间可能会随着开工时间的推迟而延长,此类现象称为工件的恶化效应.在钢铁生产、救灾资源分配等过程中,都有恶化效应的发生.因此,研究工件具有恶化效应的排序问题有着重要的理论意义和应用价值.本文主要研究了工件具有恶化效应的在线平行批排序问题和工件具有恶化效应的继列批排序问题,工件的加工时间是其开工时间的线性增函数.本文讨论的目标函数包括最小化工件的最大完工时间、最小化工件的最大流程时间和最小化工件的最大处理时间.全文共分四章,具体如下:第一章主要介绍了排序问题的研究背景、相关知识以及相关领域的研究现状,并简要概括了本文的主要工作.第二章研究了单机上工件具有简单线性恶化效应的在线平行批排序问题,工件Jj的加工时间为pj=αjSj,其中αj是工件Jj的恶化率,Sj为工件Jj的开工时间.当问题的目标函数为最小化工件的最大完工时间时,若工件按照恶化率大小的不增序到达,考虑批容量有界的情形,分析了该问题的下界并且给出了竞争比为1+αmax的最好可能的在线算法,其中αmax是全部工件中最大的恶化率;当问题的目标函数为最小化工件的最大流程时间时,若所有工件具有相同的恶化率α,考虑批容量无界的情形,分析了该问题的下界并且给出了竞争比为2+α的最好可能的在线算法.第三章研究了单机上工件具有成比例线性恶化效应的在线平行批排序问题,工件Jj的加工时间为Pj=αj(A+BSj),其中αj是工件Jj的恶化率,Sj为工件Jj的开工时间,A ≥ 0,B ≥ 0,A和B不同时为0.当问题的目标函数为最小化工件的最大完工时间时,考虑批容量无界的情形,分析了该问题的下界并且给出了竞争比为2+Bαmax的在线算法;当问题目标函数为最小化工件的最大处理时间时,考虑批容量无界的情形,分析了该问题的下界并且给出了竞争比为1+Bαmax的最好可能的在线算法.第四章研究了单机上工件具有成比例线性恶化效应的继列批排序问题,问题假设工件具有不同的类型并且每批次有依赖于顺序的设置时间,目标函数为最小化工件的最大完工时间.针对该问题设计了一个最优算法,并证明了该算法的时间复杂度为O(nlogn).

关键词：排序分批排序恶化效应在线排序竞争比

来源：评论

学校读者我要写书评

暂无评论

工件允许重启的平行分批在线排序研究

工件允许重启的平行分批在线排序研究

引用

作者：刘海玲郑州大学

学位级别：博士

排序论是运筹学与组合最优化的重要分支.分批排序是人们十分关注的现代排序模型;其特点是可将工件分批进行加工,每一批工件具有相同的开工时间和相同的完工时间.在本文研究的平行分批排序模型中,每一批的加工时间等于该批中工件的最长... 详细信息

排序论是运筹学与组合最优化的重要分支.分批排序是人们十分关注的现代排序模型;其特点是可将工件分批进行加工,每一批工件具有相同的开工时间和相同的完工时间.在本文研究的平行分批排序模型中,每一批的加工时间等于该批中工件的最长加工时间.按照每一批可以加工的工件数目b的限制(称为批容量),平行分批排序又可分为批容量有限(b<∞)和批容量无限(b=∞)两种情形.在线排序问题是近年来排序论研究的热点方向;其特点是工件的信息事先并不确定,决策者在没有获得所有工件信息之前就必须对已有工件进行排序.本文所研究的在线排序是工件实时到达(over time)的情形,即工件是随着时间逐渐到达的.工件的所有信息在其到达时刻才能获知.针对在线优化问题设计的算法称为在线算法.人们常用竞争比来衡量在线算法性能的好坏.对于一个极小化目标函数的优化问题,我们称一个在线算法是ρ-竞争的,如果对于该问题的任意实例,算法所产生的目标函数值不大于最优离线算法所产生的目标函数值的ρ倍.在线算法A的竞争比定义为ρA=inf{ρ:A是ρ-竞争的}.不难看出,ρA总是大于等于1的.由于信息的缺乏,ρA=1的情形只有在很特殊的问题上才会出现.一般而言,ρA越是接近于1,在线算法A的性能越好.如果不存在竞争比小于ρA的其他在线算法,就称算法A是该问题的最好可能的的在线算法.为了得到性能更好的在线算法,人们常常允许工件重启.这里的“重启”指的是:我们可以中断正在加工的工件或工件批,中断加工的工件被重新释放出来(以前的加工作废)再重新安排加工.允许工件重启给了我们纠正错误的机会,但重启次数过多很容易造成资源的浪费和工件的损坏.因此,在线算法的设计中,有限重启也是人们采用的策略.本文中,有限重启指的是:每个工件最多只能重启一次,相应地,如果一个正在加工的批里面包含有被中断重启过的工件,这个批就不能被中断了.本学位论文研究工件允许重启或有限重启的在线平行分批排序问题.对所研究的四个在线排序问题,均给出了最好可能的在线算法.学位论文的结构如下.第一章介绍了排序论中的基本概念,常用符号和相关的研究进展.第二章研究了等长工件在m台容量无限的平行批处理机上加工,工件允许有限重启,目标函数是最小化最大完工时间的在线排序问题.对于该问题我们设计出了一个竞争比为1+αm的最好可能的在线算法.不同于已有文献中的竞争比的显式表达式,这里的1+αm是由一个算法确定的.第三章研究了等长工件在一台容量有限的平行批处理机上加工,工件允许有限重启,目标函数是最小化最大完工时间的在线排序问题.令α是方程(1+x)(2x+4x+1)=3的正根.β是方程x(1+x)=1的正根.当批容量为2时,我们给出了一个竞争比为(1+α)的最好可能的在线算法.当批容量大于等于3时,我们给出了一个竞争比为(1+β)的最好可能的在线算法.第四章研究了等长工件在一台容量有限的平行批处理机上加工,工件允许重启,目标函数是最小化最大完工时间的在线排序问题.令γ是方程x(x+1)(2x+3)=2的正根.?是方程x(x+1)(2x+1)=1的正根.当批容量为2时,我们证明了第三章中允许有限重启时批容量为2的情形的最好可能的在线算法也是允许重启时的最好可能的在线算法.当批容量为3时,我们给出了一个竞争比为(1+γ)的最好可能的在线算法.当批容量大于等于4时,我们给出了一个竞争比为(1+?)的最好可能的在线算法.第五章研究了等长工件在一台容量有限的平行批处理机上加工,工件允许有限重启且目标函数是最小化最大运输完工时间的在线排序问题.令α是方程2x(1+x)=1的正根.β是方程x(1+x)=1的正根.当批容量为2时,我们给出了一个竞争比为(1+α)的最好可能的在线算法.当批容量大于等于3时,我们给出了一个竞争比为(1+β)的最好可能的在线算法.

关键词：在线排序平行批在线算法重启有限重启

来源：评论

学校读者我要写书评

暂无评论

带有工件运输的在线排序研究

带有工件运输的在线排序研究

引用

作者：刘其佳郑州大学

学位级别：博士

在线排序是排序论的一个前沿研究方向,近二十年来得到人们广泛的研究。文献中有多种不同的在线排序模型,而本文的“在线排序”指的是“时间在线(onlinetime)排序”:工件是按时间到达,并且当一个工件到达时,才知道这个工件的具体信息。... 详细信息

在线排序是排序论的一个前沿研究方向,近二十年来得到人们广泛的研究。文献中有多种不同的在线排序模型,而本文的“在线排序”指的是“时间在线(onlinetime)排序”:工件是按时间到达,并且当一个工件到达时,才知道这个工件的具体信息。对在线问题的研究中,决策者在当前时刻需要在仅仅知道已经到达的工件信息的前提下做出决策。因而,很多在线排序问题是没有最优算法的。人们通常用竞争比来衡量一个在线算法的好坏。我们以最小化目标函数的排序问题为例。在线算法A的竞争比ρA定义为ρA=sup{A(I)/OPT(I):I是任意一个实例且满足OPT(I)>0},其中I是排序问题的任意一个实例,A(I)是执行了在线算法A得到的实例I的目标函数值,而OPT(I)则是由离线最优排序所得到的实例I的目标值。因而竞争比ρA≥1,而且ρA越趋近于1,在线算法的性能越好。如果不存在竞争比小于ρA的其他在线算法,我们就说在线算法A是最好可能的。在本文中我们研究了四类带工件运输时间的在线排序问题:在线折衷排序问题;工件具有不相容性并考虑工件运输的在线排序问题;工件的加工时间有限制的在线排序问题;工件具有退化效应的在线排序问题。本文的主要结果如下:在第二章中,我们研究了单台机器上的在线折衷排序问题,目标是最小化时间表长和最大运输完成时间。对该问题,我们给出了一个折衷竞争比为(ρ,1+(1/ρ))的最好可能的(非支配的)在线算法,其中1≤ρ≤(?)/2。在第三章中,我们研究了单台无界平行批处理机工件具有不相容性并考虑工件运输的在线排序问题,目标是最小化最大运输完成时间。这里,工件的不相容性指的是:不同工件组的工件不能放在同一个加工批或者同一个运输批进行加工或者运输。本章假设不相容工件组的数目事先不知道,运输车辆只有一台并且它的容量是充分大的。对该问题,我们给出了一个竞争比为2的最好可能的在线算法。在第四章中,我们继续研究单台无界平行批处理机工件具有不相容性并考虑工件运输的在线排序问题,目标仍是最小化最大运输完成时间。本章假设不相容工件组的数目f事先已经确定,而运输车辆依旧只有一台并且它的容量是充分大的。对于pj=p且Ti=T的情形,我们给出了一个竞争比为1+(?)f的最好可能的在线算法。对于一般情形,我们给出了一个竞争比为2的在线算法。在第五章中,我们研究了单台机器考虑工件运输且工件的加工时间有限制的在线排序问题,目标是最小化最大运输完成时间。这里,工件的加工时间有限制是指所有的工件的加工时间都在[p,(1+α)p]内。本章假设运输车辆只有一台。对该问题,在运输车辆的容量是无界和有界的两种情形,我们均给出了竞争比为√5+12的最好可能的在线算法。在第六章中,我们研究了单台机器考虑工件运输的退化工件的在线排序问题,目标是最小化最大运输完成时间。工件的退化效应是指工件的加工时间依赖于工件的开工时间,即pi=ait,其中ai≥0,t表示工件的开工时间。当运输车辆的容量无界时,我们给出了竞争比为(?)的最好可能的在线算法。当运输车辆的容量有界时,我们给出了一个竞争比为2的在线算法。

关键词：在线排序在线算法运输时间不相容工件组退化工件

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：