Time-hierarchical scheduling A worst case analysis of a hierarchical approach integrating planning and scheduling in an online problem

摘要

In this paper, the general time hierarchical planning and scheduling approach is introduced, which integrates both detailed scheduling and due date assignment for an online problem. In this approach, time is divided into intervals of increasing size, and the different sizes form a hierarchy. We show that for a simplified model, a multiple level bin packing approach is an approximation algorithm, and we further prove that under weak assumptions, the approximation quality is bounded independently of the depth of the hierarchy.