A great deal of attention has been paid to design and optimization of low-temperature liquefaction and gas separation problems over the past years, due to their difficult nature.In this paper, two approaches featuring sequential and simultaneous methods for selection and arrangement of sub-ambient separation systems and their associated refrigeration cycles are compared. The effect of ignoring heat integration within the separation system and between the separation and refrigeration systems is addressed as well as fixing the sequence order of separation. The optimization is carried out using two famous stochastic search methods i.e. Genetic Algorithm (GA) and Simulated Annealing (SA). Three case studies are examined to illustrate the significant differences between optimization results. Also, the design optimality is re-checked with respect to usage of different refrigerants and the resulting structure is verified by application of a comprehensive exergy analysis.