具有两个不相容工件族单位工件的有界分批在线排序问题

研究具有两个不相容工件族单位工件单机有界平行分批的在线排序问题.工件按时在线到达,目标是最小化最大完工时间.在有界平行分批排序中,容量有限制机器最多可将b个工件形成一批同时加工,每个工件及每一批的加工时间为1.不相容工件族是指来自不同工件组的工件不能放在同一批加工.对该问题提供了一个竞争比为√17+3/4的最好可能的在线算法.     

具有前瞻区间的两个工件组单机在线排序问题

研究具有前瞻区间的两个不相容工件组单位工件单机无界平行分批在线排序问题.工件按时在线到达, 目标是最小化最大完工时间. 在无界平行分批排序中, 一台容量无限制机器可将多个工件形成一批同时加工, 每一批的加工时间等于该批中最长工件的加工时间. 具有前瞻区间是指在时刻t, 在线算法能预见到时间区间(t,t+\beta]内到达的所有工件的信息.不可相容的工件组是指属于不同组的工件不能安排在同一批中加工.对该问题提供了一个竞争比为\ 1+\alpha 的最好可能的在线算法,其中\ \alpha 是方程2\alpha^{2}+(\beta +1)\alpha +\beta -2=0的一个正根, 这里0\leq \beta <1.     

工件可自由下线最小化总完工时间的有界平行分批排序

考虑工件可自由下线最小化总完工时间的有界平行分批排序问题.在该问题中,一台平行批机器可以同时处理b个工件作为一个平行批,这里b是批容量,一个批的加工时间等于分配给这个批的工件的最大加工时间.关于可自由下线工件,每一个工件的完工时间等于包含这个工件的批的开工时间与工件的加工时间的和.也就是,如果一个批■有一个开工时间S,那么包含在批■中的每一个工件乃的开工时间定义为S,而它的完工时间定义为S+p_j,这里p_j是工件J_j的加工时间.对此问题,首先研究最优排序的一些性质.然后,基于这些性质,给出一个运行时间为O(n~(b(b-1))的动态规划算法.     

工件可自由下线最小化总完工时间的平行分批排序问题

考虑工件可自由下线最小化总完工时间的有界平行分批排序问题. 在该问题中, 一台平行批机器可以同时处理 b 个工件作为一个平行批, 这里b 是批容量, 一个批的加工时间等于分配给这个批的工件的最大加工时间. 关于可自由下线工件, 每一个工件的完工时间等于包含这个工件的批的开工时间与工件的加工时间的和. 也就是, 如果一个批B 有一个开工时间S, 那么包含在批B 中的每一个工件J_j 的开工时间定义为S, 而它的完工时间定义为S+p_j, 这里p_j 是工件J_j 的加工时间. 对此问题, 首先研究最优排序的一些性质. 然后, 基于这些性质, 给出一个运行时间为O(n^{b (b-1)})的动态规划算法.     

单位工件的平行机并行分批在线排序问题的算法

本文研究一类批容量有界的并行分批、平行机在线排序问题。模型中有n个相互独立的工件J={J₁,…,J_n}要在m台批处理机上加工。批处理机每次可同时加工至多B(Bj(1≤j≤n)的到达时间为r_j,加工时间为1,工件是否会到达事先未知,而只有等到工件的到达时间才能获知它的到达。目标为最小化工件的最大完工时间。针对该排序问题,本文设计了两个竞争比均达到最好可能的在线算法。     

工件按加工长度不增序到达的最小化最大流程在线分批排序

研究单处理机工件按加工长度不增顺序到达的在线分批排序问题．工件按时在线到达,目标是最小化最大流程．流程时间是指工件的完工时间与到达时间的差值,它体现了工件在系统内的逗留时间．对于批容量有界的情形,给出了一个竞争比为1＋√5/2的最好可能的在线算法;对于批容量无界的情形,给出了一个竞争比为√2的最好可能的在线算法．     

最小化总完工时间与分批费用之和的有界分批排序问题

考虑了当每分一批均产生固定费用、批容量有界且为固定值b、加工不允许中断抢先.所有工件在零时刻到达时的单机平行分批排序问题.目标是最小化总完工时间与分批费用之和.利用动态规划方法给出了多项式时间算法,时间界为O(n~(b(b-1))).     

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

研究当不相容工件组的个数与机器数相等时,具有前瞻区间的单位工件平行机无界平行分批在线排序问题.工件按时在线到达, 目标是最小化 最大完工时间. 具有前瞻区间是指在时刻t, 在线算法能预见到时间区间(t,t+\beta) 内到达的所有工件的信息.不可相容的工件组是指属于不同组的工件不能被安排在同一批中加工. \beta\geq 1 时, 提供了一个最优的在线算法; 当0\leq \beta < 1时, 提供了一个竞争比为1+\alpha 的最好可能的在线算法, 其中\alpha是方程\alpha^{2}+(1+\beta) \alpha+\beta-1=0的一个正根.最后, 给出了当\beta =0 时稠密算法竞争比的下界,并提供了达到该下界的最好可能的稠密算法.     

单机两组工件继列分批与平行分批混合排序

研究单机两组工件继列分批与平行分批混合排序.在问题中有两组工件J^A和JA和J^B.A-工件可以在平行批中进行加工,B-工件可以在继列批中进行加工.对若干正则目标函数给出了多项式时间算法.主要结果如下:·排序问题1|s-p-batch,s(B),(∞,∞)|L_(max)在O(n_An_Bn)时间可解.·排序问题1|s-p-batch,s(B),(∞,b(B))|∑C_j在O(n_An_Bn)时间可解.·排序问题1|s-p-batch,p_j=1,s(B),(b(A),b(B))|∑w_jC_j在O(n_An_Bn)时间可解.·排序问题1|s-p-batch,s(B),(∞,b(B))|f_(max)可以在时间界为O(log(max_jf_j(M))×(nlogM+n_An_Bn))内可解.其中,M是工件完工时间的一个上界.     

带有分批费用的容量有界的单机平行分批排序问题

考虑的问题是在添加工资费用或包装费用等附加的分批费用下,如何使单机平行分批中总完工时间和分批费用之和达到最小.首先我们假定工件和批处理机都在零时刻到达,工件被成批地进行加工,一旦开始加工就不允许中断,每批的加工时间等于该批中最大的加工时间,而且假设每分一批都产生一个分批费用.然后对具有m个不同的加工时间,批容量有界且为固定值b的情形下目标函数为∑C_j与分批费用之和这一排序问题,利用动态规划的方法给出了多项式时间算法,时间界为O(b²m2m²222^m).     

具有相同批容量和相同工期的单机准时分批排序问题

研究具有相同批容量和相同工期的单机准时分批排序问题.这里相同批容量是指每批加工的工件数相同且恰为b个.准时排序要求工件在工期准时完工,提前或误工均受到惩罚.在两种分批方式下进行排序:继列分批和平行分批.目标函数为最小化加权总绝对误差和加权非准时惩罚.这里的权重不是工件自身所拥有的,而是工件所在的批一旦排在某个位置所获得的位置权重.证明了这些问题均可在O(nlogn)时间内解决.     

工件的运输和继列分批加工协作排序问题

近年来,工件的运输和加工协作排序问题在物流和供应链管理领域得到广泛关注. 讨论了先用 $\ m$ 台车辆将工件从等待区域运输到继列分批处理机处, 再进行分批加工的协作排序问题, 加工一批工件需要支付一定的费用, 目标为最小化工件的总完工时间与批的加工费用之和. 在工件的加工时间都相等的情况下, 如果工件运输方案确定, 给出了多项式时间的动态规划算法; 如果工件运输方案不确定, 证明了该问题是{\, NP}-难的, 给出了车辆返回时间 $\ t=0$ 时, 最差性能比等于 $\ 2-\frac{1}{m}$ 的近似算法.     

具有线性恶化效应的在线分批排序问题

本文研究一类具有线性恶化效应的单机在线分批排序问题,工件$J_j$的加工时间为$p_j=b_j+\alpha t$, 其中$b_j$为基本加工时间, $\alpha>0$为恶化率, $t$是开工时间. 工件的到达时间是未知的, 工件的基本加工时间只有在工件到达之后才能知道.多个工件可以作为一批被机器同时加工, 批的加工时间为该批中工件最大加工时间.本文对于目标为极小化makespan的批容量无限的单机问题给出一个在线算法$\beta H^\infty$,并证明其竞争比和问题的下界相同, 进而算法是最优的.     

工件具有任意尺寸的混合分批平行机排序问题的近似算法

本文考虑了工件具有任意尺寸且机器有容量限制的混合分批平行机排序问题。在该问题中, 一个待加工的工件集需在多台平行批处理机上进行加工。每个工件有它的加工时间和尺寸, 每台机器可以同时处理多个工件, 称为一个批, 只要这些工件尺寸之和不超过其容量; 一个批的加工时间等于该批中工件的最大加工时间和总加工时间的加权和; 目标函数是极小化最大完工时间。该问题包含一维装箱问题为其特殊情形, 为强NP-困难的。对此给出了一个$\left( {2 + 2\alpha+\alpha^{2}}\right)$-近似算法, 其中$\alpha$为给定的权重参数, 满足$0\leq\alpha\leq 1$。     

并行分批排序综述

并行分批排序起源于半导体芯片制造过程。在并行分批排序中,工件可成批加工,批加工机器最多可同时加工B个工件,批的加工时间为批中所有工件的最大工时。首先根据传统的机器环境和目标函数对并行分批排序已有成果进行分类介绍,主要为单机和平行机的机器环境,以及极小化最大完工时间、极小化总完工时间、极小化最大延迟、极小化误工工件数、极小化总延误和极小化最大延误的目标函数;然后梳理了由基本问题所衍生出来的具有新特点的16类新型并行分批排序,包括差异尺寸工件、多目标、工件加工时间或顺序存在限制、考虑费用和具有特殊机制等情况;最后展望未来的研究方向。     

加工时间离散可控的分批配送排序问题

研究了工件的加工时间是离散可控的,并且工件加工完后需要分批配送到客户的单机排序问题.一个客户在初始时刻将一批工件交给一个制造商进行加工.每个工件有多种加工模式,分配给每个工件的加工资源越多,则其加工时间越短.工件生产完后需要分批配送到客户处,每一批需要花费一定的时间和费用.研究了排序理论中主要的四个目标函数,构建了单机情况下的具体模型,分析了问题的复杂性,对具体的问题给出了它们的最优算法.     

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

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

提前预知信息的在线分批排序问题

研究工件可提前预知信息的在线分批排序问题, 工件的预知信息时间依时间到达, 目标为极小化最大完工时间. 已知从工件的信息可预知到该工件可加工需要时间~$a$, 所有工件的最大加工时间为~$p_{{\rm max}}$, 多个工件可以作为一批被机器同时加工, 批的加工时间为该批工件中最长加工时间. 对于批容量无限的单机问题给出一个在线算法~$\gamma H^\infty$, 并证明其竞争比和问题的下界都为~$1+\gamma$, 其中~$\gamma=\left(-1+\sqrt{1+\frac{4p_{{\rm max}}}{p_{{\rm max}}+a}}\right)/2$, 进而算法是最优的.     

带交货期的工件族生产与配送的排序问题

本文考虑了多个客户订购不同种类的工件,工件生产完后需要运输到客户的单机供应链排序问题.由于工件属于不同的种类,在加工不同种类工件前要有一个准备时间.每个客户分布在不同位置,客户的每个工件都有一个交货期,工件是分批配送的,每一批配送需要花费一定的时间及费用.考虑了两个与交货期有关的目标函数,分别给出了它们的最优算法.     

工件具有任意尺寸的混合分批平行机排序问题的近似算法

本文考虑了工件具有任意尺寸且机器有容量限制的混合分批平行机排序问题。在该问题中, 一个待加工的工件集需在多台平行批处理机上进行加工。每个工件有它的加工时间和尺寸, 每台机器可以同时处理多个工件, 称为一个批, 只要这些工件尺寸之和不超过其容量; 一个批的加工时间等于该批中工件的最大加工时间和总加工时间的加权和; 目标函数是极小化最大完工时间。该问题包含一维装箱问题为其特殊情形, 为强NP-困难的。对此给出了一个$\left( {2 + 2\alpha+\alpha^{2}}\right)$-近似算法, 其中$\alpha$为给定的权重参数, 满足考虑了不同于Goldfarb和Iyengar （2003）的因子模型,通过横截面回归分析以及Fama-MacBeth估计构造了关于资产的平均收益向量和协方差矩阵的不确定性集合（置信区域）。基于这些不确定性集合以及Markowitz“均值-方差模型”的鲁棒投资组合问题,提出了多个鲁棒投资组合问题,并对应的推导出其等价的半正定规划形式,使得问题可以在多项式时间内求解。