# Dynamic Job and Conveyor-Based Transport Joint Scheduling in Flexible Manufacturing Systems
## 4 Exploring the Solution Space
### Detailed Solution
For each of them, it explores its neighbors locally uniformly at random with a budget \((1-\alpha)B/R\) (lines 15-21). The exploration stops when one of the following conditions is reached: (i) the maximum number of iterations \(T_{\max}\); (ii) no improvements are found for \(t_{\mathrm{idle}}\) iterations (not shown in Algorithm 2). Figure 3 shows a high-level view of the processing flow. Figure 3: Exploration flow: starting from a solution at time \(t-1\), we explore the local neighbors, along with a set of distant neighbors. If we find a better solution, we update the current solution. ``` input:\(J\), set of jobs to be scheduled input:\(M\), set of machines input:\(\{A_{0}\}\), availability intervals input:\(\textit{BySize}\), True if jobs need to be ordered by size input:\(B,\alpha,R\), parameters for exploration
1\(s_{0}\leftarrow\textsc{InitTaskOrder}(J,\textit{BySize})\); \(\mathcal{O}\leftarrow\textsc{EvalSolution}(s_{0},\{A_{0}\})\);
2\(i=1\);
3 while\(i\leq T_{\text{max}}\)do
4\(s_{i}\gets s_{i-1}\);
5 for\(\alpha\)B timesdo
6\(s_{i}^{\prime}\leftarrow\textsc{RandomLocalPerm}(s_{i-1})\);
7\(\mathcal{O}^{\prime}\leftarrow\textsc{EvalSolution}(s_{i^{\prime}}^{\prime}\{A_{i-1 }\})\);
8 if\(\mathcal{O}^{\prime}<\mathcal{O}\)then
9\(s_{i}\gets s_{i}^{\prime}\);
10\(\mathcal{O}=\mathcal{O}^{\prime}\);
11\(\{A_{i}\}\leftarrow\textsc{UpdateAval}(s_{i})\);
12
13 forR timesdo
14\(s_{i-1}^{\prime}\leftarrow\textsc{RandomRemotePerm}(s_{i-1})\);
15 for\((1-\alpha)B/R\) timesdo
16\(s_{i}^{\prime}\leftarrow\textsc{RandomLocalPerm}(s_{i-1}^{\prime})\);
17\(\mathcal{O}^{\prime}\leftarrow\textsc{EvalSolution}(s_{i}^{\prime},\{A_{i-1 }\})\);
18 if\(\mathcal{O}^{\prime}<\mathcal{O}\)then
19\(s_{i}\gets s_{i^{\prime}}^{\prime}\);
20\(\mathcal{O}=\mathcal{O}^{\prime}\);
21\(\{A_{i}\}\leftarrow\textsc{UpdateAval}(s_{i})\);
22
23
24
25
26
27
28
29
30
310
320
331
342
353
364
375
386
390
391
3922
393
394
3955
396
397
398
3999
4001
4102
4203
4399
5990
60112
59913
6102
6103
6214
622
63915
6392
6404
6505
666
6706
6807
6908



in Section 5, we show the running time for different instance sizes. Compared to the job processing time (e.g., tens of minutes), the scheduling processing time is very small, and therefore, the approach based on total rescheduling is justified. In case of high job arrival rates, rather than recomputing the scheduling at every arrival, it is possible to collect some new jobs before running Sched-T. As a rule of thumb, if the scheduling processing time is \(P_{\text{proc}}\) seconds, and the average arrival rate (estimated considering the last arrivals) is \(V_{\text{arr}}\) jobs/s, then the new scheduling can be computed once \(\left\lceil\beta\cdot V_{\text{arr}}\cdot P_{\text{proc}}\right\rceil\) jobs have arrived, with the parameter \(\beta\geq 1\) that controls the trade-off between the delay and processing load. Alternatively, at every job arrival, it is possible to consider only a subset of jobs waiting to be processed (e.g., the last W jobs in line) as part of the set of jobs that are included in the new schedule computation so that the other subset can be used to feed the production line during the computation. ## 5 Experimental Results

In this section, we demonstrate the validity of our proposed heuristic Sched-T. First, we compare our heuristic with state-of-the-art approaches for solving the FJSS problem, using public benchmarks without the transport system. Then, we apply our heuristic to both a real-world scenario and a simulated scenario to evaluate its performance when the transport system is present. ### Experimental Methodology and Settings

In order to compare Sched-T with other heuristics, we consider the set of publicly available instances described in [12; 16]. These instances have been created using the instance generator available at [31]. The generated instances contain information regarding the jobs, assuming that transportation is part of the task-processing time. We use these instances to evaluate the performance of our proposed scheduling heuristic with respect to the state-of-the-art.