Font Size: a A A

Research On Algorithm And Case For The Space-Time Optimization Scheduling Problem

Posted on:2018-12-06Degree:MasterType:Thesis
Country:ChinaCandidate:H YangFull Text:PDF
GTID:2428330569485452Subject:Computer technology
Abstract/Summary:PDF Full Text Request
Based on the research of NP-hard rectangular/cubiod packing problem,the space-time optimization scheduling problem taking time and space factors into account was presented.In Euclid space,given a rectangular container and finite rectangular items,each rectangular item needs to be continuously processed with a time length in the container,the target is to minimize the makespan of the schedule.First,for the three-dimensional space-time optimization problem,on the basis of an action space based efficient heuristic algorithm proposed by He Kun et al,we design a caving degree based scheduling algorithm.By improving the definition of caving degree,rectangular items can quickly find the optimal layout on rectangular sheet,and with an definition of the evaluation criteria,rectangular items with longer processing time will be preferentially filled.In order to test the effect of the algorithm,the case construction algorithm is designed,and on the basis of 21 classic benchmarks from two-dimensional rectangular packing problem,generate 30 guillotine cut benchmarks and 60 no guillotine cut benchmarks.Furthermore,for four dimensional space-time optimization problem,we design a cuboid binding based greedy scheduling algorithm and test benchmarks which generate on the base of benchmarks from three-dimensional packing problem.When the dimension of time is simply regarded as space,the space-time optimization scheduling problem can turn into the corresponding dimensional packing problem.In three dimension and four dimension,experimental comparisons are made between these two problems.The results illustrate the space-time optimization scheduling problem can increase the space utilization to get minimal makespan.For three-dimensional space-time optimization problem,the average makespan of the algorithm is close to the optimal makespan of theory,which proves that the algorithm can solve problem effectively.
Keywords/Search Tags:Space-time optimization, Three dimension, Four dimension, Layout, Schedule
PDF Full Text Request
Related items