A new composite heuristic to minimize the total tardiness for the single machine scheduling problem with variable and flexible maintenance

A new composite heuristic to minimize the total tardiness for the single machine scheduling problem with variable and flexible maintenance Antonio Costa a,* , Roberto Rosario Corsini a , Daniele Pagano b , Victor Fernandez-Viagas c a DICAR Department, University of Catania, Viale Andrea Doria 6, 95125 Catania, Italy b STMicroelectronics - Stradale Primosole, 50, 95121 Catania, Italy c University of Seville, Department of Industrial Organization and Business Management I, School of Engineering, Camino Descubrimientos s/n, 41092 Sevilla, Spain ARTICLE INFO Keywords: Linear programming Optimization Preventive maintenance Setup times Release times ABSTRACT Inspired by a real-world maintenance/job scheduling issue coming from the semiconductor industry, the present paper proposes a new heuristic algorithm structure for the single machine scheduling T-problem with flexible and variable maintenance, job release dates and sequence dependence setup times. Considering the typical shortterm production planning needs, a single maintenance problem has to be scheduled within a certain time interval, along with a set of jobs so as to minimize the total tardiness. A twofold contribution emerges from the present paper. First, four mixed-integer linear programming models are developed for the problem at hand and compared in terms of time to convergence and computational complexity. Second, a novel heuristic algorithm, which has been configured into three distinct variants, has been compared with 17 alternative heuristics from the relevant literature based on a comprehensive experimental campaign. The numerical results allow the selection of the most suitable MILP model and confirm the effectiveness of the proposed heuristic approach. 1. Introduction In production scheduling theory, machines are usually considered available production resources. However, they often need to be arbitrarily stopped because of preventive maintenance operations. Addressing scheduling problems while being unavailable the production resources is a demanding issue that has captured the attention of both academics and industrial stakeholders (Ma et al., 2010). Actually, several kinds of maintenance activities may be accomplished on the manufacturing resources, such as cleaning, tool replacement, refilling, recharging, and other planned activities that make any job processing temporarily blocked (Luo et al., 2015). Whenever a maintenance activity and a set of jobs have to be scheduled, two primary information are needed, i.e., starting time and duration. Nonetheless, motivated by a more realistic perspective, several studies cope with the scheduling problem with flexible maintenance, in which the maintenance starting time may fall within a certain time range. In some real-world production contexts, the working conditions may bias the duration of the maintenance activity, which becomes a variable of the scheduling problem. Beyond the considerations of starting time and duration of preventive maintenance, a twofold research stream can be detected in the literature that deals with the topic at hand. The former studies the problem of scheduling jobs with a single preventive maintenance, while the latter considers multiple unavailability intervals, i.e., periodic maintenance activities along the time horizon. Although most recent studies investigate scheduling problems with periodic maintenance, we believe that scheduling jobs with a single maintenance activity simultaneously still constitute a valid challenge, typical of many real-life scenarios where the time length of the machine unavailability is consistent with the short-term planning horizon. To further motivate the scientific validity of this issue, the seminal work of Qi et al. (1999) demonstrates that even minimizing the total completion time for a single machine scheduling problem with preventive maintenance is NP-hard in the strong sense. In this regard, the present paper addresses the single machine scheduling problem with a single unavailability interval due to a flexible and variable preventive maintenance operation. It has been inspired by a real-life semiconductor manufacturing problem concerning the silicon carbide (SiC) epitaxial deposition, where a chemical vapor deposition (CVD) method is usually used to deposit a layer of single crystal on the wafer to form an epitaxial wafer. Every week a highly skilled worker has to accomplish a flexible and variable maintenance operation. Briefly, it consists of a twofold time-consuming activity: 1) stopping the reactor and waiting until room temperature and atmospheric pressure in the * Corresponding author. E-mail address: [email protected] (A. Costa). Contents lists available at ScienceDirect Computers and Operations Research journal homepage: www.elsevier.com/locate/cor https://doi.org/10.1016/j.cor.2024.106849 Received 21 November 2023; Received in revised form 1 August 2024; Accepted 8 September 2024 Computers & Operations Research 173 (2025) 106849 Available online 14 September 2024 0305-0548/© 2024 The Author(s). Published by Elsevier Ltd. This is an open access article under the CC BY-NC-ND license ( http://creativecommons.org/licenses/bync-nd/4.0/ ). chamber are achieved; 2) mechanical cleaning of the chamber for a time ranging in 2–3 h. Since the machine at hand is dedicated to high added-value products for top clients, and the customer demand exceeds the production capability, an effective scheduling strategy is required to minimize the total tardiness. Therefore, the problem under investigation can be configured as a single machine scheduling problem with a flexiblevariable maintenance to be executed within a specific time window, also including sequence dependent setup times and non-zero release times, with the objective to minimize the total tardiness. Such a kind of problem is strongly NP-hard as it can be reduced to 1rj∑Tj or 1sij∑Tj, both of which are strongly NP-hard (Lawler et al., 1982). Compared with previous research, the leading contributions of the present study are the following: i) Three distinct mixed-integer linear programming models are proposed and compared in terms of time to convergence and gap from the optimality. ii) A new heuristic algorithm configured in three distinct variants is developed and tested by means of an extended experimental analysis involving 17 heuristics from the relevant literature. For the sake of clarity, the present paper can be configured as the development of another research by Costa and Fernandez-Viagas (2022), where the same single machine scheduling problem was investigated by proposing a MILP model and a modified harmony search algorithm. The remainder of this paper is arranged as follows. Section 2 analyzes the literary background. Section 3 presents the problem statement while the related MILP models are in Section 4. Section 5 allows assessing the computational complexity of the proposed MILP models. The proposed heuristic algorithms are introduced in Section 6. The way the test cases have been constructed is explained in Section 7. Section 8 presents and discusses the numerical results arising from an extended experimental campaign. Section 9 reports the final conclusions on the research work. 2. Review of literature and contributions Two research streams on the single machine scheduling problem with flexible-variable preventive maintenance (SMFVM) may be identified in the literature. The former deals with a kind of problem where a single maintenance activity must be scheduled along with a set of jobs. The latter focuses on scheduling multiple maintenance activities on a single machine over a wider time horizon; thus, maintenance activities are spread out over a longer time horizon (weeks, months, years) that, in some cases, may result inconsistent with the needs typical of the shortterm production planning. Motivated by these considerations, the literary background is reviewed under a twofold perspective. First, the contributions on the single machine scheduling problem with a single maintenance activity are explored. Then, we review the literature on the single machine scheduling problem with periodic maintenance tasks. As for the first kind of problem, most contributions on the SMFVM problem copes with the so-called basic problem in which no restriction concerning setup times and/or release times occurs. In this context, many authors just developed polynomial time algorithms to optimize different turnaround or timeliness performance measures. Chen (2006) proposed several binary mixed integer programming models to minimize the total tardiness in the presence of a flexible maintenance operation. Mosheiov and Sarig (2009) developed a pseudo-dynamic programming model for solving the total weighted completion time SMFM problem, thus demonstrating the NP-hardness of the problem under investigation. Mosheiov and Sidney (2010) demonstrated that in the SMVM problem wherein the maintenance duration is a nondecreasing function of the starting time, some objectives such as makespan, flowtime, maximum lateness, and number of tardy jobs, can be optimally solved in a polynomial time. Considering the single machine problem with variable maintenance to be started earlier than a certain dead-line, Low et al. (2010) showed that the total weighted completion time is weakly NP-hard and an approximate solving approach can be adopted. Later, Luo et al. (2015) investigated the same scheduling problem and found out that makespan, total completion time, maximum lateness and number of tardy jobs can be optimized by polynomial time algorithms. Luo and Ji (2015) addressed a variant of the previous scheduling problem with deteriorating jobs and variable maintenance, and proved that both makespan and total completion times can be minimized by fully polynomial time approximation schemes. Some years later, Luo and Liu (2017) developed a (2 +e)- approximation algorithm to minimize the total weighted completion time. Detti et al. (2019) introduced a further restriction, i.e., a time window in which the variable maintenance task must be executed. The most related research corresponds to Costa and Fernandez-Viagas (2022), which addresses the single machine scheduling problem with a flexible-variable maintenance, and propose a MILP model, several heuristics, and a modified harmony search. Although several research contributions deal with the single machine scheduling problem with periodic maintenance, it is worth pointing out that all of them focus a kind of basic problem wherein many sources of complexity such as sequence dependent setup times, job release times, and variability of maintenance operations are ignored. Sun and Geng (2019) cope with the optimization of the total completion time in the basic single-machine scheduling problem with deteriorating effects on the machine itself, which can be resumed by a proper maintenance operation. Chen et al. (2020) test a series of fast heuristics such as LPT, FFD, MW, LBI, to minimize makespan in a singlemachine scheduling problem with flexible maintenance and nonresumable jobs. Chen et al. (2021) investigate the single machine scheduling problem in which both imperfect and perfect maintenance operations may be executed to minimize the total tardiness. They ignore job release times and setup times and, in case of failure, jobs will resume after repair with no extra processing time. A similar study proposes a genetic algorithm for production and maintenance scheduling in a degrading multi-failure modes single machine environment (Sharifi and Taghipour, 2021). Touat et al. (2022) proposes a guided local search metaheuristic for the single machine scheduling problem with flexible maintenance and human resource constraints with the aim of minimizing a bicriteria objective function based on earliness and tardiness. Yazdani et al. (2023) compare different new metaheuristic algorithms for the maximum earliness and tardiness minimization in a single machine environment where periodic maintenance occurs. Penz et al. (2023) introduce two mixed integer programming models to minimize the sum of completion times in a single machine problem with job families, machine deterioration, and flexible maintenance operations. Specifically, they consider both the daily case problem in which the time horizon is equal to one day and a single maintenance must be sequenced, and the weekly case in which at most two maintenance operations have to be scheduled. Conforming to the previous contributions, no release times, variable maintenance, and setup times are included in the problem complexity. 3. Problem statement In the single machine scheduling problem under investigation a set of n jobs (j =1,…,n) has to be processed on a single machine, with p j being the job processing times. Preemption is not allowed, and each job is available to be processed at a different time r j . Every job requires an attached sequence dependent setup time s ij . A preventive maintenance task must be accomplished within a specific time interval [I min , I max ], known a-priori. The maintenance activity is variable so, the later its starting time, the longer its duration. However, both starting time Z and completion time ZC of the maintenance activity (being Z<ZC) must be placed within the allowed time interval. The maintenance duration is A. Costa et al. Computers and Operations Research 173 (2025) 106849 2 modelled as a combination of two contributions, the former being a constant (γ), the latter a variable λ =f(Z), i.e., a positive non-decreasing function of the starting time Z∈ [Imin,Imax]. In particular, the maintenance duration is designed as δ=γ+λ where λ=m• (Z−Imin)and m is the slope of the linear function. The objective function is the total tardiness T=∑n j=1Tj, where Tj=max{0,Cj−dj}, being Cj and dj completion time and due date of each job j, respectively. According to the well-known three-field classification rule (Graham et al., 1979), the problem at hand can be coded as 1|rj,sij,nr,vm,fm|∑Tj, where nr means non-resumable jobs while vm and fm variable and flexible maintenance, respectively. From now on, the single machine scheduling problem with flexible and variable maintenance will be denoted by SMFVM. Further details on the problem statement as well as an illustrative example can be retrieved in Costa and Fernandez-Viagas (2022). A list of notations useful for the readers are in the following: 4. MILP models MILP modelling has been used to optimally solve a series of smallsized scheduling problems, with the aim of providing a robust validation support for the heuristic algorithms to be compared. More specifically, four MILP models are described in this section and all of them are based on the precedence-decision rationale. This choice is motivated by the fact that this approach assures a better performance in terms of convergence to global optima and computational times than the position-based scheme (also called sequence-position), even in more challenging scheduling problems (Demir and ˙ Is¸leyen, 2013, Meng et al., 2022). The first model (hereinafter denoted as MILP1) consists of the MILP model proposed by Costa and Fernandez-Viagas (2022). Then, three new models were developed as a modification of the former one. Hence, for the sake of brevity, notation, parameters, and decisions variables common to all models are in the following paragraphs. Table 1 holds notation and parameters common to all models, even though the last column allows detecting how a specific MILP model uses the job indices. As for example, as concerns setup times sij, three out of four MILP models make use of a job index i starting from zero (dummy job), while only MILP3 employs the job index i starting from one. Furthermore, only MILP3 needs to separately run the setup time of the job processed as first (i.e., aj). Table 2 allows matching each decision variable with the different MILP models. Interestingly, all MILP models with exception of MILP3 use a dummy job (i =0) for the decision variable Yij, while MILP1 is the only model in which the maintenance operation is handled as an additional job, so n +1 jobs are considered when computing starting and completion times. As expected, the objective function to be minimized, i.e., the total tardiness, is common to all MILP models: Objective Min ∑ n j=1 Tj(1) Since the proposed SMFVM problem under investigation is inspired to a real-life issue of a semiconductor manufacturer, it is worthy to describe how the MILP model captures the practical features of such real issue. The time window ranging in [I min , I max ] represents the time interval in which the machine can be stopped, and a skilled operator can clean the reactor’s chamber. In the real practice, the time window goes from 8:00 am to 6:00 pm, so optimizing the maintenance scheduling issue would mean to place the operator’s starting time (Z) in way that the maintenance completion time is lower than I max and the total tardiness is minimized as well. As the maintenance task basically consists of a cleaning operation, the maintenance duration was modeled as an increasing function of the maintenance starting time. 4.1. MILP 1 This mathematical model was proposed by Costa and FernandezViagas (2022). Beyond the job tardiness Tj, two continuous decision variables (Cj,Ej) and one binary variable Yij are considered. Looking at the notation, a dummy job 0 is included in the set of the preceding jobs. In addition, note that the maintenance activity is handled as an added job (i.e., job n +1). Subject to: ∑ n+1 i=0 Yij =1,j=1,⋯,n+1 (2) ∑ n+1 j=1 Yij ≤1,i=0,1,⋯,n+1 (3) ∑ n j=1 Y0j=1 (4) Ej≥rj+∑ n i=0 Yij,j=1,⋯,n(5) Table 1 Notations and parameters common to all MILP models. Parameter Definition Models and Indices i,j job indices All nnumber of jobs All p j processing time of job jAll:j=1,⋯,n r j release time of job jAll:j=1,⋯,n d j due date of job jAll:j=1,⋯,n I min earliest starting time of maintenance interval All I max latest completion time of maintenance interval All γmaintenance base time All mslope of the linear relationship related to the variable maintenance duration All Ma big number All sij setup time of job j processed after job iMILP1/2/4: i=0,1,⋯, n; j=1,⋯,n MILP3: i=1,⋯,n; j= 1,⋯,n ajsetup time of job j in case it is processed as first MILP3:j=1,⋯,n Note: i=0 is a dummy job. Table 2 Decisions variables common to all MILP models. Variable Definition Models and Indices Yij ∈ {0,1}Binary decision variable: 1 if job j is processed immediately after job i, 0 otherwise. MILP1/2/4: i=0,1, ⋯,n; j=1,⋯,n MILP3: i=1,⋯,n; j=1,⋯,n Xj∈ {0,1}Binary decision variable: if job j is processed at some time before the maintenance interval, 0 otherwise MILP2/3/4:j=1,⋯, n Wj∈ {0,1}Binary decision variable: 1 if job j is processed immediately after the maintenance interval, 0 otherwise MILP3/4:j=1,⋯,n Vj∈ {0,1}Binary decision variable: 1 if job i is processed as last, 0 otherwise MILP3:j=1,⋯,n Ejstarting time of job jMILP1:j=1,⋯,n+1 MILP2/4:j=1,⋯,n Cjcompletion time of job jMILP1:j=1,⋯,n+1 MILP2/3/4:j=1,⋯, n Tjtardiness of job jAll:j=1,⋯,n Zmaintenance starting time MILP2/3/4 Rmaintenance duration MILP2/4 ZC maintenance completion time MILP3 Note: i=0 is a dummy job; job n +1 in MILP1 is the maintenance interval. A. Costa et al. Computers and Operations Research 173 (2025) 106849 3 Ej≥rj+∑ n i=0 sij •Yi(n+1)−M•(1−Y(n+1)j),j=1,⋯,n(6) Ej≥Ci+sij −M•(1−Yij),i=1,⋯,n,j=1,⋯,n(7) Ej≥C(n+1)+∑ n i=0 sij•Yi(n+1)−M•(1−Y(n+1)j),j=1,⋯,n(8) Cj≥Ej+pjj=1,⋯,n(9) C(n+1)≥E(n+1)+γ+m•(E(n+1)−Imin )(10) E(n+1)≥Cj−M•(1−Yij)j=1,⋯,n(11) E(n+1)≥Imin (12) C(n+1)≤Imax (13) Tj≥Cj−djj=1,⋯,n(14) Y(n+1)(n+1)=0 (15) Constraint (2) states that each job must have a predecessor. According to constraint (3), each job can precede one other job at most. Constraint (4) sets at least one job to be processed before the maintenance interval. Constraints (5) and (6) state that each job can be processed after it is released to the system. Specifically, constraint (5) refers to the case that the job is preceded by a real job, while constraint (6) works in the case that the job arrives immediately after the maintenance interval. Similarly, constraints (7) and (8) impose each job to start after the preceding job is completed, in case the preceding job is real or it coincides with the maintenance interval, respectively. Constraint (9) links starting and completion time of each job. Constraint (10) calculates maintenance completion time. Constraint (11) calculates maintenance starting time. Constraints (12) and (13) fix bounds for maintenance starting and completion time, respectively. Constraint (14) calculates tardiness of jobs. Constraints (15) impose the maintenance interval not to precede itself. 4.2. MILP 2 Subject to: ∑ n i=1 Yij =1j=1,⋯,n(16) ∑ n j=1 Yij ≤1i=0,1,⋯,n(17) ∑ n j=1 Xj≥1 (18) Ej≥Z+R+∑ n i=0 sij •Yij −M•Xjj=1,⋯,n(19) Cj≤Z+M•(1−Xj)j=1,⋯,n(20) Z≥Imin (21) Z+R≤Imax (22) R≥γ+m• (Z−Imin)(23) Additional constraints: 5, 7, 9, 14. Constraint (16) states that each job must have a predecessor. According to constraint (17), each job can precede one other job at most. Constraint (18) sets at least one job to be processed before the maintenance interval. In case a job is processed after the maintenance interval, constraint (19) states that its starting time must follow the maintenance completion time. Constraint (20) states that its completion time must precede the maintenance starting time. Constraints (21) and (22) fix bounds for maintenance starting and completion time, respectively. Constraint (23) calculates maintenance duration. 4.3. MILP 3 Subject to: ∑ n j=1 Yij =1−Vii=1,⋯,n(24) ∑ n j=1 Yij =1−Wij=1,⋯,n(25) Cj≥Ci+sij +pj−M•(1−Yij)i=1,⋯,n;j=1,⋯,n(26) Cj≥(rj+aj+pj)•Wjj=1,⋯,n(27) Cj≥(rj+sij +pj)•Yij i=1,⋯,n;j=1,⋯,n(28) Cj≥ZC+(sij +pj)•Yij −M•Xji=1,⋯,n;j=1,⋯,n(29) ZC ≤Imax (30) ZC ≥Z+γ+m• (Z−Imin)(31) ∑ n i=1 Vi=1 (32) ∑ n j=1 Wj=1 (33) Additional constraints: 14, 18, 20, 21. Constraint (24) states that each job must precede another job, unless it is processed as the last. Constraint (25) states that each job must be preceded by another job, unless it is processed as the first. Constraint (26) imposes each job to start after the preceding job is completed. Constraints (27) and (28) state that each job can be processed after it is released to the system. Specifically, constraint (27) is referred to the case the job processed as first, while constraint (28) works otherwise. In case a job is processed after the maintenance interval, constraint (29) states that its starting time must follow the maintenance completion time. Constraint (30) fixes bounds for maintenance starting and completion time, respectively. Constraint (31) calculates maintenance duration. Constraints (32) and (33) impose one only job to be processed as first and as last, respectively. 4.4. MILP 4 Subject to: ∑ n i=1 Xi=1 (34) Ej≥Z+R+∑ n i=0 sij •Yij −M•(1−Wj)j=1,⋯,n(35) Wj≥Yij +Xi−1i=1,⋯,n;j=1,⋯,n(36) Additional constraints: 3, 5, 7, 9, 14, 16, 20, 21, 22, 23. Constraint (34) sets exactly one job to be processed immediately A. Costa et al. Computers and Operations Research 173 (2025) 106849 4 before the maintenance interval. Constraint (35) states that its starting time must follow the maintenance completion time. Constraint (36) identifies the couple of jobs between which maintenance is performed. Table 3 shows the number of constraints as well as constraint equations related to all MILP models. 5. Complexity of MILP models MILP models can be evaluated and compared in terms of size complexity and computational complexity (Demir and ˙ Is¸leyen, 2013). To assess the size complexity of the proposed MILP models, number of binary variables (NBVs), number of continuous variables (NCVs), and number of constraints (NCs) can be taken on as indicators. Table 4 allows comparing the size complexity of the proposed MILP models, by distinguishing between binary and continuous variables. Although MILP1 adopts only a binary variable Yij, it uses a number of NBVs higher than models 2–4. Such finding can be motivated by the fact that, in MILP1, the job indices for Yij take on values from zero to (n +1). However, MILP3 has the highest NBVs, likely due to the four binary variables it needs. As for the continuous variables, MILP1 needs only three variables, but it requires the highest NCVs, such as models 2–4. On the other hand, MILP3 has the least NCVs since it disregards the job starting times Ej as independent variables. In conclusion, it can be noted that MILP2 is the model adopting the least NBVs, while MILP 3 has the least NCVs. As a further insight, it is worth noting that MILP2 and MILP3 have the least and the most NCs, respectively. To further evaluate the MILP models from the size complexity viewpoint, Fig. 1 shows how NCs, NBVs, NCVs and the number of nonzero coefficients (NZCs) as the problem size ranges in step two in [8, 16]. The choice of such problem sizes is motivated by the first part of the experimental analysis (See Sec. 8) in which all MILP models are solved by IBM ILOG CPLEX® V20.1 and compared in terms of efficacy/efficiency related performance indicators. Fig. 1a) confirms that MILP2 makes use of the least NCs, while MILP3 holds a remarkably higher number of constraints. Fig. 1b) highlights the efficiency of MILP2 in terms of NZCs. In general, reducing the number of non-zeros coefficients can be particularly useful because the run-time of many sub-routines in a MIP solver depends on this number. Under the number of binary variables viewpoint, no significant difference emerges (Fig. 1c), even though MILP 2 and MILP3 appear less in need of integer variables, which make any model more complex and challenging to solve. Instead, a notable difference can be observed in Fig. 1d) as MILP3 assures a significantly lower NCVs than the other models. 6. Proposed heuristics This section thoroughly explains the three proposed heuristics developed to solve the SMFVM problem at hand. The first heuristic, denoted as BCH, is a constructive heuristic which obtains a good solution in short CPU time. This heuristic is explained in Section 6.1. This solution can be used as initial solution of more complex heuristics and metaheuristics. In fact, this is the idea of our second proposal, denoted as composite heuristic NCH, and the basis of the last composite heuristic, denoted by MCH. Both heuristics are detailed in Sections 6.2 and 6.3, respectively. Finally, in Section 6.4 we enumerate the heuristics that are reimplemented and adapted to be compared with the proposals. 6.1. Basic constructive heuristic, BCH Starting with the first proposal, BCH constructs a solution by inserting jobs, one by one, at the end of an initially empty partial sequence (Π). Once a job has been inserted at the end of the sequence, this job is removed from the set of unscheduled jobs, and a new job is selected to be placed again at the end of the sequence. The procedure is repeated until n jobs have been placed and then there is no job in the set of unsequenced jobs. In order to select the best job in each iteration, many advances have been achieved in the literature by using tailored indicators which do not depend on the objective function of the problem, but on the characteristics of the job that is introduced (see in this regard e.g., Fernandez-Viagas et al., 2016). Following these recommendations, in the proposed heuristic, we select job α to be placed, according to the following indicator: δj=⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ −pmax +pj 2+n⋅(s π k−1,j−smin)+n⋅max(rj−C π k−1,0),ifTj>0 Ej+pj 2+n⋅(s π k−1,j−smin) + n⋅max(rj−C π k−1,0),otherwise Being j an unscheduled job of the partial solution Π in iteration k, with Π= ( π 1,⋯, π k−1).Then, in each iteration k, job j with minimal δj is placed at the end of Π. This indicator considers the following elements to select the jobs: - Earliness of the new job, Ej: For a job j, its earliness can be defined by Ej=max(0,dj−Cj). It is indirectly related with the objective Table 3 Constraint equations related to each MILP model. MILP1 MILP2 MILP3 MILP4 Const. n. Constr. Eq. Const. n. Constr. Eq. Const. n. Constr. Eq. Const. n. Constr. Eq. 1 (2) 1 (4) 1 (13) 1 (2) 2 (3) 2 (6) 2 (18) 2 (4) 3 (4) 3 (8) 3 (20) 3 (6) 4 (5) 4 (13) 4 (21) 4 (8) 5 (6) 5 (16) 5 (24) 5 (13) 6 (7) 6 (17) 6 (25) 6 (16) 7 (8) 7 (18) 7 (26) 7 (20) 8 (9) 8 (19) 8 (27) 8 (21) 9 (10) 9 (20) 9 (28) 9 (22) 10 (11) 10 (21) 10 (29) 10 (23) 11 (12) 11 (22) 11 (30) 11 (34) 12 (13) 12 (23) 12 (31) 12 (35) 13 (14) 13 (32) 13 (36) 14 (15) 14 (33) Table 4 Number of binary and continuous variables for all milp models. Models Binary variable NBVs Continuous variable NCVs NCs MILP1 Yij n2+ 3n Cj,Ej,Tj3n+ 2 n2+8n+8 MILP2 Yij, Xjn2+ 2n Cj,Ej,Tj,Z,R3n+ 2 n2+7n+ 5 MILP3 Yij, Xj,Wj,Vjn2+ 3n Cj,Tj,Z,ZC 2n+ 2 3n2+5n+ 6 MILP4 Yij, Xj,Wjn2+ 3n Cj,Ej,Tj,Z,R3n+ 2 2n2+7n+ 5 A. Costa et al. Computers and Operations Research 173 (2025) 106849 5 function, since jobs with short earliness times in an iteration k will probably have tardiness in the following iterations, if they are not placed in that iteration. - Processing time of the new job, pj: It has an influence on both the completion time of the new job to be inserted and the completion times of the following inserted jobs. - Set-up time incurred by the new job, s π k−1,j: As in the previous case, it influences the completion times of job j and of the following jobs. Then, (s π k−1,j−smin)indicates the difference between its setup time and the minimal setup time in the shop, defined by smin (i.e., smin = min ∀j,ksjk with j,k∈ {1,⋯,n}). - Tardiness of the jobs, Tj. The indicator prioritizes jobs with tardiness greater than 0 by subtracting pmax (being pmax the maximum processing time in the shop, i.e. pmax =max ∀i,jpij with i∈ {1,⋯,m},j∈ {1, ⋯,n}), since not placing them will directly increase the objective function in the following iterations. - Idle time. The idle time has a direct influence on the completion time of the new job and consequently on the completion times of the following jobs. As this idle time could be reduced by selecting a different job, the indictor tries to minimize it. The idle time is measured by max(rj−C π k−1,0). The complexity of BCH is O(n2) as n iterations are performed and a job is selected in each iteration from the set of unscheduled jobs. This set has a size of n−k+1 in iteration k. 6.2. Neighborhood composite heuristic, NCH After a fast solution has been achieved by BCH, the composite heuristic NCH tries to obtain the best solution in its neighborhood. More specifically, the following three specific local searches are applied to the solution obtained by BCH: •Insertion local search, LS1. This local search is applied to the solution Π obtained in BCH. Each job of this sequence is iteratively removed and tested in each position of the sequence. The job is inserted in the position yielding the best objective function value and the new sequence replaces the iteration sequence. Once all jobs are reinserted, the complete search is repeated until there is no further improvement. Let Π2 denote the sequence obtained by using this procedure. •Pairwise insertion local search, LS2. This local search is applied to the solution Π2 obtained after applying LS1. This procedure is analogous to LS1, but considering pairs of two consecutive jobs, i.e., each pair of two consecutive jobs is removed and reinserted in the best position. Again, the complete search is repeated until there is no more improvement. Let Π3 denote the sequence obtained using this procedure. •Interchange local search, LS3. This local search is applied to the solution Π3 obtained after applying LS2. In this local search, each job is interchanged with each other job in the sequence, and the movement yielding the minimal total tardiness is selected. In this case, the procedure is completed when all jobs are tested and Πʹ denote the final obtained sequence. The complexity of NCH is the maximum complexity between BCH, LS1, LS2, and LS3. BCH has a complexity of O(n2), while LS1, LS2 and LS3 has the same complexity equals to O(k⋅n4), being k the number of iterations without improvements. Hence, the complexity of NCH is O (k⋅n4). 6.3. Multi-start composite heuristic, MCH(λ) Based on NCH, composite heuristic MCH(λ) constructs solutions repeating a procedure similar to NCH. More specifically, the heuristic randomizes the procedure to generate a solution from the BCH heuristic and the LS1, LS2 and LS3 local searches are applied after that. In order to randomize the solution constructed before the local searches, the procedure BCH is applied, but selecting a random job in each iteration among the two jobs with the lowest δj value (instead of selecting the job yielding the lowest δj value). This procedure is repeated λ times, and the best solution is returned. As a consequence, the complexity of MCH(λ)is O(k⋅λ⋅n4). A more detailed explanation of this constructive heuristic MCH(λ) is present below: Πb:= {∅} For each iteration i∈ {1,⋯,λ} Initialization of the initial empty partial sequence and the set of unscheduled jobs: Π:= {∅}and ℧:= {1,2,⋯,n}. NCs NBVs NVCs NZCs Fig. 1. Plots of constraints and variables of the MILP models. A. Costa et al. Computers and Operations Research 173 (2025) 106849 6 For each position k∈ {1,⋯,n} Calculate δj, ∀j∈ {1,⋯,|℧|}. α 1:=Job with minimal δj, ∀j∈ {1,⋯,|℧|}. α 2:=Job with the second smallest value of δj, ∀j∈ {1,⋯,|℧|}. α :=Random job between α 1 and α 2. Insert α in the last position of Π (position k) and remove it from ℧. Π2:=LS1(Π) Π3:=LS2(Π2) Πʹ:=LS3(Π3) If i=0 or Tmax(Πʹ)<Tmax(Πb), then Πb=Πʹ Return Πb 6.4. Implemented heuristics To validate the efficiency of the proposals, we compare them with the most promising heuristics in the related literature. To deal with that, the following heuristics are re-implemented and adapted to the problem under consideration: •ERD: Established as the best static dispatching rule by Costa and Fernandez-Viagas (2022) for the problem under consideration (compared with SPT, LPT, EDD and LPT). •MDD: Established as the best dynamic dispatching rule by Costa and Fernandez-Viagas (2022) for the problem under consideration. It places the job with lowest d*=max(dj,t+pj), with t=max(rj,Cj−1). •MDD2: Proposed variant to adapt MDD to the problem. It places the job with lowest d*=max(dj,t+pj+s π j−1,j), with t=max(rj,Cj−1). •MWSPT: Proposed for 1rj,sij∑wjCj by Chou et al. (2009). To adapt it to the problem, we consider wj=1. •NEHedd. Established as the best NEH heuristic by Costa and Fernandez-Viagas (2022) to the problem under consideration. •NEHedd(TB IT1 ). The heuristic proposed by Fernandez-Viagas and Framinan (2015) for the Fm|prmu|∑Tj. •NEHedd(TB IT2 ). The heuristic proposed by Fernandez-Viagas and Framinan (2015) for the Fm|prmu|∑Tj. •CH_i (∀i∈ {1,⋯,6}): The heuristics proposed by Li et al. (2015) for Fm|prmu|∑Tj. •RI: Proposed by Montoya-Torres et al. (2012) for the 1rj,sijCmax problem. •ATCS: The heuristic proposed by Lee et al. (1997) for the 1sij∑Tj problem. •MATCS: The heuristic proposed by Shin et al. (2002) for the 1rj, sij∑Lmax problem. 7. Benchmark of test cases To generate the benchmark of test cases, the two-phase computational procedure proposed in Costa and Fernandez-Viagas (2022) has been used. In brief, during the first phase, the major job descriptors (i.e., release times, sequence-dependent setup times, processing times, and due dates) are generated through a series of parameters in accordance with Ovacikt and Uzsoy (1994). In the second phase, data regarding the maintenance issue (i.e., Imax,Imin,γ) are yielded by starting from the earliest release dates (ERD) schedule. As the present paper focuses on evaluating both efficiency and efficacy of several heuristic algorithms for solving the SMFVM problem with sequence-dependent setup times and non-zero job release times, the two-phase procedure was carried out by considering six control parameters, regardless of the problem size (i. e., n). In general, the two-phase procedure makes use of a uniform distribution U(1, s) to generate the setup times. Release times are randomly drawn in the range [0, e•LB], where LB is a lower bound on the makespan. The earliest maintenance starting time (Imin) is controlled by parameter h. The latest maintenance completion time (Imax) depends on parameter g, while the minimum maintenance duration (i.e., γ) is a function of parameter l. Finally, the slope coefficient according to which maintenance duration increases with its starting time, is controlled by parameter m. In this paper, a twofold experimental analysis is proposed. The former aims at comparing a large set of heuristic algorithms, also including the proposed algorithms, with the global optima achieved by the proposed MILP models. Indeed, such analysis even allows the evaluation of both efficacy and computational efficiency of the MILP models by means of a series of performance indicators. To this end, a data set of 500 small-sized test problems has been generated as follows. The number of jobs was varied at five levels in the set {8, 10, 12, 14, 16}. For each problem size, 100 instances have been randomly generated by means of the above-mentioned two-phase procedure, in which the six control parameters are randomly selected in the following sets: s∈ { U (1,100), U(1,200)}, e∈ {0.6,1.0,1.4}, h∈{1 4,1 2}, g∈ {3,6}, l∈ {0.1, 0.3}, m∈ {tan(1 8),tan(1 4)}. The latter refers to the experimental analysis for large-sized instances, which aims to again compare several heuristics from the relevant literature and the proposals as well. In this context, a full factorial design of experiments (DOE) has been arranged, conforming to the control parameter values mentioned in the previous analysis. Hence, considering that the problem size was varied in {20, 50, 100, 150, 300} jobs, five control parameters were varied at to levels and one at three levels, as reported in Table 5. Since five instances were randomly generated for each parameter configuration, a total number of 5×2 5 ×3×5 =2,400 instances was built using the two-phase benchmark generation procedure. Although the present paper is inspired by a real-life semiconductor manufacturing problem, motivated by the non-disclosure restrictions imposed by the company the aforementioned problem descriptors are slightly dissimilar from the industrial ones. Specifically, the coefficient of maintenance variability, i.e., “m” is usually smaller and setup times primarily follow a normal distribution with a smaller dispersion than the one used in the testbed. However, it is worth pointing out that a series of test runs performed on the actual problem have revealed the quality of the proposed approach. 8. Experimental results and analysis 8.1. Small-sized problems The experimental analysis presented in this section involves 500 small-sized test problems with a twofold objective. First, we evaluate the efficacy and computational efficiency of the proposed MILP models. Second, we use the global optima achieved by the MILP models to validate the seventeen heuristics from the relevant literature and four new proposals. 8.1.1. Comparing MILP models Conforming to Sec. 7, 100 instances were randomly generated for five classes of problems involving a number of jobs varying from 8 to 16 jobs and solved by IBM ILOG CPLEX V13® commercial software on a Workstation equipped with Win11 OS, Intel i9 X-core processors and 32 Table 5 DOE. Factors and levels of the full factorial design of experiments. Factor Levels sU(1,100) U(1,200) e0.6 1.0 1.4 h1/4 1/2 g3 6 l0.1 0.3 mtan(1/8) tan(1/4) A. Costa et al. Computers and Operations Research 173 (2025) 106849 7 Gb RAM. Fig. 2a shows the average computational time (ACT) in seconds required by each MILP model as the problem size changes and clearly proves that MILP2 and MILP3 outperform the other models as the problems size is greater than 10. As expected, though a time limit of 1,000 s was set on the solver, the average computational time grows more than exponentially and about 400 s on the average are required to converge to the global optimum for a 16-jobs problem, at least. Fig. 2b depicts how the computational time varies in terms of relative percentage deviation over the best result (RPD_time) for each class of problem. It reveals that the efficiency of the MILP model is almost the same until 12 jobs, while an increasing deviation among the models emerges as the problem size grows. Again, MILP 2 and MILP3 can be considered as the most efficient models, while MILP1 appears to be the slowest in solving the scheduling problem at hand. Due to the time limit on the solving time, the gap from the lower bound at convergence was taken on as a further KPI for comparison purposes. The gap is an indicator to assess if the optimal solution is achieved or not, as any solution with zero gap is a global optimum. Fig. 2c shows that 1,000 s is enough to achieve the global optimum when the problem size is 8 or 10, regardless of the specific MILP model. When the problem size increases from 12 to 16 the number of heuristic solutions rises up as well (see also N_heur in Fig. 2d) along with the average percentage gap (Gap_ave) from the lower bound. Both Fig. 2c and d confirm the higher efficacy of MILP3 and MILP2 in solving the problem under investigation than MILP4 and even more MILP1, which appears to be the least suitable model under all the provided KPIs. Interestingly, the two most performing models, i.e., MILP2 and MILP3, holds different features in terms of modelling structure. More precisely, MILP2 is the model assuring the least number of binary variables, while MILP3 needs the least number of continuous variables (see bold values in Table 4). Under these perspectives, NBVs would justify the outperformance of MILP2 in terms of average time to convergence and number of global optima over the other models. However, a counterintuitive finding regards the number of constraints of MILP2 and MILP3, as the former requires the smallest NCs while the latter the largest one over all models; thus, it can be stated that the proposed MILP models are not sensitive to NCs. In conclusion, it can be asserted that MILP2 and MILP 3 are the most preferable models to be considered for solving the complex single machine scheduling problem under investigation. Fig. 3 reveals that MILP2 and MILP 3 outperform the other models under every performance indicator, under quality of solutions and computational time perspectives. Notably, MILP2 achieves a better score when the time to convergence is c taken on as a KPI. Besides, the advantage of MILP 2 and MILP3 over the direct competitors grows as much as the problem size increases and a clear incremental value of over the MILP1 model from Costa and Fernandez-Viagas (2022) emerges in terms of computational efficiency, number of heuristics solutions and average gap from the lower bound. Although the complexity of the scheduling problem in the real-life context does not allow to use any MILP model, it is worth pointing out that global and/or near-optimal solutions provided by a MILP model surely represent a valid support for heuristic algorithms validation. Hence, MILP3 and even more MILP2, which assures a lower computational time in solving the 16-jobs scheduling problem, can be deployed for validation purposes of heuristic and metaheuristic algorithms. For the sake of clarity, the following paragraphs deal with an illustrative example to emphasize the difference of performance between MILP and a well-established heuristic rule for dynamic scheduling problems, i.e., ERD. Let’s consider a SMFVM problem with n =10 jobs, allowed maintenance time interval [I min , I max ] =[763, 1963], maintenance basic duration γ =360, and slope of variable maintenance duration m =tan(0.3). Being the problem data reported in Table 6, MILP and ERD schedules are S 1 =[1 3 9 2 10 4 M 6 7 8 5] and S 2 =[1 2 3 9 4 M 10 6 7 8 5], respectively; M means the maintenance task. The total tardiness related to S 1 is 1,140.14 time units, while the one related to S 2 is equal to 1,314.01 time units. However, the difference between the two solutions can be appreciated by Fig. 3 that depicts the Gantt diagrams for both MILP solution (a) and ERD solution (b), being the grey blocks the Fig. 2. Graphs to compare MILP models. A. Costa et al. Computers and Operations Research 173 (2025) 106849 8 sequence dependent setup times required by each job. Interestingly, though the maintenance duration of the MILP solution is longer than the ERD one, the way the jobs are sequenced assures a better total tardiness than ERD. 8.1.2. Comparing heuristics To validate and assess the performance of the proposed composite heuristics, an extended comparison analysis was carried out by using the same dataset mentioned in the previous sub-section. In particular, the four proposals are compared with the MILP models and seventeen wellknown heuristics from the relevant literature. Table 7 reports the values of four performance indicators for each optimization method and for each class of problems, depending on the problem size. The first KPI is the median relative percentage deviation (MRPD), i.e., the median of the percentage deviations of the total tardiness achieved by each method from the best value, over the provided 100 instances for each class of problems. Then, the number of heuristic solutions (related to MILP models not converging in 1,000 s) and the number of unfeasible solutions (related to heuristics yielding solutions not satisfying the provided maintenance constraints) are considered as another indicator of efficacy. N_opt means the times each method reaches the minimum total tardiness, while ACT is the average computational time (in seconds) of each method over 100 instances. Bold MRPD values are equal to zero and indicate the most performing methods under the quality of solutions viewpoint. As the reader can notice, regardless of the MILP models, three of the proposed composite heuristics (namely NCH, MCH(10) and MCH (20)) assure the least MRPD values, with the exception of NCH for the largest scenario problem with 16 jobs. For the smallest class of problems, CH algorithms are capable of guaranteeing MRPDs equal to zero, while RI provides MRPD performances comparable to the best proposed algorithms for each class of problems. All tested heuristics converge to feasible solutions, thus demonstrating that all of those are suitable for solving the problem under investigation. On the other hand, as expected, for all MILP models the N_heur indicator increases as much as the problem size increases too. However, MILP2 and MILP3 appears again as the best models if N_heur is taken on as performance indicator. Similar considerations for the MILP models can be done whether N_opt indicator is observed. As expected, it reduces with the problem size and still MILP2 and MILP3 ensure the highest values for each scenario problem. Looking at the heuristics, MCH(10) and MCH(20) show the best results in terms of N_opt, along with the RI heuristic, regardless of the specific problem size. NCH emerges as a good heuristic if compared with the rest of the tested methods, but N_opt values confirm a lower efficacy than MCH variants and RI as well for all class of problems. Considering the ACT performance measure, such indicator increases as much as the problem size grows, even if such a tendency comes out only for the MILP Fig. 3. Gantt diagram of a 10-job SMFVM problem: a) S 1 -MILP solution; b) S 2 -ERD solution. Table 6 Illustrative example: job descriptors. j1 2 3 4 5 6 7 8 9 10 r j 47 62 67 576 2011 1260 1293 1969 291 653 p j 84 145 2 61 30 19 38 70 80 108 d j 372 1178 71 466 2192 1267 1524 2101 822 1244 s ij 83 191 189 156 97 106 183 191 1 197 135 62 106 21 11 131 69 131 122 34 41 137 137 89 114 102 148 123 65 28 173 173 63 179 29 187 144 23 104 184 6 177 136 58 117 116 175 188 175 138 133 17 165 57 138 178 123 89 71 14 83 8 4 26 21 28 148 114 179 149 111 34 148 4 82 28 69 81 123 149 28 173 195 134 137 160 54 47 4 182 40 20 148 42 82 79 177 178 184 141 158 83 56 53 10 33 85 114 137 25 A. Costa et al. Computers and Operations Research 173 (2025) 106849 9