## 3 Proposed Solution Approach for \(Qm,h_{in_{i}}|a|C_{max}\)
### Proposed-Solution Approach
#### 3.2.1 \(Lptbh\) Heuristic Procedure  
The main idea of \(LPTBH\) is to divide the set of jobs \(N\) into two subsets. The first set includes jobs that can be assigned to one of the machines' availability intervals. The second set contains the remaining jobs. The \(LPTBH\) consists of two phases. The first is the main phase, as it schedules the maximum of jobs. First, for every machine, a list of job candidates is formed on the basis of whether they could fit the machine's availability intervals except the last ones. This step is achieved by using the \(Candidate\_Search\) procedure shown in Algorithm 1. Second, jobs in every constructed list are sorted in decreasing order of their processing times. Then, for every machine, starting from machine 1, select the first job in the candidate list of machine 1. If the selected job is only in that machine's list, assign it to the availability interval that can fit it. Otherwise, assign it to the machine on which it can finish as early as possible. The first phase ends when all the machines' job-candidate lists are empty. The remaining unscheduled jobs are input for the second phase. The pseudocode of the \(LPTBH\) heuristic is shown in Algorithm 2. Table 1 lists notations used to develop Algorithms 1 and 2.  
\begin{table}.  
\begin{tabular}{l l} \hline \hline
**Notation** & **Meaning** \\ \hline \(S\) & Set of all the jobs to be scheduled \\ \(C_{i},\ i=1,\ldots,m\) & Completion time of last job assigned to machine \(i\) \\ \(av_{ik},\ i=1,\ldots,m;k=1,\ldots,n_{i}\) & Length of \(k^{th}\) availability interval of machine \(i\) \\ \(maxAv_{i},\ i=1,\ldots,m\) & Length of largest availability interval of machine \(i\) \\ \(Lc_{i},\ i=1,\ldots,m\) & List of jobs that can be processed in any availability interval on machine \(i\) \\ \(LR\) & List of remaining unscheduled jobs \\ \hline \hline \end{tabular}.  
\end{table}
Table 1: Notations used in Algorithms 1 and 2.  
```
1:procedure(Input \(N=\{1,\ldots,n\}\), \(m\), \(p_{ij}\), \(i=1,\ldots,m;j=1,\ldots,n\), \(maxAv_{i}\), \(i=1,\ldots,m\))
2:for\(i=1\) to \(m\)do
3:for\(j=1\) to \(n\)do
4:if\((p_{ij}\leq maxAv_{i})\)then
5:\(Lc_{i}\cup\{j\}\)
6:endif
7:endfor
8:endfor
9:endfor
10: Sort the jobs in every \(Lc_{i}\), \(i=1,\ldots,m\) in a nonincreasing order of their processing times.
11:endprocedure
12:
13:procedure(Input \(N=\{1,\ldots,n\}\), \(m\), \(p_{ij}\), \(i=1,\ldots,m;j=1,\ldots,n\), \(N_{i}\), \(i=1,\ldots,m\), \(S_{ik},E_{ik}\), \(i=1,\ldots,m;k=1,\ldots,N_{i}\). Output \(S=C_{max}\))
14:for\(i=1\) to \(m\)do
15:for\(k=1\) to \(N_{i}\)do
16:\(av_{ik}=E_{ik}-S_{ik-1}\)
17:endfor
18:\(maxAv_{i}=\max_{k}av_{ik}\)
19:\(C_{i}=0\)
20:endfor
21: Call \(Candidate\_Search\)
22:while\((S\
eq\varnothing)\)do
23: Among the jobs of \(Lc_{i}\), \(i=1,\ldots,m\), select the job with the highest processing time. Let \(l\) be that job and \(i_{l}(s)\) the machine(s) to which it can be assigned.
24:if\((l\) exists in more than one \(Lc_{i})\)then
25: Assign \(l\) to the machine on which it can finish as early as possible.
26:elseAssign \(l\) to machine \(i_{l}\)
27: Update \(C_{i_{l}}\)
28:endif
29:\(S=S\setminus\{l\}\)
30: Update \(av_{ik}\) of the machine to which job \(l\) was assigned.
31: Call \(Candidate\_Search\)
32:if\((Lc_{i}=\emptyset,\forall\;i=1,\ldots,m)\)then
33:if\((|S|\
eq n)\)then
34:\(LR\gets N\setminus S\)
35: Schedule the jobs of \(LR\) according to \(LPT\) rule.
36: Calculate \(C_{i}\), \(\forall\;i=1,\ldots,m\)
37:endif
38:\(S\gets S\setminus LR\)
39:endif
40:endwhile
41:\(S=\max_{i}C_{i}\)
42:return S.
43:endprocedure
```  
**Algorithm 1**\(Candidate\_Search\).