Heating rods control using PWM
i gather from your description of 'hardware' that you are driving a relay to operate the heating rod.

You state that "replacement of hardware is out of option.", but you may be able to "fit" a Solid State Relay into your current design.

You will be better served to use a solid state relay (SSR) instead of a mechanical relay. The SSR can be cycled over and over without damaging it and would be ideally suited for your purpose (if I correctly understand your current method.)

PWM or (pulse width modulation) is a percentage of 'ON' and 'OFF' where an ON percentage of 100 and an OFF time of 0 would mean the relay is simply ON all the time.

Then as our temperature approaches your 'set point' you can change the percentage of ON time down so that the relay is supplying power less and less of the time. Until you reach your temperature and the ON time is 0% while the OFF time is 100%. 

I have used this same method to control the heater of a photographic developer of many years ago.

Depending on the voltage and current your heating rod requires there are SSR options from "3-32V DC to 24-480V AC 40A Output Single Phase SSR Solid State Relay" to small less than $1.00 options.

A bit of researching solid state relays will show you many, many options...