Tabu search for a parallel-machine scheduling problem with periodic maintenance, job rejection and weighted sum of completion times

A taxonomy and a general review on order acceptance and scheduling (OAS) can be found in Slotnick (2011). This problem is to jointly decide about job acceptance and the scheduling of accepted jobs. Different problem characteristics and problem-solving methodologies, starting from this basic scheme, have been proposed in the literature. In the following, papers dealing with a single machine and different objective functions are reviewed, followed by a discussion on problems with two or more machines.

The scheduling problem with job rejection has been studied in different contexts, as indicated in a recent survey (Shabtay et al. 2013), and is motivated by industrial applications (Thevenin et al. 2017a), although mostly for single-machine problems.

In Li and Chen (2017), the authors consider the scheduling problem with job rejection and a maintenance activity that becomes less effective over time. The main objective is to determine the timing of the maintenance activity and the sequence of accepted jobs to minimize the scheduling cost of accepted jobs plus the total cost of rejected jobs. The authors provide polynomial time algorithms for this problem. Shabtay et al. (2012) propose a bicriteria analysis of a large class of single-machine scheduling problems with a common property, namely the consideration of rejection costs plus other additional criteria (makespan, sum and variation of completion times, earliness and tardiness costs).

Since scheduling with rejection is mostly studied in bicriteria contexts (Shabtay et al. 2013), concepts from the theory of bicriteria scheduling are commonly used when dealing with such problems. Below, we review papers addressing the weighted sum of completion times and the total cost of rejected jobs. Cao et al. (2006) first prove that the problem for a single machine is NP-hard. A few years later, a pseudo-polynomial algorithm and a fully polynomial time approximation scheme (FPTAS) for multiple parallel machines are proposed by Zhang et al. (2009). Engels et al. (2003) also report more general techniques such as linear programming relaxations. In Moghaddam et al. (2012), the authors study a single-machine scheduling problem with job rejection, while considering again minimization of the weighted sum of completion times plus the total cost of rejected jobs. They propose a mathematical formulation and three different bi-objective simulated annealing algorithms to estimate the Pareto-optimal front for large-size instances. The authors in Zhong et al. (2017) study a scheduling problem on two parallel machines with release times and job rejection. The objective is to minimize the makespan of accepted jobs plus the total cost of rejected jobs. They develop a \((1.5 + \varepsilon )\)-approximation algorithm to solve the problem. Ou et al. (2015) consider m parallel machines in a context where job rejection is allowed. The objective is to minimize the makespan plus the total cost of rejected jobs. They develop a heuristic of complexity \(O(n \cdot log(n) + n/\varepsilon )\) to solve the problem with a worst-case bound of \(1.5 + \varepsilon \). With the same goal, Zhong and Ou (2017) present a 2-approximation algorithm with a complexity of \(O(n \cdot log(n))\) by making use of specific data structures. The authors also propose a PTAS to solve the problem. In Ma and Yuan (2016), the authors consider that the information about each job, including processing time, release date, weight and rejection cost, is not known in advance. They develop a technique named Greedy-Interval-Rejection to produce good solutions. Finally, the authors in Agnetis and Mosheiov (2017) consider the minimization of the makespan in a flow shop with position-dependent job processing times and job rejection. A polynomial time procedure is proposed to solve this problem.

The authors in Kaabi and Harrath (2014) have written a comprehensive survey about scheduling in parallel-machine environments in the presence of availability constraints (which can be induced, in particular, by maintenance activities). Sun and Li (2010) consider two problems. In the first problem, they minimize the makespan on two parallel machines when maintenance activities are performed periodically. In the second problem, maintenance activities are determined jointly with job scheduling, while minimizing the sum of the job completion times. They introduce an algorithm of complexity \(O(n^{2})\) and show that the classical shortest processing time algorithm (SPT) is efficient for the second problem with a worst-case bound less than or equal to \(1+2 \cdot \sigma \), where \(\sigma =t/T\), and T is the maximum continuous working time for each machine and t is the time required to perform each maintenance activity. Li et al. (2017) investigate a parallel-machine scheduling problem where each machine must undergo periodic maintenance. The authors propose two mathematical programming models and two heuristic approaches to address instances of large size. In Qi et al. (2015), the authors investigate a scheduling problem on a single machine with maintenance, in which the starting time of the maintenance is given in advance but its duration depends on the previous machine load.

LO is particularly relevant for industrial applications, as highlighted by Gallay and Zufferey (2018). LO is widely used in control engineering and scheduling applications (T’kindt and Billaut 2006; Aggelogiannaki and Sarimveis 2006; Kerrigan and Maciejowski 2002; Ocampo-Martinez et al. 2008; Respen et al. 2016). In a work closely related to ours, the authors in Thevenin et al. (2017b) model a parallel-machine scheduling problem with job incompatibility through an extension of the graph coloring problem. Different objectives like makespan, number of job preemptions and total time spent by the jobs in the production shop are considered and addressed through LO. A mathematical model, two greedy constructive algorithms, two tabu search methods and an adaptive memory algorithm are proposed to solve the problem.

In this subsection, we highlight how the literature led us to consider the proposed methods, neighborhood structures and objective-function priority.

As discussed before, despite the industrial relevance of the combination of features that characterizes the considered problem (P) (e.g., different parallel machines, rejection costs, inventory penalties, maintenances), it has not attracted attention in academia. Relying on the above literature review, we can, however, deduce that the following ingredients are relevant when facing the features of (P): small-sized instances can be solved with the use of a MILP formulation, whereas meta/heuristics are required for large-sized instances. For tackling the large-sized instances, constructive heuristics are useful, in particular for generating initial solutions for local-search algorithms. Our motivation to employ tabu search comes from its great success for various job-scheduling problems, in particular in a parallel-machine production environment when various objectives are considered (Respen et al. 2016; Thevenin et al. 2017a, b).

Regarding the neighborhood structures, four moves are widely employed and well known in the job-scheduling literature (Thevenin et al. 2015): insert (i.e., move a job somewhere else in the schedule), swap (i.e., exchange two jobs in the schedule), drop (i.e., remove a job from the schedule) and add (i.e., insert a non-scheduled job in the schedule). None of these neighborhood structures can be used alone (in particular when considering job rejection), as a single type of move does not allow to reach all the solutions of the solution space (which means that the search space would not be connected). Several papers [e.g., Shin et al. (2002)] confirmed that using jointly several types of moves leads to better results. For these reasons, the local search that we propose employs various types of moves, including swapping a scheduled job with a non-scheduled jobs (which corresponds to a drop-and-add combination) or reinserting a block of jobs somewhere else in the schedule (which corresponds to an imposed sequence of insert moves).

The two objective functions \(f_1\) (rejection penalty, which is related to shortage costs) and \(f_2\) (weighted sum of completion times, which is related to inventory costs) are well known in the literature. However, the consideration of both of them, furthermore in a lexicographic fashion (i.e., \(f_1 > f_2\)), is new. Their joint consideration within such a hierarchy corresponds to natural priorities encountered in practice, for example Respen et al. (2016), where minimizing shortage is more important than minimizing inventory penalties, Thevenin et al. (2018), where maximizing the gain of the scheduled jobs is more important than minimizing an inventory-oriented penalty, and more generally, throughout the order-acceptance-and-scheduling literature (Cesaret et al. 2012; Shabtay et al. 2013).

Let J be a set of n independent jobs to be scheduled on two parallel, different machines \(M_i\), \(i \in I = \{1, 2\}\). The planning horizon is five days (i.e., 7200 min). Accordingly, we define \({\tilde{d}}\) = 7200 min as the common deadline for all jobs in set J. If a job cannot be feasibly scheduled during the current week, it is then postponed to the next week and a rejection cost is incurred. A feasible solution S of problem (P) is illustrated in Fig. 1. It is made of two schedules on machines \(M_1\) and \(M_2\), with the corresponding sets \(J_S\) and \({\overline{J}}_S\) of accepted and rejected jobs, respectively. Each machine \(M_i\) must undergo a PM at intervals that cannot exceed \(T_i\) minutes. In other words, the interval between the end time of a given PM and the start time of the next PM cannot exceed \(T_i\) minutes. The jobs scheduled between two consecutive PMs define a block, where \(B_{k}^{i}\) is the kth block on machine \(M_i\) scheduled between the \((k-1)\)th and kth PMs (the 0th and last PMs are the start and end of the schedule, respectively). The scheduling of a PM activity on each machine \(M_i\) is flexible and can actually occur before \(T_i\) minutes have elapsed, if it is not possible to avoid it or if it is beneficial to do so. Accordingly, the time length of a block is variable, although it can never exceed \(T_i\) for machine \(M_i\). The duration of a PM activity on machine \(M_i\) is denoted by \(\delta _i\). As illustrated in Fig. 1, there is no idle time in a schedule between two consecutive jobs or between a job and a PM.

Each job \(j \in J\) is characterized by a known processing time \(p_j\), a rejection cost \(u_j\) and a weight \(w_j=h_j+b_j\) which is the sum of its inventory penalty \(h_j\) and its priority level \(b_j\), where a larger \(b_j\) corresponds to a larger penalty. It should also be noted that no preemption is allowed. The two machines are different in the sense that PMs must be done more frequently on \(M_2\). Thus, the maximum time interval \(T_2\) between two consecutive PMs is smaller than \(T_1\) (i.e., \(T_2 < T_1\)). A feasible solution S of problem (P) is evaluated first through objective \(f_1\), which is the total rejection cost of the jobs in \({\overline{J}}_S\), and second through objective \(f_2\), which is the weighted sum of the completion times of the jobs in \(J_S\). Formally, we have \(f_2 = \sum _{j=1}^{n}w_j C_j\), where \(C_j\) is the completion time of job j. With respect to \(f_2\), the WSPT (weighted shortest processing time) rule introduced in Smith (1956) is particularly important, because it optimally solves the \(1 \mid \mid \sum _{j=1}^{n}w_{j}C_{j}\) scheduling problem, which minimizes the weighted sum of completion times on a single machine without side constraints. The WSPT rule states that the jobs should be scheduled in decreasing order of the \(w_j/p_j\) ratios. This rule will be exploited in our algorithms, although in a heuristic way since we have two machines with some operational constraints.

In our study and in line with the literature (Thevenin and Zufferey 2019), \(u_j\) depends on \(b_j\) and \(p_j\). Moreover, we have calibrated \(f_2\) in order to give the same importance to the inventory penalty \(h_j\) and to the priority \(b_j\) of each job j, as both values belong to the same interval (which is [10, 30] in our experiments). Note that if the two components \(b_j\) and \(h_j\) of \(w_j = b_j + h_j\) are fully in conflict for a given job j, it means that \(h_j = 10\) (or 30, respectively) whereas \(b_j = 30\) (or 10, respectively). As a result, \(w_j = b_j + h_j = 40\), which corresponds to the average value of \(w_j\) over all jobs. In other words, a job j such that its inventory penalty and its priority are fully in conflict will have a medium weight (or importance \(w_j\)) in the scheduling process, which is consistent with \(f_2\). In contrast, if \(b_j\) and \(h_j\) are not in conflict, it means either that \(w_j\) is low (typically below 30) or high (typically above 50). Therefore, from this calibration of \((f_2, u_j, b_j, h_j)\), we can deduce the following hierarchy of KPIs: (1) minimize the rejection costs; (2) minimize the bad scheduling of high-priority jobs; (3) minimize the inventory penalties. This hierarchy is in line with the industrial KPIs of various companies (Thevenin et al. 2015, 2016; Respen et al. 2017; Thevenin and Zufferey 2019). Note, however, that our models and methods proposed below are general: they do not depend on the calibration of \((f_2, u_j, b_j, h_j)\). Actually, this calibration has to be made in collaboration with the involved industrial partner in order to capture its KPIs.

The mathematical programming formulation of problem (P) is presented below. It involves five different types of decision variables.It is important to note that job j is rejected when \(z_{j}^{1} = z_{j}^{2} = 0\). For the sake of the MILP formulation, two dummy jobs 0 and \(n+1\) with no processing time are added to the model with completion times \(C_0 = 0\) and \(C_{n+1} = {\tilde{d}}\). We also have \(m^1_{0} = m^2_{0} = 0\). Note finally that M is an arbitrary large number.

Due to the lexicographic ordering of the two objectives, problem (P) can be solved optimally in two steps with an exact solver. A first model is solved with the objective of minimizing \(f_1\) (while ignoring \(f_2\)). Next, a second model is solved, with the objective of minimizing \(f_2\), that includes a constraint for not exceeding the optimal value of \(f_1\).

The first model is the following:This model relies on the fact that the number of PMs and blocks on a machine is at most the total number of jobs. Since a machine has normally fewer PMs and blocks in a solution, there are variables \(m^i_{k}\) that do not correspond to real PMs and whose values do not matter. Equation (1) corresponds to the first objective function considered in this work. Constraints (2) define the relationship between the start time of two consecutive PMs on a machine. The end time of a PM cannot exceed the due date \({\tilde{d}}\), as indicated by constraints (3). Constraints (4) and (5) establish a relationship between variables \(C_j\) and \(m_i^k\). Basically, they state that the completion time of a job assigned to block k on a machine lies between the end time of PM \(k-1\), plus the processing time of the job, and the start time of PM k. Constraints (6) indicate that every scheduled job, including job 0, must have a successor. Constraints (7) indicate that every scheduled job, including job \(n+1\), must have a predecessor. Constraints (8) state that two jobs scheduled consecutively must be assigned to the same machine. Constraints (9) and (10) define bounds on the completion time of each scheduled job. In particular, they force the completion time of a rejected job to be 0. Constraints (11) indicate that two jobs scheduled on the same machine cannot overlap. Constraints (12) state that the sum of processing times over all jobs in the same block on machine \(M_i\) must be less than or equal to \(T_i\). Constraints (13) indicate that an accepted job must be part of a block on a machine. Constraints (14) force each accepted job to be scheduled in a block of either machine \(M_1\) or \(M_2\) but not both. Similarly, constraints (15) force each accepted job to be scheduled either on \(M_1\) or \(M_2\) but not both. Constraints (16) state that if two jobs l and j are scheduled on the same machine, then l is scheduled either before or after j. Constraints (17) set the completion times of dummy jobs 0 and \(n+1\), and the start time of the dummy PM 0 on each machine. Constraints (18), (19) and (20) define the binary variables, whereas the continuous variables are defined in constraints (21).

Let \(f_1^{\star }\) be the optimal value of \(f_1\) after solving the above model. In a second step, constraint \(f_1\le f_1^{\star }\) is added to the model and the latter is solved with objective \(f_2\) only. In other words, the model below is considered:Equation (22) corresponds to the second objective, while constraint (24) bounds the value of the first objective. The solution obtained at the end of this second step is the optimal solution of (P). We observed that the CPLEX solver could only be used for small instances. More precisely, we were able to solve instances with up to 25 jobs within approximately 16 h of computation time. But CPLEX had to be stopped after 24 h of computation time, with a very large optimality gap, on instances with 40 jobs. These results support the use of heuristics and metaheuristics for instances of larger, more realistic, size.

In the following, our problem-solving methodologies are presented, starting with the greedy heuristic to generate a first feasible schedule, which is then improved with tabu search-based metaheuristics.

We can see from the description in Algorithm 1 that GrH starts by calling the greedy construction procedure (presented in Algorithm 2) with a set of jobs \(J'\), which is initially the set of all jobs J (steps 1 and 2). The construction procedure then returns a feasible solution S, which is associated with a set of accepted jobs \(J_S\) and a set of rejected jobs \({\overline{J}}_S\). If not all jobs in \(J'\) are accepted in solution S, we select the \(|J_S|\) jobs in J with the largest \(u_j\) to obtain a smaller set \(J'\) (step 3a). The construction procedure is then called again with the new \(J'\) (step 3b). If the solution S obtained does not contain all jobs in \(J'\), we select again the \(|J_S|\) jobs in J with the largest \(u_j\) to obtain a new set \(J'\) (step 3a again), and the construction procedure is called with the latter (step 3b again). This is repeated until all jobs in \(J'\) are accepted in the obtained solution S, that is, when \(J_S = J'\). Thus, the aim of the loop (step 3) is to schedule as many jobs as possible with the largest rejection costs, since \(f_1\) is the main objective. Next (step 4), we consider the rejected jobs in the last solution obtained and we try to add them at the end of the schedule of machines \(M_1\) and \(M_2\). These jobs are considered one by one in decreasing order of rejection costs. First, we check if the current job j can be added without exceeding the deadline \({\tilde{d}}\) (if the addition of job j leads to exceeding the due time of the next PM, a PM must also be added before job j). If job j is feasible on a single machine, it is added to this machine; if job j is feasible on both machines, it is added to the machine with minimum completion time \(C_j\) (in order to account for \(f_2\)); if job j is not feasible on any machine, it is skipped.

One can remark that steps 3 and 4 are complementary. Indeed, step 3 aims at scheduling as many jobs with the top (i.e., highest) rejection costs. Next, step 4 fills the “holes” in the schedule, by greedily adding other jobs to the solution (i.e., with respect to decreasing rejection costs).

The construction procedure, described in Algorithm 2, produces a solution S from scratch in a greedy way. Using the set \(J'\) of jobs provided in input, a new job j is selected and added, at each iteration, at the end of the schedule of \(M_1\) or \(M_2\). This is repeated (step 3) as long as there are jobs which can be added to the schedule of at least one machine without exceeding the deadline \({\tilde{d}}\) (if the addition of job j leads to exceeding the due time of the next PM, a PM must also be added before job j). This feasibility check is performed through calls to AssignFeasible, as described in Algorithm 3. AssignFeasible considers the set of jobs provided in input and returns only the subset of feasible jobs. In the process, each feasible job is tentatively assigned (but not scheduled) to a machine. If job j is feasible on a single machine, it is added to this machine; if job j is feasible on both machines, it is added to the machine with minimum completion time \(C_j\) (to account for \(f_2\)). Note that the procedure AssignFeasible is a variant of the worst-fit greedy heuristic for the well-known bin-packing problem (Korte et al. 2012; Johnson 1973).

In the construction procedure, the selection of the next job is done as follows. First (step 3a), we consider the subset \(J'_1 \subset J'\) of the \(q_1\) (parameter \(< n\)) jobs with the largest \(w_{j}/p_{j}\) ratio, which is a good heuristic rule with respect to objective \(f_2\). Second (steps 3b and 3c), we select the subset \(J'_2 \subset J'_1\) containing the \(q_2\) (parameter \(< q_1\)) jobs with the smallest completion times \(C_j\), as determined in AssignFeasible. For each job \(j \in J'_2\) (and its associated machine), we compute the slack time with the due time of the next PM, and we finally select the job \(j^{\star }\) with the smallest slack time. The slack time is the time period between the completion time of the last job scheduled in the considered machine and the due starting time of the next PM. The job \(j^{\star }\) is then added (as well as a PM before \(j^{\star }\), if required) at the end of the schedule of its associated machine. Note that we choose to schedule jobs with the smallest slack times in order to try to reduce the number of PMs (as we are likely to better use the available working time between two consecutive PMs). Finally, it should be noted that all jobs are considered in the first and second steps when the number of remaining jobs is smaller than \(q_1\) and \(q_2\), respectively.

Preliminary experiments that are not reported here showed that the following parameter setting is reasonable: \((q_1, q_2) = (0.2n, 0.1n)\). We have tested \(q_1 \in \{ 0.05n, 0.1n, 0.2n, 0.3n, 0.4n, 0.5n, n\}\) and \(q_2 = \frac{q_1}{2}\).

TSMN improves the initial starting solution produced by the greedy heuristic GrH, while always maintaining feasibility. As shown in Algorithm 4, TSMN has three different phases with different neighborhood structures. The algorithm stops when \(I^{TSMN }\) global iterations have been performed (step 2) and the best-encountered solution \(S^{\star }\) is returned. The latter is updated after each step of Algorithm 4 with respect to the lexicographic ranking \(f_1 > f_2\).

Each global iteration corresponds to three consecutive tabu search phases. Phase 1 optimizes objective \(f_1\), whereas the sequence of scheduled jobs obtained at the end of Phase 1 is modified in Phases 2 and 3 to optimize \(f_2\). In these two last phases, no scheduled job can be rejected; thus, only the sequences of jobs on the two machines are modified.

The neighborhood structures of the tabu search procedures exploit different types of moves for updating the current solution (as explained below). The best non-tabu move—over a random proportion Pr of all possible moves—is performed at each iteration of each tabu search procedure. The following values have been tested for parameter Pr in our computational study: 0.25, 0.5, 0.75 and 1. Each modification to the current solution needs to be correctly evaluated. It implies that jobs may have to be shifted to the right or to the left (in the latter case, to fill any idle time between two consecutive jobs). However, this is done only from the point of insertion of a new job to the end of the schedule, since nothing changes before the insertion point.

When a move is performed, its reverse move is forbidden for tab iterations, where tab is an integer randomly chosen in [5, 10] for Phases 1 and 3, and in [3, 7] for Phase 2 (these intervals were tuned after preliminary experiments).TSMNcomprises a standard criterion aspiration: The tabu status of a move is revoked if it leads to a solution which is better than the best-encountered solution. There is no risk of cycling in this case, since this new best solution has clearly not been previously visited. The stopping criterion for each Phase \(l \in \{1, 2, 3\}\) corresponds to a maximum number of iterations, denoted as \(I^{TSMN }_l\). Preliminary experiments that are not reported here showed that the following parameter setting is reasonable: \((I^{TSMN }_1, I^{TSMN }_2, I^{TSMN }_3) = (2n, n/5, 3n)\). It should be noted that \(I^{TSMN }_2\) is smaller than the two other values given the relatively small size of the corresponding neighborhood, where blocks are moved rather than individual jobs.

Phase 1. The tabu search Tabu(S;  SWAP\(^{1}\); INSERT\(^{1}\)) optimizes only \(f_1\) (rejection cost) using a neighborhood structure based on SWAP\(^{1}\) and INSERT\(^{1}\). More precisely, a move consists in sequentially swapping two jobs \(j \in J_S\) and \(j' \in {\overline{J}}_S\) (SWAP\(^{1}\)), and then, in trying to insert in the schedule jobs \(j'' \in {\overline{J}}_S\) with a large rejection cost (INSERT\(^{1}\)). In SWAP\(^{1}\), every pair of jobs \(j \in J_S\) and \(j' \in {\overline{J}}_S\) are considered for exchange (it could appear as a disadvantage at first sight, but it helps in diversifying the exploration of the solution space). That is, a scheduled job is rejected and replaced by a previously rejected job. After each such potential exchange, the jobs \(j'' \in {\overline{J}}_S\) are sorted in decreasing order of rejection cost \(u_{j''}\). Then, INSERT\(^{1}\) considers the jobs in \({\overline{J}}_S\) one by one for insertion in the schedule, with the goal of inserting as many jobs as possible while keeping solution feasibility. Indeed, when a swap is applied between \(j \in J_S\) and \(j' \in {\overline{J}}_S\), the processing time \(p_{j'}\) can well be greater than \(p_j\), which may lead to exceeding the deadline \({\tilde{d}}\) (if it occurs, such a swap move is ignored). Conversely, when \(p_{j'}\) is smaller than \(p_j\), some idle time is created in the schedule and this flexibility can then be exploited by INSERT\(^{1}\). Note that each swap move is evaluated with respect to objective \(f_1\) after having performed the subsequent insertion moves.

Phase 2. The tabu searches in Phases 2 and 3 are aimed at improving the scheduling of accepted jobs, as identified in Phase 1, with respect to objective \(f_2\). The neighborhood structure SWAP\(^{2}\) exchanges every pair of blocks scheduled on the same machine only. Indeed, after some preliminary tests, we discovered that swapping blocks between the two machines was not beneficial because the blocks are not of the same size (\(T_2 < T_1)\). Consequently, the schedule of machine \(M_2\) often exceeded the deadline after such a move, as illustrated in Fig. 2 for the exchange of blocks \(B_1^2\) and \(B_2^1\).

Phase 3. The neighborhood structure in Phase 3 is based on \(\hbox {SWAP}^{3}\) moves where pairs of jobs, scheduled on the same machine or not, are exchanged. We consider all possible swaps between two jobs j and \(j'\), except when j appears before \(j'\) in the schedule of a given machine and \(w_{j'}/p_{j'} < w_j/p_j\) (to be in line with the WSPT rule). The goal here is to obtain a better scheduling of the jobs within the blocks with respect to objective \(f_2\).

This tabu search is inspired from the work in Zufferey and Vasquez (2015), where satellite range scheduling problems are addressed. As opposed to TSMN, infeasible neighbor solutions are considered but are immediately repaired to restore feasibility. This approach leads to the design of a simpler algorithmic scheme, as shown in Algorithm 5. There are two main phases in CTS, each based on a tabu search which is aimed at optimizing one of the two objectives.

An initial solution S is first generated using the greedy heuristic GrH (step 1). A total number of \(I^{CTS }\) global iterations are then performed (step 2). First, objective function \(f_1\) is optimized in Phase 1 through insertion moves (based on the below-described INSERT\(^{2}\) neighborhood structure). A maximum number of \(I^{CTS }_1\) iterations are performed with this tabu search, but the procedure is repeated as long as an improvement to the best-encountered solution is observed (step 2a). Next, \(f_2\) is optimized in Phase 2 with the SWAP\(^{4}\) neighborhood structure (step 2b), which is similar to the SWAP\(^{3}\) used in TSMN. This tabu search is stopped after a maximum number of \(I^{CTS }_2\) iterations. As opposed to Phase 1, the procedure is not repeated as long as an improvement to the best-encountered solution is observed, because \(f_2\) is a secondary objective. Since the two neighborhood structures explored in CTS are similar to the ones in Phases 1 and 3 of TSMN, we have also fixed \((I^{CTS }_1, I^{CTS }_2) = (2n, 3n)\).

Like TSMN, a tabu tenure is associated with each move. In Phase 1, a rejected job is tabu for reinsertion in the schedule for tab iterations, whereas the reverse swap move is tabu in Phase 2. In both cases, tab is an integer randomly chosen in the interval [5, 10], based on preliminary experiments. The aspiration criterion is the same as in TSMN. The neighborhood structures are now presented.

Phase 1. Objective \(f_1\) (rejection cost) is optimized using the neighborhood structure INSERT\(^{2}\), where every rejected job is considered for insertion at every position in the schedule of machines \(M_1\) and \(M_2\). It is important to note that the insertion is enforced even if the deadline \({\tilde{d}}\) is exceeded. In such a case, the tentative solution is immediately repaired by removing accepted jobs that are positioned from the maintenance occurring just before j (or from the first job if there is no maintenance before j) to the end of the schedule (the selection of such candidate jobs to be removed limits the impact of a job removal on the solution structure, while facilitating the evaluation). More precisely, while the solution is not feasible, we sequentially remove a job \(j'\) from \(J_S\) in increasing order of their rejection costs (i.e., focus on \(f_1\)), and we break ties with the smallest ratio \(w_{j'}/p_{j'}\) (i.e., focus on \(f_2\)).

Phase 2. Objective \(f_2\) (weighted sum of completion times) is optimized using the neighborhood structure SWAP\(^{4}\) (see SWAP\(^3\) in TSMN). When a swap leads to exceeding the deadline \({\tilde{d}}\) on a machine, feasibility is restored as in Phase 1.

The baseline local-search heuristic works as CTS, with the following simplifications in order to better capture what a decision maker would do in practice.Indeed, from a practical standpoint, a decision maker is likely to perform two modifications. First, s/he could enforce the scheduling of a rejected job j (even if other jobs have to be rescheduled or removed to maintain feasibility) because j has suddenly received a big priority with respect to a client. Second, s/he could swap two scheduled jobs, for instance, to easily delay the production of a job because its raw material or components are not yet available.

In order to compare, in a fair manner, BLSH with TSMN and CTS, BLSH is restarted with a different initial solution provided by GrH, as long as the computation time limit (employed for TSMN and CTS as well) is not reached, and the best-encountered solution is returned at the end.

Since there are no available benchmark instances in the literature for problem (P), we carried out experiments based on randomly generated data, inspired from a real case in the pharmaceutical industry, as reported in Zufferey et al. (2017). We propose small-sized instances (with \(n=20\) jobs) for experiments involving the MILP, and large-sized instances for comparing the meta/heuristics (with \(n \ge 100\)). The weight \(w_j=b_j+h_j\) is distributed in the interval [20, 60]. That is, the priority \(b_j\) is randomly selected in the set \(\lbrace 10, 20, 30 \rbrace \), whereas \(h_j\) is uniformly distributed over the interval [10, 30]. Finally, \(u_j\) is uniformly distributed over the interval \([b_jp_j/2, 2b_jp_j]\), since the rejection cost of a job j depends on its priority \(b_j\) and its processing time \(p_j\). All the instances and best results can be found in http://​dx.​doi.​org/​10.​17632/​hbs7pm7yhb.​1.

Considering the large instances, Table 2 reports the impact of Phase 2 and Phase 3 of TSMN with respect to the objective functions \(f_1\) and \(f_2\). At this point, we must remember that Phase 1 is aimed at reducing \(f_1\), whereas Phases 2 and 3 both focus on \(f_2\). For each value of n (which involves 10 instances) and each objective function \(f_i\) (\(i \in \{1,2\}\)), we report the following information: the average value of \(f_i\) obtained by TSMN (i.e., with all its phases), the augmentation percentage (Gap(%)) of \(f_i\) if TSMN is performed without Phase 2, and the augmentation percentage of \(f_i\) if TSMN is performed without Phase 3. The larger the gaps are, the worse the solutions are.

The following observations can be made. First and interestingly, even if Phase 2 and Phase 3 are dedicated to \(f_2\) only, they both contribute to the reduction of \(f_1\) because all the gaps associated with \(f_1\) are positive. In other words, Phase 2 and Phase 3 propose promising solutions to Phase 1, and the collaboration among the phases seems to be efficient. Second, regarding \(f_2\) (and often regarding \(f_1\)), Phase 3 seems to be more important than Phase 2, as the values of “Gap(%) w/o Ph3” are larger than “Gap(%) w/o Ph2.” In other words, when reworking the schedule of one machine at a time, swapping two jobs appears to be more beneficial than swapping two blocks. Finally, when observing \(f_1\) for one instance group at a time (i.e., L1, L2 and L3), the following trend appears: the gaps decrease when n moves from its smallest value to its largest value (i.e., from \(n=100\) to \(n=110\) in L1, from \(n=200\) to \(n=220\) in L2, from \(n=300\) to \(n=330\) in L3). This can be explained by the fact that more jobs are likely to be rejected if we have more jobs to schedule within the same planning horizon. In other words, the augmentation of n has a bigger impact on \(f_1\) when compared to \(f_2\), since \(f_1\) is directly associated with job rejection. Therefore, the importance of Phase 2 and Phase 3 often decreases with the increase of n.

Table 3 presents the following results for the 30 small instances (labeled from I1 to I30) with respect to \(f_1\). First, for the MILP, we indicate either “Optimal” if an optimal solution was found within the allowed 2 h of computing time, or “Feasible” if only a feasible solution was found (i.e., without any proof of optimality). The associated time to find an optimal/feasible solution is also given. The number of rejected jobs is indicated in column OUT(MILP) for the MILP, and OUT(TSMN) for TSMN. Next, we indicate the gap in percentage between GrH and MILP, computed as \(100 \times [(GrH - \text{ MILP})/\text{MILP}]\) (for a single run of GrH). A positive gap means that MILP is better than GrH. Finally, we provide the same information, but for the best tabu search TSMN (see the next subsection for a comparison between TSMN and CTS). Note that no computing time is given for GrH and TSMN, because such methods can find their best solutions in an order of magnitude of a second.

The following observations can be made.Considering the objective function \(f_2\) and the same time limits, additional experiments (not reported here) were performed for the nine instances for which the MILP is able to prove optimality on \(f_1\). For such experiments, each method was constrained by the fact that no job can be rejected (i.e., \(f_1\) cannot be deteriorated). The average results are the following: the MILP was able to generate a feasible solution in 7.4 min (without proving optimality within the allocated 2 h); the MILP outperforms GrH by 9.63%; TSMN outperforms the MILP by 1.87% (but using less than 5 s to do it). In other words, such experiments are in line with the results on \(f_1\).

Tables 4 and 5 compare BLSH, CTS and TSMN with respect to objectives \(f_1\) and \(f_2\), respectively. For each size n (which involves a group of 10 instances), we give the following information.The following observations can be made.Relying on the above observations, the superiority of TSMN over CTS for objective \(f_1\) could be explained by the larger diversification ability of TSMN (i.e., its capacity to explore various regions of the solution space). Indeed, in contrast with CTS, TSMN does not spend any energy in repairing infeasible solutions, but only focuses on the quick generation of feasible solutions. Moreover, its Phase 2 brings some diversity (as full blocks of jobs are swapped). On the contrary, the superiority of CTS over TSMN for objective \(f_2\) could be explained by the larger exploitation ability of CTS (i.e., its capacity to intensify the search in a specific region of the solution space). Indeed, relying on an efficient repair process, CTS is able to enforce some solution modifications and to deeply investigate a move (indeed, SWAP\(^{4}\) of CTS can enforce some swap moves involving two jobs assigned to the same machine, whereas SWAP\(^{3}\) of TSMN cannot).

The number of rejected jobs (denoted here as R) is an important KPI from an industrial perspective. For each instance, a way to estimate R is presented in Sect. 6.1.1. Considering the large instances, the average performance of all the solution methods with respect to this KPI is presented in Table 6, along with the estimations. The following observations can be made. First and as expected, for each group of instances, R increases with the increase of n. Second, in line with the previous results, the methods can be ranked as follows: \(GrH< BLSH {}< CTS {} < TSMN \). Finally, the gap between the estimated R and the average number of rejected jobs provided by TSMN is reasonable for the instance groups L1 and L2, but not for L3. This highlights the complexity in estimating R for the largest instances.