I don't fully understand the requirement here, but assuming you tweak your sketch to incorporate checking millis against an array of unsigned longs for remembering when each relay was turned on, does it matter that having turned the relays off, they may well be immediately turned back on if the threshold is still exceeded?
In other words, why worry about the 30 seconds at all - turn the relay on when the threshold is exceeded and off when it isn't. A second threshold would let you add some hysterisis to avoid continuous cycling of the relay around the threshold value.