摘要
给定一系列作业和只能在有限的时间段可用的资源,如何预留和分配资源以实现作业的最大完成时间最小化的问题是NP难的。本文将其归结为一种新型的尺寸可变装箱问题并给出了作业信息和资源信息完全已知条件下的六种离线算法,理论分析表明所给算法的渐进最坏比为2,在作业相互独立的条件下推广的降序最佳适合(Best FitDecreasing)算法的平均性能最优,在作业有先后依赖关系的条件下推广的最佳适合(Best Fit)算法的平均性能最优。
Given a List of jobs and a resource with limited available intervals,it is a NP-hard problem to decide how to reserve and allocate available intervals of the resource to the Jobs with the goal to minimize the maximum completion time of jobs. The paper attempts to define a mathematical model for the problem in terms of a Variant of the Variable- Sized Bin Packing problem and six algorithms in the classic bin packing problem are adapted for the offline version of the VVSBP problem. Analytical results show that the competitive ratios of the adapted algorithms are of 2. Experi- mental results for average cases show the adapted First Fid(Decreasing) algorithm outperforms any others when jobs are precedence-constrained (independent).
出处
《计算机科学》
CSCD
北大核心
2005年第2期28-30,共3页
Computer Science
