A multi-objective optimization model is proposed for power system reconstruction. Objective functions of the model are generating units' starting-up sequence， system-partitioning strategy and time requirements for system reconstruction. Fast and elitist non-dominated sorting genetic algorithm（NSGA-Ⅱ） is applied in order to avoid artificially balanced solutions. Priority-based genetic encoding and decoding are designed for NSGA-Ⅱ. With non-dominated sorting and crowding-distance calculation the means of dummy fitness are used to find optimal solutions in different objectives. The system-partitioning and time requirements for unit start-up are considered in power system reconstruction algorithms. An elitist checking strategy is adopted to check Pareto-optimal solutions. Simulation results on IEEE 30-bus system show that the proposed algorithms are able to find better spread of solutions， better convergence and lower computational complexity compared to other power system reconstruction methods based on genetic algorithms. The effectiveness of the proposed algorithms is further validated by the numerical results on the power system of Shandong Province， China.