计算机工程与设计
計算機工程與設計
계산궤공정여설계
COMPUTER ENGINEERING AND DESIGN
2008年
9期
2269-2271
,共3页
箱覆盖问题%调度问题%组合优化%近似算法%最坏情况渐进性能比
箱覆蓋問題%調度問題%組閤優化%近似算法%最壞情況漸進性能比
상복개문제%조도문제%조합우화%근사산법%최배정황점진성능비
提出了如下定义的受位置约束的有色箱覆盖问题,即在有色物品的箱覆盖过程中,要求重(长)的物品置于轻(短)的物品下方.该问题是一个新的组合优化问题,来源于多处理器任务调度.给出一个求解该问题的局内近似算法KC-LIBFF算法,分析其最坏情况渐进性能比为0,并给出了相应的实验结果;进一步对求解该问题的局内算法性能比的下界进行了讨论.
提齣瞭如下定義的受位置約束的有色箱覆蓋問題,即在有色物品的箱覆蓋過程中,要求重(長)的物品置于輕(短)的物品下方.該問題是一箇新的組閤優化問題,來源于多處理器任務調度.給齣一箇求解該問題的跼內近似算法KC-LIBFF算法,分析其最壞情況漸進性能比為0,併給齣瞭相應的實驗結果;進一步對求解該問題的跼內算法性能比的下界進行瞭討論.
제출료여하정의적수위치약속적유색상복개문제,즉재유색물품적상복개과정중,요구중(장)적물품치우경(단)적물품하방.해문제시일개신적조합우화문제,래원우다처리기임무조도.급출일개구해해문제적국내근사산법KC-LIBFF산법,분석기최배정황점진성능비위0,병급출료상응적실험결과;진일보대구해해문제적국내산법성능비적하계진행료토론.