Due to their significance both in theory and industrial application, zero-wait scheduling problems (ZWSPs) of batch plants have received more and more attentions. However, how to tackle large-scale ZWSPs with setup times is still a challenging problem. This paper presents a novel hybrid permutation-based differential evolution (HPDE) for this purpose. More specifically, ZWSPs are formulated as asymmetrical traveling salesman problems (ATSP). To deal with ATSP model effectively, a permutation-based DE (PDE) algorithm and fast complex heuristic (FCH) local search scheme are proposed. Furthermore, HPDE, a hybrid approach of PDE and FCH local search, is proposed. The performances of HPDE are illustrated based on extensive experiments and comparisons with recently developed approaches in literature. The results demonstrate that HPDE reaches high-quality solutions in short computational time. Furthermore, it requires fewer user-defined parameters, rendering it applicable to real-life large-scale ZWSPs with setup times. (C) 2012 Elsevier Ltd. All rights reserved.