## 3 Problem Description  
The problem under study corresponds to a real industrial problem of a packaging company that prints, on average, 1000 jobs per month. The operations can be categorized into four main groups, ranging from the preparation of printing materials to the printing process and shifting process (winding, perforation, and coating) and finally shaping process aiming to make orders into their final form. Moreover, it is important to point out that this process is characterized by flexibility, where machines might be skipped and not all the machines must be visited by all the jobs. A job \(i\) consists of a number \(n\) of operations; each operation \(O_{ij}\) can be processed by a subset of machines and has a processing time on machine \(k\), and it may be zero for some jobs as the jobs are not processed in some stages (skipping). Note that \(p_{i}\) denotes the processing time of job \(i\). Before starting processing, a setup time (ST) is needed between each of two consecutive scheduled jobs on each machine. That is to say that, to transition from the processing of the current operation \(O_{ij}\) to the next one \(O_{ij^{\prime}}\) on machine \(k\), some setup settings must be implemented according to the characteristics of each operation, such as color, size, etc. An example of setup for the printing phase consists of removing the ink colors not required for  
the next job on that printing machine to free up the ink trays for colors that are required for the next job. Transitioning from one job to another requires to change ink colors. The time required to set up one job for the printing phase can be divided into three steps: the first one to empty the tray from the previous ink, the second one to clean the ink tray, and the last one to reload the appropriate ink color. The global needed setup time depends on the number of color changes. On average, the significant setups may contribute to 40% of the global printing step, including processing time and setup time. However, if a job \"\(i\)\" requires the same color as the previous job \"\(i-1\)\", then the setup time for this color may be avoided because the considered printing machine is already loaded with appropriate color and, therefore, major setups are not needed. The setup time duration is correlated to the setup settings' similarities between two consecutive operations. The more resemblance the operations' settings, the shorter the machine setup. Another important feature of the considered problem is resource calendar constraints (RC), which allow to set the work shifts of all machines. The work shift is a segment of continuous available times of a machine. This means that machines are available only during working times in the calendar. These unavailability periods are the consequence of shift patterns or planned maintenance. On the other hand, the machine setup cannot be interrupted by unavailable periods, and the end of the setup must be immediately followed by the beginning of the operation processing. Furthermore, a transportation time is needed to transport a job from the current processing machine to the next one. Based on the key features of the considered production system, a production schedule should be planned to maximize the production effectiveness so that the printing line can gain as much production benefit as possible. The production effectiveness can be represented by an objective function that should be defined based on the production targets of the problem. In flexible manufacturing plants operating in a make-to-order environment, the efficient utilization of manufacturing resources is typically pursued to meet delivery deadlines. Thus, in our case, we aim to minimize the total tardiness of all jobs, meaning that we seek to find a job sequence that minimizes the total amount of time by which all jobs are completed after their due dates.