文献类型：期刊文献

中文题名：机器使用有限制的两台同类机排序

英文题名：Two Uniform Machines Scheduling with an Availability Constraint

作者：李红英[1];苏纯洁[1]

机构：[1]华东理工大学数学系,上海200237

年份：2005

卷号：31

期号：4

起止页码：512

中文期刊名：华东理工大学学报（自然科学版）

外文期刊名：Journal of East China University of Science and Technology

收录：CSTPCD;;EI(收录号：2005389375492);Scopus;北大核心:【北大核心2004】；CSCD:【CSCD2011_2012】；

语种：中文

中文关键词：同类机;使用限制;算法;性能比

外文关键词：uniform machine; availability constraint; algorithm; worst-case ratio

摘要：研究两台同类机的排序问题,其中一台机器在一个给定的时间段内不可用,目标函数为工件的最大完工时间。证明了LPT算法的性能比是max{32,1s2},并说明了这个界是紧的。
In this paper the two uniform machines scheduling problem is studied,in which one machine has an availability constraint and the objective function is makespan. The worst-case ratio of LPT algorithm is proved to be max{3/2,1/s2 }, and the ratio is tight.