Optimal scheduling for active cell balancing

Active cell balancing is performed to minimize the variation in the charge levels of the individual cells in a high-power battery pack, to improve its usable capacity. The process of charge equalization is carried out by scheduling pairs of cells to transfer charge over a hardware circuit. Improving the time for charge equalization has been studied in the power electronics and the electronic design automation domains. However, these approaches have focused on the electronics issues and used heuristics to determine the charge transfer schedule. Hence, no optimality results on charge equalization times are known. We, for the first time, take a real-time systems approach and propose an optimal scheduling framework for active cell balancing. The proposed framework employs a hybrid optimization technique consisting of two sequential stages. In the first stage, we solve a mixed-integer linear programming problem to identify the time-optimal set of charge transfers required to achieve charge equalization. In the second stage, we construct a conflict graph based on the obtained charge transfers, to which we apply the minimum vertex coloring algorithm to synthesize the minimum length schedule. Results show that our proposed framework can reduce the charge equalization time by more than 50% (e.g., from 11 h to 5h). Hence, this has real benefits, e.g., in the context of charging electric vehicles. While task and message scheduling problems have been extensively studied in the real-time systems literature, the scheduling problem we study here, has not been addressed before.