并行分批排序问题综述

并行分批排序是兴起于上世纪末的一类新型排序问题，它最初来源于半导体生产中的芯片测试过程，有重要的应用价值，在理论上也有重要的意义．因此，并行分批排序问题近年来受到了越来越广泛的关注，新的研究成果不断涌现．本文就并行分批排序问题的最新进展作了全面的介绍，指出了许多尚未解决的问题和许多新的研究方向，给出了丰富的参考文献，旨在把感兴趣的读者迅速带到此研究领域的前沿．     

带序约束的恒同机分批作业排序问题

研究一类由林诒勋教授提出的带序约束的恒同机分批作业排序问题，证明了这类排序问题均是ＮＰ—困难的，给出了其执行比为３２的一种启发式算法。     

机器带准备时间的同类机分批排序算法

讨论了两类机器带准备时间的同类机分批排序问题.对工件无到达时间及有常数个到达时间,目标函数为极小化加权总完工时间这两类问题进行研究,给出了两个最优算法,并对算法及其计算复杂性给予了分析与证明.     

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

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

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

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

并行加工系统中的一种排序算法

通过对现有单机和相同机组并行加工系统排序问题的研究，建立了一类多机非相同机组并行加工系统的排序模型，模型的优化目标是工件排序的拖期总数为极小。由于已经证明它是一个NP问题，本提出了一个针对该问题的快速、实用的启发式排序算法，并用实例说明了算法的有效性。     

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

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

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

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

有尺寸的同型机分批排序问题的近似算法

对工件有不同到达时间、不同加工时间和尺寸的同型机分批排序问题寻找近似算法.对于大工件(工件的体积严格大于机器容量的÷)的加工时间不小于小工件(工件的体积小于或等于机器容量的÷)的加工时间的特定情形,利用动态规划的方法和拆分的技巧,我们设计了近似算法并分析了其最差性能比.     

极小化加权总完工时间的分批排序问题

本文讨论了分批排序中极小化加权总完工时间的两个问题.就所有工件的加工时间都相等这一特殊情况,分别给出两个算法,并证明了算法的最优性.     

考虑常数客户批运输的单机排序问题

本文考虑工件首先在单机上加工,完工的工件由一辆容量有限的车配送到指定客户的模型,目标是最小化makespan。对于工件物理大小相同的情况,我们考虑了常数个客户的情形,并且给出了一个多项式时间的动态规划算法。对于工件物理大小不同的情况,我们讨论了一类特殊的三个客户的情形,并给出了一个2-近似算法。     

无限批量调度中最小化加权完工时间和问题的一个线性时间近似方案

本文考虑n个工件的无限批量机器调度问题．一台机器可以同时加工B≥n个工件．每个工件具有一个正权因子、一个释放时间和一个加工时间．一个批次的加工时间是该批次所包含所有工件的加工时间的最大者．在同一批次中加工的工件有相同的完工时间，即它们的共同开始时间加上该批次的加工时间．对于最小化加权完工时间和问题，本文给出了第一个多项式时间近似方案(PTAS)．对任意给定精度，该算法的运行时间为线性的．     

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

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

Scheduling UET task systems with concurrency on two parallel identical processors

Problems with unit execution time tasks and two identical parallel processors have received a great deal of attention in scheduling theory. In contrast to the conventional models, where each task requires only one processor, we consider a situation when a task may require both processors simultaneously. For problems without precedence constraints we present several polynomial time algorithms which complement recent results of Lee and Cai. We also show that the introduction of precedence constraints leads to NP-hardness results for maximum lateness and mean flow time objective functions. For the maximum lateness problem, a family of algorithms, based upon the idea of modified due dates, is considered. The worst case behaviour of these algorithms is analysed, and it is shown that the same upper bound is tight for each algorithm of this family.     

基于仿真优化的炼钢生产批调度求解方法

论文针对钢铁企业炼钢工序具有高温、高能耗、复杂工况的实际特征,从中提炼出生产批调度问题,其工件根据其实际工艺属性可分为多个簇,基于给定的工件簇,决策工件的分批和调度情况,综合考虑工件之间的切换费用,以及工件提前、拖期所导致的惩罚,使得总的生产成本期望最小化,从而降低生产成本;针对该问题,考虑工件的处理时间、工件的加工属性具有不确定性,基于仿真优化思想,建立数学模型,并基于大数定理,对模型目标函数进行近似;提出基于样本近似方法的求解框架,通过随机抽样的方法获得不同规模的样本,针对不同规模的样本,提出Filter & Fan算法对问题进行求解;最后,通过基于实际数据的计算实验验证所提算法的有效性。     

带机器准备时间的平行机ordinal排序及近似算法

本文研究带机器准备时间的m台平行机ordinal在线排序问题。讨论了在极小化最大机器完工时间和极小化最大工件完工时间两种目标下的不同下界和相应的在线近似算法。对第一个目标，我们得到了3/2的下界和最坏情况界为2-1/m的近似算法。对第二个目标，我们得到了最坏情况为m的最好近似算法。我们还对一些特殊情况进行了分析。     

平行机物流排序的近似算法

本文研究一个两阶段物流排序问题,即第一阶段工件在平行机上加工,在第二阶段这些被加工过的工件以某种运输方式分批运送到预先指定的目的地.优化的目标是使工件带权送到的时间与运输费用的总和为最小.应用动态规划及组合优化方法,分别研究“满足一致性条件”和一般情形下该问题的多项式时间近似算法,并分析算法的性能比.