摘要
讨论有资源约束和有机器准备时间的平行机排序问题 ,资源约束为每个机器至多可加工 k个工件 .在极小化 m akespan的目标下给出了一个匹配算法 ,证明其最坏情况紧界是 2 - m- 1 ,并进一步给出了它的两个带参数的最坏情况界 .
A parallel machine scheduling problem with constraints is considered.An approximation algorithm with its worst|case bound is presented.
出处
《高校应用数学学报（A辑）》
CSCD
北大核心
2001年第1期114-118,共5页
Applied Mathematics A Journal of Chinese Universities(Ser.A)
基金
国家自然科学基金(19701028)
关键词
排序
近似算法
最坏情况分析
Scheduling
Approximation Algorithm
Worst-case Analysis
