应用数学
應用數學
응용수학
MATHEMATICA APPLICATA
2010年
1期
1-6
,共6页
平行机调度%周期维护%时间表长%LPT算法
平行機調度%週期維護%時間錶長%LPT算法
평행궤조도%주기유호%시간표장%LPT산법
Parallel machine scheduling%Periodical maintenance%Makespan%LPT algorithm
本文讨论了具有周期维护的两台平行机调度问题,目标函数为最小化时间表长.设T为维护周期,t为每次对机器维护需要的时间,当t≤T/3时,本文证明了对于该问题由LPT算法得到的最坏误差界为2.
本文討論瞭具有週期維護的兩檯平行機調度問題,目標函數為最小化時間錶長.設T為維護週期,t為每次對機器維護需要的時間,噹t≤T/3時,本文證明瞭對于該問題由LPT算法得到的最壞誤差界為2.
본문토론료구유주기유호적량태평행궤조도문제,목표함수위최소화시간표장.설T위유호주기,t위매차대궤기유호수요적시간,당t≤T/3시,본문증명료대우해문제유LPT산법득도적최배오차계위2.
A two parallel machines scheduling problem where the two machines are periodically maintained with the objective of minimizing makespan is considered. It is showed that the worst-case bound of the classical LPT algorithm is 2 for the case t ≤ T/3 where t is the time to perform each maintenance activity and T is the time interval between two consecutive maintenance periods.
