How can I decide relay on-off periods depending on the PID output
Your diagram shows on-off control, not PID. This is behaving rather like a thermostat. Your P is set to max and your I and D terms to zero.


  As you know PID output increases over time if the actual point goes above the set point. 


If your application is a heating one then your output decreases if the actual (process value) exceeds the setpoint.


  I am using relays to give input to the system. 


OK.


  Because of the thermal inertia, output increases even I turn off the relays. 


Be careful with your thinking and wording. I think you mean to say, "Because of the thermal inertia temperature continues to increase even after I turn off the relays. (If your relays have turned the output off then it's off.) This is a common problem but it can be reduced or eliminated by proper tuning.


  The main question in my mind is, how can I determine the on-off periods of relays depending on the PID output? For example, in the second on period of relay, when should I turn off the relay to avoid overshoot? 


You let the PID controller do it.



Figure 1.

Read through Eurotherm's PID control made easy twice and then try using their technique to set yours up.



Update from comments:



Figure 2.


  As shown in the red rectangle, Xosc = 8&deg;C and tosc = 225 s. So I choose P = 16, I = 337.5 and D = 67.5. In the graph, I turned on my relays when error is positive.


This is not how PID is used. You are not using the PID output correctly.

In any case, you do not seem to have followed the Eurotherm procedure correctly.



Figure 3.

Set your PID for on-off (thermostat control) as shown in the upper graph of Figure 3 and then take the measurements for xosc and tosc.


  I am thinking that I should decide when to open my relay not just looking at the error but output. 


No, the PID controller does this. The output (heating in your case) should be proportional to the PID output. When using relay control that means you have to vary the duty cycle (the amount of 'on' time) in proportion to the PID output.


  So how should I write my algorithm? 



Create a duty cycle timer, \$ t_{cycle} \$. The relays should be able to handle being switched every 10 s and your system's response time is relatively long so that should give good control.
Then calculate the on-time by \$ t_{on} = u(k) \times t_{cycle} \$ where u(k) is the percentage out of the PID loop.


For example, if the PID output is 26% and you are running a 10 s duty cycle then the relay should be on for 2.6 s out of 10 s.

Let the PID do its work directly. Stop trying to override it.