Energy integration is a matter of substantial importance in process engineering. Much attention was given in the last decades, in special, to heat recovery. However, recently, simultaneous work and heat recovery has arisen as an important area of study in process engineering. It has been demonstrated that work and heat exchange networks (WHEN) may improve the energetic efficiency of processes such as liquefied natural gas (LNG) production. Optimization-based frameworks for WHEN synthesis developed so far are based on deterministic approaches and commercial solver implementations. This work aimed to present a novel alternative framework based on a matrix-based implementation fit for the use of a meta-heuristic solution approach. The superstructure employed is inspired on previous literature and extended for a broader analysis. The method was applied to three examples, being two based on real processes. In benchmark tests, the approach was able to outperform all other solutions reported with respect to total annual cost, the objective function adopted in these studies.