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

doi:10.11896/j.issn.1002-137X.2018.04.007

摘要/Abstract

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

关键词: 背包调度,动态规划,分枝限界,遗传算法

Abstract: 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.

Key words: Knapsack scheduling,Dynamic programming,Branch and bound,Genetic algorithm

王正理,谢添,何琨,金燕. 考虑时间因素的0-1背包调度问题[J]. 计算机科学, 2018, 45(4): 53-59. https://doi.org/10.11896/j.issn.1002-137X.2018.04.007

WANG Zheng-li, XIE Tian, HE Kun and JIN Yan. 0-1 Knapsack Variant with Time Scheduling[J]. Computer Science, 2018, 45(4): 53-59. https://doi.org/10.11896/j.issn.1002-137X.2018.04.007

参考文献

[1] STEINBERG A.A Strip-Packing Algorithm with Absolute Performance Bound 2[J].SIAM Journal on Computing,1997,26(2):401-409.
[2] ZHU P,HE K,CAO W G,et al.A Caving-degree based Greedy Scheduling Algorithm for the Three-dimensional Space-Time Optimization Problem[J].Journal of Frontiers of Computer Science & Technology,2016,10(8):1051-1062.(in Chinese) 朱鹏,何琨,曹伟刚,等.基于穴度的三维时空优化问题的贪心调度算法[J].计算机科学与探索,2016,10(8):1051-1062.
[3] HUANG W Q,HE K.On the Weak Computability of a Four-dimensional Orthogonal Packing and Time Scheduling Problem[J].Theoretical Computer Science,2013,501(3):1-10.
[4] HUANG W Q,HE K.An Optimal Time Scheduling Problem on Cuboids Packing over Four-Dimensional Space-Time and Its Computability Proof[J].Chinese Journal of Computers,2013,36(9):1880-1888.(in Chinese) 黄文奇,何琨.四维时空高效利用的装箱调度问题及其可计算性证明[J].计算机学报,2013,36(9):1880-1888.
[5] HUANG W Q,HE K.Optimal Time Scheduling of Three-Dimensional Space Packing[J].Journal of Huazhong University of Science and Technology(Natural Science Edition),2010,38(12):102-104.(in Chinese) 黄文奇,何琨.三维装箱工作的优化调度问题[J].华中科技大学学报(自然科学版),2010,38(12):102-104.
[6] MERKLE R C,HELLMAN M E.Hiding Information and Signatures in Trapdoor Knapsacks[J].IEEE Transactions on Information Theory,1978,24(5):525-530.
[7] CONNOLLY D.Knapsack Problems:Algorithms and Computer Implementations[J].Journal of the Operational Research Society,1991,42(6):513-513.
[8] HU J S,CHEN G L,GUO G C.Solving the 0/1 Knapsack Problem on Quantum Computer[J].Chinese Journal of Computers, 1999,2(12):1314-1316.
[9] CORMEN T H,LEISERSON C E.Introduction to Algorithm[M].Beijing:China Machine Press,2013.
[10] IBARRA O H,KIM C E.Fast Approximation Algorithms forthe Knapsack and Sum of Subset Problems[J].Journal of the Acm,1975,22(4):463-468.
[11] DU D Z,KERI K O,HU X D.Design and Analysis of Approximation Algorithms[M].New York:Springer ,2012.
[12] YANG Z X,YONG Z Z,YU M,et al.Improved Genetic Algorithm for Solving Knapsack Problem[J].Journal of Shenzhen University(Science & Engineering),2006,23(2):128-132.(in Chinese) 杨泽星,雍正正,俞敏,等.解决背包问题的改进遗传算法[J].深圳大学学报(理工版),2006,23(2):128-132.
[13] DAREHMIRAKI M,NEHI H M.Molecular Solution to the 0-1 Knapsack Problem Based on DNA Computing[J].Applied Mathematics & Computation,2007,187(2):1033-1037.
[14] MA L,WANG L D.Ant Colony Optimization Algorithm forKnapsack Problem[J].Journal of Computer Applications,2001,21(8):4-5.(in Chinese) 马良,王龙德.背包问题的蚂蚁优化算法[J].计算机应用,2001,21(8):4-5.
[15] IMAHORI S,YAGIURA M,IBARAKI T.Local Search Algo-rithms for the Rectangle Packing Problem with General Spatial Costs.Math Program[J].Mathematical Programming,2004,167(1):48-67.
[16] GEHRING H,BORTFELDT A.A Parallel Genetic Algorithm for Solving the Container Loading Problem[J].International Transactions in Operational Research,2002,9(9):497-511.
[17] LEUNG T W,YUNG C H,TROUTT M D.Applications of Genetic Search and Simulated Annealing to the Two-Dimensional Non-guillotine Cutting Stock Problem[J].Computers & Industrial Engineering,2001,40(3):201-214.
[18] CHAN H H,MARKOV I L.Practical Slicing and Non-slicingBlock-packing without Simulated Annealing[C]∥Proceedings of the 14th ACM Great Lakes symposium on VLSI.ACM,2004:282-287.
[19] CHEN M,HUANG W.A Two-level Search Algorithm for 2D Rectangular Packing Problem[J].Computers & Industrial Engineering,2007,53(1):123-136.
[20] BAKER B S,COFFMAN E G,RIVEST R L.Orthogonal Pac-kings in Two Dimensions[J].Siam Journal on Computing,1980,9(4):846-855.
[21] CHAZELLE B.The Bottomn-Left Bin-Packing Heuristic:AnEfficient Implementation[J].IEEE Transactions on Compu-ters,1983,C-32(8):697-707.
[22] HOPPER E.Two-Dimensional Packing Utilising EvolutionaryAlgorithms and Other MetaHeuristic Methods[D].Wales:University of Wales Cardiff,2000.
[23] ZHANG D,LIU Y,CHEN S,et al.A Meta-heuristic Algorithm for the Strip Rectangular Packing Problem[J].Lecture Notes in Computer Science,2005,3612(8):437-437.
[24] HOLLAND J H.Adaptation in Natural and Artificial Systems[M].Massachusetts:MIT Press,1992.
[25] HOPPER E,TURTON B C H.An Empirical Investigation of Meta-heuristic and Heuristic Algorithms for a 2D Packing Problem[J].European Journal of Operational Research,2001,128(1):34-57.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed