两台带准备时间的同类机的半在线排序  

Semi On-line Schedule on Two Uniform Machines With Machines Available Times

作　　者：柏庆国[1] 徐健腾[1] 卢文丽[2] 张玉忠[1] 

机构地区：[1]曲阜师范大学运筹与管理学院,山东日照276826 [2]淄博师范高等专科学校教育科学系,山东淄博255100

出　　处：《洛阳大学学报》2006年第4期46-48,52,共4页Journal of Luoyang University

基　　金：国家自然科学基金资助项目(项目编号:10671108);山东省自然科学基金资助项目(项目编号:Y2005A04)

摘　　要：研究了带机器准备时间的两台同类机的半在线排序问题,这里目标函数为极小化最大机器完工时间.对于所有工件总的加工时间已知的半在线情形,我们给出了一个竞争比为max{52+1,1+bb}的半在线算法,其中b为机器速度.并且算法对于对于机器加工速度b<2时的同型机情形是最好的.In this paper, we consider a semi on-line scheduling problem on two uniform machines with machine available times, where the objective is to minimize makespan of the schedule. For the case that the total processing times being known in advance, we propose a semi on-line algorithm with the competitive ratio max{（√5＋1）/2,（1＋b）/b}, and we prove that the algorithm is the best on two identical machines with machines available times when b 〈 2.

关 键 词：运筹学 半在线算法 竞争比 准备时间 

分 类 号：O224[理学—运筹学与控制论]