MapReduce同类机排序问题的改进算法

研究了MapReduce系统中极小化最大完工时间的同类机排序问题.每个工件包含两类任务集:Map任务集和Reduce任务集.工件的Reduce任务必须在该工件的所有Map任务完成后才能开始加工.Map任务是可分的,即可以被任意分割并在多台机器上同时加工,而Reduce任务是不可分的.针对m台同类机离线模型,分别考虑了Reduce任务可中断和不可中断两种情形.对于可中断情形,设计了一个近似比为2-■的近似算法,其中g_1≥1,s_i为机器σ_i的加工速度且s_1≥s_2≥…≥s_m;对于不可中断情形,则给出了一个近似比为2+3~(1/2)/3的近似算法.上述结果是对已有文献的改进.     

两台恒速机上的MapReduce排序算法研究

研究源自于MapReduce系统的一类排序问题。给定两台恒速机和一组按列表到达的工件,每个工件包含两类任务:Map Task和Reduce Task。假设Map任务和Reduce任务都是不可中断的,Map任务可以并行处理,即可以任意分割成若干小的任务并在两台机器上同时处理,而Reduce任务只可以在单台机器上处理。一旦工件到达,必须为其指派机器和开工时间,目标是使得最后完工时间最小。对LSc算法的竞争比进行了分析,得到其一般情形下的竞争比当s≥(1+5~(1/2))/2时为1+1/s,否则为1+s/(s+1)。而当每个工件Jj都满足其Map任务总长大于等于Reduce任务总长时,其竞争比当s≥(1+3~(1/2))/2时不超过1+1/(2s),否则为不超过1+s/(2s+1)。     

两台恒速机上的MapReduce排序算法研究

研究源自于MapReduce系统的一类排序问题。给定两台恒速机和一组按列表到达的工件，每个工件包含两类任务：Map Task和Reduce Task。假设Map任务和Reduce任务都是不可中断的，Map任务可以并行处理，即可以任意分割成若干小的任务并在两台机器上同时处理，而Reduce任务只可以在单台机器上处理。一旦工件到达，必须为其指派机器和开工时间，目标是使得最后完工时间最小。对LSc算法的竞争比进行了分析，得到其一般情形下的竞争比当$s\geq（1+\sqrt{5}）/2$时为$1+1/s$，否则为$1+s/（s+1）$。而当每个工件$J_j$都满足其Map任务总长大于等于Reduce任务总长时，其竞争比当$s\geq（1+\sqrt{3}）/2$时不超过$1+1/（2s）$，否则为不超过$1+s/（2s+1）$。     

具有学习效应的两台机上最优混合流水作业算法

研究相同工件在两台机器(分别称为机器M_1和M_2)上的混合流水作业问题,每个给定工件有两个任务,分别称之为任务A和任务B,任务B只能在任务A完工后才能开始加工,每个工件有两种加工模式供选择:模式1是将两个任务都安排在机器M_2上加工;模式2是将任务A和B分别安排在机器M_1和M_2上加工.假设在加工工件时,机器具有学习效应,即工件的实际加工时间与工件的加工位置有关.目标函数是最小化最大完工时间.分别讨论了具有无缓冲区与无限缓冲区两种加工环境情况,两种情况下都得到了最优算法.     

带两个服务等级的三台机最优在线算法

研究了带服务等级约束的三台平行机在线排序问题.每台机器和每个工件的服务等级为1或者2,工件只能在等级不高于它的机器上加工,即等级为1的工件只能在等级为1的机器上加工,等级为2的工件可在所有机器上加工.每个工件的加工时间为一个单位,目标是极小化所有工件的总完工时间.考虑两种情形:当一台机器等级为1,两台机器等级为2时,给出了竞争比为17/14的最优在线算法;当两台机器等级为1,一台机器等级为2时,给出了竞争比为43/36的最优在线算法.     

具有学习效应的两台机上最优混合流水作业算法

研究相同工件在两台机器（分别称为机器M₁和M₂）上的混合流水作业问题,每个给定工件有两个任务,分别称之为任务A和任务B,任务B只能在任务A完工后才能开始加工,每个工件有两种加工模式供选择：模式1是将两个任务都安排在机器M₂上加工;模式2是将任务A和B分别安排在机器M₁和M₂上加工.假设在加工工件时,机器具有学习效应,即工件的实际加工时间与工件的加工位置有关.目标函数是最小化最大完工时间.分别讨论了具有无缓冲区与无限缓冲区两种加工环境情况,两种情况下都得到了最优算法.     

需要安装时间的平行多功能机排序问题的启发式算法

考虑需要安装时间的平行多功能机排序问题。在该模型中,每个工件对应机器集合的一个子集,其只能在这个子集中的任一台机器上加工,称这个子集为该工件的加工集合;工件分组,同组工件具有相同的加工时间和加工集合,不同组中的工件在同一台机器上连续加工需要安装时间,目标函数为极小化最大完工时间。对该问题NP-难的一般情况设计启发式算法:首先按照特定的规则将所有工件组都整组地安排到各台机器上,然后通过在各机器间转移工件不断改进当前最大完工时间。通过与下界的比较检验算法的性能,大量的计算实验表明,算法是实用而有效的。     

具有m台通用机和两台专用机的Qm＋2／rj／Cmax问题的改进LS算法

对于实践中存在的机器加工速度不同的,具有两组任务的优化排序问题进行了讨论,在经典的LS算法的基础上提出了一种改进的LS算法,利用＂首先空闲＂准则选择机器,按照工件的到达顺序安排工件,讨论了将两组工件安排在两台速度不同的专用机,m台速度相同的通用机上的Cmax问题,其中工件具有调整时间或安装时间,且工件的调整时间或安装时间均不超过其加工时间的α倍.目标是在最短的时间内完成所有给定的任务.得到了利用该近似算法所得的解TLS与最优解T＊在不同条件下的两个估计,并且证明了这两个估计是紧的。     

可转包的两机自由作业排序问题(英文)

本文研究两机器自由作业问题,每工件恰有两个操作,除本身两台机器用于加工外,制造商可以将部分工件转包给承包商加工.该承包商有一台机器,可以加工全部操作。一旦承担转包任务,制造商需要支付转包费用给承包商,该费用与承包商机器单位时间价格有关.制造商需要确定转包工件集及未转包工件的排序时间表,使得转包费用与时间表的加工总长最小.本文证明该问题是NP困难的,设计动态规划算法,并讨论承包商机器时间的定价方案.     

带运输机的流水车间调度的最优算法

研究带运输时间的流水调度:在该问题中有两台机器A,B和一个运输机V,n个工件,工件需要先在机器A上加工然后在机器B上加工最后被运输机V运往目的地,而且运输机V最初停在机器B旁边.模型的目标是使所有工件都运往目的地的时间最短.文中给出了三种情况下的最优调度算法:i)A,B机器加工工件顺序给定时我们给出了线性时间的最优算法;ii)所有的工件加工时间在机器B上时间相等时我们给出了时间复杂度为O(nlogn)的最优算法;iii)机器B上工件最短加工时间大于等于机器A上工件最长加工时间时给出了时间复杂度为O(n~2)的最优算法.     

具有等级约束的三台机排序问题的可中断在线算法

研究具有等级约束的三台机在线排序问题．机器和工件的等级数均为1或2,工件只能在等级数不超过自身等级的机器上加工,且加工允许中断,目标是极小化最大工件完工时间．如果有两台机器等级为1,给出竞争比为3／2的在线算法,并证明算法是最好可能的;如果只有一台等级为1的机器,也给出竞争比为3／2的在线算法．     

转包且具有不同费用时间段的排序问题

本文研究制造商可以将工件转包给承包商加工的排序模型,承包商仅有一台机器,转包费用由分配给转包工件的不同时间段费用确定.本文分别研究制造商有一台单机及两台自由作业机器环境情形,需要确定被转包工件集及全部工件的加工顺序,使得工件最大完工时间与转包费用和最小.本文利用归约方法对制造商每个机器环境,证明问题NP困难性,并提出动态规划算法.     

转包且具有不同费用时间段的排序问题（英文）

本文研究制造商可以将工件转包给承包商加工的排序模型,承包商仅有一台机器,转包费用由分配给转包工件的不同时间段费用确定.本文分别研究制造商有一台单机及两台自由作业机器环境情形,需要确定被转包工件集及全部工件的加工顺序,使得工件最大完工时间与转包费用和最小.本文利用归约方法对制造商每个机器环境,证明问题NP困难性,并提出动态规划算法.     

带机器准备时间的两台同型机复合半在线排序问题

本文研究了预知两种信息,带机器准备时间的两台同型平行机复合半在线排序问题,即已知所有工件加工时间总和和工件按加工时间非增顺序到达,目标为极小化最大机器完工时间的半在线排序模型.我们分析了它的下界,并给出了竞争比为7/6的最优算法.     

带有装卸服务器的两台平行机调度问题的LS和LPT算法

研究带有一个装载服务器和一个卸载服务器的两台平行机调度问题.每个工件在加工前必须由装载服务器安装到机器上,加工结束后由卸载服务器从机器上进行卸载.装载和卸载时间均为单位时间,目标是极小化最大完工时间.该问题是NP难问题,文章主要分析LS和LPT两个经典的启发式算法,分别证明了这两个算法的紧界为11/7和7/6改进了已有结果.     

基于退化效应的两台机器流水作业可拒绝排序

考虑了工件具有退化效应的两台机器流水作业可拒绝排序问题,其中工件的加工时间是其开工时间的简单线性增加函数.每个工件或者被接收,依次在两台流水作业机器上被加工,或者被拒绝但需要支付一个确定的费用.考虑的目标是被接收工件的最大完工时间加上被拒绝工件的总拒绝费用之和.证明了问题是NP-难的,并提出了一个动态规划算法.最后对一种特殊情况设计了多项式时间最优算法.     

带机器准备时间的m台平行机在线和半在线排序

本文研究了目标为极大化机器最早完工时间的带机器准备时间的m台平行机在线和半在线排序问题.对于在线排序问题,本文证明了LS算法的竞争比为m.对于已知所有工件加工时间总和(sum)和最大工件加工时间(max)的两个半在线模型,本文分析了它们的下界,并给出了竞争比均为m-1的最优算法.     

具有特殊工件的平行机在线排序问题

本文研究一类具有特殊工件的平行机在线排序问题,目标是最小化最大完工时间.此模型有两种工件:正常工件和特殊工件.正常工件能够在m台平行机的任何一台机器上加工,而特殊工件仅能够在它唯一被指定的机器上加工.文中所有特殊工件的指定机器为M1.我们提供了竞争比为(2m2-2m 1)/(m2-m 1)的在线近似算法.当m=2时,算法是最好可能的.当m=3时,算法的竞争比为13/7≈1.857,并且提供了竞争比的下界(1 (平方根33))14≈1.686.     

带转包选项的自由作业排序

本文研究两机自由作业排序问题,工件的两个工序既可以在制造商的两台自由作业环境机器上加工,也可以转包给两承包商加工.每承包商有一台单机,仅能加工指定的工序.工件被转包时制造商需要付出一定数量的转包费用.制造商需要同时确定转包工件集及未转包工件的加工顺序,目标是极小化转包费用与未转包工件时间表加工总长之和.本文根据转包费用系数的不同,分析问题     

费用有限的柔性两机自由作业与流水作业排序问题

研究制造商加工环境为两机自由作业和流水作业柔性排序问题,即工件既可以在制造商两台机器上加工,又可以转包给承包商机器加工.承包商有足够多机器,使得每台机器至多加工一个工件.工件在制造商及承包商机器上所需加工时间及费用均不同.本文需要确定被转包的工件集及未转包工件的加工顺序,在加工及转包总费用不超过给定值的情况下,分别极小...