The synthesis and optimization of low-temperature gas separation processes is made complex due to the large number of design options. In this paper, a new synthesis framework is proposed for screening low-temperature heat-integrated separation systems. Task representation is applied to the separation options. Separation options include flash drums, dephlegmators, and simple and complex distillation columns. Each task has been developed with several device representations. Short-cut models of all the novel separation options are provided. Condensation for the separation system is provided by the refrigeration system or heat integration. An integration procedure with the refrigeration system is presented on the basis of shaft power targeting. A sequence-based superstructure is presented to accommodate all separation process options. In this paper, the optimization is carried out using a stochastic method (Genetic Algorithm). Various case studies are examined to illustrate the approach.