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