Minimization of maximum lateness on parallel machines with a single server and job release dates

Abstract

This paper addresses the problem of scheduling independent jobs with release dates on identical parallel machines with a single server. The goal consists in minimizing the maximum lateness. This is a realistic extension of the traditional parallel machine scheduling problem with a single server, in which all jobs are assumed to be available at the beginning of the schedule. This problem, referred to as $P,S1|r_j|L_{max}$, has various applications in practice. To date, research on it has focused on complexity analysis. To solve small-sized instances of the problem, we present two mixed-integer-programming formulations, along with a valid inequality. Due to the ${\mathcal {N}}{\mathcal {P}}$-hard nature of the problem, we propose a constructive heuristic and two metaheuristics, namely a General Variable Neighborhood Search (GVNS) and a Greedy Randomized Adaptive Search Procedures, both using a Variable Neighborhood Descent as an intensification operator. In the experiments, the proposed algorithms are compared using a set of new instances generated randomly with up to 500 jobs, in line with the related literature. It turns out that GVNS outperforms by far the other approaches.

1 Introduction

Parallel machine scheduling problems have been widely studied in the literature (Mokotoff 2001). Among all these problems, the parallel machine scheduling with a single server (PSS) has received much attention over the last 2 decades. In the PSS problem, it is considered that the server is in charge of the setup operation of jobs. This setup operation can be also considered as a loading and/or unloading operation of a job on a particular machine (Bektur and Saraç 2019; Hamzadayi and Yildiz 2017; Kim and Lee 2012). Indeed, in the classical parallel machine scheduling problem, it is assumed that the jobs are ready to be executed without prior setup. However, this assumption is not always satisfied in practice where industrial systems are more flexible. For more information about scheduling with setup times, readers can refer to Allahverdi and Soroush (2008).

The PSS problem has many industrial applications. In container terminals, Bish (2003) showed that the multiple-crane-constrained vehicle scheduling and location problem is similar to the PSS problem, where crane loading/unloading operations represent the setup times, crane represent the server, each container corresponds to a job, and vehicles corresponds to machines. The objective is to minimize the maximum turnaround time of a ship, which can represent the makespan. In the printing industry, Huang et al. (2010) considered a set of printing machines that must be set up by a team before printing orders on machines. The authors stated that the setup times are sequence dependent. They considered the problem as a dedicated PSS problem. The objective function involved the minimization of the makespan. In robotic cells and in the semiconductor industry, it is necessary to share a single server (or robot), by a number of machines to carry out machine setups. Then job processing is executed automatically and independently by the individual machines (see Kim and Lee 2012). In supply chain optimization, Torjai and Kruzslicz (2016) studied a biomass truck scheduling problem that originated from a real-life herbaceous biomass supply chain. The authors considered it as an identical PSS problem, for which two objective functions have to be minimized: the number of machines and the idle times. The authors stated that the identical trucks represent the identical parallel machines in charge of delivering biomass from satellite storage locations to a central bio-refinery operating a single unloader (the single server). They considered two assumptions regarding the server. The unload operation of the server has a unit time length for each trip and idle periods are not allowed for it. In the plastic injection industry, Bektur and Saraç (2019) considered a set of plastic injection machines, which involve a team of workers who must work together to set up (clean, prepare, etc.) orders on machines. The team is considered as a single server. The authors considered it as an unrelated PSS problem. The objective function involved the minimization of the total weighted tardiness. In healthcare, Hsu et al. (2020) studied a scheduling problem of anaesthesia operations in operating rooms. The authors considered operating rooms as machines, and operations as jobs. Each operation consists of two parts, anaesthesia operation and surgical operation. They assumed that only a single anaesthetist is available for carrying out all anaesthesia operations across the available rooms. The objective is to minimize the makespan.

In this paper, we investigate an identical PSS (IPSS) problem by taking into account job release dates. The objective is to minimize the maximum lateness. Following the standard $\alpha |\beta |\gamma$ classification scheme for scheduling problems known as the Graham triplet (Graham et al. 1979), our problem can be denoted as $P,S1|r_j|L_{max}$, where P represents identical parallel machines, S1 represents the single server, $r_j$ is the release date of job j, and $L_{max}$ is the maximum lateness.

In the scheduling literature, only a limited number of works addressed the problem $P,S1|r_j|L_{max}$. Among them, Hall et al. (2000) showed that the problem $P2,S1|s_j=1|L_{max}$ is unary ${\mathcal {N}}{\mathcal {P}}$-hard and that the earliest-due-date rule can solve optimally the more general problem with an arbitrary number of machines with unit processing times ($P,S1|p_j=1|L_{max}$) in $O(n \log n)$. Brucker et al. (2002) showed that the problem $P2,S1|r_j=1|L_{max}$ is unary ${\mathcal {N}}{\mathcal {P}}$-hard. However, regarding the problem $P|r_j|L_{max}$, without considering the single server, the studies have considered sequence-dependent setup times. We are not aware of any recent work suggesting solution methods for the problem $P,S1|r_j|L_{max}$. A goal of our paper aims at bridging this gap, and to generalize the problem $P|r_j|L_{max}$.

The problem $P,S1|r_j|L_{max}$ is ${\mathcal {N}}{\mathcal {P}}$-hard since it is a generalization of the problem $P2,S1|p_j,r_j=1|L_{max}$. However, only small-sized instances can be solved optimally, and meta/heuristics are generally required. We therefore suggest: (1) a constructive heuristic; (2) a Variable Neighborhood Descent (VND); (3) a metaheuristic based on General Variable Neighborhood Search (GVNS); (4) a metaheuristic relying on Greedy Randomized Adaptive Search Procedures (GRASP). Both GVNS and GRASP employ VND as an intensification operator. Such choices are in line with the fact that many metaheuristics have been proposed for different variants of the IPSS problem, namely: simulated annealing (Kim and Lee 2012; Hasani et al. 2014b; Hamzadayi and Yildiz 2017; Bektur and Saraç 2019), genetic algorithm (Abdekhodaee et al. 2006; Huang et al. 2010; Hamzadayi and Yildiz 2017), tabu search (Kim and Lee 2012; Alharkan et al. 2020; Bektur and Saraç 2019), ant colony optimization (Arnaout 2017), geometric particle swarm optimization (Alharkan et al. 2020), iterative local search (Silva et al. 2019), and worm optimization algorithm (Arnaout 2021). To the best of our knowledge, VND, GVNS and GRASP have not been adapted to scheduling problems involving a single server. This might appear as surprising, given the success of that kind of methods for industrial scheduling problems (Respen et al. 2016; Thevenin and Zufferey 2019). In particular, our GVNS and GRASP approaches are based on various neighborhood structures and inherent diversification mechanisms (namely, a construction phase for GRASP and a shaking phase for GVNS). Such features obviously favor the escape from local optima, and thus the search space is likely to be efficiently explored. Indeed, in line with the findings in Thevenin et al. (2017), a strong exploration ability appears to be appropriate for scheduling problems involving several parallel machines.

The main contributions of this paper are the following. First, we provide two mixed-integer-programming (MIP) formulations, along with a valid inequality for the problem $P,S1|r_j|L_{max}$. Second, we propose for the first time dedicated solution methods, namely a constructive heuristic, a VND algorithm, and two metaheuristics (GVNS and GRASP). Finally, numerical results are provided for reasonable computing times (with respect to the literature and to the industrial practice), including a comparison with an exact method using a well-known commercial solver.

The remainder of this paper is organized as follows. Section 2 surveys the related literature. In Sect. 3, after introducing the problem, we present two Mathematical formulations along with a valid inequality. In Sect. 4, a streamline heuristic and two metaheuristics are proposed. Numerical experiments are performed in Sect. 5. Finally, concluding remarks are made in Sect. 6.

2 Literature review

Despite its importance in practice, the problem $P,S1|r_j|L_{max}$ has not received much attention in the recent publications. However, the literature on closely related problems gives us some insights on how to deal with the problem $P,S1|r_j|L_{max}$. We will see that the following ingredients have been widely employed: MIP formulations, greedy heuristics and metaheuristics, which motivates us to propose the same ingredients (see Sects. 3, 4) to tackle the problem $P,S1|r_j|L_{max}$.

In this section, we present a comprehensive literature review considering the PSS (PSS) problem, with different machine environments and objective functions. To date, most of the related works considering the PSS problem assume that all jobs are available at the beginning of the schedule (i.e., no release date is considered) and are limited to two machines. Table 1 summarizes the useful notation. The literature is characterized by three research streams, namely: complexity results (Sect. 2.1), the case of two machines (Sect. 2.2), and the case of an arbitrary number of machines (Sect. 2.3). Next, we discuss the literature related to the problem $P|r_j|L_{max}$ without a single server (Sect. 2.4). Finally, a classification of the papers related to the IPSS (Sect. 2.5).

Table 1 Notation used throughout the paper

2.1 Complexity results

Kravchenko and Werner (1997) showed that the problems $P,S1|p_j,s_j=1|C_{max}$ and $P2,S1|p_j,s_j=s|IT$ are unary ${\mathcal {N}}{\mathcal {P}}$-hard. Kravchenko and Werner (1998) proposed polynomial-time algorithms and some complexity results for the cases of one server, as well as k servers with $k <m$. Later, Hall et al. (2000) extended the previous studies and presented new complexity results and heuristics for many objective functions of the PSS problem, namely: $C_{max}$, $L_{max}$, $\sum w_jC_j$, $\sum C_j$, $\sum w_jT_j$, $\sum T_j$, $\sum w_jU_j$, and $\sum U_j$. For the case of parallel dedicated machines, Glass et al. (2000) addressed the problem $PD,S1||C_{max}$. They showed that it is ${\mathcal {N}}{\mathcal {P}}$-hard in the strong sense, even in the case where all setup times and all processing times are equal.

2.2 Case with two machines

Three objective functions (to be minimized) have been mainly considered, namely: makespan ($C_{max}$), total machine idle time (IT) and total completion time ($\sum C_j$). Koulamas (1996) showed that the problem $P2,S1|p_j,s_j|IT$ is ${\mathcal {N}}{\mathcal {P}}$-hard in the strong sense, and proposed a beam search algorithm to solve it. Jiang et al. (2013) considered the problem $P2,S1|prmp|C_{max}$. They proposed an algorithm with a tight bound of 4/3 and showed that it can generate optimal schedules for two special cases: equal setup times and equal processing times. Abdekhodaee and Wirth (2002) addressed the problem $P2,S1|p_j,s_j|C_{max}$. They proposed a MIP formulation for the regular case and two greedy heuristics for the general case. Abdekhodaee et al. (2004) investigated the problem $P2,S1|p_j=p,s_j=s|C_{max}$ with equal processing times and equal setup times. They showed that the problem is ${\mathcal {N}}{\mathcal {P}}$-hard and proposed two heuristics. Abdekhodaee et al. (2006) developed two greedy heuristics, a genetic algorithm and the Gilmore-Gomory algorithm for the general case of the problem $P2,S1|p_j,s_j|C_{max}$. Later, Gan et al. (2012) addressed the problem $P2,S1|p_j,s_j|C_{max}$. They presented two MIP formulations and two branch-and-price algorithms. Hasani et al. (2014a) proposed a MIP formulation for the problem $P2,S1|p_j,s_j|C_{max}$, based on the idea of decomposing a schedule into a set of blocks. The results showed that the proposed formulation outperformed all heuristics of Gan et al. (2012). Hasani et al. (2014b) addressed the problem $P2,S1|p_j,s_j|C_{max}$. They proposed two metaheuristics based on simulated annealing (SA) and genetic algorithm (GA). The results obtained are much better than all the previous algorithms proposed in Abdekhodaee et al. (2006) and Gan et al. (2012). Hasani et al. (2016) investigated the problem $P2,S1|p_j,s_j|C_{max}$. They proposed two greedy heuristics to solve very large-sized instances with up to 10,000 jobs. The results obtained are much better than the ones of all previous algorithms presented in the literature for very large-sized instances. Arnaout (2017) suggested a brand and bound and an ant colony optimization (ACO) for the problem $P2,S1|p_j,s_j|C_{max}$. The results obtained are much better than the ones proposed by Hasani et al. (2014b) for large-sized instances. Benmansour et al. (2018) addressed the problem $P2,S1|p_j=p,s_j|C_{max}$ with equal processing times. They showed that the problem is equivalent to the single machine scheduling problem with time restriction (STR). The STR is a new scheduling problem that was firstly studied by Braun et al. (2014) and Benmansour et al. (2014). Recently, Alharkan et al. (2020) proposed two metaheuristics based on tabu search (TS) and geometric particle swarm optimization (GPSO) algorithms for the problem $P2,S1|p_j,s_j|C_{max}$. The results showed that the proposed metaheuristics outperformed the algorithms of Hasani et al. (2014b) for large-sized instances. Recently, Arnaout (2021) proposed a worm optimization algorithm for the problem $P2,S1|p_j,s_j|C_{max}$ involving two identical parallel machines.

2.3 Case with an arbitrary number of machines

Three machine environments have been investigated: identical parallel machines, dedicated parallel machines and unrelated parallel machines. In addition, only three objective functions (to be minimized) have been considered: makespan ($C_{max}$), total weighted completion time ($\sum w_jC_j$), and total weighted tardiness ($\sum w_jT_j$).

Identical parallel machines Wang and Cheng (2001) proposed an approximation algorithm for the problem $P,S1|p_j,s_j|\sum w_jC_j$. Kim and Lee (2012) addressed the problem $P,S1|p_j,s_j|C_{max}$, and they suggested two MIP formulations and a hybrid heuristic algorithm. Zhang et al. (2016) proved that the SPT (shortest processing time) rule has a worst-case ratio of $1 + \frac{\sqrt{m-1}}{\sqrt{m}\sqrt{m-1}}$ for the problem $P,S1|p_j = p,s_j|\sum C_j$ (m being the number of machines). Hamzadayi and Yildiz (2017) considered the problem $P,S1|ST_{sd}|C_{max}$ with sequence-dependent setup time. They proposed a MIP formulation and two metaheuristics based on SA and GA. Cheng et al. (2017) considered the problems $P2,S1|prmp|C_{max}$ and $P,S1|prmp|C_{max}$, by taking into account job preemptions. They showed that the problems are ${\mathcal {N}}{\mathcal {P}}$-hard and presented pseudo-polynomial-time algorithms to solve them. Liu et al. (2019) presented a branch-and-bound algorithm, a lower bound, and dominance properties for the exact resolution of the problem $P,S1|p_j,s_j|\sum w_jC_j$. Silva et al. (2019) proposed a MIP formulation based on arc-time-indexed variables and an iterative local-search metaheuristic for the problem $P,S1|ST_{sd}|C_{max}$. The results showed that the MIP formulation and the iterative local search outperformed the methods presented by Hamzadayi and Yildiz (2017). Elidrissi et al. (2021) proposed several MIP formulations based on different decision variables for solving general and regular job sets of the problem $P,S1|p_j,s_j|C_{max}$. The results showed that two of the proposed formulations outperformed the formulations suggested by Kim and Lee (2012). For the case of multiples servers: Xu et al. (2021) addressed a parallel machine scheduling problem involving multiple servers. The authors assumed that the servers are in charge of the setup and removal operations of the jobs. In addition, they considered slack times (between the setup operation and the removal operation), machine-server eligibility restrictions, and machine-server availability periods. To solve the problem, the authors proposed a MIP formulation along with some heuristics based on dispatching rules. Lee and Kim (2021) addressed a new variant of the IPSS problem, namely a parallel machine scheduling problem with job splitting, sequence-dependent setup times, and limited setup servers. The objective function involves the minimization of the makespan. To solve this new problem, the authors proposed a MIP formulation and a heuristic. Recently, Heinz et al. (2022) studied a parallel machine scheduling problem with sequence-dependent setup times, multiple servers, and makespan objective. To solve this new problem, the authors suggested a constraint programming model and constructive heuristics.

Dedicated parallel machines Huang et al. (2010) proposed a MIP formulation and a hybrid genetic algorithm for the problem $PD,S1|ST_{sd}|C_{max}$ with sequence-dependent setup times and dedicated parallel machines. Cheng et al. (2019) were the first to investigate the problem $PD,S1~|~fixed~-~seq~|~C_{max}$ in which the job processing sequences are fixed. They showed that the problem is ${\mathcal {N}}{\mathcal {P}}$-hard even if all the jobs have the same processing duration or all the loading operations require the same time; two heuristics were proposed for the latter case with unit setup time for all the jobs. Recently, Cheng et al. (2021) addressed the parallel machine scheduling problem with a single server and fixed job sequence constraint in order to minimize the makespan. They showed that the problem becomes binary ${\mathcal {N}}{\mathcal {P}}$-hard for $m = 3$ machines, and suggested a pseudo-polynomial algorithm to solve the problem with fixed m.

Unrelated parallel machines Bektur and Saraç (2019) were the first to address the problem $R,S1|M_j,ST_{sd}|\sum w_jT_j$. They presented a MIP formulation and two metaheuristics based on TS and SA by taking into consideration machine eligibility restrictions and sequence-dependent setup times.

Uniform parallel machines Kim and Lee (2021) addressed a new variant of the IPSS problem, namely a uniform parallel machine scheduling problem with machine eligibility, job splitting, sequence-dependent setup times, and limited setup servers. The objective function involves the minimization of the makespan. This new problem is motivated by a real application of piston manufacturing. To solve the problem, the authors proposed a MIP formulation and an efficient heuristic algorithm.

2.4 Studies on the problem $P|r_j|L_{max}$ without a single server

In this section, we present the papers related to the parallel machine scheduling with release dates to minimize the maximum lateness without a single server. Ovacik and Uzsoy (1995) addressed the problem $P|ST_{sd},r_j|L_{max}$ with sequence-dependent setup times. They proposed a family of rolling horizon procedures. The results showed that proposed methods outperformed dispatching rules combined with local-search techniques. Schutten and Leussink (1996) proposed lower bounds and a branch-and-bound algorithm for the parallel machine scheduling problem with release dates and family setup times to minimize the maximum lateness ($P|r_j,s_j|L_{max}$). Centeno and Armacost (1997) suggested an algorithm for the problem $P|r_j,M_j|L_{max}$ for the special case where due dates are equal to release dates plus a constant. Haouari and Gharbi (2003) proposed lower bounds for the problem $P|r_j|L_{max}$. Kim and Shin (2003) presented a restricted TS for the problem $P|ST_{sd},r_j|L_{max}$. Lee et al. (2010) developed a restricted SA for the problem $P|ST_{sd},r_j|L_{max}$. Ying and Cheng (2010) suggested an iterated greedy heuristic for the problem $P|ST_{sd},r_j|L_{max}$. Later, Lin et al. (2011) proposed an improved iterated greedy heuristic with a sinking temperature for the same problem. The metaheurictics of Lee et al. (2010) and Ying and Cheng (2010) have not been compared. It can be noticed that no solution algorithm has been designed for the problem $P|r_j|L_{max}$.

Table 2 An overview of the IPSS problem works with a single server

2.5 Studies on the IPSS problem

The papers considering the IPSS problem are summarized in Table 2, which also highlight our contributions (see the last line). This table reveals that only two papers addressed the problem $P,S1|r_j|L_{max}$. In the first one, Hall et al. (2000) showed that the problem $P,S1|p_j=1,s_j|L_{max}$ (without release dates) can be solved in $O(n\log n)$, and that the problem $P2,S1|p_j,s_j=1|L_{max}$ (with unit setup time) is unary ${\mathcal {N}}{\mathcal {P}}$-hard. In the second one, Brucker et al. (2002) showed that the problem $P2,S1|p_j=1,r_j|L_{max}$ with unit processing time is unary ${\mathcal {N}}{\mathcal {P}}$-hard. Therefore, no solution algorithm has been designed for the general problem $P,S1|r_j|L_{max}$. In addition, no previous work on scheduling problems involving a single server proposed solution methods for the case where jobs are released over time. Note that for the problem $P|r_j|L_{max}$ without considering the single server, no solution algorithm has been suggested.

3 Problem formulation

To define the problem $P,S1|r_j|L_{max}$ addressed in this paper, let $M=\{1,2,\ldots ,m\}$ be the set of m identical parallel machines that are available to process a set $N=\{1,2,\ldots ,n\}$ of n independent jobs. Each job $j \in N$ is to be processed by exactly one of the machines during a given positive time $p_j$. Before its processing, job j must be set up on a machine by the server. The setup operation, which can be also considered as a loading or preparation operation, has a predefined duration $s_j$. Each job j becomes available at its release date $r_j$ and should be completed by its due date $d_j$. In addition, during the setup operation, both the machine and the server are occupied, and after setting up a job, the server becomes available for setting up the next job. The processing operation starts immediately after the end of the setup operation. Moreover, there is no precedence among jobs, and preemption is not allowed. The objective is to find a feasible schedule that minimizes the maximum lateness $L_{max}=\max _{j \in N} L_j$, where $L_j=C_j-d_j$ is the lateness of job j. If $L_j < 0$, job j is early, and if $L_j > 0$, it is tardy. Such an objective function $L_{max}$ is highly relevant from a practical standpoint, as its minimization contributes to the satisfaction of the clients. In contrast, minimizing $C_{max}$ focuses on the satisfaction of the production plant. This shift from the manufacturer satisfaction to the client satisfaction can be observed in recent works (Respen et al. 2017; Thevenin et al. 2017).

3.1 Network variables formulation $(MIP_{1})$

We present here a MIP formulation based on network variables for the problem $P,S1|r_j|L_{max}$. Network variables formulation, known also as traveling-salesman-problem variables formulation or tour-constraint formulation, was initially proposed by Queyranne and Schulz (1994) to model the nonpreemptive single machine scheduling problem with sequence-dependent processing times to minimize the makespan. This technique has been successfully used to model different ${\mathcal {N}}{\mathcal {P}}$-hard scheduling problems (Baker and Keller 2010; Anderson et al. 2013). In this formulation, a dummy job 0 is required to be the first and the last job processed on each machine, and its release date, setup time and processing time are set to 0. Indeed, it indicates the start and the completion of the job setup and processing operations on each machine [similarly to the vehicle routing problem, where the jobs represent the customers and the machines represent the vehicles being routed (Unlu and Mason 2010)].

The decision variables are defined as follows:

$x_{i,j} = \left\{ \begin{array}{ll} 1 &{} \text {if job}\ i\ \text {immediately precedes job}\ j \ \text {on the same machine} \\ 0 &{} \text {otherwise} \\ \end{array}\right.$

$z_{i,j} = \left\{ \begin{array}{ll} 1 &{} \text {if job}\ i\ \text {finishes its processing before job} \ j\ \text {on the server} \\ 0 &{} \text {otherwise}\\ \end{array}\right.$

$C_j$: completion time of job j.

Let B be a sufficiently large positive integer, such as $B \ge \sum _{j \in N} (r_j+s_j+p_j)$.

The problem $P,S1|r_j|L_{max}$ can be formulated as the following $MIP_{1}$.

$$\begin{aligned}&\min \qquad L_{max} \end{aligned}$$

(1)

$$\begin{aligned}&\ s.t. \qquad L_{max} \ge C_j - d_j \qquad \forall j \in N \end{aligned}$$

(2)

$$\begin{aligned}&\qquad \qquad \sum _{j=1}^{n} x_{0,j} \le m \end{aligned}$$

(3)

$$\begin{aligned}&\qquad \qquad \sum _{i=1}^{n} x_{i,0} \le m \end{aligned}$$

(4)

$$\begin{aligned}&\qquad \qquad \sum _{j=0: j \ne i}^{n} x_{i,j} = 1 \qquad \forall i \in N \end{aligned}$$

(5)

$$\begin{aligned}&\qquad \qquad \sum _{i=0: i \ne j}^{n} x_{i,j} = 1 \qquad \forall j \in N \end{aligned}$$

(6)

$$\begin{aligned}&\qquad \qquad \qquad \qquad \quad \ C_j \ge r_j + s_{j}+ p_j \qquad \forall j \in N \end{aligned}$$

(7)

$$\begin{aligned}&\qquad \qquad C_i + s_{j} + p_{j} \le C_{j} + B(1-x_{i,j}) \qquad \forall i,j \in N,i \ne j \end{aligned}$$

(8)

$$\begin{aligned}&\qquad \qquad C_{i} + s_{j} + p_{j} \le C_{j} + p_{i} + B(1 -z_{i,j}) \qquad \forall i,j \in N, i \ne j \end{aligned}$$

(9)

$$\begin{aligned}&\qquad \qquad \qquad z_{i,j} + z_{j,i} \ge \qquad \forall i,j \in N, i \ne j \end{aligned}$$

(10)

$$\begin{aligned}&\qquad \qquad \qquad \qquad \quad x_{i,j} \in \{0,1\} \qquad \forall i \in N \cup \{0\}, \forall j \in N \cup \{0\} \end{aligned}$$

(11)

$$\begin{aligned}&\qquad \qquad \qquad \qquad \quad \ z_{i,j} \in \{0,1\} \qquad \forall i,j \in N \end{aligned}$$

(12)

The objective function (1) indicates that the maximum lateness has to be minimized. Constraints (2) stipulate that the maximum lateness is greater than or equal to the difference between $C_{j}$ and $d_{j}$. Constraints (3) and (4) are presented in line with some vehicle-routing formulations, where the jobs are assigned to the m available machines, such that each machine starts and finishes its schedule with job 0. Constraints (5) and (6) guarantee that each job is scheduled on a particular machine. Constraints (7) state that each job j should starts after its release time. Constraints (8) indicate that no two jobs i and j, scheduled on the same machine, can overlap in time. Constraints (9) and (10) state that the server can set-up at most one job at a time. Constraints (11) and (12) define variables $x_{i,j}$ and $z_{i,j}$ as binaries.

3.2 Completion-time variables formulation $(MIP_{2})$

We present here a MIP formulation based on completion-time variables for the problem $P,S1|r_j|L_{max}$. Completion-time variables, known also as natural-date variables, were initially used by Balas (1985) for a job shop scheduling problem. This formulation has been also used to model different ${\mathcal {N}}{\mathcal {P}}$-hard scheduling problems (see Elidrissi et al. 2018; Krim et al. 2020; Elidrissi et al. 2022).

The decision variables are defined as follows:

$y_{j,k} = \left\{ \begin{array}{ll} 1 &{} \text {if job}\ j\ \text {is scheduled on machine}\ k \\ 0 &{} \text {otherwise} \\ \end{array}\right.$

$z_{i,j} = \left\{ \begin{array}{ll} 1 &{} \text {if job}\ i\ \text {finishes its processing before job}\ j \ \text {on the server} \\ 0 &{} \text {otherwise} \\ \end{array}\right.$

The problem $P,S1|r_j|L_{max}$ can be formulated as the following $MIP_2$.

$$\begin{aligned}&\min \qquad L_{max} \end{aligned}$$

(13)

$$\begin{aligned}&\ s.t. \qquad L_{max} \ge C_j - d_j \qquad \forall j \in N \end{aligned}$$

(14)

$$\begin{aligned}&\qquad \qquad \sum _{k=1}^{m} y_{j,k} =1 \qquad \forall j \in N \end{aligned}$$

(15)

$$\begin{aligned}&\qquad \qquad \ C_j \ge r_{j} + s_{j}+ p_{j} \qquad \forall j \in N \end{aligned}$$

(16)

$$\begin{aligned}&\qquad \qquad C_{i} + s_{j} + p_{j} \le C_{j}+ B (3 - y_{i,k} - y_{j,k} - z_{i,j}) \qquad \forall i,j \in N, i < j, \forall k \in M \end{aligned}$$

(17)

$$\begin{aligned}&\qquad \qquad C_{j} + s_{i} + p_{i} \le C_{i} + B(2 - y_{i,k} - y_{j,k} + z_{i,j}) \qquad \forall i,j \in N, i < j, \forall k \in M \end{aligned}$$

(18)

$$\begin{aligned}&\qquad \qquad C_{i} + s_{j} + p_{j} \le C_{j} + p_{i} + B(1 -z_{i,j}) \qquad \forall i,j \in N, i < j \end{aligned}$$

(19)

$$\begin{aligned}&\qquad \qquad C_{j} + s_{i} + p_{i}\le C_{i} + p_{j} + Bz_{i,j} \qquad \forall i,j \in N, i < j \end{aligned}$$

(20)

$$\begin{aligned}&\qquad \qquad y_{j,k} \in \{0,1\} \qquad \forall j \in N, \forall k \in M \end{aligned}$$

(21)

$$\begin{aligned}&\qquad \qquad z_{i,j} \in \{0,1\} \qquad \forall i,j \in N \end{aligned}$$

(22)

In this formulation, the objective function (13) indicates that the maximum lateness has to be minimized. Constraints (14) indicate that the maximum lateness is greater than or equal to the difference between the completion time and the due date of each job. In order to guarantee that each job is scheduled on exactly one machine, constraints set (15) is added to the formulation. The completion time $C_j$ is greater than or equal to the sum of the release, the setup, and the processing times of the job j, and is calculated according to constraints (16). Constraints (17) to (20) show that a job can be processed only if the server and the machines are available simultaneously. Constraints (17) and (18) indicate that no two jobs, scheduled on the same machine, can overlap in time. Constraints (19) and (20) state that the server can set-up at most one job at a time. Finally, constraints (21) and (22) define binary variables $x_{i,k}$ and $z_{i,j}$.

3.3 Valid inequalities

In order to reduce the time required to solve the problem by one of the proposed formulations $MIP_1$ and $MIP_2$, the following constraint set can be added. Let $L_{max}^{*}$ denotes the objective-function value of an optimal solution of the problem $P,S1|r_j|L_{max}$. Let $\hat{L}_{max}^{H1}$ denotes the objective-function value of the solution provided by the constructive heuristic H1 for the problem $P,S1|r_j|L_{max}$. The constructive heuristic H1 is presented in Sect. 4.2.

Proposition 1

The following constraints are valid for $MIP_1$ and $MIP_2$ formulations.

$$\begin{aligned} C_{j} - C_{i} \ge r_j + s_j + p_j - (\hat{L}_{max}^{H1}+d_i) \qquad \forall i,j \in N, i \ne j \end{aligned}$$

(23)

Proof

The maximum lateness verifies the following equation:

$$\begin{aligned} C_j - d_j \le L_{max}^{*} \le \hat{L}_{max}^{H1} \qquad \forall j \in N \end{aligned}$$

(24)

Combining the constraints sets 24 and 7, we obtain:

$$\begin{aligned} r_j + s_j +p_j \le C_j \le \hat{L}_{max}^{H1} + d_j \qquad \forall j \in N, \end{aligned}$$

(25)

and accordingly, the constraints set is valid. $\square$

$MIP_1^{*}$ refers to formulation $MIP_1$ with constraints set (23). $MIP_2^*$ refers to formulation $MIP_2$ with constraints set (23). A comparative study among $MIP_1$, $MIP_2$, $MIP_1^{*}$, and $MIP_2^{*}$ is performed in Sect. 5.

3.4 Illustrative example

We illustrate the previous formulation for an instance with $n = 6$, and $m = 3$. The processing time $p_j$, the setup time $s_j$, the release date $r_j$ and the due date $d_j$ of the jobs are given in Table 3. It takes 0.44 s to solve the instance using the above $MIP_1$ formulation on IBM ILOG CPLEX 12.6. The optimal objective-function value is 6, and the obtained schedule is given in Fig. 1.

Table 3 Instance with $n=6$ and $m=3$

Fig. 1

Optimal schedule for the considered instance with 6 jobs and 3 machines

4 Solution methods

In this section, we first discuss the solution representation and the objective-function calculation of the studied problem. Next, we present a constructive heuristic H1. Finally, we present two metaheuristics: GVNS and GRASP, both using VND as an intensification operator. Note that H1 is used to generate initial solutions for GVNS.

4.1 Solution representation and objective-function calculation

A schedule of the problem $P,S1|r_j|L_{max}$ can be represented as a permutation $\pi = \{\pi _1,\ldots ,\pi _k,\ldots ,\pi _n\}$ of the job set N, where $\pi _k$ indicates the job which is processed in the kth position by the server (see Hasani et al. 2014b; Elidrissi et al. 2019). Any permutation of all jobs defines a feasible schedule, where each job will be scheduled as soon as it is released, and only if a machine and the server are available simultaneously. This is an indirect solution representation as it requires the scheduling of the jobs on the machines (while taking into account the server constraint) in order to compute the value of the maximum lateness ($L_{max}$) and the completion times of the jobs. Having in mind that all jobs are independent, all permutations (n!) represent feasible solutions, and therefore the search space is very large.

Additional notation is defined in Table 4.

Table 4 Employed notation

In order to compute the objective function of a given sequence $\pi$ of jobs, denoted as $L_{max}(\pi )$, the following Proposition 2 is used.

Proposition 2

Given a sequence $\pi$ of jobs, $S_{\pi _k}$ is computed as follows:

$$\begin{aligned} S_{\pi _k} = \left\{ \begin{array}{lcl} r_{\pi _k} &{} \text{ if } &{} k=1 \\ \max \left( r_{\pi _{k}},S_{\pi _{k-1}}+s_{\pi _{k-1}}\right) &{} \text{ if } &{} 2 \le k \le m \\ \max \left( r_{\pi _{k}},S_{\pi _{k-1}}+s_{\pi _{k-1}}, \mathop {\textrm{min}}\limits _{1 \le t \le m} E_{t,\pi _{k}}\right) &{} \text{ if } &{} m+1 \le k \le n\\ \end{array}\right. \end{aligned}$$

Proof

The first job will start immediately at its release date. Thus, $S_{\pi _k} = r_{\pi _k}$ if $k = 1$.

Second, each job in position $k \in \{2, \ldots , m\}$ will start immediately its setup operation if it is released, and after the completion of the setup operation of the job in position $k-1$, on one of the $\{1,\ldots ,m\}$ available machines. This is trivial because in such cases, at least one machine will be available for processing this job. Therefore: $S_{\pi _k} =\max \left( r_{\pi _{k}}, S_{\pi _{k-1}}+s_{\pi _{k-1}}\right) , \, \forall k \in \{2, \ldots , m\}$.

Third, suppose that we want to schedule a job in position $k \ge m+1$. Its start time $S_{\pi _k}$ will depend on its release date and also on the availability of the server and a machine. The job at position k can only be scheduled if it is released, thus $S_{\pi _k} \ge r_{\pi _k}$.

Moreover, the server will be available to perform the setup operation of the job at position k if $S_{\pi _k} \ge S_{\pi _{k-1}} + s_{\pi _{k-1}}$. In addition, the job at position k will be scheduled on the first available machine t, which corresponds to the one with the smallest completion time of all jobs scheduled on it. Hence, $t=\textrm{arg} \mathop {\textrm{min}}\nolimits _{1 \le t' \le m}\left( E_{t',\pi _{k}}\right)$.

Finally, in order to ensure that the job, the server and a machine are available at same time, we choose the maximum of the three values: $r_{\pi _k}$, $S_{\pi _{k-1}} + s_{\pi _{k-1}}$ and $\underset{1\le t \le m}{\text {min}}E_{t,\pi _{k}}$. $\square$

Therefore, the objective-function value associated with the job sequence $\pi$ is computed as follows:

$$\begin{aligned} L_{max}(\pi ) =\underset{1\le k \le n}{\text {max}} (C_{\pi _k}-d_{\pi _k})=\underset{1\le k \le n}{\text {max}}(S_{\pi _k} + p_{\pi _k} + s_{\pi _k} -d_{\pi _k}) \end{aligned}$$

It can be noticed that Proposition 2 can be used as a dispatching rule for other scheduling problems with a single server involving different objective functions.

4.2 Constructive heuristic (H1)

The idea of the heuristic H1 relies on the work of Lin et al. (2011) for the problem $P|ST_{sd},r_j|L_{max}$, considering parallel machines with job release dates, sequence-dependent setup times and maximum lateness minimization. Indeed, in Lin et al. (2011), the authors developed a simple heuristic in order to generate an initial solution for an iterated greedy algorithm. Thus, we adapt this heuristic to our problem $P,S1|r_j|L_{max}$ by taking into account the single server, and sequence-independent setup times constraints. In each step of H1, we choose a job to be scheduled taking into account its release date, the availability of the machines and the availability of the server.

For the first job $\pi _{1}$ to be scheduled, we choose the job j of N with the smallest release date $r_j$. Ties are broken with the largest lateness (computed here as $s_j+p_j-d_j$). The potential remaining ties are broken randomly. The job $\pi _{1}$ will be scheduled in the first machine of M. For the second job $\pi _{2}$ to be scheduled, among all the non-scheduled jobs of N that are released before the end of the setup operation of the job $\pi _{1}$, we choose again the job with the largest lateness (if such a job does not exist, the job with the smallest release date is chosen). The job $\pi _{2}$ is scheduled in the second machine of M. This process continues the same way for the m first jobs to be scheduled, as there is always an available machine in such a case. Next, a job in position k ($k > m$) can start its setup operation if it is released and if both a machine and the server are simultaneously available. Thus, the chosen job to be scheduled in the position k must be released before a given time $\max (T_{\pi _{k-1}} + s_{\pi _{k-1}}, E_{t,\pi _k})$, where $t = \textrm{arg} \mathop {\textrm{min}}\limits _{h \in M}(E_{h,\pi _k})$. Among all jobs that are released before that time, we choose the job with the largest lateness, and we schedule it in the available machine.

4.3 General Variable Neighborhood Search (GVNS)

Variable Neighborhood Search (VNS) is a metaheuristic initially proposed by Mladenović and Hansen (1997). It employs various neighborhood structures ${\mathcal {N}}_1, {\mathcal {N}}_2, \ldots$ (usually ranked increasingly with respect to the modification they can bring to the solution structure) for exploring the search space (diversification ability) and a local search procedure for intensifying the search around promising solutions (exploitation ability). Since 1997, VNS and its variants have been widely applied to different fields (Hansen et al. 2008; Bierlaire et al. 2010; Perron et al. 2010; Mladenović et al. 2013; Schneider et al. 2015; Thevenin and Zufferey 2019; Todosijević et al. 2016). At the beginning of the search, let $\pi$ be the initial solution (usually generated with a constructive heuristic) and let $i = 1$ (index of the employed neighborhood structure). VNS repeats the following three main steps until a stopping criterion is met (e.g., a time limit).

• 1. Shaking generate a neighbor solution $\pi ' \in {\mathcal {N}}_i(\pi )$.

• 2. Local search try to improve $\pi '$ with a local search, and let $\pi ''$ be the resulting solution.

• 3. Move or not if $\pi ''$ is not better than $\pi$, set $i = i+1$; otherwise, set $i=1$ and $\pi = \pi ''$.

More generally, anytime step (2) does not lead to an improvement of the current solution $\pi$, we use the next neighborhood structure in the next iteration, which will perform more modifications on $\pi$ (as more diversification is required to move the search away from the local optimum $\pi$). In contrast, anytime $\pi ''$ improves $\pi$, the new current solution becomes $\pi ''$ (as we set $\pi = \pi ''$ in step (3)), and we intensify the search in this promising zone of the search space by coming back to smaller modifications in the shaking phase (i.e., employing again ${\mathcal {N}}_1$).

The simplest VNS variant is Reduced VNS (RVNS), which is VNS without the local-search step. In most of the cases, it is applied to provide good initial solutions for other VNS variants. If the shaking step is omitted, the corresponding method is known as Variable Neighborhood Descent (VND), where a local search is performed relying on multiple neighborhood structures. Furthermore, different variants of VND are proposed in the literature, such as: sequential VND, pipe VND, cyclic VND (Hansen et al. 2017). In General VNS (GVNS), VND is used as a local search (Hansen et al. 2010). Following this research line, in this paper, we propose a GVNS to solve the problem $P,S1|r_j|L_{max}$. It starts with an initial solution generated by the heuristic H1. Next, the shaking procedure and VND are applied to try to improve the current solution. This procedure continues until all predefined neighborhoods have been explored.

4.3.1 Neighborhood structures ${\mathcal {N}}_1, {\mathcal {N}}_2, {\mathcal {N}}_3$

Below, we propose three different neighborhood structures ${\mathcal {N}}_1, {\mathcal {N}}_2, {\mathcal {N}}_3$ to tackle the problem $P,S1|r_j|L_{max}$. These neighborhood structures have been widely used in the literature [e.g., for the two parallel machines scheduling problem with a single server (Hasani et al. 2014b; Alharkan et al. 2020), for other scheduling problems on parallel machines (Respen et al. 2017; Thevenin et al. 2016; Thevenin and Zufferey 2019)].

• ${\mathcal {N}}_1(\pi )$ = Swap($\pi )$. It consists of all solutions obtained from solution $\pi$ by swapping two jobs of $\pi$.

• ${\mathcal {N}}_2(\pi )$ = Insert($\pi )$. It consists of all solutions obtained from solution $\pi$ by reinserting one of its job somewhere else in the sequence.

• ${\mathcal {N}}_3(\pi ) = 2$-$opt(\pi )$. It consists of all solutions obtained from solution $\pi$ by reversing a subsequence of $\pi$. More precisely, given two jobs $\pi _i$ and $\pi _j$, we construct a new sequence by first deleting the connection between $\pi _i$ and its successor $\pi _{i+1}$ and the connection between $\pi _j$ and its successor $\pi _{j+1}$. Next, we connect $\pi _{i-1}$ with $\pi _j$ and $\pi _{i}$ with $\pi _{j+1}$.

4.3.2 Variable Neighborhood Descent (VND)

We propose to use ${\mathcal {N}}_1$, ${\mathcal {N}}_2$ and ${\mathcal {N}}_3$ in a VND framework. The output solution will be a local optimum with respect to all the proposed neighborhood structures. The employed VND pseudocode is presented in Algorithm 1. Preliminary experiments led to the following settings. Such experiments are not reported here as they concern minor parameters with respect to the overall proposed approaches. First, the following sequence of the neighborhood structures is the most efficient: ${\mathcal {N}}_3, {\mathcal {N}}_1, {\mathcal {N}}_2$. Second, when generating a solution $\pi ' \in {\mathcal {N}}_i$ in step (1), the first-improvement process (i.e., in each iteration, stop the generation of neighbor solutions as soon as the current solution can be improved) is better than the best-improvement process (i.e., in each iteration, generate all the neighbor solutions and pick up the best one). Third, and in line with Hansen et al. (2017), for step (3) of VND, we have tested three different techniques for changing the employed neighborhood structure. The techniques are summarized below, and Pipe turns out to be the best technique in our context.

• Cyclic set $k = k+1$. In other words, the search mechanism employs always the next neighborhood structure of the list.

• Pipe set $k = k+1$ if there is no improvement in step (2). In this case, the search mechanism keeps the same neighborhood structure as long as it is successful.

• Sequential set $k = k+1$ if there is no improvement in step (2); otherwise set $k=1$. It means that an improvement imposes the search mechanism to come back to the first neighborhood structure of the list.

Algorithm 1

VND

4.3.3 Shaking procedure and overall pseudocode

Starting from the input solution $\pi$, the employed shaking procedure consists of sequentially generating h (diversification parameter) neighbor solutions in ${\mathcal {N}}_3$ (we have selected ${\mathcal {N}}_3$ because it modifies the structure of the considered solution more deeply than ${\mathcal {N}}_1$ and ${\mathcal {N}}_2$, which is in line with the role of a shaking mechanism). In other words, h iterations are performed in ${\mathcal {N}}_3$. In each iteration, a single neighbor solution is generated at random. The overall pseudocode of GVNS is given in Algorithm 2. The stopping criterion is a CPU time limit T. The diversification (resp. intensification) ability of GVNS relies on the shaking phase (resp. VND).

In line with the VNS literature, we have decided to employ increasing values of h if step 3 of GVNS does not lead to an improvement of the current solution $\pi$. More precisely, we start with $h=h_{min}$. Next, if there is no improvement in step 3, we augment h by $\varDelta h$ (as long as h does not exceed $h_{max}$) because more modifications seem to be required to escape from the current local optimum (and we impose the threshold $h_{max}$ for h in order to control the search process and not make the shaking process resemble a restart mechanism). In contrast, anytime there is an improvement of $\pi$ in step 3, we come back to smaller modifications by setting $h=h_{min}$ again (to allow the search process exploiting this new promising region of the solution space). After preliminary experiments that are not reported here, we have decided to set $(h_{min}, h_{max}, \varDelta h) = (2, 10, 1)$.

Algorithm 2

GVNS

4.4 Greedy randomized adaptive search procedures (GRASP) with VND

GRASP (Feo and Resende 1995) is a multi-start metaheuristic used to solve hard optimization problems. It has been applied for different scheduling problems (Yepes-Borrero et al. 2020; Báez et al. 2019; Armentano and de Franca Filho 2007). As presented in Algorithm 3, it consists of two phases which are repeated in turn as long a stopping condition is not met: (1) a greedy randomized construction phrase CP (presented below in Algorithm 4); (2) an improvement procedure (VND in our case). The diversification (resp. intensification) ability of GRASP relies on CP (resp. VND).

Algorithm 3

GRASP

CP relies on the following ingredients: a Candidate List CL; a subset RCL of RL called Restricted Candidate List; the incremental cost $\varDelta (j)$ associated with the integration of a job $j \in CL$ into $\pi$. CP generates a solution $\pi =\{\pi _1,\ldots ,\pi _n\}$ iteratively from scratch. All jobs of N are initially inserted in CL and the algorithm ends when all jobs of CL are scheduled in $\pi$. In each iteration, a new job j is randomly selected in $RCL \subseteq CL$ and then scheduled in $\pi$. Now, the key issue is to determine RCL. At the beginning of the iteration r, the job sequence $\pi$ contains r jobs (i.e., $\pi =\{\pi _1,\ldots ,\pi _r\}$). The incremental cost $\varDelta (j)$ associated with the integration of a job $j \in CL$ into $\pi$ is computed as in Eq. (26), where $\alpha$ is the randomness parameter. The incremental cost is employed to decide if a job j is selected or not to be part of RCL. More precisely, let $\varDelta ^{min}$ and $\varDelta ^{max}$ be the smallest and largest values of $\varDelta (j)$ (among the jobs of CL), respectively. RCL contains the jobs j of CL satisfying $\varDelta (j) \le \varDelta ^{min} + \alpha (\varDelta ^{max}-\varDelta ^{min})$.

$$\begin{aligned} \varDelta (j)= \max (T_{\pi _r} + s_{\pi _r}, \mathop {\textrm{min}}\limits _{1 \le t \le m} E_{t,\pi _{k}}, r_{j}) + s_{j} + p_{j} - d_{j} \end{aligned}$$

(26)

The amount of randomness in CP is controlled by the parameter $\alpha$, which is selected uniformly at random in interval [0, 1]. $\alpha = 1$ (resp. $\alpha = 0$) corresponds to the purely random (resp. greedy) construction.

Algorithm 4

Construction Phase CP of GRASP

5 Computational experiments

In this section, the performances of $MIP_{1}$, $MIP_{1}^{*}$, $MIP_{2}$, $MIP_{2}^{*}$, H1, VND, GVNS, and GRASP are compared. The MIP formulations were solved using the concert technology library of CPLEX 12.6 using default settings in C++, whereas H1, VND, GVNS and GRASP were coded in C++. We use a personal computer Intel(R) Core(TM) with i7-4600 M 2.90 GHz CPU and 16GB of RAM, running Windows 7. Except for the small-sized instances for which one run is sufficient, the metaheuristics were executed 10 times in all experiments, and average results are provided. The stopping conditions employed for all the methods are presented in Table 5. Up to one hour of computing time is in line with the current practice in the job-scheduling industry (Respen et al. 2016; Thevenin et al. 2016, 2017). Moreover, for the problem $P2,S1|p_j,s_j|C_{max}$, Gan et al. (2012) proposed a stopping time of $\frac{300}{8} \cdot n$, and 3600 s for instances with $n \ge 100$. In this paper, we use the same limits for the computation times.

Table 5 Stopping conditions of the MIP formulations, H1, VND, GVNS and GRASP

5.1 Benchmark instances

As far as we know, there are no publicly available benchmark instances in the literature for the problem $P,S1|r_j|L_{max}$. Therefore, we have generated a set of instances according to the existing literature, as proposed by Bektur and Saraç (2019). These instances are publicly available at https://sites.google.com/view/dataforps1rjlmax/accueil.

The instances are characterized by the following features:

• The number of jobs $n \in \{8,10,12,15,20,25,30,50,75,100,250,500\}$.

• The number of machines $m \in \{2,3,4\}$.

• The integer processing times $p_j$ are uniformly distributed in the interval [10, 100] .

• The integer setup times $s_j$ are uniformly distributed in the interval [5, 50].

• Due dates $d_j$ are uniformly generated based on the due-date tightness factor $\uptau =1-\bar{d}/C_{max}$ (where $C_{max}$ is the estimated makespan, and $\bar{d}$ is the average due date), and the due-date range factor R such that $d_j = r_j + s_j + p_j + U~(~\bar{d}~-R~\bar{d}~, \bar{d}~)$. In line with Bektur and Saraç (2019), we have set $\uptau \in \{0.65, 0.8\}$ and $R = 0.2$.

• The release dates are generated with a uniform distribution: $r_j = U(0, \bar{d})$.

For each combination of n, $m \in \{2,3,4\}$ and $\uptau \in \{0.65, 0.8\}$, an instance was created, resulting to 6 instances (composing a group of instances) for each n. Therefore, we have a total of 72 instances, leading to a total of 12 groups of instances. The parameters of the test problems are given in Table 6. Due to the ${\mathcal {N}}{\mathcal {P}}$-hard nature of the problem, and using the MIP formulations ($MIP_{1}$, $MIP_{1}^{*}$, $MIP_{2}$ and $MIP_{2}^{*}$), optimal solutions were found for small-sized instances ($n \in \{8,10\}$), feasible solutions were obtained for medium-sized instances ($n \in \{12,15,20,25,30\}$), but no feasible solution was found for large-sized instances ($n \in \{50,75,100,250,500\}$). Therefore, H1, VND, GVNS and GRASP were designed to solve medium-sized and large-sized instances.

Table 6 Parameters of the test problems

5.2 Results of the exact methods

In Table 7, we compare the CPLEX performance of models $MIP_{1}$, $MIP_{1}^{*}$, $MIP_{2}$, and $MIP_{2}^{*}$ for 7 instance groups ($g1, \ldots , g7$) with a time limit of 1 h (since no feasible solution is found for the instance groups g8 to g12). For each MIP formulation, the following information is given: the number of instances solved to optimality within 1 h, #opt; the average computing time for these optimally solved instances, CPU; the number of instances unsolved within 1 h (instances with feasible solutions), #fs; and the average optimality gap for the instances which could not be solved within 1 h, gap (%).

The following observations can be made:

• For the instance group g1, formulations $MIP_{1}$, $MIP_{1}^{*}$, $MIP_{2}$, and $MIP_{2}^{*}$ are able to produce an optimal solution for all instances. For the formulations $MIP_{2}$ and $MIP_{2}^{*}$, CPLEX is able to produce an optimal solution in less computational time in comparison with the formulations $MIP_{1}$ and $MIP_{1}^{*}$.

• For the instance group g2, formulations $MIP_{1}$, $MIP_{1}^{*}$, $MIP_{2}$, and $MIP_{2}^{*}$ are able to produce an optimal solution for all instances. $MIP_{2}^{*}$ is able to produce an optimal solution in less computational time than the other formulations.

• For the instance group g3, $MIP_{1}$, $MIP_{2}$, and $MIP_{2}^{*}$ are able to produce an optimal solution for all instances. $MIP_{1}^{*}$ is able to produce an optimal solution for only 3 instances. Again, $MIP_{2}^{*}$ works faster than the other formulations.

• For the instance group g4, $MIP_{2}$ and $MIP_{2}^{*}$ are able to find an optimal solution for only one instance. $MIP_{2}^{*}$ produces, on average, much smaller gaps than $MIP_{2}$. In addition, $MIP_{1}$ and $MIP_{1}^{*}$ produced a feasible solution for all instances.

• For the instance groups g5 to g7 no formulation is able to find an optimal solution for all instances. On average, formulation $MIP_{2}^{*}$ produces much smaller gaps than the other formulations.

Overall, the results showed that $MIP_{2}^{*}$ outperforms, on average, the other formulations on almost all instances. This highlights the positive impact of the strengthening constraints in Eq. (23). Therefore, in the next experiments, we compare only $MIP_{2}^{*}$ with the other approaches.

Table 7 Results of $MIP_{1}$, $MIP_{1}^{*}$, $MIP_{2}$, and $MIP_{2}^{*}$

5.3 Results of the solution methods

5.3.1 Comparison of $MIP_{2}^{*}$, H1, VND, GVNS and GRASP for the small-sized instances

Note first that for all tables, an empty cell means that the same value as the above one is kept, and all the computing times are indicated in seconds. In Table 8, we compare the performance of $MIP_{2}^{*}$, H1, VND, GVNS and GRASP for small-sized instances, where an optimal solution can be found by $MIP_{2}^{*}$ within 1 h. Each instance is characterized by the following information: an ID; a number n of jobs; a number m of machines; the due date tightness factor $\uptau$; the optimal value $L_{max}^{opt}$ of $L_{max}$ (found with the formulation $MIP_{2}^{*}$). Next, the obtained value of $L_{max}$ is given for H1 (but not the computing time, as it is always below 0.0001 s) and VND (but not the computing time, as it is always below 0.01 s). Finally, the computing time to find an optimal solution is given for the $MIP_{2}^{*}$, GVNS and GRASP. The last line of the table indicates average results.

The following observations can be made:

• GVNS and GRASP can reach an optimal solution for each instance in significantly less computing time than the formulation $MIP_{2}^{*}$.

• VND is able to find an optimal solution for four instances, namely: I1, I5, I6, I11.

• H1 is never able to find an optimal solution (its average gap to optimality is around $25\%$), except for instance I6.

• GVNS requires the smallest average computing time (0.31 s) to find optimal solutions.

Table 8 Results of $MIP_{2}^{*}$, H1, VND, GVNS and GRASP for the small-sized instances

5.3.2 Comparison of $MIP_{2}^{*}$, H1, VND, GVNS and GRASP for the medium-sized instances

Table 9 presents the results for the medium-sized instances (the best results are indicated in bold face). The instance characteristics are first indicated. For $MIP_{2}^{*}$, the following information is given: the lower bound $LB_{MIP_{2}^{*}}$, the upper bound $UB_{MIP_{2}^{*}}$, the percentage gap to optimality $Gap_{MIP_{2}^{*}}(\%)$, and the time requested to prove optimality (if below 1 h). Note that for the instances I35 to I37, no information is provided as CPLEX is not able to return a feasible solution. Next, the found value of $L_{max}$ is given for H1 and VND (with its associated computing time). Finally, the following results are showed for GVNS and GRASP: the best (resp. average) objective-function value over 10 runs denoted as $L_{max}^{\star }$ (resp. $L_{max}^{avg}$). The average computing times are also provided (computed over the 10 runs, and the computing time of a run corresponds to the time at which the best visited solution is found).

Table 9 Results of $MIP_{2}^{*}$, H1, VND, GVNS and GRASP for the medium-sized instances

The following observations can be made:

• CPLEX (i.e., the $MIP_{2}^{*}$ formulation) is able to prove the optimality of the obtained solutions for the instances I16 to I18.

• The limitations of CPLEX seem to start from $n=15$, and they are obvious from $n=30$.

• GVNS and GRASP outperform significantly $MIP_{2}^{*}$ both in terms of quality (i.e., objective-function values) and speed (i.e., time requested to find competitive solutions). Moreover, for the instances I16 to I18, GVNS and GRASP are also able to find optimal solutions, but within 25 s.

• The results of H1 allow to measure the benefit of GVNS, as the latter employs the former to generate an initial solution.

• GVNS and GRASP outperform VND significantly (except for the instances I29 and I34). This shows the benefit of all the ingredients (e.g., diversification mechanisms) added to VND to derive GVNS and GRASP.

• GVNS and GRASP have a similar performance. In addition, the difference between $L_{max}^{avg}$ and $L_{max}^{\star }$ is very small (often below one unit).

• GVNS is able to obtain the best results for all instances but two (with $n=20$).

5.3.3 Comparison of VND, GVNS and GRASP for the large-sized instances

Table 10 has the same structure as Table 9, and the best average results are indicated in bold face. It presents the results for VND, GVNS and GRASP, which are the method specifically designed for tackling the large-sized instances (indeed, $MIP_{2}^{*}$ cannot find a feasible solution for such instances, and the role of H1 is simply to generate an initial solution for GVNS).

Table 10 Results of VND, GVNS and GRASP for the large-sized instances

The following observations can be made:

• Overall, for the provided instances, the methods can be ranked as follows: GVNS > GRASP > VND. This ranking is very obvious for $n \in \{250, 500\}$.

• GVNS and GRASP have comparable objective-function values for $n \in \{50, 75, 100\}$. However, for such instances, GVNS requires generally less computing time to find its best solutions. In contrast, GVNS significantly outperforms GRASP for the larger instances ($n \in \{250, 500\}$).

• GVNS has a best $L_{max}^{\star }$ value for 26 instances, whereas GRASP has best values for only 8 instances.

• For GVNS and GRASP, the difference between $L_{max}^{avg}$ and $L_{max}^{\star }$ grows with n and m, which is likely to indicate the robustness degradation with the increase of the instance size (i.e., with the increase of the problem complexity). This degradation is however smaller for GVNS when compared to GRASP.

5.4 Discussion

Table 11 presents the performance of VND, GVNS and GRASP in terms of the percentage deviation from the best-known solutions according to the due date tightness factor $\tau$ and the number n of jobs. In order to compute each percentage deviation, two values of $L_{max}^{\star }$ are compared: the best one over all the runs of all the methods, and the one obtained by the considered method. Again, we can easily observe the superiority of GVNS over GRASP (in particular for the large-sized instances), and both methods outperforms their intensification operator VND. Furthermore, VND and GRASP perform better with $\tau = 0.85$ rather than with $\tau =0.65$ (with respect to the deviation from the best-known solutions). This might indicate that these methods are less efficient with tighter due dates.

Table 11 Comparison of VND, GVNS and GRASP in terms of percentage deviation from the best-known solutions

6 Conclusions and future works

In this work, we investigated the problem of scheduling a set of jobs that are released over time on an arbitrary number of identical parallel machines with a single server. The objective function involved the minimization of the maximum lateness. We proposed two mixed-integer-programming (MIP) formulations to solve optimally instances with up to 12 jobs. Due to its ${\mathcal {N}}{\mathcal {P}}$-hard nature, a constructive heuristic (H1) and two metaheuristics were designed to obtain solutions for larger instances with up to 500 jobs. The first metaheuristic is a General Variable Neighborhood Search (GVNS), whereas the second is a Greedy Randomized Adaptive Search Procedure (GRASP). Both algorithms use a Variable Neighborhood Descent (VND) for the intensification phase, which involved three well-known neighborhood structures for such problems.

In line with the good practice of the related literature, we have built 72 benchmark instances to compare the proposed methods. For small-sized instances, GVNS and GRASP outperformed the MIP formulations in terms of the computing time to find an optimal solution. However, for medium and large-sized instances, the results show the very good performance of GVNS with respect to quality (of the obtained solutions), speed (i.e., time needed to generate efficient solutions) and some robustness indicators (e.g., deviation percentage from the best-known results, difference between the best and average solution values). This success can be explained by the good balance between the inherent diversification and intensification features of GVNS, namely the alternate and fine-tuned use of the VND operator for intensifying the search, and the shaking phase for diversifying the search. It also outlines that the exploration mechanism of GRASP (i.e., building another solution from scratch) might be too strong when compared to the shaking phase of GVNS. Indeed, the latter preserves a significant portion of the incumbent solution (a mechanism has been added to avoid the shaking phase resemble a restart mechanism, which results in well-controlled trajectory when exploring the solution space).

An avenue of research would be to adapt the proposed methods to other machine environments, such as dedicated and unrelated parallel machines, taking into account sequence-and-machine-dependent setup times. Further works could propose tight bounds on the machine impact for the problem $P,S1|r_j|L_{max}$ as done by Rustogi and Strusevich (2013) for the parallel machine scheduling problem to minimize the makespan and the total flow time.