## 3 Resolution Approaches
### Approximate Approaches
#### 3.2.1 Greedy Constructive Heuristic  
We begin with a greedy constructive heuristic based on a list algorithm. A solution to our problem will contain:  
* The starting times (\(STJ_{j}\)) and finish times (\(FTJ_{j}\)) of jobs, \(\forall j\in 1\ldots n\);
* The starting times (\(STM_{i}\)) and finish times (\(FTM_{i}\)) of machines, \(\forall i\in 1\ldots m\);
* The starting times (\(STR_{rq}\)) and finish times (\(FTR_{rq}\)) of resources, \(\forall r\in 1\ldots k,\forall q\in 1\ldots l_{r}\);* The assignments of machines to jobs \((AMJ_{j})\), \(\forall j\in 1\ldots n\);
* The assignment of resources to jobs \((ARJ_{jr})\), \(\forall j\in 1\ldots n\), \(\forall r\in 1\ldots k\). Algorithm 1 illustrates the constructive heuristic. ```
1\(S\gets EmptySolution()\)
2\(g^{\prime}\leftarrow ComputeCriterionA()\)
3\(ordj\leftarrow OrderJobs(g^{\prime})\)
4 for\(j\in ordj\)do
5\(s^{\prime}\gets GetStartDates()\)
6\(q^{\prime}\leftarrow GetResourceAssignments()\)
7\(g^{\prime\prime}\leftarrow ComputeCriterionB(s^{\prime},q^{\prime})\)
8\(ordi\leftarrow OrderMachines(g^{\prime\prime})\)
9 for\(i\in ordi\)do
10 if\(s^{\prime}_{i}+t_{ij}<\tilde{d}_{j}\wedge g^{\prime\prime}_{i}>\) - \(pc_{j}\)then
11\(S\leftarrow UpdateSolution(S,s^{\prime}_{i},q^{\prime}_{i})\)
12 break
13 return\(S\)
```  
**Algorithm 1**Greedy constructive heuristic  
We begin by initializing the solution \(S\). It is initially empty, with its elements \((STJ,FT)\), \(STM\), \(FTM\), \(STR\), \(FTR\), \(AMJ\), \(ARJ\)) set to 0, i.e., 0 starting and completion times for all jobs, machines, and resources, as well as no assignments of jobs to machines and resources. We then compute a first criterion in order to evaluate each job (line 2 of Algorithm 1, called by function \(ComputeCriterionA()\)). This criterion consists of two sub-criteria:  
* Tardiness-related aspects;
* Cost-related aspects. The first sub-criterion is given as:  
\[\frac{tc_{j}}{d_{j}\cdot t^{\prime}_{j}\cdot m^{\prime}_{j}},\forall j\in 1\ldots n\]  
where \(t^{\prime}_{j}\) is the average processing time of task \(j\) on all of the machines that can process it and \(m^{\prime}_{j}\) is the number of such machines. If we were to order tasks in decreasing order of this sub-criterion, we would give priority to tasks with a high tardiness cost, small due date, and small average processing time. The second sub-criterion is given as:  
\[p_{j}\ -fc_{j}\ -\sum_{r=1}^{k}a_{j}r\cdot rcr_{r}\cdot t^{\prime}_{j}+pc_{j}\]  
Ordering tasks in decreasing order of this sub-criterion gives priority to high-paying and high-penalty jobs. We combine the two sub-criteria by normalizing the first and multiplying it with the second. This first criterion is then used to sequence the jobs in decreasing order (line 3 of Algorithm 1). For each job \(j\) in this order, we proceed to construct a sequence of machines to which it should be assigned. In order to construct this sequence, we first go through several steps. We start by identifying the earliest starting date for job \(j\) on each machine \(i\) that can process it (line 5 of Algorithm 1):\[s^{\prime}_{i}=\max\left(trtj_{ij_{r}},FTM_{i_{r}},\max_{r\in 1\dots k}\left(a_{ jr}\cdot\min_{q\in 1\dots l_{r}}\left(FTR_{rq}+trtr^{\prime}_{irq}\right)\right)\right),\]  
where  
\[trtr^{\prime}_{irq}= \begin{cases}trtr_{r}&\text{, if }i\
eq AMj_{r}^{\prime} \text{ where }j^{\prime}=\operatorname*{arg\,max}_{\begin{subarray}{c}j^{ \prime\prime}_{r}\in 1\dots n\\ Akj_{r^{\prime\prime}}-q\end{subarray}}FTJ_{j^{\prime\prime}}\\ 0&\text{, otherwise}\end{cases} \]  
A job \(j\) will start on machine \(i\) no earlier that the time needed to transport it to the machine and the time the machine and the resources that it requires become available. When estimating the availability time of resources, we consider all resources and use \(a_{jr}\) to reduce this value to \(0\) if the resource type \(r\) is not required to process job \(j\).