Researches Of Packing Problem With Time Dimension

In recent years, with the development of science and technology, there is increasing awareness that time is efficiency and time is the lifeline. Thus, in the large-scale food and lathe processing, how to rationally arrange the processing sequence so that the total processing time is minimal becomes the subject of constant attention.In the above-mentioned process, if the processing time, the property, is removed, it is a Packing problem. So, the above-mentioned problem can be regarded as a Packing problem with time dimension. This problem is regarded as the Baking problem, since its solving process is very similar to the course of meat baking.Since Packing problem, which is NP-hard, could be regarded as one subproblem of the Baking problem, our Baking problem is NP-hard too. That is, there never exists the optimal algorithm with polynomial time for Baking problem. Therefore we turn to the near optimal algorithms, which contain heuristic algorithms and approximation algorithm. These two kinds of algorithms have their advantages and disadvantages. The former algorithm is designed to be simple but ineffective; latter algorithm is designed to be difficult but with a better and stabler results.When the baking sequence is ordered, the greedy algorithm is proven to be optimal for baking problem by introducing the concept of the working scheme; while it's NP-hard for baking problem when the baking sequence is out of order. Therefore, for one-dim Baking problem, some heuristic algorithms are given, together with an approximation algorithm under the worst situation and four strategies based on shelf idea. Under multi-dimensional situation, unfortunately, the effects of corresponding heuristic algorithms are relatively poor. At this point, its equivalent form—Strip Packing problem is used to solve the Baking problem and thus some nicer strategies, especially the gravity disappearing strategy and horizontal shifting strategy, are developed during a series of analysis. Finally, selecting address strategy and segmentation strategy are proposed for Baking problem with many ovens, and it works well.