王正理,谢添,何琨,金燕.考虑时间因素的0-1背包调度问题[J].计算机科学,2018,45(4):53-59
考虑时间因素的0-1背包调度问题
0-1 Knapsack Variant with Time Scheduling
投稿时间:2017-07-02  修订日期:2017-08-12
DOI:10.11896/j.issn.1002-137X.2018.04.007
中文关键词:  背包调度,动态规划,分枝限界,遗传算法
英文关键词:Knapsack scheduling,Dynamic programming,Branch and bound,Genetic algorithm
基金项目:本文受国家自然科学基金项目(61472147,6,61173180),深圳市科技计划项目(JCYJ20170307154749425)资助
作者单位E-mail
王正理 华中科技大学计算机科学与技术学院 武汉430074
深圳华中科技大学研究院 广东 深圳518057 
 
谢添 南加州大学维特比工程学院 洛杉矶90089  
何琨 华中科技大学计算机科学与技术学院 武汉430074
深圳华中科技大学研究院 广东 深圳518057 
brooklet60@hust.edu.cn 
金燕 华中科技大学计算机科学与技术学院 武汉430074
深圳华中科技大学研究院 广东 深圳518057 
 
摘要点击次数: 318
全文下载次数: 217
中文摘要:
      文中提出考虑时间因素的0-1背包调度问题这一具有NP难度的组合优化问题。给定n个物体(每个物体i的重量为wi,连续加工时间为ti),以及一个容量为S的背包,要求给出一个调度方案(物品的放入顺序和放入时间),使得任意时刻放入背包的物品总重量不超过背包容量,每个物体需放入背包连续加工时长ti后才能取出,该问题是求使所有物体均加工完毕的时间尽可能短的调度方案。提出了3种求解算法:迭代动态规划算法、基于分枝限界的完备算法和遗传进化算法。迭代动态规划算法使用动态规划策略放置尽可能多的未加工物体到背包中,然后每次迭代取出加工完成的物品后再使用动态规划放入尽可能多的剩余未加工物品,直至所有物品被加工完成。基于分枝限界的完备算法通过定义上下界及剪枝操作,有效地降低了算法的计算复杂度。遗传进化算法将一个物品装填序列定义为个体,并定义了相应的适应度、选择、交叉与变异操作。在所设计的3组共计36个算例上的实验结果表明,迭代动态规划算法可以很快求出高质量的解,基于分枝限界的完备算法对小规模算例有很好的效果,遗传算法在处理几百个物体的算例时能在1500s内得到比动态规划算法更好的结果。
英文摘要:
      This paper proposed an NP-hard 0-1 knapsack variant problem considering the space and time issues.Given n items with each item i having weight wi and continuous storage time length ti,and a knapsack with capacity S,a scheduling is asked to provide for the packing time of each item(the removing time can be deduced accordingly).At any time instant,the total weights of the packed items should not exceed the capacity of the knapsack.This paper proposed three algorithms to address this problem:a quick dynamic programming(DP) algorithm,a branch and bound(BnB) based exact algorithm and a genetic algorithm.The dynamic programming(DP) algorithm first regards all items as raw items,and uses DP to pack as much raw items as possible into the knapsack.Whenever there is an item that becomes mature,i.e.,it has been stored enough time in the knapsack,the mature item is removed from the knapsack,and for the remaining Knapsack capacity,DP is used again to pack as much raw items as possible.The above process continues until all items are mature and removed from the knapsack,completing the DP scheduling.The BnB based exact algorithm defines the lower bound and upper bound,and cuts the unnecessary branches to shorten the running time.The genetic algorithm defines each individual as a packing order,and defines the corresponding fitness value,selection,mutation and crossover operators.Experiments on three sets with a total of 36 designed benchmark instances show that DP can quickly produce high quality schedules,BnB based exact algorithm works well for small instances,the genetic algorithm can deal with hundreds of items within 1500 seconds and it outputs schedules with considerably shorter makespan when compared with DP.
查看全文  查看/发表评论  下载PDF阅读器