1. Prioritize. Have management determine which change needs to go in first and that team tests their change first. The other team must then add their changes to the new copy of the program.
2. Some applications allow use of multiple sets of transactions (ADxx transactions and programs may be test group one, AExx transactions and programs test group two, and so forth) -- if so, you can test both at the same time. Reconciliation of the changes in the two different versions of the program could be difficult, though. If this is not set up for your application already, though, you probably don't want to go through the major effort to set this up.
The usual recommendation, due to the reconciliation issue, is not to allow simultaneous testing of changes to the same program. Note that CICS will not allow access to two copies of one program on disk so there is no way to test two copies of a single program in a single region at the same time.