机器使用有限制的两台同类机排序

李红英, 苏纯洁. 机器使用有限制的两台同类机排序[J]. 华东理工大学学报（自然科学版）, 2005, (4): 512-516.

引用本文:

李红英, 苏纯洁. 机器使用有限制的两台同类机排序[J]. 华东理工大学学报（自然科学版）, 2005, (4): 512-516.

Two Uniform Machines Scheduling with an Availability Constraint[J]. Journal of East China University of Science and Technology, 2005, (4): 512-516.

Citation:

Two Uniform Machines Scheduling with an Availability Constraint[J]. Journal of East China University of Science and Technology, 2005, (4): 512-516.

Two Uniform Machines Scheduling with an Availability Constraint

摘要: 研究两台同类机的排序问题,其中一台机器在一个给定的时间段内不可用,目标函数为工件的最大完工时间。证明了LPT算法的性能比是max32,1s2,并说明了这个界是紧的。

Abstract: 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 max32,1s_2, and the ratio is tight.

/