Optimal search of distributed arrival time control

Distributed arrival time control (DATC) is a heuristic feedback control algorithm for scheduling which has been developed for a real-time distributed scheduling of heterarchical systems. It has been renowned not only for its fast solution searching algorithm but also for its flexibility to changing environment. However, the optimality of this heuristic method has not been analytically explained until recently because it has been designed to discover a near optimal solution instead of the true optimum. In this paper, we provide a novel optimal search method for the DATC scheduling problem by introducing a scalar cost function over the vector space of time and show the existence and location of true optima for the DATC scheduling problem through geometric approach. This geometrical interpretation enables us to find the true optimal by direct projection without iterations like previous DATC approaches. Based on the true optimum found, we evaluate the optimality of DATC algorithms by examining their dependency on initial conditions and explain their intrinsic causality mechanism for the discrepancy with true optimum. The implication of this study is on the new viewpoint over the vector space of DATC, which not only solves the optimality issue of DATC but also provides a new direction of direct search approach like projection method for the true optimum.