Abstract Autonomous cluster operation such as cluster reconfiguration is one of the enabling technologies for fractionated spacecraft. By virtue of the multi-agent system theory, this paper presents an organizational architecture for fractionated spacecraft, which not only enables autonomous cluster operations but also facilitates its non-traditional attributes. Within this organizational architecture, a decentralized framework is proposed to solve cluster reconfiguration problems based on primal and dual decomposition, where subgradient methods are adopted to include reconfiguration cases with non-differentiable objectives. Two typical constraints are considered: final configuration constraints representing coupling variables and collision avoidance constraints representing coupling constraints, both of which are non-convex. General schemes are proposed to convexify those constraints via the linearization and convex restriction technology. Then final configuration constraints are tackled by primal decomposition, while collision avoidance constraints by dual decomposition. To the end, multi-level primal and dual decompositions are employed to solve reconfiguration problems with both coupling variables and coupling constraints. For illustration an example of in-plane cluster reconfiguration is solved and compared with the centralized approach the solution is optimal.