运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2011年
3期
62-69
,共8页
排序%流水作业%使用限制%近似算法%竞争比
排序%流水作業%使用限製%近似算法%競爭比
배서%류수작업%사용한제%근사산법%경쟁비
研究有使用限制的二台机器流水作业排序问题,目标为最小化最大完工时间,工件加工可以被机器的不可用时间段中断.讨论两台机器上均有使用限制离线问题的可近似情形,并给出性能比为3/2的近似算法.同时还考虑在第二台机器上存在一个不可用时间段情况下的半在线问题,给出一个竞争比为3/2的半在线算法.
研究有使用限製的二檯機器流水作業排序問題,目標為最小化最大完工時間,工件加工可以被機器的不可用時間段中斷.討論兩檯機器上均有使用限製離線問題的可近似情形,併給齣性能比為3/2的近似算法.同時還攷慮在第二檯機器上存在一箇不可用時間段情況下的半在線問題,給齣一箇競爭比為3/2的半在線算法.
연구유사용한제적이태궤기류수작업배서문제,목표위최소화최대완공시간,공건가공가이피궤기적불가용시간단중단.토론량태궤기상균유사용한제리선문제적가근사정형,병급출성능비위3/2적근사산법.동시환고필재제이태궤기상존재일개불가용시간단정황하적반재선문제,급출일개경쟁비위3/2적반재선산법.
