Computer Science ›› 2018, Vol. 45 ›› Issue (4): 53-59.doi: 10.11896/j.issn.1002-137X.2018.04.007

Previous Articles     Next Articles

0-1 Knapsack Variant with Time Scheduling

WANG Zheng-li, XIE Tian, HE Kun and JIN Yan   

  • Online:2018-04-15 Published:2018-05-11

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

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

[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.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] . [J]. Computer Science, 2018, 1(1): 1 .
[2] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[3] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[4] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[5] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[6] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[7] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[8] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[9] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[10] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .