Invoice Approval using Spreadsheet has performance issues due to huge volumn of rows

For our client we are facing issues with performance as in the invoice takes more then 30 mins to approve, so because of that we reduced the rows in the spreadsheet by combining the rules for countries and cost centers. Now the issue that any changes (employee leaving the organisation) which come up in the invoice approval matrix requires huge effort as the rules are combined together and changes requires lot of analysis and changes.

Could any share if this issue is being faced by other clients specially big ones and what is the solution.