1 Introduction

The parallel machine scheduling problem (PMSP) consists of determining a production schedule of jobs in parallel machines, with each job requiring a single operation in one of the machines, while optimizing a given objective such as the minimization of the maximum job completion time (makespan), total tardiness, mean completion time, and maximum tardiness. Three classes of PMSPs have been considered in the literature (Cheng and Sin 1990), namely identical, uniform and unrelated PMSP. The unrelated PMSP (UPMSP) is the most general of the three classes (Torabi et al. 2013) and assumes that the machines perform the same functions, but have different processing velocities, resources or capacities. The UPMSP is often found in real manufacturing and service settings, such as in the textile, chemical, electronic, mechanical and service industries (Ying et al. 2012).

Machine setup times and job due-date constraints are relevant aspects when addressing the UPMSP in practice. As pointed out in the literature, the consideration of sequence- and machine-dependent setup times and due date constraints is important in different industrial and service contexts to derive feasible and effective production schedules (Arnaout et al. 2014). Due-date constraints have broad industrial implications in many manufacturing systems (Lin et al. 2011), as they impose that the due dates of certain jobs from primary customers must not be violated.

In this paper, we consider the UPMSP with due-date constraints and sequence- and machine-dependent setup times. In practice, various parameters involved in this variant, such as job processing and machine setup times, are usually uncertain due to diverse sources of uncertainty such as machine breakdowns, environment changes, worker performance, among other machine and/or human factors (Chyu and Chang 2011; Liao and Su 2017). These uncertainties are natural in production planning and scheduling problems and, if ignored, they can lead to schedules that are infeasible or perform poorly under real conditions (Bougeret et al. 2019). In spite of this, few studies presented thus far in the literature have considered such uncertainties.

1.1 Related work

Different approaches have been used to address uncertain data in scheduling environments, such as sensitivity analysis, fuzzy programing, stochastic programming, and robust optimization (Macedo et al. 2016; Rodríguez et al. 2009; Salmasnia et al. 2015; Tadayon and Smith 2015; González-Neira et al. 2017; Bougeret et al. 2019). Some of these studies considered the single machine scheduling problem (Tadayon and Smith 2015; Bougeret et al. 2019), while others addressed the UPMSP but without explicitly considering due-date constraints. A fuzzy model for the UPMSP with sequence-dependent setup times was proposed in Gharehgozli et al. (2009). The authors considered uncertain processing times and minimized the total weighted flow time and the total weighted tardiness simultaneously. In Chyu and Chang (2011), the authors used the fuzzy theory to address the UPMSP with sequence- and machine-dependent setup times to minimize the makespan and the average tardiness under fuzzy processing times, fuzzy due dates and fuzzy deadlines for the completion of all jobs. A multi-objective UPMSP with sequence and machine-dependent setup times considering uncertainty in processing times and due dates was introduced in Torabi et al. (2013). The authors proposed a fuzzy approach to minimize the total weighted flow time, the total weighted tardiness, and the machine load variation. More recently, the UPMSP was studied in Liao and Su (2017) taking into account the fuzzy processing, release and sequence-dependent setup times when minimizing the makespan.

Stochastic programing and robust optimization have been used to address variants of the PMSP with identical machines. In Xu et al. (2013), the authors addressed a makespan minimization scheduling problem in identical parallel machines, in which uncertain processing times are represented as intervals using a min–max regret scheduling model. Robust optimization approaches were proposed in Seo and Chung (2014) for the identical PMSP with uncertain processing times and minimizing the makespan. Neither of these two papers have considered production setup times or due date constraints. A PMSP variant with sequence-dependent setup times was also addressed in Hu et al. (2016), but without any consideration of due dates. The authors developed a scenario based mixed-integer linear programming (MIP) formulation to consider uncertainty in processing and arrival times when minimizing the makespan. A scenario-based approach was developed in Feng et al. (2016) to take into account uncertainty in processing times, for the makespan minimization scheduling problem in a two-stage hybrid flow shop. The first production stage has only one machine, while the second stage has identical parallel machines. These two papers identified robust schedules using min–max regret models based on the worst case scenario.

The UPMSP with sequence and machine-dependent setup times and due date constraints has been studied by a few authors (Chen 2009; Lin et al. 2011; Zeidi and MohammadHosseini 2015; Chen 2015), but without considering uncertainties in the problem parameters. Different objectives have been addressed for this scheduling problem, such as minimizing the total tardiness (Chen 2009; Lin et al. 2011), the total cost of tardiness and earliness (Zeidi and MohammadHosseini 2015) and the total weighted completion time (Chen 2015). Other papers deal with the UPMSP with sequence and machine-dependent setup times, but without taking into account due date constraints or uncertainties (Ravetti et al. 2007; Arnaout et al. 2014; Nogueira et al. 2014; Avalos-Rosales et al. 2015; Afzalirad and Rezaeian 2016; Salehi Mir and Rezaeian 2016; Sadati et al. 2017; Gomes and Mateus 2017). To the best of our knowledge, there are no studies so far in the literature considering uncertainties in the UPMSP with sequence- and machine-dependent setup times and explicit due date constraints.

1.2 Contributions

In this paper, we contribute to the literature by considering for the first time the UPMSP with due date constraints and sequence- and machine-dependent setup times under the hypothesis of uncertain processing and setup times. Uncertainty is incorporated into the problem via a robust optimization (RO) approach using budgeted uncertainty sets (Ben-Tal and Nemirovski 2000; Bertsimas and Sim 2004; Bertsimas et al. 2011). RO has some advantages over other stochastic approaches, such as: (1) it does not require probability distribution information to describe parameter uncertainty. Information of the data probability distribution may be not available in some real contexts of multiple machine scheduling problems. In this case, managers can define realistic intervals for the uncertain parameter values based on their own experience and the available data; (2) the robust counterpart of an uncertain MIP model can be reformulated as a deterministic MIP depending on the uncertainty set; and (3) it provides a feasible solution (uncertainty-immunized solution) for any parameter realization belonging to a predetermined uncertainty set (Seo and Chung 2014). In the UPMSP, RO can provide robust schedules, which are desirable from a practical perspective because they protect against adverse conditions of the system (Bougeret et al. 2019). We propose two RO models for the addressed UPMSP variant, considering the minimization of the makespan as the objective function. We are not aware of other RO models in the literature for any variant of the UPMSP considering sequence and machine-dependent setup times.

The difficulty of considering the classical RO approaches for the addressed problem is that all the uncertain parameters (processing and/or setup times) related to a given machine need to appear in the same model constraint (Bertsimas and Sim 2004; Sungur et al. 2008; Alem and Morabito 2012). Otherwise, if we have only one uncertain parameter by constraint and apply the classical RO approach using the budgeted uncertainty set, the RO formulation would be equivalent to a deterministic formulation where the uncertain data assumes its worst-case value, making the formulation totally conservative. This is because the robust counterpart is obtained dualizing the protection function inserted into each constraint (see Sects. 3.2 and 3.3 ), and each protection function considers the variation in the uncertain parameters defined in its corresponding constraint only. Hence, to overcome the mentioned difficulty, we first present two deterministic models for the addressed UMPSP variant that are convenient for using RO. Computational experiments using problem instances from the literature were carried out to compare the performance of the proposed RO models. We analyze the impact of the uncertainties to the solutions and verify the corresponding trade-off between cost and risk (robustness) of the solutions. Furthermore, a risk analysis using a Monte-Carlo simulation indicates the potential of the RO models to address the cost-risk trade-off in the addressed UPMSP variant. It is worth mentioning that the developments presented in this paper are not restricted only to the addressed UPMSP variant and hence can also be used for related variants of the PMSP.

1.3 Organization of the paper

The remainder of this paper is organized as follows. Section 2 describes the UPMSP with sequence- and machine-dependent setup times and due-date constraints and presents two MIP formulations for its deterministic (nominal) variant. These formulations are convenient for developing the RO models proposed in Sect. 3. In Sect. 4, we report the results of the computational experiments with the proposed RO approach. Finally, Sect. 5 presents final remarks and discusses perspectives for future research.

2 Problem description and deterministic formulations

In this section, we describe the UPMSP (Sect. 2.1) and present two deterministic mathematical formulations for the problem. The formulations use decision variables that describe job precedences (Sect. 2.2) and decision variables that describe the position of the jobs in the production sequence of the machines (Sect. 2.3).

2.1 The UPMSP

The UPMSP with sequence- and machine-dependent setup times and due-date constraints consists of determining a schedule for a set of jobs \({\mathcal {N}}\) in a set of unrelated parallel machines \({\mathcal {M}}\). All machines have the same functions, but with different resources and capacities. Each job requires a single operation in one of these machines. There is a given due date for finishing the processing of each job in the subset \({\mathcal {B}} \subseteq {\mathcal {N}}\). These jobs are related to primary customers and their due dates cannot be violated.

In the deterministic variant of the problem (also known as nominal problem), all job processing and setup times are assumed to be known in advance. As the machines are unrelated, the processing time to perform the operation of a given job depends on the machine. The same happens for the setup time to perform the operation of a given job, which further depends on the production sequence of the machine. To take into account the setup time of the first job in the production sequence of a given machine, we define the dummy job 0 and the node set \({\mathcal {N}}_0 = {\mathcal {N}} \cup \{0\}\) (Gharehgozli et al. 2009). This dummy job has to be the first job in the sequence of any machine, with null processing time and null setup times from each job to it.

Using the sets defined, we state the following input parameters of the problem:

\({\bar{p}}_{ik}\):

Nominal processing time of job \(i \in {\mathcal {N}}\) in machine \(k \in {\mathcal {M}}\);

\({\bar{s}}_{ijk}\):

Nominal setup time from job \(i \in {\mathcal {N}}_0\) to job \(j \in {\mathcal {N}}\) in machine \(k \in {\mathcal {M}}\);

\(b_i\):

Due date of job \(i \in {\mathcal {B}}\);

V:

Sufficiently large number. For example, V can be equal to the sum of all the processing and setup times.

The objective of the problem is to determine the sequences of jobs in the machines that minimize the production makespan (i.e., the total time required to finish all jobs). Different formulations are available in the literature for the addressed UPMSP variant (Avalos-Rosales et al. 2015; Gomes and Mateus 2017). We adapt these formulations in the remainder of this section, to make them more convenient for incorporating uncertainties via RO.

2.2 Deterministic precedence-based formulation

The addressed UPMSP variant can be formulated as a MIP model using decision variables that describe job precedences. Consider the following decision variables:

\(C_{\mathrm{max}}\):

Completion time of the last processed job;

\(C_{ik}\):

Completion time of job \(i \in {\mathcal {N}}_0\) in machine \(k \in {\mathcal {M}}\);

\(R_{ik}\):

Position of job \(i \in {\mathcal {N}}_0\) in the production sequence of machine \(k \in {\mathcal {M}}\);

\(x_{ijk}\):

1, if job \(j \in {\mathcal {N}}\) is processed immediately after job \(i \in {\mathcal {N}}_0\) in machine \(k \in {\mathcal {M}}\); 0, otherwise;

\(z_{ijk}\):

1, if the processing of job \(i \in {\mathcal {N}}_0\) precedes the processing of job \(j \in {\mathcal {N}}\) in machine \(k \in {\mathcal {M}}\); 0, otherwise.

Notice that we have defined two types of variables to represent the production sequence in the machine, namely \(x_{ijk}\) and \(z_{ijk}\). The difference between them is that \(x_{ijk} = 1\) means that job i precedes job j immediately in the sequence of machine k, while \(z_{ijk} = 1\) means that job i precedes job j, but not necessarily immediately. These two types of variables are necessary to guarantee that all uncertain parameters related to the jobs assigned to a given machine are available in the same constraint, which makes the model convenient for using RO.

Using the decision variables and parameters defined, the deterministic precedence-based formulation is as follows:

$$\begin{aligned} \displaystyle \text{ Minimize } \quad C_{\mathrm{max}} \end{aligned}$$
(1)

subject to:

$$\begin{aligned}&\sum _{i \in {\mathcal {N}}_0: \atop i \ne j} \sum _{k \in {{\mathcal {M}}}} x_{ijk} = 1, \quad \forall j \in {{\mathcal {N}}},\quad \end{aligned}$$
(2)
$$\begin{aligned}&\sum _{ i \in {{\mathcal {N}}}_0: \atop i \ne h} x_{ihk} - \sum _{j \in {{\mathcal {N}}}_0: \atop j \ne h} x_{hjk} = 0, \quad \forall h \in {{\mathcal {N}}}, \, \forall k \in {{\mathcal {M}}},\quad \end{aligned}$$
(3)
$$\begin{aligned}&\sum _{j \in {{\mathcal {N}}}_0} x_{0jk} = 1, \quad \forall k \in {{\mathcal {M}}},\quad \end{aligned}$$
(4)
$$\begin{aligned}&\sum _{i \in {{\mathcal {N}}}} {\bar{p}}_{ik}z_{ijk} + \sum _{i \in {{\mathcal {N}}}} \sum _{ l \in {{\mathcal {N}}}_0: \atop l\ne j } {\bar{s}}_{lik} x_{lik} z_{ljk} \le C_{jk}, \quad \forall j \in {{\mathcal {N}}}, \, \forall k \in {{\mathcal {M}}},\quad \end{aligned}$$
(5)
$$\begin{aligned}&C_{ik} \le b_i, \quad \forall i \in {{\mathcal {B}}}, \, \forall k \in {{\mathcal {M}}},\quad \end{aligned}$$
(6)
$$\begin{aligned}&C_{\mathrm{max}} \ge C_{ik}, \quad \forall i \in {{\mathcal {N}}}, \, \forall k \in {{\mathcal {M}}},\quad \end{aligned}$$
(7)
$$\begin{aligned}&R_{jk} \ge R_{ik}+1 - |{{\mathcal {N}}}|\left( 1-x_{ijk}\right) , \quad \forall i, j \in {\mathcal {N}}, \, i \ne j, \, \forall k \in {{\mathcal {M}}}, \quad \end{aligned}$$
(8)
$$\begin{aligned}&Vz_{ijk} \ge R_{jk}-R_{ik}-V\left[ 2-\sum _{l\in {{\mathcal {N}}}_0}x_{lik}-\sum _{l \in {{\mathcal {N}}}_0} x_{ljk}\right] , \quad \forall i, j \in {{\mathcal {N}}}, \, i \ne j, \, \forall k \in {{\mathcal {M}}},\quad \end{aligned}$$
(9)
$$\begin{aligned}&2x_{ijk} \le z_{iik}+z_{jjk}, \quad \forall i, j \in {{\mathcal {N}}}, \, i \ne j, \, \forall k \in {{\mathcal {M}}},\quad \end{aligned}$$
(10)
$$\begin{aligned}&\sum _{k \in {{\mathcal {M}}}} z_{iik} = 1, \quad \forall i \in {{\mathcal {N}}},\quad \end{aligned}$$
(11)
$$\begin{aligned}&C_{0k} = 0, \quad \forall k \in {{\mathcal {M}}}, \end{aligned}$$
(12)
$$\begin{aligned}&C_{ik} \ge 0, \quad \forall i \in {{\mathcal {N}}}, \, \forall k \in {{\mathcal {M}}}, \end{aligned}$$
(13)
$$\begin{aligned}&0 \le R_{ik} \le |{{\mathcal {N}}}|, \quad \forall i \in {{\mathcal {N}}}, \, \forall k \in {{\mathcal {M}}}, \end{aligned}$$
(14)
$$\begin{aligned}&x_{ijk}, z_{ijk} \in \{0,1\}, \quad \forall i, j \in {{\mathcal {N}}}_0, \, \forall k \in {{\mathcal {M}}}. \end{aligned}$$
(15)

The objective function (1) consists of minimizing the total time required to process all jobs (makespan). Constraints (2)–(4) are the flow constraints: (2) ensure that each job j must be processed in exactly one machine; (3) impose that each job h processed in a machine has an immediate predecessor and an immediate successor; and (4) ensure that the dummy job 0 is the immediate predecessor of the first actual job processed in each machine. Note that in accordance with these constraints, the dummy job 0 must immediately precede the first and immediately succeed the last actual jobs in each of the \(|{{\mathcal {M}}}|\) machines.

Constraints (5) determine the completion time of the jobs assigned to each machine. For a given job \(j \in {\mathcal {M}}\) and machine \(k \in {\mathcal {M}}\), the first term on the left-hand side of (5) computes the processing times of all jobs that are processed before j in the sequence of machine k, while the second term computes all the setup times corresponding to changing from job l to job i, such that l immediately precedes i in the sequence, and l and i are processed before j. This computation requires the product of variables \(x_{lik} z_{ijk}\), as the setup times depend on the immediate precedence of jobs in the machine (expressed by \(x_{lik}\)) and we are interested only in those jobs that are processed before j and in the same machine (expressed by \(z_{ljk}\)). In fact, we have \(z_{ljk} = 1\) for any job l that is processed before j in machine k; thus, \(x_{lik} z_{ljk} = 1\) if and only if l is the job that immediately precedes i in the same machine (notice that constraints (2) guarantee that there must be exactly one job in \(l \in {\mathcal {N}}\) that immediately precedes node i). If job l does not precede j in machine k, then \(z_{ljk} = 0\) and the product of variables is equal to zero.

Constraints (6) ensure that the due dates of jobs of primary customers are met. The makespan is computed by constraints (7), together with the objective function. Note that \(C_{\mathrm{max}}\) corresponds to the completion time of the last processed job. Constraints (8) link the variables \(R_i\) and \(x_{ijk}\) based on two jobs i and j such that i immediately precedes j. Constraints (9) link variables \(z_{ijk}\) to \(R_i\) and \(x_{ijk}\) based on the jobs that are processed before job j in machine k. To determine if job i precedes job j, job i needs to be processed before job j (i.e., \(R_{jk}>R_{ik}\)) and both jobs need to be processed in the same machine k. This second requirement is guaranteed by the expression inside the brackets on the right-hand side of the constraints, which is zero only if i and j have an immediate predecessor in machine k (and hence both are processed in the same machine). If in addition \(R_{jk} > R_{ik}\), then variable \(z_{ijk}\) assumes the value of 1 (recall that it is a binary variable).

Constraints (10) are added to the formulation to impose that two different jobs i and j are predecessors of themselves if they are processed in the same machine. Constraints (11) impose that job i is predecessor of itself in a unique machine. A null value for the completion time of job 0 in each machine is set by constraints (12). Finally, constraints (13), (14) and (15) determine the type and domain of the decision variables.

The formulation (1)–(15) is a non-linear model because of the product of variables in constraints (5). Nevertheless, this product of binary variables can be linearized by adding binary variables to the model, together with a set of linear constraints. Let \(y_{lijk}\) be a new binary variable that assumes the value of 1 if and only if job l immediately precedes job i and both jobs (l and i) are processed before job j in machine k. The following set of constraints corresponds to the linearization of constraints (5):

$$\begin{aligned}&\sum _{i \in {{\mathcal {N}}}} {\bar{p}}_{ik}z_{ijk} + \sum _{i \in {{\mathcal {N}}}} \sum _{l\in {{\mathcal {N}}}_0} {\bar{s}}_{lik}y_{lijk} \le C_{jk}, \quad \forall j \in {{\mathcal {N}}}, \, \forall k \in {{\mathcal {M}}}, \quad \end{aligned}$$
(16)
$$\begin{aligned}&y_{lijk} \le x_{lik}, \quad \forall i, j \in {{\mathcal {N}}}, \, \forall l \in {{\mathcal {N}}}_0, \, \forall k \in {{\mathcal {M}}}, \quad \end{aligned}$$
(17)
$$\begin{aligned}&y_{lijk} \le z_{ljk}, \quad \forall i, j \in {{\mathcal {N}}}, \, \forall l \in {{\mathcal {N}}}_0, \, \forall k \in {{\mathcal {M}}}, \quad \end{aligned}$$
(18)
$$\begin{aligned}&y_{lijk} \ge x_{lik}+z_{ljk}-1, \quad \forall i, j \in {{\mathcal {N}}}, \, \forall l \in {{\mathcal {N}}}_0, \, \forall k \in {{\mathcal {M}}}. \quad \end{aligned}$$
(19)

Note that if \(x_{lik}=1\) and \(z_{ljk}=1\), then constraints (19) imply that variable \(y_{lijk}\) is equal to 1. Otherwise, variable \(y_{lijk}\) is equal to 0. Thus, by replacing constraints (5) with the set of constraints (16)–(19), we obtain a MIP formulation based on decision variables that describe the job precedences.

One clear disadvantage of the proposed linearization would be the addition of a large number of binary variables. Fortunately, because of constraints (19) and variables \(x_{lik}, z_{ljk}\) being binary, the set of constraints (16)–(19) is satisfied for the binary variables \(y_{lijk}\) if this set is also satisfied for the continuous variables \(y_{lijk}\) in the interval [0, 1]. Therefore, the same number of binary variables in the non-linear formulation is maintained in the MIP model, although there is an increase in the number of continuous variables.

2.3 Deterministic position-based formulation

We can also model the UPMSP variant addressed in this paper as a MIP model using decision variables that describe the position of the jobs in the production sequence of the machines. The following formulation assumes that each machine k has a vector of fixed size, hereafter referred to as permutation, that assigns jobs to positions of the production sequence of the machine. Let \({\mathcal {P}}\) be the set of positions in the permutation of a machine. In addition to variables \(C_{\mathrm{max}}\) and \(C_{ik}\) defined in Sect. 2.2, we further define the following decision variables:

\(x_{hik}\):

1, if job \(i \in {\mathcal {N}}\) is assigned to position \(h \in {\mathcal {P}}\) of the permutation used in machine \(k \in {\mathcal {M}}\); 0, otherwise;

\(\Theta _{hk}\):

completion time of the job assigned to position \(h \in {\mathcal {P}}\) of the permutation used in machine \(k \in {\mathcal {M}}\).

The position-based formulation is posed as follows:

$$\begin{aligned} \text{ Minimize } \qquad C_{\mathrm{max}} \end{aligned}$$
(20)

subject to:

$$\begin{aligned}&\sum _{h \in {{\mathcal {P}}}} \sum _{k \in {{\mathcal {M}}}} x_{hjk} = 1, \quad \forall j \in {{\mathcal {N}}},\quad \end{aligned}$$
(21)
$$\begin{aligned}&\sum _{h \in {{\mathcal {P}}}} \sum _{k \in {{\mathcal {M}}}} x_{h0k} = |{{\mathcal {M}}}|,\quad \end{aligned}$$
(22)
$$\begin{aligned}&\sum _{j \in {{\mathcal {N}}}} x_{hjk} \le 1, \quad \forall h \in {{\mathcal {P}}}, \, \forall k \in {{\mathcal {M}}},\quad \end{aligned}$$
(23)
$$\begin{aligned}&\Theta _{hk} \ge \sum _{ m \in {{\mathcal {P}}}: \atop m \le h } \sum _{j \in {{\mathcal {N}}}} {\bar{p}}_{jk}x_{mjk} + \sum _{ m \in {{\mathcal {P}}}: \atop m \le h } \sum _{i \in {{\mathcal {N}}}_0}\sum _{j \in {{\mathcal {N}}}} {\bar{s}}_{ijk}x_{(m-1)ik}x_{mjk}, \quad \forall h \in {{\mathcal {P}}}, \, \forall k \in {{\mathcal {M}}},\quad \end{aligned}$$
(24)
$$\begin{aligned}&C_{jk} \ge \Theta _{hk}-V(1-x_{hjk}), \quad \forall h \in {{\mathcal {P}}}, \, \forall j \in {{\mathcal {N}}}, \, \forall k \in {{\mathcal {M}}},\quad \end{aligned}$$
(25)
$$\begin{aligned}&C_{jk} \le b_j, \quad \forall j \in {{\mathcal {B}}}, \, \forall k \in {{\mathcal {M}}},\quad \end{aligned}$$
(26)
$$\begin{aligned}&\sum _{i \in {{\mathcal {N}}}_0} x_{(h+1)ik} \le \sum _{j \in {{\mathcal {N}}}_0} x_{hjk}, \quad \forall h \in {{\mathcal {P}}}, \, \forall k \in {{\mathcal {M}}},\quad \end{aligned}$$
(27)
$$\begin{aligned}&x_{0jk}=0, \quad \forall j \in {{\mathcal {N}}}, \, \forall k \in {{\mathcal {M}}},\quad \end{aligned}$$
(28)
$$\begin{aligned}&x_{00k} = 1, \quad \forall k \in {{\mathcal {M}}},\quad \end{aligned}$$
(29)
$$\begin{aligned}&\Theta _{0k} = 0, \quad \forall k \in {{\mathcal {M}}},\quad \end{aligned}$$
(30)
$$\begin{aligned}&C_{0k} = 0, \quad \forall k \in {{\mathcal {M}}},\quad \end{aligned}$$
(31)
$$\begin{aligned}&C_{\mathrm{max}} \ge C_{ik}, \quad \forall i \in {{\mathcal {N}}}, \, \forall k \in {{\mathcal {M}}},\quad \end{aligned}$$
(32)
$$\begin{aligned}&C_{ik}, \Theta _{ik} \ge 0, \quad \forall i \in {{\mathcal {N}}}, \, \forall k \in {{\mathcal {M}}},\quad \end{aligned}$$
(33)
$$\begin{aligned}&x_{hjk} \in \{0,1\}, \quad \forall h \in {{\mathcal {P}}}, \, \forall j \in {{\mathcal {N}}}, \, \forall k \in {{\mathcal {M}}}. \quad \end{aligned}$$
(34)

The objective function (20) consists of minimizing the production makespan \(C_{\mathrm{max}}\). Constraints (21) ensure that each job j is assigned to a unique position of exactly one machine. Constraints (22) guarantee the assignment of the dummy job 0 to a single position of the permutations used in the machines. Constraints (23) ensure that at most one job can be assigned to position h of the permutation used in machine k, hence avoiding the overlapping of jobs. Constraints (24) determine the completion time of the job assigned to position h of the permutation used in machine k. The first term on the right-hand side of these constraints accumulates the processing times of all jobs assigned to the first h positions of the permutation used in machine k. The second term accumulates the setup times related to the jobs in these first h positions. Notice that we use the product \(x_{(m-1)ik} x_{mjk}\) to verify the immediate precedence of jobs. Given two jobs i and j, we have that i immediately precedes j only if \(x_{(m-1)ik} x_{mjk} = 1\) for a given \(m \le h\).

Constraints (25) determine the completion time of job j in the permutation of machine k. Note that if job j is assigned to position h of the permutation of machine k, then the second term on the right-hand side of the constraints is equal to zero and thus the completion time of job j becomes the completion time of the job assigned to this position. Constraints (26) ensure that the due dates of the jobs from the primary customers are met. Constraints (27) allow the assignment of a job in position \(h+1\) of the permutation of machine k only if there is a job assigned to position h of this permutation. They are used to break symmetry in the solution space. Constraints (28) avoid assigning a job at position 0 of the permutations as this position is uniquely used by the dummy job according to constraints (29). Constraints (30) and (31) set initial values to variables \(\Theta _{0k}\) and \(C_{0k}\), respectively. Finally, constraints (32) impose lower bounds to the makespan and constraints (33) and (34) define the type and domain of the decision variables.

Constraints (24) can be linearized similarly to constraints (5). Let \(y_{hijk}\) be the binary variable that assumes the value of 1 if job i is assigned to position \(h-1\) and job j is assigned to position h of the permutation of machine k. The following set of constraints describes the linearization of constraints (24):

$$\begin{aligned}&\Theta _{hk} \ge \sum _{ m \in {{\mathcal {P}}}: \atop m \le h } \sum _{j \in {{\mathcal {N}}}} {\bar{p}}_{jk}x_{mjk}+\sum _{ m \in {{\mathcal {P}}}: \atop m \le h} \sum _{i \in {{\mathcal {N}}}_0} \sum _{j \in {{\mathcal {N}}}} {\bar{s}}_{ijk}y_{mijk}, \, \nonumber \\&\quad \forall h \in {{\mathcal {P}}}, \, \forall k \in {{\mathcal {M}}}, \end{aligned}$$
(35)
$$\begin{aligned}&y_{hijk} \le x_{(h-1)ik}, \quad \forall h \in {{\mathcal {P}}}, \, \forall i \in {{\mathcal {N}}}_0, \, \forall j \in {{\mathcal {N}}}, \, \forall k \in {{\mathcal {M}}}, \end{aligned}$$
(36)
$$\begin{aligned}&y_{lijk} \le x_{ljk}, \quad \forall h \in {{\mathcal {P}}}, \, \forall i \in {{\mathcal {N}}}_0, \, \forall j \in {{\mathcal {N}}}, \, \forall k \in {{\mathcal {M}}}, \end{aligned}$$
(37)
$$\begin{aligned}&y_{hijk} \ge x_{(h-1)ik} + x_{hjk} - 1, \quad \forall l \in {{\mathcal {P}}}, \, \forall i \in {{\mathcal {N}}}_0, \, \forall j \in {{\mathcal {N}}}, \, \forall k \in {{\mathcal {M}}}. \end{aligned}$$
(38)

Constraints (38) ensure that variable \(y_{hij}^k\) is equal to 1 if both variables \(x_{(h-1)ik}\) and \(x_{hjk}\) are also equal to 1. From these constraints, we observe that the set of constraints (35)–(38) is satisfied for the binary variables \(y_{hij}^k\) if this set is also satisfied for the continuous variables \(y_{hij}^k\) in the interval [0, 1]. Hence, we obtain a MIP formulation for the problem by replacing constraints (24) with the set of constraints (35)–(38).

3 Robust optimization approaches

This section presents RO models for the UPMSP with uncertain processing and setup times based on the nominal MIP models of Sect. 2. RO is a mathematical programming based methodology to model and solve optimization problems under uncertain parameters (Ben-Tal et al. 2009; Bertsimas et al. 2011, 2015). It has been successfully applied in different contexts, such as production-inventory problems (Bertsimas and Thiele 2006; De Ruiter et al. 2017), portfolio management (Bertsimas et al. 2018), emergency medical systems (Bertsimas and Ng 2019), terminal traffic flow (Ng et al. 2020), vehicle routing (Munari et al. 2019; De La Vega et al. 2019; De La Vega et al. 2020) and scheduling (Ng et al. 2017; Bougeret et al. 2019). Different from the stochastic programming methodology, RO does not require a complete knowledge of the probability distributions of the random parameters. If they are known, they can be used to build the so-called uncertainty set (Ben-Tal et al. 2009). This set contains all possible realizations of the uncertain parameters and it can be represented by a box, a polyhedron, an ellipsoid or intersections of these sets (Gorissen et al. 2015). RO is a methodology based on worst-case analysis and involves determining here-and-now decisions that optimize some criteria and are insensitive to the possible variations of the uncertain parameters (Bertsimas and Sim 2004; Ben-Tal et al. 2009). The decisions prescribed by the RO methodology ensure 100% of solution feasibility if the uncertain parameter values belong to the uncertainty set, i.e., the solution is deterministically feasible. Even if the uncertainty set does not contain all possible realizations of the uncertain parameters, the RO methodology generally ensures solution feasibility with high probability (Bertsimas and Sim 2003, 2004).

3.1 Uncertain parameters and uncertainty set for the robust UPMSP

The uncertain parameters, namely processing time \({\tilde{p}}_{ik}\) and setup time \({\tilde{s}}_{ijk}\), are modeled as independent, limited and symmetric random variables that assume values in the intervals \([{\bar{p}}_{ik}-{\hat{p}}_{ik},{\bar{p}}_{ik}+{\hat{p}}_{ik}]\) and \([{\bar{s}}_{ijk}-{\hat{s}}_{ijk},{\bar{s}}_{ijk}+{\hat{s}}_{ijk}]\), respectively, where \({\bar{p}}_{ik}\) and \({\bar{s}}_{ijk}\) represent the expected (nominal) values, and \({\hat{p}}_{ik}\) and \({\hat{s}}_{ijk}\) represent the maximum deviations (from their nominal values) allowed for the possible realizations of the random variables. We define the primitive random variables \(\xi _{ik}\) and \(\eta _{ijk}\), which assume values in the interval \([-1,1]\), and rewrite the original random variables as \({\tilde{p}}_{ik}={\bar{p}}_{ik}+{\hat{p}}_{ik}\xi _{ik}\) and \({\tilde{s}}_{ijk}={\bar{s}}_{ijk}+{\hat{s}}_{ijk}\eta _{ijk}\). For the sake of simplicity, we assume that the processing and setup times of all jobs in all machines are uncertain.

We restrict the possible realizations of the primitive random variables \(\xi _{ik}\) and \(\eta _{ijk}\) to cardinality-constrained sets defined for each machine k. Thus, the risk is distributed among the production schedules of each machine and, consequently, the highly unlikely scenario in which all the uncertainties of the processing and setup times are concentrated in a single machine is excluded. Thus, the budget of uncertainty \(\Gamma _k\) defines the number of uncertain parameters allowed to vary from their respective nominal values in machine k. The uncertainty sets are defined as follows, for each machine k:

$$\begin{aligned} {{\mathcal {U}}}_k(\Gamma _k)= & {} \left\{ ({\varvec{\xi }},{\varvec{\eta }})\in {{\mathbb {R}}}^{{(1+ |{{\mathcal {N}}}_0|)|{{\mathcal {N}}}|}} : -1 \le \xi _{ik} \le 1, \, \forall i \in {{\mathcal {N}}}; \right. \nonumber \\&\left. -1 \le \eta _{ijk} \le 1, \, \forall i \in {{\mathcal {N}}}_0, \forall j \in {{\mathcal {N}}}; \, \sum _{i \in {\mathcal {N}}} | \xi _{ik} | + \sum _{i \in {\mathcal {N}}_0} \sum _{j \in {\mathcal {N}}} | \eta _{ijk} | \le \Gamma _k \right\} . \end{aligned}$$
(39)

Notice that as the uncertainty set depends on the budget of uncertainty \(\Gamma _k\), the larger the number of uncertain parameters \(\xi _{ik}\) and \(\eta _{ijk}\) allowed to vary, the higher the conservatism of the robust approach. Note also that the nominal and Soyster problems (Soyster 1973) result from assigning values to \(\Gamma _k\), for each \(k \in {{\mathcal {M}}}\), equal to 0 and \(|{{\mathcal {N}}}|+|{{\mathcal {N}}}_0| |{{\mathcal {N}}}|\), respectively. Indeed, in the nominal problem, none of the uncertain parameters deviates from their nominal value, while in the Soyster problem, all of them attain their worst case.

3.2 Robust precedence-based formulation

We now develop a RO model for the addressed UPMSP under uncertainty, based on the nominal MIP model defined in Sect. 2.2 and using the uncertainty set define in equation (39). The robust counterpart of the constraints (16) can be written as follows:

$$\begin{aligned} \sum _{i \in {{\mathcal {N}}}} \left[ {\bar{p}}_{ik} z_{ijk}+\sum _{ l \in {{\mathcal {N}}}_0 \atop l \ne j } {\bar{s}}_{lik} y_{lijk}\right] + {\mathcal {B}}_k^j({\varvec{z}}, {\varvec{y}}, \Gamma _k) \le C_{jk}, \quad \forall j \in {{\mathcal {N}}}, \, \forall k \in {{\mathcal {M}}}, \end{aligned}$$
(40)

where the \({\mathcal {B}}_k^j({\varvec{z}}, {\varvec{y}}, \Gamma _k)\) define the primal protection function. For a given solution \(({\varvec{z}}^{\star },{\varvec{y}}^{\star })\), the protection function \({\mathcal {B}}_k^j({\varvec{z}}^{\star }, {\varvec{y}}^{\star }, \Gamma _k)\) of constraint (j, k) is equivalent to the following linear optimization model:

$$\begin{aligned}&\max _{{\varvec{\xi }} \ge 0, {\varvec{\eta }} \ge 0} \left\{ \sum _{i \in {{\mathcal {N}}}} {\hat{p}}_{ik} z_{ijk}^{\star } \xi _{ik} + \sum _{i \in {{\mathcal {N}}}} \sum _{ l \in {{\mathcal {N}}}_0 \atop l \ne j } {\hat{s}}_{lik} y_{lijk}^{\star } \eta _{lik} : \right. \nonumber \\&\left. \quad \xi _{ik} \le 1, \quad \forall i \in {{\mathcal {N}}},\right. \nonumber \\&\left. \quad \eta _{lik} \le 1,\quad \forall l \in {{\mathcal {N}}}_0, \, \forall i \in {{\mathcal {N}}}, \right. \nonumber \\&\left. \quad \sum _{i \in {{\mathcal {N}}}} \xi _{ik}+ \sum _{i \in {{\mathcal {N}}}}\sum _{ l \in {{\mathcal {N}}}_0 \atop l \ne j } \eta _{lik} \le \Gamma _k \right\} . \end{aligned}$$
(41)

By duality, we can rewrite (41) as

$$\begin{aligned}&\min _{ {\varvec{\alpha }} \ge 0, {\varvec{\beta }} \ge 0, {\varvec{\lambda }} \ge 0 } \left\{ \sum _{i \in {{\mathcal {N}}}} \alpha _{ijk}+ \sum _{i \in {{\mathcal {N}}}}\sum _{ l \in {{\mathcal {N}}}_0 \atop l \ne j } \beta _{lijk} + \Gamma _k \lambda _{jk} : \right. \nonumber \\&\left. \quad \alpha _{ijk} + \lambda _{jk} \ge {\hat{p}}_{ik} z_{ijk}^{\star }, \quad \forall i \in {{\mathcal {N}}}, \right. \nonumber \\&\left. \quad \beta _{lijk}+\lambda _{jk} \ge {\hat{s}}_{lik} y_{lijk}^{\star }, \, l \in {{\mathcal {N}}}_0, \, l \ne j, \, i \in {{\mathcal {N}}} \right\} , \end{aligned}$$
(42)

where the decision variables \(\alpha _{ijk}\), \(\beta _{lijk}\) and \(\lambda _{jk}\) are the dual variables associated with the primal optimization problem (41). Replacing constraints (16) with (40) in the MIP model of Sect. 2.2, we obtain the following RO model for the addressed UPMSP under uncertainty:

$$\begin{aligned} \text{ Minimize } \qquad C_{\mathrm{max}} \end{aligned}$$
(43)
$$\begin{aligned} &{\text{subject\, to}}: \\& \qquad \begin{aligned}&\text {constraints: (2)-(4), (6)-(15), (17)-(19)}, \end{aligned} \end{aligned}$$
(44)
$$\begin{aligned}&\sum _{i \in {{\mathcal {N}}}} \left[ {\bar{p}}_{ik} z_{ijk}+\sum _{l \in {{\mathcal {N}}}_0 \atop l \ne j } {\bar{s}}_{lik} y_{lijk}\right] + \sum _{i \in {{\mathcal {N}}}} \alpha _{ijk}+ \sum _{i \in {{\mathcal {N}}}} \sum _{ l \in {{\mathcal {N}}}_0 \atop l \ne j } \beta _{lijk} + \Gamma _k \lambda _{jk} \nonumber \\&\quad \le C_{jk}, \quad \forall j \in {{\mathcal {N}}}, \, \forall k \in {{\mathcal {M}}}, \end{aligned}$$
(45)
$$\begin{aligned}&\alpha _{ijk} + \lambda _{jk} \ge {\hat{p}}_{ik} z_{ijk}, \quad \forall i, j \in {{\mathcal {N}}}, \, \forall k \in {{\mathcal {M}}}, \end{aligned}$$
(46)
$$\begin{aligned}&\beta _{lijk} + \lambda _{jk} \ge {\hat{s}}_{lik} y_{lijk}, \quad \forall l \in {{\mathcal {N}}}_0, \quad \forall i, j \in {{\mathcal {N}}}, \nonumber \\&\quad l \ne j, \quad \forall k \in {{\mathcal {M}}}, \end{aligned}$$
(47)
$$\begin{aligned}&\lambda _{jk} \ge 0, \quad \forall j \in {{\mathcal {N}}}, \, \forall k \in {{\mathcal {M}}}, \end{aligned}$$
(48)
$$\begin{aligned}&\alpha _{ijk} \ge 0, \quad \forall i, j \in {{\mathcal {N}}}, \, \forall k \in {{\mathcal {M}}}, \end{aligned}$$
(49)
$$\begin{aligned}&\beta _{lijk} \ge 0, \quad \forall l \in {{\mathcal {N}}}_0, \, \forall i, j \in {{\mathcal {N}}}, \, l \ne j, \, \forall k \in {{\mathcal {M}}}. \end{aligned}$$
(50)

The objective function (43) consists of minimizing the makespan. Constraints (44) have already been explained and correspond to the constraints of the nominal MIP model. The set of constraints (45)–(50) is obtained from the robust counterpart (40), where \({\mathcal {B}}_k^j({\varvec{z}}, {\varvec{y}}, \Gamma _k)\) is defined in (42). Note that there is no need for explicitly adding the minimization of (42) in model (43)–(50), as we are only concerned with guaranteeing the feasibility of constraints (45). Indeed, if there is a solution that satisfies (45), then the minimum of (42) also satisfies these constraints.

3.3 Robust position-based formulation

We can develop another RO model for the addressed UPMSP variant, associated to the nominal MIP model of Sect. 2.3 based on decision variables that describe the position of the jobs in the production sequence of each machine. To formulate this robust model, we replace the nominal parameters in constraints (35) by their respective random variables, similarly to the development presented in the previous subsection. Using the uncertainty set (39), the robust counterpart of the constraints (35) can be stated as follows:

$$\begin{aligned} \Theta _{hk}\ge & {} \sum _{ m \in {\mathcal {P}}: \atop m \le h } \sum _{j \in {{\mathcal {N}}}} {\bar{p}}_{jk}x_{mjk} + \sum _{ m \in {\mathcal {P}}: \atop m \le h }\sum _{i \in {{\mathcal {N}}}_0}\sum _{j \in {{\mathcal {N}}}}{\bar{s}}_{ijk}y_{mijk} + \nonumber \\&{\mathcal {B}}_k^h({\varvec{x}}, {\varvec{y}}, \Gamma _k),\quad \forall k \in {{\mathcal {M}}}, \, \forall h \in {{\mathcal {P}}}, \end{aligned}$$
(51)

where the primal protection function for a given solution \(({\varvec{x}}^{\star },{\varvec{y}}^{\star })\), \({\mathcal {B}}_k^h({\varvec{x}}^{\star }, {\varvec{y}}^{\star }, \Gamma _k)\), is given by the following linear optimization model:

$$\begin{aligned}&\max _{ {\varvec{\xi }} \ge 0, {\varvec{\eta }} \ge 0 } \left\{ \sum _{ m \in {\mathcal {P}}: \atop m \le h } \sum _{j \in {{\mathcal {N}}}} {\hat{p}}_{jk} x_{mjk}^{\star } \xi _{jk} + \sum _{ m \in {\mathcal {P}}: \atop m \le h } \sum _{i \in {{\mathcal {N}}}_0}\sum _{j \in {{\mathcal {N}}}} {\hat{s}}_{ijk} y_{mijk}^{\star } \eta _{ijk}: \right. \nonumber \\&\left. \quad \xi _{jk} \le 1, \quad \forall j \in {{\mathcal {N}}}; \right. \nonumber \\&\left. \quad \eta _{ijk} \le 1,\quad \forall i \in {{\mathcal {N}}}_0, \, \forall j \in {{\mathcal {N}}}; \right. \nonumber \\&\left. \quad \sum _{ j \in {{\mathcal {N}}} } \xi _{jk} + \sum _{i \in {{\mathcal {N}}}_0} \sum _{j \in {{\mathcal {N}}}} \eta _{ijk} \le \Gamma _k \right\} . \end{aligned}$$
(52)

Applying the duality technique to primal protection function (52), we can rewrite it as follows:

$$\begin{aligned}&\min _{ {\varvec{\gamma }} \ge 0 , {\varvec{\vartheta }} \ge 0 , {\varvec{\mu }} \ge 0} \left\{ \sum _{ j \in {{\mathcal {N}}}} \gamma _{jhk} + \sum _{ i \in {{\mathcal {N}}}_0} \sum _{j \in {{\mathcal {N}}}} \vartheta _{ijhk} +\Gamma _k \mu _{hk}: \right. \nonumber \\&\left. \quad \gamma _{jhk} + \mu _{hk} \ge \sum _{ m \in {\mathcal {P}}: \atop m \le h } {\hat{p}}_{jk} x_{mjk}^{\star }, \, \quad \forall j \in {{\mathcal {N}}}, \right. \nonumber \\&\left. \quad \vartheta _{ijhk} +\mu _{hk} \ge \sum _{ m \in {\mathcal {P}}: \atop m \le h } {\hat{s}}_{ijk} y_{mijk}^{\star }, \quad \forall i \in {{\mathcal {N}}}_0, \, \forall j \in {{\mathcal {N}}} \right\} , \end{aligned}$$
(53)

where the decision variables \(\gamma _{jhk}\), \(\vartheta _{ijhk}\) and \(\mu _{hk}\) are the dual variables associated with the constraints of the inner optimization problem of primal protection function (52). Therefore, the RO model for the addressed UPMSP under uncertainty, associated to the nominal position-based MIP model of Sect. 2.3 can be stated as follows:

$$\begin{aligned}&\text {Minimize} \qquad C_{\mathrm{max}}. \end{aligned}$$
(54)

subject to:

$$\begin{aligned}&\text {constraints: (21){-}(23), (25){-}(34), (36){-}(38) }. \end{aligned}$$
(55)
$$\begin{aligned}&\Theta _{hk} \ge \sum _{ m \in {\mathcal {P}}: \atop m \le h } \sum _{j \in {{\mathcal {N}}}} {\bar{p}}_{jk}x_{mjk} + \sum _{ m \in {\mathcal {P}}: \atop m \le h } \sum _{i \in {{\mathcal {N}}}_0}\sum _{j \in {{\mathcal {N}}}}{\bar{s}}_{ijk}y_{mijk} + \sum _{ j \in {{\mathcal {N}}}} \gamma _{jhk} + \sum _{ i \in {{\mathcal {N}}}_0} \sum _{j \in {{\mathcal {N}}}} \vartheta _{ijhk} +\Gamma _k \mu _{hk}, \nonumber \\&\forall k \in {{\mathcal {M}}}, \, \forall h \in {{\mathcal {P}}}, \end{aligned}$$
(56)
$$\begin{aligned}&\gamma _{jhk} + \mu _{hk} \ge \sum _{m \in {\mathcal {P}}: \atop m \le h } {\hat{p}}_{jk} x_{mjk}, \, \forall j \in {{\mathcal {N}}}, \, \forall h \in {{\mathcal {P}}}, \, \forall k \in {{\mathcal {M}}}, \end{aligned}$$
(57)
$$\begin{aligned}&\vartheta _{ijhk} +\mu _{hk} \ge \sum _{ m \in {\mathcal {P}}: \atop m \le h } {\hat{s}}_{ijk} y_{mijk}, \, \forall i \in {{\mathcal {N}}}_0, \, \forall j \in {{\mathcal {N}}}, \forall h \in {{\mathcal {P}}}, \, \forall k \in {{\mathcal {M}}}, \end{aligned}$$
(58)
$$\begin{aligned}&\gamma _{jhk} \ge 0, \quad \forall j \in {{\mathcal {N}}}, \, \forall k \in {{\mathcal {M}}}, \, \forall h \in {{\mathcal {P}}}, \end{aligned}$$
(59)
$$\begin{aligned}&\vartheta _{ijhk} \ge 0, \quad \forall i \in {{\mathcal {N}}}_0, \, \forall j \in {{\mathcal {N}}}, \, \forall k \in {{\mathcal {M}}}, \, \forall h \in {{\mathcal {P}}}. \end{aligned}$$
(60)
$$\begin{aligned}&\mu _{hk} \ge 0, \quad \forall k \in {{\mathcal {M}}}, \, \forall h \in {{\mathcal {P}}}, \end{aligned}$$
(61)

3.4 Other objective functions

The RO models presented in Sects. 3.2 and 3.3 (precedence-based and position-based formulations) can be easily modified to deal with other criteria, such as minimizing total tardiness or the maximum tardiness. This is done by simply adding auxiliary (slack) variables to constraints (6) and (26) of the nominal models and by appropriately changing the model objective functions. For instance, to minimize the total tardiness in the precedence-based formulation, we can include the variable \(T_{ik}\) to represent the tardiness of job i in machine k. Then, we replace constraints (6) with

$$\begin{aligned} T_{ik} \ge C_{ik} - b_i, \quad \forall i \in {{\mathcal {B}}}, \, \forall k \in {{\mathcal {M}}}, \end{aligned}$$

and the objective function (1), with the minimization of \(\sum _{i \in {{\mathcal {B}}}} \sum _{k \in {{\mathcal {M}}}}T_{ik}\). Note that only jobs with due date (jobs in set \({{\mathcal {B}}}\)) can present tardiness.

4 Computational experiments

The goal of this section is threefold: first, to compare the computational performance of the precedence-based robust model and the position-based robust model (Sect. 4.2); second, to expose the benefits of considering parameter uncertainties into the problem (Sect. 4.3); third, to illustrate the impact of the uncertainties on the structure of the scheduling solutions (Sect. 4.4). All instances and parameter values used in the computational experiments are described in Sect. 4.1. The models were implemented in C++ programming language and solved using the general-purpose optimization software IBM CPLEX version 12.7, with its default configuration. A Linux PC with a CPU Intel Core i7 3.4 GHz and 16.0 GB of memory was used to run the experiments. The stopping criterion was due to either the elapsed time exceeding the time limit of 3600 s or the relative optimality gap becoming smaller than \(10^{-4}\).

4.1 Instances and parameter values

We carried out the computational experiments using adapted instances from the literature. We used four sets of instances, namely A, B1, B2 and B3, which are based on other problem instances from the literature. The first set (A) is based on the instances used in Chen (2009) and Lin et al. (2011) for the deterministic UPMSP with sequence- and machine-dependent setup times and due date constraints. We selected 16 original instances from Chen (2009) and Lin et al. (2011). Using these instances, we perform preliminary computational experiments and evaluate the efficiency of the CPLEX solver on the robust MIP models within the time limit. Given the difficulty of solving large-scale instances within the time limit using CPLEX, we present results with instances limited to at most 10 jobs and 4 machines. More specifically, we selected the first \(|{\mathcal {M}}|\) machines and \(|{\mathcal {N}}|\) jobs of each instance, where \(|{\mathcal {M}}| {\in } \{2, 4\}\) and \(|{\mathcal {N}}| {\in } \{8, 10\}\), totaling 64 instances in set A.

Sets B1, B2 and B3 are based on instances available on the webpage of the Scheduling Research Virtual Center (http://schedulingresearch.com/) for the deterministic UPMSP with sequence- and machine-dependent setup times (Arnaout et al. 2010, 2014), but without considering due date constraints. Therefore, for these instances, we generated the due dates of the jobs as in Chen (2009) and Lin et al. (2011) using an uniform distribution in the range \([ C_m\cdot (1-\tau -R/2), C_m\cdot (1-\tau +R/2)]\), in which \(\tau \in \left[ 0.4, 0.8\right]\), \(R \in \left[ 0.4, 1\right]\) and \(C_m\) is calculated as follows:

$$\begin{aligned} C_m={\bigg (}\sum _{j\in {{\mathcal {N}}}}\sum _{k\in {{\mathcal {M}}}}(p_{jk}+\frac{\sum _{i\in {{\mathcal {N}}}}s_{ijk}}{|{\mathcal {N}}|})/|{\mathcal {M}}|{\bigg )}/|{\mathcal {N}}|. \end{aligned}$$
(62)

Set B1 considers instances in which the processing times dominate the setup times. Set B2 considers instances in which the setup times dominate the processing times. Finally, set B3 considers instances with balanced processing and setup times. We selected five instances from Arnaout et al. (2010, 2014) for each pair machine-job (\(|{\mathcal {M}}|-|{\mathcal {N}}|\)), with \(|{\mathcal {M}}| {\in } \{2, 4\}\) and \(|{\mathcal {N}}| {\in } \{8, 10\}\), totaling 20 instances in each of these sets.

Table 1 summarizes the sets of instances, which are publicly available at http://www.dep.ufscar.br/munari/upmsp. Column Modification describes the changes carried out in the original instances. The processing and setup times of these instances are used as nominal values of the corresponding parameters in the definition of the uncertainty set. To incorporate uncertainty, we defined \(\delta\) as the percentage of maximum allowed deviation of the processing and setup times in relation to their nominal values, corresponding to \(\delta =\) \(30\%\), \(40\%\) and \(50\%\). Thus, \({\hat{p}}_{ik} = \delta {\bar{p}}_{ik}\) and \({\hat{s}}_{ijk} =\delta {\bar{s}}_{ijk}\). The budgets of uncertainty were considered integers from zero to five, i.e., \(\Gamma _1=\cdots =\Gamma _k=\Gamma = 0, 1, 2, 3, 4, 5\).

Table 1 Characteristics of the sets of instances
Full size table

4.2 Computational performance of the robust models

In this section, we compare the computational performance of the precedence- and position-based robust models. For this, we use performance profiles (Dolan and Moré 2002), which are briefly explained as follows. Given a set \({{\mathcal {P}}}\) of instances and a set \({{\mathcal {F}}}\) of solution approaches, let \(gap_{fp}\) be the gap of the solution obtained for instance p using approach f. The value P(f, q) (y-axis) when \(q > 0\) (x-axis) indicates the fraction of instances for which the approach f provides solutions with a gap within a factor of \(2^{q}\) of the best obtained gap, i.e., the fraction of instances for which \(gap_{fp} + \epsilon \le 2^{q} \cdot \min _{\begin{array}{c} f' \in {{\mathcal {F}}} \end{array}} \{gap_{f'p}+\epsilon \}\), where \(\epsilon\) is a sufficiently small value set as 0.01. The performance profile curves for each of the robust models are shown in Fig. 1, from which we can infer the following for a given p instance:

  • If we want to obtain a feasible solution with the best optimality gap, it is better to solve the position-based robust model. This is because at \(q=0.0\), CPLEX obtains feasible solutions with the best gaps in about 96% of the instances, using the position-based robust model. That percentage was just over 78% for the precedence-based robust model.

  • If we want to obtain a feasible solution with gap within a factor of \(2^{q}\) for values of \(q \in [0.1, 2.4]\), it is preferable also to solve the position-based robust model. For those values of the factor q, the position-based robust model curve is always above the precedence-based robust model curve, which means that the first model has a higher chance of offering better quality solutions.

  • For values of the q factor greater than 2.4, both robust models offer solutions within the same factor \(2^{q}\) as the two curves overlap.

Therefore, based on these observations, we conclude that solving the position-based robust model is the best alternative to obtain feasible solutions with better gaps.

Fig. 1
figure 1

Performance profile based on optimality gap

Full size image

Tables 2 and 3 summarize the average computational results. The tables present the total number of instances (Inst.) in each group (row of the table), the number of infeasible instances (Inf.), the number of instances solved to optimality (#Opt.), the percentage of instances solved to optimality (%Opt.), the average objective function value (Avg. OF), the average gap in percentage (Avg. gap) and the average elapsed time in seconds (Avg. time) for both RO models proposed in this paper. Tables 6 and 7 in Appendix A present the same results in a more detailed way, grouped by number of jobs and machines.

Table 2 Average computational results for different values of \(\Gamma\)
Full size table
Table 3 Average computational results for different values of \({\delta }\)
Full size table

The results in Tables 2 and 3 confirm that the position-based robust model leads to a better overall performance than the precedence-based robust model for the problem instances used in these experiments. On average, CPLEX solved 85.75% of the instances to optimality with the position-based model, while with the precedence-based model it solved 69.53%, within the limit of 3600 s. Furthermore, the average gap and computational time are 3.1 and 4.4 times higher for the precedence-based model than for the position-based model.

From Tables 2 and 3, we also observe that, for higher values of \(\Gamma\) and \({\delta }\), more instances become infeasible. The average gaps and computational times also increase, indicating that the instances become more challenging. Hence, the number of instances with a proven optimal solution tends to decrease as \(\Gamma\) and \({\delta }\) increase. For example, the average number of instances solved to proven optimality with the precedence-based model is 372 for \(\Gamma = 0\) (out of 372) and 187 for \(\Gamma = 5\) (out of 372). Similarly, for the same model, the number of instances solved to optimality drops from 555 to 477 (out of 744) when \({\delta }\) increases from 0.3 to 0.5. Thus, considering uncertainty in the problem clearly makes it more difficult to solve using the proposed models.

4.3 Trade-off between cost and risk

In this section, we analyze the trade-off between cost and risk of the RO solutions for different problem instances, exposing the benefits of incorporating parameter uncertainties into the problem. For this purpose, we determine the price of robustness (PoR), the empirical probability of constraint violation (Risk) and the expected cost of the solution (Exp. Cost) (i.e., the expected makespan of the solution).

Let \(x^{{{\delta }},{\Gamma }}\) be the optimal solution for a given deviation \({{\delta }}\) and budget of uncertainty \({\Gamma }\), obtained from the position-based formulation. The PoR is evaluated as \(\frac{z(x^{{{\delta }},{\Gamma }})-z^{}}{z^{}}\cdot 100\%\), in which \(z(x^{{{\delta }},{\Gamma }})\) is the optimal objective cost (i.e., the optimal makespan) of the robust model and z is the optimal objective function cost of the deterministic model.

The Risk is determined via a Monte Carlo simulation that randomly generates a sufficiently large number of realizations for the random variables and tests the feasibility of a fixed (given) solution. The Monte Carlo simulation was performed by generating random realizations for the processing and setup times in the half-intervals \([{\bar{p}}_{ik},{\bar{p}}_{ik}+{\hat{p}}_{ik}]\) and \([{\bar{s}}_{lik},{\bar{s}}_{lik}+{\hat{s}}_{lik}]\), respectively. To perform the simulation, 10,000 different uniformly distributed samples were generated and, for each sample of the simulation, we verified if the solution was infeasible for at least one realization of each sample (out of the 10,000 generated). After performing all simulation iterations, we counted the number of samples for which the solution was infeasible, which was divided by the total number of samples, to obtain the estimated risk. The expected cost (Exp. Cost) of the solutions was calculated as the average makespan of these 10,000 generated samples (i.e., we sum the makespan of all the samples and divide the total sum by the number of samples).

Table 4 shows the average objective function cost (OF) of the robust model, the expected cost of the solution (Exp. Cost), the price of robustness (PoR) and the risk for the different sets of instances with a deviation of \(50\%\) (i.e., \({\delta }=0.5\)) – experiments using \({\delta }=0.3\) and \({\delta }=0.4\) show similar overall results. Table 8 in Appendix A presents the same results as in Table 4, but they are detailed for different numbers of jobs and machines. Note that, in general, most of the instances present solutions with low risk when the number of uncertain parameters that can assume their worst case is greater than two (i.e., \(\Gamma > 2\)). For the solutions in which the risk is equal to zero, the objective function cost increases by less than 50% with respect to the objective function cost of the deterministic problem. For example, the average risk of instances of set B1 with 10 jobs and 2 machines considering that \(\Gamma =0, 1, 2\) uncertain parameters achieve their worst case is 76.16%, 16.09% and 8.43%, respectively. When \(\Gamma =3\), the risk decreases to zero while the cost of the solution increases by 17.68%.

Table 4 Average objective function cost (OF), expected cost of the solution (Exp. Cost), price of robustness (PoR), and empirical probability of constraints violation (Risk) for the different sets of instances with \({\delta }=0.5\)
Full size table

The objective function cost and the expected cost of the solutions increase for higher values of \(\Gamma\). However, the increase of the expected cost is slower than the increase of the objective function cost. Thus, for most instances with \(\Gamma =0\), the expected cost of the solutions is higher than the objective function cost. On the other hand, for \(\Gamma > 2\), the expected cost of the solutions is smaller than the objective function cost in most of the instances. These results suggest that ignoring the impact of the uncertainties (with \(\Gamma = 0\)) could provide infeasible solutions in practice violating the due date of the customers (as indicated by the risk) or solutions with a cost higher than desired (as indicated by the expected cost higher than the objective function cost). Figure 2 shows the difference between the objective function cost and the expected cost (OF − Exp. Cost) for instances with 8 jobs and 2 machines. Notice that small values of \(\Gamma\) provide solutions that underestimate the empirical actual cost of the solutions, while high values of \(\Gamma\) provide solutions that overestimate this measure.

Fig. 2
figure 2

Difference between the objective function cost and the expected cost of the solutions for instances with 8 jobs and 2 machines

Full size image

4.4 Impact of uncertainties

To illustrate the impact of the uncertainties on the problem solutions, we describe the results of an instance (arbitrarily chosen) from set B3, which has balanced processing and setup times. The instance has 2 machines and 8 jobs, in which three of these jobs are from primary customers and thus their due dates cannot be violated. The third column of Table 5 shows these due dates (jobs 4, 5 and 7).

In this experiment, we used processing and setup time deviations corresponding to \(50\%\), and \(\Gamma =0,1,2,3\). We first solved the proposed RO models to obtain robust solutions for each different value of \(\Gamma\). Then, we analyzed the impact of considering scenarios with a different number of uncertain parameters assuming their worst-case values, namely \(\Gamma ' = 0,1,2,3\), for each obtained solution with a value of \(\Gamma\). For instance, for the robust solution obtained with \(\Gamma =2\), we verify the performance of this solution in scenarios where \(\Gamma '=0,1,2,3\) uncertain parameters attain their worst-case deviations.

Table 5 shows the earliest completion times of jobs 4, 5 and 7 from primary customers, and the makespan \(C_{\mathrm{max}}\), for each of the four values of \(\Gamma '= 0,1,2,3\) in the each of the four robust solutions obtained by considering \(\Gamma = 0,1,2,3\) (last four columns of the table). For example, the value 273 highlighted in bold in the last column of the table corresponds to the earliest completion time of job 4 when \(\Gamma '=0\) parameters attain their worst case value in an optimal solution provided by the RO models with \(\Gamma =3\). If the completion time of a job violates its due date, its value is underlined in the table.

Table 5 Impact of uncertainties on the solutions of the illustrative example for different values of \(\Gamma\)
Full size table

Note that as expected, for \(\Gamma ' = 0\) (first four lines of the table), all solutions obtained by the RO models for different values of \(\Gamma\) are indeed feasible. However, when \(\Gamma ' = 1\) (next four lines of the table), the RO solution obtained for \(\Gamma = 0\) (i.e., the deterministic/nominal model) becomes infeasible, because the completion time of job 4 (399 in the fourth column of the table) becomes higher than the due date of job 4 (398 in the third column of the table). In fact, we can observe that for \(\Gamma ' > \Gamma\), all solutions are infeasible, as the due date of at least one job is violated. As a consequence, the deterministic model solution (\(\Gamma =0\)) becomes infeasible when at least one uncertain parameter assumes the worst case deviation (i.e., for \(\Gamma '>0\)).

Observe in the table that the solution values (\(C_{\mathrm{max}}\)) increase as the values of \(\Gamma\) and \(\Gamma '\) increase. For example, the makespan of the solution for \(\Gamma =0\) and \(\Gamma '=0\) (497) is 13.8% smaller than the makespan of the solution for \(\Gamma =3\) and \(\Gamma '=0\) (566). In both cases we have \(\Gamma '=0\), but the solution for \(\Gamma =3\) has a higher makespan because it is obtained considering up to three uncertain parameters assuming their worst case values. The solution value for \(\Gamma =3\) is 13.8% worse to be uncertainty-immunized (protected) against these three parameters, even if the actual values of these parameters may not be at their worst case deviations. Similarly, the solution value for \(\Gamma =3\) and \(\Gamma '=0\) (566) is 22.4% better than the one for \(\Gamma =3\) and \(\Gamma '=3\) (693).

Figure 3 shows the impact of considering \(\Gamma ' > \Gamma\) in some solutions of Table 5. The white boxes indicate setup times; the blue boxes indicate processing times and the jobs; the green boxes indicate the uncertain parameters actually assuming their worst case values; and the red boxes correspond to the infeasibility of the job due dates. Figure 3a shows the (deterministic) solution obtained by the RO models for \(\Gamma = 0\). Machine \(k=1\) processes jobs 3, 1, 4 and 6, while machine \(k=2\) processes jobs 7, 5, 2 and 8. Figure 3b shows that this deterministic solution becomes infeasible for \(\Gamma '=1\) if the first setup time of machine \(k=1\) increases, as it makes the completion time of job 4 higher than its due date. To avoid this infeasibility, we can use the RO models with \(\Gamma = 1\) to obtain the solution given in Fig. 3c, which has a different production sequence of jobs in machine \(k=1\). However, if the number of uncertain parameters assuming their worst case deviations increases to \(\Gamma '=2\), this solution also becomes infeasible, violating the due date of job 5 (see Fig. 3d). A solution obtained with \(\Gamma = 2\) avoids such infeasibility, as presented in Fig. 3e, which has a new assignment of jobs to machines and different production sequences. Finally, this solution becomes infeasible as well if up to three parameters attain their worst-case (\(\Gamma '=3\)), as presented in Fig. 3f, in which the due date of job 7 is violated. Figure 3g shows a feasible solution for this last scenario, obtained using the RO models with \(\Gamma =3\), in which jobs 4, 5 and 7 (the ones with due-date constraints) are processed first in the machines, protecting the production scheduling against uncertainties, but at the expense of a higher production makespan. Therefore, the increase of \(\Gamma\) values in the RO models changes the schedule configurations to provide more protected solutions, at the cost of higher makespans.

Fig. 3
figure 3

Solutions of the illustrative example for different values of \(\Gamma\) and \(\Gamma '\)

Full size image

5 Conclusions

We presented a robust optimization approach for the UPMSP with due-date constraints and sequence- and machine-dependent setup times under uncertain processing and setup times. We proposed two robust optimization models based on mixed integer programming models of the deterministic problem. The robust precedence-based model uses decision variables that describe the precedences of jobs, while the robust position-based model uses decision variables that describe the position of the jobs in the production sequence of each machine. Both models are suitable for incorporating uncertainties in the job processing times and in the machine setup times, using the robust optimization paradigm.

Computational results using instances from the literature and a Monte-Carlo simulation showed that the robust models represent the problem appropriately and lead to effective and robust schedules, when solved by general purpose optimization software. These results also indicated that the models can be useful for analyzing the impact of the uncertainties and the trade-off between robustness and conservativeness of the solutions, leading to managerial insights that can bring benefits in real contexts. For instance, the results suggest that the risk is substantially reduced for relatively small values of \(\Gamma\), even considering large values of \({\delta }\). These robust schedules can be useful for risk-averse managers, as the cost increases of these solutions are not too high. Managing these decisions in a tractable way and under uncertainty is often a challenge in practice. Furthermore, it was observed that ignoring the parameter uncertainties can result in infeasible schedules or in schedules with higher makespans. Regarding the computational performances observed for the two models, CPLEX was able to solve a larger number of instances to optimality using the robust position-based model than when using the robust precedence-based model.

Using the proposed models, we were able to find solutions for small instances only, considering a reasonable time limit. Hence, an interesting line of future research would be to develop effective methods to solve medium and large instances, such as meta-heuristics and tailored exact methods based on the problem decomposition. Particularly, the heuristics and meta-heuristics proposed in the literature to solve the deterministic version of the problem could be extended to solve the robust version. It is worth mentioning that the two proposed robust optimization models can be easily modified to deal with other criteria, such as minimizing total tardiness or the maximum tardiness. Another promising line of research would be to investigate how to adapt the models to consider other uncertain parameters in the UPMSP, such as in the due dates. Future research could also explore other approaches to cope with uncertainties, such as two-stage stochastic programming with recourse, fuzzy programming techniques, adjustable robust optimization, robust optimization with recourse, risk-neutral and risk-averse stochastic programming techniques.