Abstract: With the rapid development of smart grid, information and new energy technology, the concept of energy Internet has gained great research attention most recently, and the trend of flexible and secure coordination between “generation-grid-load-energy storage” has become a really hot and interesting topic. From smart grid to energy Internet, the self-healing system of power grid is always a safety-critical real-time system. When fault happens, great amount of correlated and deadline-constrained operations need to be executed timely so as to the recovery of the system. Based on the multi-agent architecture of the self-healing system of power grid towards energy Internet, a multi-agent real-time multi-criticality scheduling task model and scheduling approach are proposed in this paper. Fault chain and secure tree with deadline constraints are added into the self-healing process in the power grid in order to protect the system from unpredicted sequences of fault dealing operations，resulting in less successive fault occurrence with security assurance. The experimental results show that our proposed method can effectively increase the success ratio of self-healing tasks by average 17.74% and lower the successive fault occurrence ratio by average 7.72%, which is promising to be applied in the self-healing system of power grid for security concern.