Analysis and algorithms for scheduling with minimal switching activities

Zili Shao, Qingfeng Zhuge, Edwin H M Sha, Chantana Chantrapornchai

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review


Switching activities are one of the important factors in power minimization. This paper studies the scheduling problem which minimizes switching activities. We show that to find the schedule which minimizes switching activities only or minimizes latency and switching activities with or without resource constraints is NP-complete. Two heuristic scheduling algorithms to minimize switching activities are presented. The algorithms use the weighted bipartite matching to find a good schedule. The experimental results show that our algorithms can produce the near-optimal schedule which uses averagely the switching activities 35% less compared to the traditional list scheduling.
Original languageEnglish
Title of host publicationMidwest Symposium on Circuits and Systems
Publication statusPublished - 1 Dec 2002
Externally publishedYes
Event2002 45th Midwest Symposium on Circuits and Systems - Tulsa, OK, United States
Duration: 4 Aug 20027 Aug 2002


Conference2002 45th Midwest Symposium on Circuits and Systems
Country/TerritoryUnited States
CityTulsa, OK

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Electronic, Optical and Magnetic Materials

Cite this