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

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

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

研究带运输时间的流水调度:在该问题中有两台机器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的工件只能在等级为1的机器上加工,等级为2的工件可在所有机器上加工.每个工件的加工时间为一个单位,目标是极小化所有工件的总完工时间.考虑两种情形:当一台机器等级为1,两台机器等级为2时,给出了竞争比为17/14的最优在线算法;当两台机器等级为1,一台机器等级为2时,给出了竞争比为43/36的最优在线算法.     

两台带服务等级的可拒绝同型机排序问题的在线算法

两台同型机M_1,M_2, 加工速度一致, 但拥有不同的加工能力,用其服务等级表示, M_1的服务等级为1, M_2的服务等级为2. 工件j按列表在线到达,每个工件带有三个参数: 长度t_j,等级g_j=1或2, 罚值p_j. 当j到达时, 可以被拒绝, 但要付出相应的罚值p_j, 也可以被接受并分配给服务等级不超过该工件等级的机器加工,事实上等级为1的工件只能分给M_1加工, 等级为2的工件可以分给M_1或M_2加工, 加工不允许中断. 目标为极小化加工工件集的最晚完工时间(makespan)和拒绝工件集的总罚值之和. 对于该问题给出了一个在线算法, 其竞争比为11/6, 以及问题一个下界5/3.     

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的近似算法.上述结果是对已有文献的改进.     

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

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

带有运输且加工具有灵活性的无等待流水作业排序问题

研究一类带有运输且加工具有灵活性的两阶段无等待流水作业排序问题, 其中每阶段只有一台机器, 每个工件有两道工序需要依次在两台机器上加工, 工件在两台机器上的加工及两道工序之间不允许等待. 给出两种近似算法, 并分别分析其最坏情况界. 第一种算法是排列排序, 证明了最坏情况界不超过5/2; 第二种算法将工件按照两道工序加工时间之和的递增顺序排序, 证明其最坏情况界不超过2. 最后, 通过数值模拟比较算法的性能. 对问题中各参数取不同值的情况, 分别生成若干个实例, 用算法得到的解与最优解的下界作比值, 通过分析这些比值的最大值、最小值和平均值来比较上述两个算法的性能.     

平行机中关于关于同类机近似算法的研究

我们考虑平行机排序问题中的这样一类:机器两台,类型一样,但效率不同.其中n个工件在第一台机器上的加工时间分别为p1,p2,…,Pn,在第二台机器上的加工时间分别为αρ1,αρ2,…,αρn,其中0<α≤1.每台机器上的工件总数不受限制.n个工件的权分别为w1,w2,…,wn,我们的目标是如何在这两台机器上安排这n个工件以及如何确定每台机器上工件加工的先后顺序,使得这n个工件的完工时间的总权和 达到最小.该问题记为 .对于这个问题,我们给出一个1.1755近似算法.     

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

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

两台平行机完工时间平方和最小的排序问题

在两个竞争公司进行零和博弈过程中, 最大化两个公司收益的乘积, 在两台平行机的离线排序问题中相当于最小化两台机器完工时间的平方和. 给出了该问题修改的延缓开始\ LPT\ 算法: 首先, 将工件按照加工时间$\p_j\ $的\ LPT\ 序重新标记; 若加工时间最长的前\ $2m$\ 个工件的总加工时间\ $P(2m)< (2m+1)p_{2m+1}$, 最优的安排加工前\ $2m+1$\ 个工件, 一旦有机器空闲, 依次从第\ $2m+2$\ 个工件安排加工; 否则,\ $P(2m)\geq (2m+1)p_{2m+1}$, 最优的安排加工前\ $2m$\ 个工件, 一旦有机器空闲, 依次从第\ $2m+1$\ 个工件安排加工. 证明了该算法的最差性能比不超过\ $1+ ( \frac{1}{2m+2} )^2$, 且界是紧的.     

工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法

考虑了工件有到达时间且拒绝工件总个数不超过某个给定值的单机平行分批排序问题.在该问题中,给定一个工件集和一台可以进行批处理加工的机器.每个工件有它的到达时间和加工时间;对于每个工件来说要么被拒绝要么被接受安排在机器的某一个批次里进行加工;一个工件如果被拒绝,则需支付该工件对应的拒绝费用.为了保证一定的服务水平,要求拒绝工件的总个数不超过给定值.目标是如何安排被接受工件的加工批次和加工次序使得其最大完工时间与被拒绝工件的总拒绝费用之和最小.该问题是NP-难的,对此给出了伪多项式时间动态规划精确算法,2-近似算法和完全多项式时间近似方案.     

工件有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法

考虑了工件有到达时间且拒绝工件总个数不超过某个给定值的单机平行分批排序问题.在该问题中,给定一个工件集和一台可以进行批处理加工的机器.每个工件有它的到达时间和加工时间;对于每个工件来说要么被拒绝要么被接受安排在机器的某一个批次里进行加工;一个工件如果被拒绝,则需支付该工件对应的拒绝费用.为了保证一定的服务水平,要求拒绝工件的总个数不超过给定值.目标是如何安排被接受工件的加工批次和加工次序使得其最大完工时间与被拒绝工件的总拒绝费用之和最小.该问题是NP-难的,对此给出了伪多项式时间动态规划精确算法,2-近似算法和完全多项式时间近似方案.     

机器具有学习效应的供应链排序问题

研究了机器具有学习效应的供应链排序问题.有多个客户分布在不同位置,每个客户都有一定数量的工件需要在一台机器上进行加工.每个客户的工件在机器上加工时具有学习效应,即后面加工的工件实际加工时间是逐渐缩短的.工件生产完后需要运输到相应的客户处,每一批配送需要花费一定的时间和费用.这里研究了供应链排序理论中主要的四个目标函数,分析了这些问题的复杂性,对于一些情况给出了它们的最优算法.     

关于平行机排序问题的两点注记

本文考虑了有完工约束的平行机排序问题,证明了问题 pm|T|∑c_i是 NP-完全的,而对问题 pm|T,[_i≡p|∑w_ic_i 提出 O(n~2)的算法,并证明其最优性.将 n 个互相独立的工件(工件集 N={1,2,…,n))放在 m 台等速率平行机(机器M={M_i,…,M_m})上加工.已知每个工件必须且仅须在一台机器上加工一次,并且加工时不允许中断.工件 i(i∈N)在不同机器上加工时间不变,设为 p_i,罚权 w_i 也与机器无关,p_i 和 w_i 皆为非负实数.我们将多台机器加工工件的一个安排称为一个时间表.当时间表π确定后,记工件 i 的完工时间为 c_i(π     

两台恒速机上的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)。     

具有不可用区间且工件可拒绝下的单机重新排序问题的近似方案

本文考虑了机器具有不可用区间且工件可拒绝下的单机重新排序问题,在该问题中,给定一个工件集需在一台机器上加工,每个工件有自己的加工时间和权重,且对该工件集目标函数为极小化总加权完工时间的排序计划已给定,根据该排序计划中每个工件的完工时间已确定每个工件的承诺交付时间。然而,在工件正式开始加工前,原计划用于加工的某段时间区间因临时用于检修机器而导致机器在该时间区间不再可用,需要对工件重新排序。为了确保在新的重新排序中,工件的延误成本不致太大,决策者可以选择拒绝部分工件,但需支付相应的拒绝费用。任务是确定接受工件集和拒绝工件集,并将接受的工件在考虑机器具有不可用区间的条件下重新排序使得接受工件集的总加权完工时间,总拒绝费用及赋权最大延误之和最小。该问题是NP-困难的,对此给出了伪多项式时间动态规划精确算法,利用稀疏技术设计了完全多项式时间近似方案。     

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

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

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

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

同时最小化最大费用和最大完工时间的双代理无界平行分批排序

有两个代理A和B, 每个代理都各自有一个工件集. 同一个代理的工件可以在同一批中加工, 而且每一个代理都有一个需要最小化的函数. 研究在无界平行分批处理机上同时最小化代理A的最大费用和代理B的最大完工时间问题, 并给出一个算法, 它可在多项式时间内找到关于这个问题的所有Pareto最优点.     

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

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