单台机器E-T随机排序问题的多项式算法
단태궤기E-T수궤배서문제적다항식산법
A Polynomial Algorithm for Stochastic Scheduling Problem on Single Machine with Earliness and Tardiness Penalties
  • 万方数据
    运筹与管理 운주여관리
    OPERATIONS RESEARCH AND MANAGEMENT SCIENCE
    2008年 5期 64-68 ,共5页

    顾满占%鲁习文

    고만점%로습문

    随机排序%贪婪算法%E-T问题%多项式算法 隨機排序%貪婪算法%E-T問題%多項式算法
    수궤배서%탐람산법%E-T문제%다항식산법
    本文研究排序问题中的E-T问题,工件在单台机器上加工,n个工件的加工时间都为整数p,相同的工期d为离散分布,满足∑i=1P(d=ξ)=1,其中ξ为整数,目标是使E(∑(Ej+Tj))的期望值最小.应用贪婪算法和二分法思想,我们提出解决该问题的一个最优算法,并得出该算法的复杂性为O(nmlogp).
    본문연구배서문제중적E-T문제,공건재단태궤기상가공,n개공건적가공시간도위정수p,상동적공기d위리산분포,만족∑i=1P(d=ξ)=1,기중ξ위정수,목표시사E(∑(Ej+Tj))적기망치최소.응용탐람산법화이분법사상,아문제출해결해문제적일개최우산법,병득출해산법적복잡성위O(nmlogp).
    원문보기 원문다운로드 사이트로이동
저자의 최근 논문