摘要：研究了單機(jī)上工件具有簡(jiǎn)單線(xiàn)性退化效應(yīng)的隨機(jī)在線(xiàn)調(diào)度問(wèn)題.工件以時(shí)間在線(xiàn)的方式到達(dá)，決策者對(duì)將來(lái)到達(dá)工件的信息一無(wú)所知，當(dāng)工件到達(dá)之后，決策者立刻知道工件加工時(shí)間的期望，且工件加工時(shí)間的期望是開(kāi)工時(shí)間的簡(jiǎn)單線(xiàn)性函數(shù)，直到工件完工才能知道工件的實(shí)際加工時(shí)間.目標(biāo)函數(shù)是最小化工件總完工時(shí)間和的期望.對(duì)于這個(gè)隨機(jī)在線(xiàn)調(diào)度問(wèn)題，通過(guò)改變工件的釋放時(shí)間給出了競(jìng)爭(zhēng)比為1+b max的SHIFT-SDR在線(xiàn)算法.這與LIU M等人所研究的確定性情形的下界相匹配，因此可以證明，對(duì)所研究的問(wèn)題給出的在線(xiàn)算法是最好可能的在線(xiàn)算法.