Improvements in java based test framework to reduce execution time

Let me give a bit of background on the problem.

We have a java application which has MQ integration and an Integration Test pack which is also written in java.

The test pack runs all scenarios (positive and negative) by running the test cases (methods) and changing the parameters depending on the scenario. The way it does the assertions is to put a message on the input queues of the application and expects a message in the output queues of the application. The message body is checked because it differs depending on the test scenario.

There is only 1 input queue and 1 output queue in the main application. The number of test cases (methods) are about 300 and due to running all the known scenarios, the number of test cases actually executed are about 2500. Due to this, the test pack takes around 6 hours to execute fully.

Since there is only 1 queue on which the test pack asserts the output message, we have to clear the queue each time before we run the next test case. Otherwise it may lead to mixing of the output messages. For e.g. method call#2 might end up consuming output message for method call#1. Hence we can't run the test cases in parrallel too.

I want to improve this process and would be highly grateful for any suggestions to optimize the test pack. Right now I am thinking to separate out the input and output queues of the main application as per business function and thus assert on multiple queues in parallel. But this approach means I have to change the original architecture so that my Test cases run faster and this is not easy since there are already clients using this application and interacting using the 2 queues and they will have to change their applications too.

Apologies for the long post but I would love to hear inputs of so many creative people in SO community.

Thanks!