摘要
研究资源定时投放的单机排序问题,目标为极小化工件的总完工时间,首先采用多项式时间归约法证明了该问题即使在每个工件的资源需求量与加工时间成比例的情况下也是NP-难的,接着对求解该问题的SPT近似算法进行了最坏情况分析,最后证明了其最坏情况紧界为9/7.
Given a set of jobs,which need certain resource before being processed on a single machine,the goal is to minimize the total completion times under the assumption that the resource is timing released.By the polynomial time reduction method,the problem is shown to be NP-hard even when there are only two release times and the resource demand of each job is proportional to its processing time.The SPT algorithm is analyzed,which has a worst case ratio of 9/7.
出处
《杭州电子科技大学学报（自然科学版）》
2017年第2期85-88,共4页
Journal of Hangzhou Dianzi University：Natural Sciences
基金
国家自然科学基金资助项目(11571252
11401149)
关键词
资源需求
单机排序
NP-难
最坏情况界
resource demand
single machine scheduling
NP-hard
worst-case analysis
