## 4 A Biased-Randomized Discrete-Event Algorithm
```
1:\(\textbf{makespan}(jobsList,pT,sT)\)
2:\(availableTime\leftarrow\) initAvailableTimes()
3:\(previousTypeMachine\leftarrow\) initPreviousTypeMachine()
4:\(machinesType\leftarrow\) initMachinesType()
5:\(jobsWaiting\leftarrow\) initJobsWaiting()
6:\(eventList\leftarrow\) emptyList
7:\(mkSpn\gets 0\)
8:foralljob\(\in\)\(jobsList\)do
9:\(setupTime\gets 0\)
10:if\(type(job)\
eq previousTypeMachine[^{\prime}machine1^{\prime}]\)then
11:\(setupTime\gets sT[^{\prime}machine1^{\prime}][job]\)
12:endif
13:\(t\gets pT[^{\prime}machine1^{\prime}][job]+setupTime\)
14:\(event\leftarrow\) createEndingEvent(\(t\),job,'\(machine1^{\prime}\))
15:\(eventList\leftarrow\) append(\(eventList\),\(event\))
16:endfor
17:\(eventList\leftarrow\) sortingByTime(\(eventList\))
18:while\(eventList\
eq emptylist\)do
19:\(event\leftarrow\) first(\(eventList\))
20:ifisStarting(\(event\))then
21: processingStartingEvent(\(event\), \(pT\), \(sT\), \(availableTime\), \(previousTypeMachine\), \(machineTypes\),\(eventList\))
22:else
23: processingEndingEvent(\(event\), \(pT\), \(sT\), \(availableTime\), \(previousTypeMachine\), \(machineTypes\), \(WaitingJobs\),\(eventList\))
24:endif
25:\(mkSpn\leftarrow\) time(\(event\))
26:endwhile
27:return\(mkSpn\)
```  
**Algorithm 3** Discrete-Event Makespan Method  
At each iteration, the next event, \(event\), is selected, which can belong to one of the following types: job starts in a machine (starting-event) or job ends in a machine (ending-event):  
* In case of a starting-event, job \(job\) is just placed at the entrance of machine \(j\) at time \(t\). Algorithm 4) proceed as follows: job \(job\), machine \(machine\), time \(t\), and type \(typejob\) are recovered in lines 2-4; in line 6, we check whether \(job\) belongs to the \(machine\) path; if it does not, then a new ending-event is created with the same job, machine, and time (lines 18-19); otherwise, the algorithm advances the clock time \(t\); next, the algorithm determines the \(setupTime\), which is set to 0 if the previous job type and the current one match; otherwise, \(sT[machine][job]\); hence, the new time \(t^{\prime}\) is set to previous time \(t\) plus the job-processing time \(pT[machine][job]\) and the \(setupTime\) (lines 7-14); finally, we create a new ending-event \(nEvent\) with the same job and machine but at time \(t^{\prime}\); this event is insert into the event list. * In case of an ending-event (Algorithm 5), like a job _job_ of type _typeJob_ leaving machine machine at time \(t\), the algorithm works as follows: initially, job, type, and time are obtained from event in lines 2-3; in line 4, this machine release time is computed with the maximum between the current time \(t\) and the current machine release time \(availableTime[machine]\); then, the algorithm verifies whether the job belongs to this machine path; if it does not, then a new starting-event is created with the same job and time but in the next machine (lines 18-19); otherwise, it continues to the next step; in the next step, our algorithm assumes that the size of all batches is set to 1 except for \(Ba1\) and \(Ba2\); hence, the current job is added to the list of jobs in the current machine \(waitingJobs\) (lines 8-9); in lines 10-16, the algorithm checks if the number of jobs in this machine reaches the batch size, in which case a new starting event \(nvEvent\) is scheduled at time \(t\) for each job \(job^{\prime}\) in the \(waitingJobs\) (these new events are inserted into the \(eventList\)). Finally, when \(eventList\) is empty (line 18 in Algorithm 3, the algorithm finishes returning the time \(mkSpn\) of the last event processed, which is an ending-event of the last job in the last machine. This time is the makespan of the processed \(jobsList\).