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

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

0-1 Knapsack Variant with Time Scheduling

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 w_i and continuous storage time length t_i,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.