# Near-Optimal Heuristics for Just-In-Time Jobs Maximization in Flow Shop Scheduling
## 4 Constructive Heuristics  
To efficiently solve the problem described in Section 3, ten constructive heuristic methods are proposed based on an investigation of the problem structure and inspired by relevant classical algorithms, such as the NEH heuristic [17], [PERSON]'s algorithm [18] and well-known priority rules, such as the EDD which is the ascending order of due dates, and the minimum slack time (MST) which sequences jobs according to the smallest amount of slack (\(d_{j}-\sum_{k=1}^{m}p_{jk}\)). It is known that, in a single-machine problem, the EDD and MST rules minimize the maximum tardiness and earliness, respectively [19]. All the heuristics require a timing adjustment procedure that consists of checking the best instant to start the operations for a given sequence to complete a greater number of jobs on time. The simple shifting of an early job with a slack time to match its conclusion to its due date could result in an overall improvement in the solution. A pseudo-code of the timing adjustment procedure is given in Algorithm 1. Note that a shift is applied only in the last operation of a job (Step 3 in Algorithm 1) because keeping each previous operation starting at its earliest possible instant can be an advantage in this problem as it enables jobs that could be late because of their first operations to be anticipated. In addition, this shift is maintained when there is an improvement in the solution (or at least a tie); otherwise, the replacement is reversed to anticipate operations which contribute to eliminating possible tardiness in subsequent jobs. _Timing adjustment procedure_  
1. For the given sequence, considering starting each operation as early as possible, compute the number of just-in-time jobs (\(n_{|IT}\)) and consider \(J_{\text{initial}}=J_{[1]}\), where \(J_{[j]}\) is the job in position \(j\) of the sequence. 2. From \(J_{\text{initial}}\), identify the first early job in the sequence (\(J_{E}\)) and go to Step 3. If there are no early jobs (from \(J_{\text{initial}}\)), STOP. 3. Move the last operation of job \(J_{E}\) to eliminate earliness and make its conclusion coincide with its due date. Properly reschedule the last operations of the jobs after \(J_{E}\). \begin{table}
\begin{tabular}{c c c} \hline \hline Variables & Binary & \(n^{2}+2n\) \\  & Integer & \(n^{2}+m+n+1\) \\  & Total & \(n(2n+3)+m+1\) \\ \hline Constraints & (2) & \(n^{2}m+nm\) \\  & (3) & \(nm\) \\  & (4) & \(n\) \\  & (5) & \(n\) \\  & (6) & \(1\) \\  & (7) & \(n\) \\  & (8) & \(n+1\) \\  & (9) & \(n+1\) \\  & Total & \(n(n+2m+6)+m+3\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Model’s size in relation to numbers of variables and constraints. Step 4. Compute the new number of just-in-time jobs (\(n_{JIT}\)'). If \(n_{JIT}\)' \(<n_{JIT}\) (the new solution is worse than the previous one), return both the last operation of \(J_{E}\) and the operations of the following jobs to their previous positions, set \(J_{\text{initial}}=J_{\text{[initial]}}+1\) and go to Step 2. Else (the new solution is better than or equal to the previous one), keep the new schedule, set \(J_{\text{initial}}=J_{\text{[$E$]}}+1\) and go to Step 2. **Algorithm 1. ** Pseudo-code of timing adjustment procedure. The first four heuristics proposed are adaptations of the NEH algorithm's insertion method and are given in Algorithms 2-5. H1 and H2 employ the EDD rule as the initial order while H3 and H4 consider the MST rule. Another feature is that H2 and H4 improve on H1 and H3, respectively, by using neighborhood search in the partial sequence. Two types of neighborhood search are employed, insertion and permutation, in the same way as [20]. Given a sequence (or a partial sequence) of n jobs, its insertion neighborhood consists of all \((n-1)^{2}\) sequences obtained by removing a job from its place and relocating it to another position. The permutation neighborhood is composed by all \(n(n-1)/2\) sequences obtained by permuting the positions of two jobs (see Example 1).