# Dynamic Job and Conveyor-Based Transport Joint Scheduling in Flexible Manufacturing Systems
## 4 Exploring the Solution Space
### Detailed Solution  
Our scheme for the exploration of the neighborhood uses a two-level hierarchical approach. At a higher level, we have jobs, while at the lower level, we have tasks. **Initialization**: In the case of a cold start, in which the system is completely unloaded, and a set of jobs has been collected and are ready to be executed (e.g., during the night, the production line does not work and arriving orders are collected), we initialize the order of the jobs according to the _longest processing first_ policy since it has been shown to improve the makespan compared other policies [30]. We define the processing time of a job as the sum of the processing time of its tasks. If a task (\(\tau_{ij}\)) can be processed by more than one machine, then we consider the minimum (\(p_{ijk}\)) (see Algorithm 1, procedure InitTaskOrder, and parameter \(BySize\) set to True). In the case of a running system, the order is given by the output of the previous schedule (considering only the jobs not yet launched), with the newly arrived job placed at the end. We then establish the order of tasks within each job by grouping tasks with the same precedence and randomly arranging the tasks within each group. The final output is an ordered sequence of tasks, denoted as \(s_{l}\). The makespan value is computed based on this sequence (refer to Algorithm 1 and procedure EvalSolution). We allocate each task to a machine, considering machine availability and dependencies for previous tasks. If multiple machines can perform a task, we choose the machine where the task terminates earlier, including the transportation time. **Neighborhood**: For a given sequence (\(s_{l}\)) of tasks, we define a _close neighbor_ as the feasible solution where we work at a low level. In other words, we switch tasks to obtain a new sequence (\(s_{l^{\prime}}\)) for evaluation. A random neighbor is obtained by (i) uniformly selecting a task (\(\tau_{ij}\) in \(s_{l}\)) and (ii) uniformly selecting another task (\(\tau_{ij^{\prime}}\)). The latter must belong to the same job (\(i^{\prime}=i\)) or to a job that comes before or after job \(i\) in the ordered set \(J\). If the tasks belong to the same job, our choice is limited to tasks with no dependencies on task \(\tau_{ij}\) (such a subset can be pre-computed upon job arrival). We define a _remote neighbor_ as a new solution in which jobs are swapped in the ordered set \(J\) (i.e., higher-level permutations). Thus, remote neighbors allow for the exploration of new solution areas, and close neighbors can be used to fine-tune the current solution. Figure 2: Example of the randomized exploration approach. We start from the current solution and evaluate some random close neighbors, along with remote neighbors (chosen randomly). ```
1 ProcedureInitTaskOrder(\(J\),BySize):
2 ifBySizethen
3 foreachjob ido
4\(i(size)\leftarrow\sum_{j}\min_{k}p_{ijk}\) ;
5\(J\leftarrow\textsc{OrderBySize}(J)\);
6\(s_{l}\leftarrow\emptyset\);
7 foreachjob i \(\in J\)do
8\(G_{i}\leftarrow\textsc{GroupByPrecedence}(i)\);
9 foreachgroup g \(\in G_{i}\)do
10\(g\leftarrow\textsc{RandomOrder}(g)\);
11\(\textsc{AddTasks}(s_{l},g))\);
12
13 return\(s_{l}\)
14 ProcedureEvalSolution(\(s,\{A\}\)):
15 foreachtask\(\tau_{ij}\in s\)do
16\(q\leftarrow\arg\min_{k}(t_{lk}+p_{ijk})\);
17\(\textsc{Update}(A,q,\tau_{ij})\);
18
19 return\(\max C_{ij}\);
```  
**Algorithm 1**Initialization and Evaluation  
**Exploration**: The number of close and remote neighbors (solutions) explored during an iteration is governed by the budget, \(B\). At each iteration, we update the current solution with a new one if it improves the current one (see Algorithm 2). The exploration starts by considering the current solution \(s_{i}\) and \(\alpha B\) as close neighbors, chosen uniformly at random among the feasible close neighbors (lines 6-12). The parameter \(\alpha\) is given as input, with \(0<\alpha<1\). The exploration continues by evaluating \(R\) remote neighbors (lines 13-14), selected uniformly at random.