###### Abstract  
In this paper, we are discussing a research project aiming to optimize the scheduling of production orders within a real application in the packaging field. As a first approach, we model the problem as an extended version of the hybrid and flexible flowshop scheduling problem with precedence constraints, parallel machines, and sequence-dependent setups. The optimization objective considered is the minimization of the total tradiness. To tackle this problem, we use two methodologies: mixed-integer linear programming (MILP) and constraint programming (CP). These two models were further extended by adding resource calendar constraints named also availability constraints; this implies that the tasks should be scheduled only when the machine is available. The different proposed models were compared to each other on a set of generated benchmarks that reflect the specific properties of the industrial partner. Finally, as the studied configuration relies on practical real-world application, where thousands of orders are produced monthly, a novel dedicated heuristic was designed to address the need for quick solutions. The latter outperforms the other proposed algorithms for expected total tardiness minimization. The proposed problem can be readily modified to suit a wide range of real-world situations involving the scheduling of activities that share similar characteristics. s +
Footnote †: journal: Applied  
1  
class=MSC] [Primary ]60F10, [Primary ]60F1  
avoid bottlenecks if some operations are too long, it is possible to multiply the number of machines that can perform the same operation. The resulting model is known in the literature as hybrid flowshop (HFS), also called flowshop with parallel machines; it consists of a set of processing stages, in which each stage may have several identical or non-identical machines, with at least one stage having two or more parallel machines. The classical hybrid flowshop assumes that all jobs need to visit all stages in the same order. However, in practice, each job might miss out or skip some stages, which can improve the performance of the model and make it better suited for real-world industrial settings. HFS scheduling problem with stage skipping is also called hybrid flexible flowshop scheduling problem. The configuration under study is described in Figure 1.  
In hybrid and flexible flowshop (HFFS) scheduling problems, two decisions should be taken: the assignment of jobs to the parallel machines as well as the sequencing of the jobs allocated to each machine. This problem is known to be NPhard in its simple version and in most of its extensions. As an example, [PERSON] et al. [1] demonstrated that preemptive scheduling in a two-stage flowshop with at least two identical parallel machines in one of the stages so as to minimize makespan is NP-hard in the strong sense. [PERSON] et al. [2] considered a non-preemptive two-stage hybrid flowshop problem in which the first stage contains several identical machines and the second stage contains a single machine; they demonstrated that the problem is NP-hard in the strong sense even when there are only two machines at the first stage. HFFS scheduling problem has been widely applied in various manufacturing environments, and several realistic constraints were considered. A fair amount of research has focused on a variety of realistic constraints, ranging from sequence-dependent setup times, constraint calendar, transportation time, due dates, and so on. Furthermore, several optimization criteria were considered, covering the commonly used makespan, costs, transportation, maximum tardiness and earliness, and the total of tardy job. In this paper, we make three significant contributions. Firstly, we introduce novel CP and MILP models that take into account specific constraints, including sequence-dependent setups and resource calendar constraints. Secondly, we assess the performance of both models using real industrial benchmarks.