两个带机器准备时间的半在线排序  

An Analysis of the Two Algorithms of Semi On-line Scheduling with Machine Available Time

作　　者：邵晶晶[1] 

机构地区：[1]云南大学滇池学院理工学院,云南昆明650228

出　　处：《广西科技师范学院学报》2017年第6期128-131,121,共5页Journal of Guangxi Science & Technology Normal University

基　　金：模糊实例的空间并置换式挖掘算法及可视化研究(2016ZZX304)

摘　　要：研究两个带机器准备时间的半在线排序算法,一个是当总加工时间已知时,工件在有准备时间的同类机上加工的半在线排序,证明了其竞争比的上下界分别为2ν和ν+1/2ν+1,都与机器加工速度有关;另一个是当最大加工时间已知时,工件在有准备时间的同型机上加工的半在线排序,证明了其竞争比为2/3.The paper is to study two algorithms of semi on-line scheduling with machine available time. In the first case, when the total processing time is known, the semi on-line scheduling on the uniform machines with machine available time proves that the upper and lower bounds of competitive ratio is 2v andν + 1/2ν + 1 respectively, both of which are related to the speed; in the second case, when the largest processing time is known, the semi on-line scheduling on the uniform machines with machine available time proves that the competitive ratio is 2/3.

关 键 词：机器准备时间 排序 半在线算法 竞争比 

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