# Dynamic Job and Conveyor-Based Transport Joint Scheduling in Flexible Manufacturing Systems
## 4 Exploring the Solution Space
### Detailed Solution
In all the comparisons, we use a cost function based on the _makespan_, i.e., the latest completion time of the entire set of scheduled tasks. The built-in parameters that guide our heuristics are (i) the number of iterations and (ii) the available budget at each iteration, divided between the budget dedicated to the exploration of local and remote neighbors. We analyzed the impact of these parameters on the makespan with a sensitivity analysis. As for the transport system, unfortunately, public instances that include this aspect, such as the one used in [32], consider different means of transport (AGVs rather than conveyor belts). Therefore, they cannot be used in our comparison. Therefore, we consider a real-world use case related to our ICE lab, in which we were able to create a set of instances that include a transport system. Finally, we consider the case of a sequence of arrivals. We assume, as is carried out in the literature [14], that a set of jobs is present at time zero and that another set randomly arrives. We evaluate the makespan in such a dynamic case (updated at every arrival), and we compare it with the makespan computed by an ideal clairvoyant scheduler, i.e., a scheduler that knows all the future arriving jobs and provides a single, optimized schedule. Sched-T is implemented in Python, and the experiments are carried out on a 3.3 GHz Intel Core i7 (Intel, Santa Clara, CA, USA) with 16 Gb of RAM (Microchip Technology Inc., Chandler, AZ, USA). ### Instances with No Transport System

We compared Sched-T with a set of heuristics that were presented in [12], in which authors applied iterated local search, genetic algorithms, differential evolution, and tabu search on a set of 50 _large_ instances defined in the same paper, along with another set of 50 _large_ instances proposed by the same authors in [16]. Each instance differs in the number of available machines (up to 97) on which tasks can be allocated, the number of jobs (up to 200), and the number of total tasks (up to 2000). None of these heuristics outperformedthe others in all the instances: for some instances, differential evolution was better than the others, and for other heuristics, tabu search provides the best makespan. Rather than listing the values of each heuristic, we consider, for each instance, the best and the worst makespan obtained by these heuristics: we used such values to represent an interval for which the gap is much more narrow than the one found with the CP approach. Within this range lie the results of the four heuristics cited before (iterated local search, genetic algorithm, differential evolution, and tabu search). Therefore, we consider such a gap as a reference with which to compare. Instead of showing the absolute values for each instance, we can normalize the maximum makespan with respect to the minimum makespan so that the gaps of the different instances are comparable and can be put in a single graph. We also normalize the makespan obtained by Sched-T so that it is simple to understand if it falls in the gap provided by other heuristics. **Makespan**: In Figure 4, we compare the makespan obtained on the set of instances by Sched-T with the one obtained with the other reference heuristics. The results show that Sched-T is able to find a makespan within the gap defined by the other state-of-the-art heuristics. In some cases, it outperforms the other heuristics by 2%, whereas in two cases, it finds a larger makespan by 3%. We notice that every heuristic proposed in the literature, including our solution, provides an approximate solution, and there are no guarantees on the error bound. Therefore, we can only observe how well these heuristics perform on real datasets. Figure 4 shows that the approximate solutions have a 4-12% gap; therefore, such an error can be considered acceptable. From these results, Sched-T performs similarly to other state-of-the-art heuristics on instances without considering the transport time.