Although the clock skew can be exploited as a manageable resource in the design of digital systems, it is very difficult to implement a wide spectrum of dedicated clock delays. The architecture of multiple clocking domains, which restricts the clock arrival time of each register to specified clocking domains, has attracted a lot of attentions recently. However, given a target clock period and an objective function, previous multidomain clock skew scheduling approach requires very high computational expense to obtain the corresponding optimal multi-domain clock skew schedule. In this paper, we present a general methodology, which is independent of the objective function, to speed up the process of multi-domain clock skew scheduling. Our contribution includes the following two aspects. First, we propose an approach to deriving the ASAP (as-soon-aspossible) schedule and the ALAP (as-late-as-possible) schedule of each register. Due to pruning the redundancies, the problem size can be considerably reduced without sacrificing the exactness (optimality) of the solution. Second, we propose a zone-based scheduling algorithm to solve a large circuit heuristically, in which a zone is part of registers extracted from the large circuit. Experimental data consistently show that the zone-based scheduling algorithm is a very good heuristic.