考虑时间因素的0-1背包调度问题

作     者：王正理 谢添 何琨 金燕 WANG Zheng-li;XIE Tian;HE Kun;JIN Yan

作者机构：华中科技大学计算机科学与技术学院武汉430074 深圳华中科技大学研究院广东深圳518057 南加州大学维特比工程学院洛杉矶90089 

出 版 物：《计算机科学》 (Computer Science)

年 卷 期：2018年第45卷第4期

页      面：53-59页

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 081202[工学-计算机软件与理论] 

基　　金：国家自然科学基金项目(61472147 61602196 61173180) 深圳市科技计划项目(JCYJ20170307154749425)资助 

主　　题：背包调度 动态规划 分枝限界 遗传算法 

摘      要：文中提出考虑时间因素的0-1背包调度问题这一具有NP难度的组合优化问题。给定n个物体(每个物体i的重量为wi,连续加工时间为ti),以及一个容量为S的背包,要求给出一个调度方案(物品的放入顺序和放入时间),使得任意时刻放入背包的物品总重量不超过背包容量,每个物体需放入背包连续加工时长ti后才能取出,该问题是求使所有物体均加工完毕的时间尽可能短的调度方案。提出了3种求解算法:迭代动态规划算法、基于分枝限界的完备算法和遗传进化算法。迭代动态规划算法使用动态规划策略放置尽可能多的未加工物体到背包中,然后每次迭代取出加工完成的物品后再使用动态规划放入尽可能多的剩余未加工物品,直至所有物品被加工完成。基于分枝限界的完备算法通过定义上下界及剪枝操作,有效地降低了算法的计算复杂度。遗传进化算法将一个物品装填序列定义为个体,并定义了相应的适应度、选择、交叉与变异操作。在所设计的3组共计36个算例上的实验结果表明,迭代动态规划算法可以很快求出高质量的解,基于分枝限界的完备算法对小规模算例有很好的效果,遗传算法在处理几百个物体的算例时能在1500s内得到比动态规划算法更好的结果。