Assuming that there is nothing wrong with the logic of the circuit (I have not checked it), my first reaction is that these design flaws will cause your problems:
1 There are no decoupling capacitors on the supply lines.
Put a 0.1uF capacitor between pins 7 ans 14 of the 74 series chips, and between pins 1 and 8 of the 555.
Put a 100uF capacitor between the +ve and -ve supply lines.
2 There are no back-emf suppression diodes on the relay coils.
Put a 1N4148 diode across each coil, anode of diode connects to the -ve supply line.
JimB