## 4 A Biased-Randomized Discrete-Event Algorithm  
In order to solve the hybrid flow-shop problem with batch processes, setup times, and priorities, a multi-start approach is proposed in Algorithm 1. This multi-start method calls a biased-randomized heuristic (Algorithm 2) that makes use of the NEH heuristic. As discussed above, variations of this heuristic can provide good results for many hybrid flow shops [6]. The original NEH was designed to minimize the makespan in a simple flow shop environment. Due to the complexity of the flow shop system considered in this work, we made use of an original discrete-event based heuristic to compute the makespan. This procedure is outlined in Algorithm 3. Our approach, which is depicted in Algorithm 1, receives as input parameters a job list _jobsList_ (where \(jobsList[i]\) is the job situated in the \(i-th\) position in the sequence), some parameters _params_, and the \(\beta\) parameter (\(\beta\in(0,1]\)) of the geometric distribution employed to induce the biased-randomization effect [26]. This algorithm works as follows: firstly, the initial solution _best_ is generated by means of the heuristic STNEH (\(\beta=1\)) at line 2. In the main loop, the algorithm iterates until the termination criterion is not reached. For each iteration, a new solution _sol_ is generated by using the biased-randomized version of the STNEH heuristic, BR-STNEH. This is achieved by setting \(\beta\) in the interval \((0,1)\), as explained in [27]. If the makespan of _sol_ is lower than solution _best_, then _best_ is replaced by _sol_; otherwise _sol_ is discarded. Concerning the biased-randomized algorithm BR-STNEH (Algorithm 2), it chooses in each iteration the next job according to a two-level criterion: the setup times in the first level and the processing times in the second-level. Consider the following parameters: the jobs list _jobList_, the \(\beta\) parameter, the job processing times \(pT\), job setup times \(sT\), a list of job types _typesPriority_, and a non-negative integer \(mL\). The algorithm starts by listing the job types \(typelob\in\{A1,A2,B1,B2\}\) to split _jobsList_ into a list of jobs of type _typejob_ called \(jobstyle_{typejob}\). The NEH heuristic is applied to each list \(jobstyle_{typejob}\)s and collected in a list of lists _types_\(jobs\) (lines 3-7). In line 8, _types_\(jobs\) is sorted in descending order according to setup times. This is done because the setup time occurs mainly when two jobs, of different types, are processed by the same machine consecutively. Hence, if we classify the jobs by type, and then sort by the setup time \(sT\), we can expect a reduction in the number of times that two jobs of different types are processed by the same machine. In lines 9-12, those jobs that are a priority (\(typejob\in typesPriority\)) must be scheduled at the beginning of the _jobsList_. The main loop iterates until all jobs are scheduled. For each iteration, the algorithm picks a type \(typejob\) from \(typejob\)s list and gets randomly an integer number \(lgth\) between 1 and \(mL\), i.e., the latter fixes the number of iterations of the inner loop. In the inner loop, a random job is selected from the list \(jobsList_{typejob}\) and appended to the partial solution in each turn (lines 16-21). Finally, the complete solution _jobsList_ is returned. This procedure is then extended into a biased-randomized algorithm by introducing the geometric distribution \(G(\beta)\) with parameter \(\beta\in(0,1)\).