###### Abstract  
Based on a real-world application in the semiconductor industry, this article models and discusses a hybrid flow shop problem with time dependencies and priority constraints. The analyzed problem considers a production where a large number of heterogeneous jobs are processed by a number of machines. The route that each job has to follow depends upon its type, and, in addition, some machines require that a number of jobs are combined in batches before starting their processing. The hybrid flow model is also subject to a global priority rule and a \"same setup\" rule. The primary goal of this study was to find a solution set (permutation of jobs) that minimizes the production makespan. While simulation models are frequently employed to model these time-dependent flow shop systems, an optimization component is needed in order to generate high-quality solution sets. In this study, a novel algorithm is proposed to deal with the complexity of the underlying system. Our algorithm combines biased-randomization techniques with a discrete-event heuristic, which allows us to model dependencies caused by batching and different paths of jobs efficiently in a near-natural way. As shown in a series of numerical experiments, the proposed simulation-optimization algorithm can find solutions that significantly outperform those provided by employing state-of-the-art simulation software. machine scheduling; hybrid flow shop; priority; batching; based-randomization; discrete-event heuristics +
Footnote †: journal:  
0000-0001-541-5000, 2000/0000-00001-5  
a result, there is an increasing need to use optimization algorithms in practice in order to handle the complexity of planning problems. This is especially the case in the use case of this study, which comes from the field of semiconductor manufacturing. The use of simulation-optimization approaches [1] could provide a differentiated answer. In planning, design, and ramp-up, these methods are well established but are not frequently used yet for operational support in decision-making. In our real-life scheduling application, and other production use cases, it is possible for jobs to take different paths through the production system. The specific path might depend upon a particular specification or parameter, which defines the machines to be visited by the job. The existence of different paths through the production system might cause time dependencies, so the order in which the jobs leave the system might be different from the order in which the jobs entered it. Consequently, this can lead to problems in the context of the planning of batch-related insertion dates, especially if batch processes are also found within the production system. Therefore, we need a simulation to model our system. In this study, a multi-path version of the hybrid flow shop scheduling problem [2] was analyzed. This version also considers two batch processes at the same time, and it is based on the real case from a German manufacturing industrial partner. Furthermore, a global priority rule and a \"same setup\" rule were considered. The before-mentioned elements make the computation of the makespan a non-trivial task: due to the existence of time-dependencies and batches, the makespan cannot be computed using a closed analytical expression anymore. Accordingly, the main contributions of this study are described next: (i) a simulation model of a hybrid flow shop problem with pre-determined paths, which are predefined by individual parameters and specifications and batching; (ii) a fast discrete-event heuristic that is able to deal with the complexity of the modeled system and compute the makespan associated with a proposed solution; (iii) the extension of the previous heuristic to a biased-randomized algorithm [3], which introduces some degree of randomness into the heuristic constructive process; and (iv) the evaluation of computational experiments, which show the performance of the proposed methodology for solving this scheduling problem.