带准备时间的同类机半在线问题的近似算法  

Algorithms for Semi On-line Scheduling Problems with Set-up Time

作　　者：武光华[1] 苑丽华[1] 

机构地区：[1]曲阜师范大学运筹与管理学院,山东日照276826

出　　处：《菏泽学院学报》2009年第5期1-4,共4页Journal of Heze University

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

摘　　要：研究了带机器准备时间的两台同类机已知工件最大加工时间的半在线排序问题,讨论了极小化最大工件完工时间这个目标函数,并给出了一个竞争比为分段函数的近似算法.In this paper, we discuss a semi on -line scheduling problem on two uniform machines where the largest processing time is known in advance, to minimize the maximum job completion time. Algorithms with corresponding competitive ratio are presented for the considered problem.

关 键 词：同类机 半在线 竞争比 机器准备时间 

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