摘要：研究了單機上工件具有簡單線性退化效應的隨機在線調度問題.工件以時間在線的方式到達，決策者對將來到達工件的信息一無所知，當工件到達之后，決策者立刻知道工件加工時間的期望，且工件加工時間的期望是開工時間的簡單線性函數，直到工件完工才能知道工件的實際加工時間.目標函數是最小化工件總完工時間和的期望.對于這個隨機在線調度問題，通過改變工件的釋放時間給出了競爭比為1+b max的SHIFT-SDR在線算法.這與LIU M等人所研究的確定性情形的下界相匹配，因此可以證明，對所研究的問題給出的在線算法是最好可能的在線算法.