A Greedy Algorithm For Solving Scheduling Problem Based On Two-dimensional Rectangular Packing

Given a large rectangular container and a number of rectangular items with timelengths for the items to be processed continuing in the container, the two-dimensionalrectangular packing based time scheduling problem asks to schedule the start time, and timeof each item in the container and its position and orientation of each time instant while it isin the container. The goal is to minimize the makespan of the whole scheduling process.Itssub problem, the two-dimensional rectangular packing problem, is an NP hard problem, andthe computational complexity is increasing exponentially on the number of rectangularitems. The scheduling problem needs to consider the layout in the container at each timeinstant, which makes it harder to be solved.First, a carving degree based algorithm is designed to solve the two-dimensionalrectangular packing problem. The distinction between the real and virtual corners isaddressed. We also design a method to find the real corners. The action space is based on atleast one real corners. A rectangular blocks, must coincides with one real corners of anaction space when it is placed into the container. By the concepts above, a baseline tobaseline algorithm to update the action space is designed, which reduces the complexity ofthe action space update process.Furthermore, by the analysis of the scheduling problem, a greedy algorithm based ontime and space is proposed. The rectangular items with the longest time length have highestpriority to be processed, so that its processing can be allocated to several earlier scheduling.If the time lengths are the same, space is taken into consideration to get the highest spaceutilization rate. This problem has a correlation with time and space, and the optimal use ofthe space could get the minimum time.As the two-dimensional rectangular packing based time scheduling problem is raised inrecent years, there is no public relevant test instance. We design several small test cases toverify the algorithm. Also, we design an algorithm to generate test instances. Experimentsshow that the proposed algorithm could solve the problem instances optimizingly andefficiently.