In this paper, by combining a stochastic optimization method with a refrigeration shaft work targeting method, an approach for the synthesis of a heat integrated complex distillation system in a low-temperature process is presented. The synthesis problem is formulated as a mixed-integer nonlinear programming (MINLP) problem, which is solved by simulated annealing algorithm under a random procedure to explore the optimal operating parameters and the distillation sequence structure. The shaft work targeting method is used to evaluate the minimum energy cost of the corresponding separation system during the optimization without any need for a detailed design for the heat exchanger network (HEN) and the refrigeration system (RS). The method presented in the paper can dramatically reduce the scale and complexity of the problem. A case study of ethylene cold-end separation is used to illustrate the application of the approach. Compared with the original industrial scheme, the result is encouraging. (C) 2015 The Chemical Industry and Engineering Society of China, and Chemical Industry Press. All rights reserved.