Assuming it is a DC injection brake (as most stand-alone brakes are) it is wired in paralell with the motor starter, and interlocked so that the 2 are never enegized at the same time. The DCB injects DC onto 2 windings of the AC motor, setting up a stationary magnetic field in the stator. That in turn creates a counter rotating magnetic field in the rotor and produces torque in the opposite rotation as the rotor, which brings the load to a stop.
The strength of that field is directly proportional to the energy applied to it, so the braking power is no different than running / starting power as far as the thermal effect on the motor. In other words at a minimum, each brake cycle needs to be counted as a start cycle, and the overload relay needs to be in the circuit at all times to protect your motor. The fact that it is tripping would indicate that your duty cycle is stressful on your motor. It is tripping because it is trying to prevent a fire!
As I see it you have 3 choices.
1) Lower the brake energy (torque, voltage, current, whatever your DCB has for a setting). This will of course mean that your stopping time will be longer.
2) If this is unacceptable, you will beed to change to a larger motor. To avoid adding starting torque problems you may also consider using a Soft Starter. Many of them come with DCB options as well.
3) Remove the starter and brake and install a VFD with a Dynamic Brake package. It works differently, by converting the mechanical energy of your spinning load back into electricity, and dumping it off into a resistor bank as heat. They tend to work faster than a DCB, but cost more. If price is no object you can go with a Regenerative Brake system, which puts the energy back into the utility grid.
Quando Omni Flunkus Moritati