The easiest way is to use the Python multiprocessing module (or similar). You can create a pool of parallel workers, each of which would run a different heuristic. The multiprocessing toolbox also allows you to pass messages between processes, which you can use to communicate information among them (e.g., solution vectors).
In order to do that you would need synchronization points inside your heuristics, i.e., "checkpoints" where each worker requests information from a manager process. If no new information is available in the message it receives, it keeps calculating as normal, and if there's new information it does stuff.
The cleanest design is to have a dedicated process as the manager, and that process will be responsible for all communication between workers. Workers should only be able to communicate with the manager, and not with each other. This design pattern is crucial for good scaling and avoiding deadlocks & bottlenecks.
Be warned though that parallel computing is hard and full of quirks and subtle edge cases, even in Python. Always implement the bare minimum of the functionality you need. Test, test, test, and if it works for you, you're done. Complexity is your greatest enemy here because debugging becomes rapidly intractable in complicated parallel code.
My advice would be to consistently test everything, even syntax that "surely" does what you think it should - in parallel it rarely does, especially in Python.
W.r.t. your second question, yes, definitely. Parallel code is very time consuming, so unless there is a clear need for it, you probably shouldn't do it. Some indicators that it might work for you are:
- There are numerous independent steps in your algorithm that take roughly the same time.
- If your tasks differ by too much in execution time you need asynchronous parallel code which is much more complicated.
- If you have one expensive chunk of calculations and everything else is cheap by comparison, you will not see benefits.
- The application actually "needs" more speed. If it doesn't you need to make a business case to your boss about why this quality of life feature is something they should be spending money on.
Finally, keep in mind that you can simply run the same Python script multiple times with different inputs as background processes, and the OS will run them in parallel if you have enough cores.