具有周期维护最小化时间表长的两台平行机调度问题(英文)  

Two Parallel Machines Scheduling with Periodic Maintenance to Minimize Makespan

作　　者：程贞敏[1] 张喜娟[1] 李洪兴[2] 

机构地区：[1]北京联合大学商务学院,北京100025 [2]大连理工大学电子与信息工程学院,辽宁大连116024

出　　处：《应用数学》2010年第1期1-6,共6页Mathematica Applicata

基　　金：Supported by the National 863 High-Tech Program of China(2006AA04Z163);National Natural Science Foundation of China(60774049)

摘　　要：本文讨论了具有周期维护的两台平行机调度问题,目标函数为最小化时间表长.设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.

关 键 词：平行机调度 周期维护 时间表长 LPT算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]