K. Dadachanji, L. Gruenwald, and S. Moses (USA)
Temporal Index, Real Time, Discrete.
A vast literature exists on scheduling to meet due dates, yet very little work considers how to set these due dates in the first place. This paper describes a highly scalable and space-efficient indexing structure specifically designed to meet the requirements of an order promising system that calculates due dates in real-time for discrete build-to-order manufacturing environments. Calculating a tight yet achievable due date for a customer order requires estimation of the date and time that each resource required to process the order will be available, and to make a challenging problem even more difficult these estimates typically must be completed in real-time. The Temporal Bin Tree (TB Tree) described in this paper is designed to support this task. It uses a discrete-time model to store data on time-phased aggregate resource availability. To facilitate efficient search for time intervals with sufficient availability, the TB Tree represents time intervals in a tree structure. The tree forms a backbone structure that does not require rebalancing. Applications of the TB Tree are not limited to the manufacturing sector: it can be used to index any application that requires determining what time that a resource will be available to process a task. Analytical evaluation and simulation experiments are performed to compare the TB Tree with existing indexing structures. Results clearly demonstrate the efficient performance of the TB Tree in terms of both time and space requirements.
Important Links:
Go Back
