## 4 Solution Procedure
### Sub-Gradiant Method
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline \# & \(i\) & \(j\) & \(t\) & \(l\) & \(\beta_{i}\) & \(p\) \\ \hline
1–4 & 10 & 100 & 2,3 & 3,4 & (80,100) & 3 \\
5–8 & 30 & 300 & 2,3 & 3,4 & (150,180) & 12 \\
9–12 & 50 & 500 & 3,4 & 3,4 & (200,300) & 20 \\
13–16 & 70 & 700 & 3,4 & 3,4 & (250,350) & 25 \\
17–20 & 100 & 1000 & 3,4 & 3,4 & (300,400) & 35 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Parameter values for the test instances. Two optimality gaps for the obtained upper bounds and lower bounds are calculated. For the problem sizes that the optimal value is available, the upper bound optimality gap and lower bound optimality gap are reported under columns \"UO-gap\" and \"LO-gap\", respectively and calculated as

\[upper\ bound\ optimality\ gap\ =\frac{(Upper\ bound-Optimal\ value)}{Optimal\ value}\]

\[lower\ bound\ optimality\ gap\ =\frac{(Optimal\ value-Lower\ bound)}{Lower\ bound}\]

#### 5.2.1 Effectiveness of the Heuristic Method

To evaluate the efficiency of the proposed heuristic method procedure for the test examples that the optimal value is available, the optimality gap is calculated and reported in Table 6. The computational time for all test problems solved with



As shown from Figure 5, for LR1 that produces an upper bound, two lower bounds can be generated using Sections 4.2.1 and 4.2.2. The first one uses the solutions of LR1 to produce a feasible solution called LR1-LB and the other lower bound is obtained from the heuristic method called LR1-HLB. LR1 is using LB as described sub-gradient method in Section 4.3 (Algorithm 2, Step 2) and heuristic method (Algorithm3, Step 4 as it is a fixed value obtained from the heuristic method). These explanations also hold for LR2 and LD. At first, the proposed Lagrangian relaxation method in Section 4.2.1 is utilized and the lower bound is obtained by the B&B method. The results for this approach are included under the column \"LR1-LB\" in Table 7. The upper bound, lower bound using the B&B method and the elapsed time in seconds for all approaches are reported under columns \"UB\", \"LB\", and \"Time\", respectively. In the second approach, the problem LR1 is solved \begin{table}
\begin{tabular}{c c c c|c c c|c c c c c} \hline \hline  & \multicolumn{2}{c}{**CPLEX**} & \multicolumn{2}{c}{**Heuristic**} & \multicolumn{2}{c}{**LR1-HLB**} & \multicolumn{4}{c}{**LR1-LB**} \\ \cline{2-13} \# & **Obj** & **Time** & **HLB** & **UB** & **Time** & **UO-Gap** & **LB** & **UB** & **Time** & **LO-Gap** & **UO-Gap** \\ \hline
1 & 56 & 1 & 55 & 80 & 37 & 0.429 & 47 & 75 & 67 & 0.191 & 0.339 \\
2 & 71 & 2 & 69 & 97 & 50 & 0.366 & 68 & 94 & 89 & 0.044 & 0.324 \\
3 & 85 & 2 & 80 & 108 & 51 & 0.271 & 80 & 110 & 85 & 0.063 & 0.294 \\
4 & 114 & 2 & 114 & 177 & 54 & 0.553 & 101 & 168 & 97 & 0.129 & 0.474 \\
5 & 1838 & 333 & 1617 & 2139 & 173 & 0.164 & 1649 & 2162 & 284 & 0.115 & 0.176 \\
6 & 2030 & 338 & 1819 & 2312 & 242 & 0.139 & 1588 & 2465 & 504 & 0.278 & 0.214 \\
7 & 2847 & 1002 & 2574 & 3289 & 262 & 0.155 & 2301 & 3402 & 560 & 0.237 & 0.195 \\
8 & 3056 & 503 & 2906 & 3496 & 409 & 0.144 & 2367 & 3540 & 734 & 0.291 & 0.158 \\ Average & & & & 159 & 0.277 & & & 302 & 0.169 & 0.272 \\ \hline \hline \end{tabular}
\end{table} 
Table 7: Computational results to compare the CPLEX and LR 1 for small size instances.