Upper and lower bounds for the permutation flowshop scheduling problem with minimal time lags

Abstract

In this paper, we consider the problem of scheduling $n$ jobs in an $m$-machine permutation flowshop with minimal time lags between consecutive operations of each job. The processing order of jobs is to be the same for each machine. The time lag is defined as the waiting time between two consecutive operations of each job. Upper bounds for the problem are provided by applying heuristic procedures based on known and new rules. Lower bounds based on Moore’s algorithm and logic-based Benders decomposition are developed. For the last one, we define a long time horizon on the last machine divided into many segments of time. We combine a mixed integer linear programming to allocate jobs to time segments and scheduled using the constraint programming. Then, computational results are reported.

1 Introduction

We address an important scheduling problem that occurs frequently in manufacturing and production contexts. We study the permutation flowshop scheduling problem with minimal time lags. According to the standard notation given by Graham et al. [8], this problem can be noted $F_{\pi }|\theta _{i,k}^{min}|\,\sum _{i}U_{i}$. It can be described as follows: There are $n$ jobs to be scheduled for processing on $m$ machines. Each machine can process at most one operation at a time and preemption is not allowed. Each job $i\in \{1,2,\ldots ,n\}$ is processed on the $m$ machines during $p_{i,1},\, p_{i,2},\ldots ,\, p_{i,m}$ time units successively subject to a due date $d_{i}$. We consider here additional constraints that extend the classical model: for each job, a definite amount of time must elapse between each two consecutive operations which has to be greater than or equal to a non negative value called minimal time lag $(\theta ^{min})$. Our objective is to find a schedule for which the total number of tardy jobs is minimized.

Although this problem arise in many industrial sectors, it proves to be quite difficult to solve. Many industrial situations involving specific manufacturing processes may be modelled using minimal time lags, for example in the field of biotechnologies and chemistry where the chemical reactions with variable processing times may be represented by minimal time lags [1]. Other examples are given by Deppner [4].

Over the scheduling literature, Hariri and Potts [9] present the first exact algorithm for the NP-hard $F_{m}||\sum U_{i}$ problem. They use a branch and bound algorithm that can solve problems with up to 3 machines with 25 jobs. For the same problem, Lenstra et al. [17] show that the problem is NP-hard for 2 machines. Lodree et al. [18] propose a new sequencing rule, Earliest Adjusted Due Date (EADD) for the $F_{m}|r_{i}|\sum U_{i}$ problems with up to 50 jobs on 3 machines. The rule is derived by considering a variation of the Moore’s algorithm [19] which is then proven to outperform the shortest processing time dispatching rule.

Recently, Dhouib et al. [5] turn to propose two mathematical formulations for the permutation flowshop scheduling problem with setup times and time lags constraints; then a simulated annealing algorithm is developed to solve this problem. Ruiz-Torres et al. [20] solve minimizing the number of tardy jobs in flow shop environment with operation and resource flexibility. They develop lower bound procedure and efficient solution approaches to solve each sub-problem. For the case of common due dates, Croce et al. [3] treat the 2-machine to minimize the total number of tardy jobs, which is an NP-hard in the ordinary sense, a compact multidimensional knapsack problem formulation of the problem is introduced together with several structural properties. Then, they propose a branch and bound procedure to find an optimal solution to the problem.

Solution methods based on partitioning the problem into many smaller problems make the problem more easy to be solved. Recently, great interests are oriented to the logic-based Benders decomposition. We can model a problem as a Mixed Integer Linear Programming $(MILP)$ or a Constraint Programming $(CP)$ which is not perfomant especially with the complex structure. The $MILP$ is effective only when we are interested in the optimization aspect and the $CP$ is more effective only for the feasibility criterion especially for highly constrained discrete optimization problems. To exploit the strength of the $MILP$ and the $CP$, we integrate them by the logic-based Benders decomposition. According to Hooker [14], the hybrid method generally achieves speedups of two or three orders of magnitude on larger instances when minimizing the number of late tasks, and it solves significantly more problems to optimality.

We consider a permutation flowshop problem with minimal time lags between operations. The objective function is to minimize the total number of tardy jobs which have different due dates. We try to adopt this technique to our problem to generate lower bounds. To make the proposed approach viable, we focus on the last machine $m$ to define a long time horizon divided into many segments of time. We develop a lower bound on the completion time on the first $m-1$ machines for each job. This bound is considered as a release date for each job to be processed to the last machine after its assignment to the time segment. So that, an assignment problem for each job on each segment of time becomes the master problem and is solved by $MILP$, while the scheduling problem becomes the subproblem which separates into several independent scheduling problems is solved by $CP.$ It is then compared to another lower bound based on Moore’s algorithm. The developed lower bounds are evaluated by determining the relative deviation from a developed upper bound. This last one is chosen as the best one among some proposed heuristic algorithms.

The organization of the remainder of this paper is as follows: in Sect. 2, we present the problem under consideration and we describe the used notations. Section 3 is devoted to present three proposed heuristic procedures useful to provide upper bounds. In Sect. 4, we present the developed lower bounds. We remind some previous works about the logic-based Benders decomposition over the literature, and we detail its application. Thereafter, we describe the lower bound based on Moore’s algorithm. Then, computational results are reported in Sect. 5, and finally in Sect. 6 we discuss concluding remarks.

2 Problem’s definition and nomenclatures

The considered problem $(F_{\pi }|\theta _{i,k}^{min}|\,\sum _{i}U_{i}$) is characterized by $n$ jobs and each one is composed of $m$ operations as we described previously. These jobs have to be processed on a set of $m$ machines $(k=1,2,\ldots ,m)$ following the same order: first on machine 1, second on machine 2, and so on until machine $m$. The order of the execution of the jobs is the same on all machines. So, only one sequence is considered. The processing time of job $i$ on machine $k$ $(p_{i, \,k})$, the minimal time lag which is a waiting time that must exist between the end of the operation $k$ and the beginning of the operation $k+1$ of the job $i$, and the due date $(d_{i})$ are fixed in advance. Then, for a considered sequence of jobs, we denote by $C_{i,k}$ the completion time of job $i$ on machine $k$ $(i=1,2,\ldots ,n;\, k=1,2,\ldots ,m)$. If job $i$ finishes on machine $k$ at $C_{i,k}$ then $i$ can start on machine $k+1$ at time $t_{i,k+1}$ such that $t_{i,k+1}\ge C_{i,k}+\theta _{i,k}^{min}$. We consider the number of tardy jobs as a criterion to minimize. A job is called tardy if its completion time exceeds its due date $(C_{j}>d_{j})$, otherwise it is early. We define $T=\sum _{i}U_{i}$ as the number of tardy jobs where $U_{i}=1$ if the job is tardy and 0 otherwise. As same, we define “$E$” as the number of early jobs $(E=\{i|C_{i}<d_{i}\}).$ As we are interested in the permutation flowshop problem, we consider the completion time on the last machine $m$ for each job $i$ $(C_{i,m}\forall i=1,2,\ldots ,n)$ to define the set of tardy and early jobs ($T=\{i|C_{i,m}>d_{i}\}$ and $E=\{i|C_{i,m}<d_{i}\}$ respectively).

It is known that the general problem of permutation flowshop without time lags is NP-hard in the strong sense even if all jobs have a common due date [17], then the considered problem is obviously NP-hard in the strong sense. $\pi =\{\pi (1),\,\pi (2),\ldots ,\pi (n)\}$ is used to design the permutation or the sequence of jobs where $\pi (1)$ for example means the job in the first position. The following example is used to explain better the problem which shows the scheduling of 3-jobs on 3 machines. The data are given in Table 1.

Table 1 The data

Here, $p_{i,1}$ for example design the processing time of job $i$ on machine 1, and $\theta _{i,1}^{min}$ design the minimal time lag of job $i$ between machines 1 and 2. Then, the scheduling is presented in Fig.1. It shows that for a given sequence of jobs $(\pi =2-1-3$), there are one tardy job which is the job in the second position in the sequence as its completion time (the noted value on the last machine which is equal for this job 25) exceeds its due date (23), then $T=\{1\}$. However, the jobs in the first and third positions in the considered sequence are early as their completion times (17 and 31 respectively) doesn’t exceed their due dates (20 and 33 respectively) and then $E=\{2,$ 3}.

Fig. 1

Scheduling figure

Then the used nomenclatures in this paper are described as follows:

• $n$: number of jobs $(i\in \{1,2,\ldots ,n\})$

• $m$: number of machines $(k\in \{1,2,\ldots ,m\})$

• $J:$ segments of time $(j\in \{1,2,\ldots ,J\})$

• $p_{i,k}:$ processing time of job $i$ on machine $k$

• $\theta _{i,k}^{min}:$ minimal time lag of job $i$ between machine $k$ and machine $k+1$

• $C_{i,k}:$ completion time of job $i$ on machine $k$

• $d_{i}:$ due date of job $i$

• $r_{i}:$ release date of job $i$

• $d_{i,k}:$ due date of job $i$ on machine $k$

• $r_{i,k}:$ release date of job $i$ on machine $k$

• $E$: set of early jobs

• $T$: set of tardy jobs

• $U_{i}$ =1 if the job $i$ is tardy and 0 else

• $\pi (i),k:$ the job in position $i$ in the schedule sequence on machine $k$

• $C_{\pi (i),k}$ : completion time of job in position $i$ on machine $k$

• $d_{\pi (i)}$: due date of job in position $i$

• $p_{\pi (i),k}:$ processing time of job in position $i$ on machine $k$

3 Upper bounds

Consider a permutation flowshop scheduling problem with minimal time lags. Some heuristic procedures are proposed where the generated solution is considered as an upper bound of the optimal solution. They are based on three different rules: the well known rule “Shortest Processing Time ($SPT$)”, and two other new proposed rules “Shortest Sum of Processing Times ($SSPT$)” and “Adjustment on the Bottleneck Machine ($ABM$)”. Then the obtained sequences by using the proposed rules are scheduled by applying the “$Algorithm\, C$” described later to obtain the total number of tardy jobs. Here $\pi (i),k$ denote the job in position $i$ in the schedule sequence $\pi$ on machine $k$; $i=1,2,\ldots ,n$ and $k=1,2,\ldots ,m$.

3.1 Shortest processing time (SPT ) rule

The $SPT$ rule states to sequence the jobs in nondecreasing order of processing times. As we are interested in a permutation flowshop problem, we may find $m$ different sequences, one sequence for each machine $k\in \{1,\ldots ,m\}$ and the jobs are arranged according to $p_{\pi (1),k}\le p_{\pi (2),k}\le \cdots \le p_{\pi (n),k}$. We can determine another sequence which is the $(m+1)^{th}$ one using the rule of Total Processing time $(TP_{\pi (1)}\le TP_{\pi (2)}..\le TP_{\pi (n)})$ as same in [7]. Now, we determine the total tardiness of all the $m+1$ sequences and we select the final schedule with the smallest total number of tardy jobs. This rule determines the final sequence through the following algorithmic steps:

Step 1: Let $k=1$.

Step 2: Sequence jobs in non-decreasing order of $p_{i,k}(p_{\pi (1),k}\le p_{\pi (2),k}\le \cdots \le p_{\pi (n),k})$ on machine $k$.

Step 3: Define a permutation schedule on all machines using this sequence and determine the total number of tardy jobs by applying the $Algorithm\, C$ described later.

Step 4: If $k=m$, go to step 5, otherwise let $k=k+1$, and go to step 2.

Step 5: Sequence jobs in non-decreasing order of $TP_{i}(TP_{\pi (1)}\le TP_{\pi (2)}\le ..TP_{\pi (n)})$. Define a permutation schedule on all machines using this sequence and then calculate the total number of tardy jobs of all the jobs by applying the “$Algorithm\, C$” described later.

Step 6: Select the final schedule with the smallest total number of tardy jobs among the $m+1$ schedules, and stop.

3.2 Shortest Sum of Processing Times (SSPT) rule

This rule is similar to the well known SPT rule, but instead of using the individual job processing time on each machine, we consider for each job the total processing times on all machines plus the exact time lags between each consecutive couple of operations. Then by obtaining a sequence, we calculate the total number of tardy jobs by applying the “Algorithm C” described later.

3.3 Adjustment on the Bottleneck Machine (ABM) rule

In this proposed algorithm, we focus on the bottleneck machine $(b\in \{1,2,\ldots ,m\})$ to adjust the number of tardy jobs. This machine is defined as the machine that requires maximum sum of processing times of all jobs amongst all machines. We determine for each job its ready time to be processed on this machine and we derive its due date. Then, we can define two sets of jobs: a set of tardy jobs and a set of early jobs. The adjustment is done by sequencing the set of tardy jobs in a decreasing order of the tardiness values and the early jobs in an increasing order of the earliness values, then we concatenate the sequence of the early jobs to the set of tardy jobs to form the final sequence to be scheduled using the “$Algorithm\, C$” described later. It is described as follows:

Step 1.

• Determine the release date of job $i$ on machine $b$

  $$\begin{aligned} r_{i,b}=\left\{ \overset{b-1}{\underset{l=1}{\sum }}(p_{i,l}+ \theta _{i,l}^{min})\right\} \end{aligned}$$

• Determine the due date of job $i$ on machine $b$

  $$\begin{aligned} d_{i,b}=d_{i}-\left( \overset{m-1}{\underset{l=b+1}{\sum }}\left( p_{i,l} +\theta _{i,l}^{min}\right) +p_{i,m}\right) \end{aligned}$$

Step 2.

Determine two sets of jobs: set of early jobs ($E$) and set of tardy jobs ($T$) on the bottleneck machine.

$$\begin{aligned} T&= \{i|r_{i,b}+p_{i,b}>d_{i,b}\}\hbox { and we define }u_{i\in T}=r_{i,b}+p_{i,b}-d_{i,b}\\ E&= \{i|r_{i,b}+p_{i,b}<d_{i,b}\}\hbox { and we define }s_{i\in E}=d_{i,b}-p_{i,b}-r_{i,b} \end{aligned}$$

Step 3.

Sequence the jobs in an increasing order of $s_{i}\,\forall i\in E$ to provide the sequence $E_{1}$

Sequence the jobs in a decreasing order of $u_{i}\,\forall i\in T$ to provide the sequence $T_{1}$

The final sequence $(\pi )$ to be scheduled is defined by concatenating the sequence $E_{1}$ to $T_{1}\Rightarrow \pi =T_{1}+E_{1}$

The obtained sequence is scheduled using the following “Algorithm C”

As it is shown from the “Algorithm C”, the constructed schedule is feasible as the precedence and the minimal time lags constraints hold, and the job sequence follows the obtained permutation $\pi$. Indeed, it is not necessary to verify the minimal time lag constraints for the job in the first position as this one has none precedent and its operations are consequently placed exactly after the minimal time lags. Also, it is shown for the other jobs that their operations are scheduled as soon as possible with respect to the precedence and the minimal time lags constraints. The complexity of this algorithm is $O(nm)$.

4 Lower bounds

In this section, lower bounds are developed which are based on the logic-based Benders decomposition and Moore’s algorithm.

4.1 Logic-based Benders decomposition based-lower bounds (LB1)

In what follows, we will remind the literature of the logic-based Benders decomposition technique, then we detail its application. We will determine the associated $MILP$ of the studied problem, its $CP$, and an hybrid approach by combining the $MILP$ and the $CP$. The hybrid approach proves a great performance to generate results more interesting and less consuming time than the ones provided by only $MILP$ or $CP$. The motivation to use this hybrid method comes from its meaningful efficiency found by many researches over the literature ($e.g$ [14–16]). The found result by each one is a lower bound of the optimal solution for the considered problem.

The way to adopt this hybrid method is to define a long time horizon noted $H$ $(H\ge C_{\pi (n),m})$ divided into $J$ segments of time as it is shown in the following Fig. 2. These segments can be inequal, but we will consider them equal for the seek of simplicity. Here, the considered problem can be decomposed into an assignment portion and a scheduling portion. Central managers assign each job $i\in \{1,\ldots ,n\}$ to the time segment $j\in \{1,2,\ldots ,J\}$, whereas operations managers prepare detailed schedules for each segment. As the done assignment can be infeasible, the operations managers are used to call the central managers to ask for different allocations of jobs. The assignment problem becomes the master problem and is solved by $MILP$, while the scheduling problem becomes the subproblem which separates into several independent scheduling problems is solved by $CP$. Hence, the discretization of the time segments is relevant and a new decision variable $x_{i,t}$ is introduced which is equal to 1 if the job $i$ starts at time $t$ and 0 else where $N$ discrete times are defined starting from 0.

Fig. 2

Horizon time

We are interested in a permutation flowshop scheduling problem where the jobs have to be processed on each machine in the same order. When we define a time horizon for each machine, it will be hard to specify non-overlapping time intervals for the machines $1,\ldots , k-1$ in advance, without sacrificing optimality. Suppose jobs $i$ and $i'$ are assigned to intervals $j$ and $j+1$, respectively, on machine $k$. Then a valid lower bound for the start time of job $i'$ on machine $k-1$ would be less than a valid upper bound for the start time of job $i$ on machine $k-1$. The intervals on machine $k-1$ would therefore overlap. One way to make this approach viable to the studied problem is to focus on the last machine $m$ to define a long time horizon. Then, we determine a lower bound on the completion time of each job $i\in \{1,2,\ldots ,n\}$ on the $m-1$ machine, this bound is considered as a release date of each job $(r_{i})$ to be processed on the last machine. $r_{i}$ is generated from the interval $[CT_{1},\, CT_{n}]$ where $CT_{1}$ is a lower bound on the completion time of the job in the first position; and $CT_{n}$ is a lower bound on the completion time of the job in the last position. Where

$$\begin{aligned} CT_{1}&= \underset{i}{min}\overset{m-1}{\underset{k=1}{\sum }}(p_{i,k} +\theta _{i,k}^{min})) \\ CT_{n}&= \underset{1\le k\le m-1}{max}\left\{ \overset{n}{\underset{i=1}{\sum }} p_{i,k}+\overset{m-1}{\underset{l=1}{\sum }} \underset{i}{min}\left( p_{i,l}+\theta _{i,l}^{min}\right) -\underset{i}{min}p_{i,k}\right\} \end{aligned}$$

Then when the job $i\in \{1,\ldots ,n\}$ is assigned to the segment of time $j\in \{1,\ldots ,J\}$, its starting time $(t\times x_{i,t})$ can’t be smaller than its release date $(r_{i})$ which is supposed to be the amount of time necessary to its completion on the first $m-1$ machines (the lower bound on the completion time defined already). If the generated value $(r_{i})$ from the interval $[CT_{1},\, CT_{n}]$ is greater than the time segment in which the job is assigned, it will be result in an infeasibility of this assignment and another one is used. $y_{1}$ and $y_{J+1}$ are used to design the start time and finish time of the long time horizon. The starting time of the horizon time can be assumed by considering the minimum sum of processing times on machines 1 until $m-1$ plus the minimal time lags between them among all the jobs, so it can be calculated as $\min _{1\le i\le n}( \sum _{k=1}^{m-1}p_{i,k}+\theta _{i,k}^{min})$ as same for lower bound on the completion time of the job in the first position.

4.1.1 Previous work

The classical Benders decomposition is useful for solving problems that contain groups of variables of different natures. However, it requires that the subproblem can be a continuous linear or nonlinear programming problem. Scheduling is a highly combinatorial problem that has no practical linear or nonlinear programming model [15]. The logic-based Benders decomposition generalizes classical Benders. It requires great interests recently, some trial values are assigned to the variables of the master problem (in our case, define the assignment of jobs to segments of time) and then we try to find the best solution with these values. In logic-based Benders decomposition, the central element is the derivation of Benders cuts which are obtained by solving the inference dual of the subproblem rather than a linear programming dual in classical benders. The solution of the inference dual is a proof of optimality when the variables of the master problem are fixed to their current values. So that, the process continues until the master problem and subproblem converge in value.

Logic-based Benders decomposition is introduced by Hooker and Yan [11] in the context of verifying logic circuits. Hooker [12] extends the Benders decomposition to a logic-based context for propositional satisfiability and 0-1 programming problem. Hooker [13] shows how to derive effective Benders cuts for at least one such case, minimum makespan problems. Computational tests show that combining $MILP$ and $CP$ to be 100 to 1,000 times faster than $MILP$ or $CP$ when all tasks have the same deadlines. In a related work, Hooker [14] applies a logic-based Benders decomposition method to minimize the number of late tasks, and minimizing total tardiness. The main contribution is a relaxation of the cumulative scheduling subproblem, also much better solutions for problems that cannot be solved to optimality are obtained. Motivated by the complementary strength of the $MILP$ and $CP$, Coban and Hooker [2] apply logic-based Benders to minimize tardiness in single-facility scheduling problems with many jobs and long time horizons. Also, Hooker [15] applies the same method to solve an important class of planning and scheduling problems where the tasks assigned to a facility may run in parallel subject to resource constraints (cumulative scheduling). The objective is to minimize cost, makespan, or total tardiness. Then, significant computational speedups are obtained, of several orders of magnitude for the first two objectives, relative to the state of the art in both $MILP$ and $CP$.

Jain and Grossmann [16] successfully apply such a method to least cost planning and scheduling problems to process a set of orders using dissimilar parallel machines subject to release and due dates constraints where the subproblems are disjunctive scheduling problems (jobs must be run one at a time). According to computational results, the hybrid models are shown to perform two to three orders of magnitude reduction in $CPU$ time compared to standalone $MILP$ and $CP$ models.

Harjunkoski and Grossmann [10] consider multistage scheduling problems in which the subproblems are feasibility problems rather than optimization problems. Thus, the Benders cuts are generally simple as the subproblem is a feasibility problem rather than an optimization problem.

4.1.2 Mixed integer linear programming

The problem can be formulated as follows: each job $i\in \{1,2,\ldots ,n\}$ has to be assigned to a segment of time $j\in \{1,2,\ldots ,\, J\}$, $p_{i}$ and $d_{i}$ represent the processing time and the due date respectively of job $i$. The binary variable $x_{i,t}$ is already defined which is equal to 1 if the job $i$ starts at time $t$, and 0 otherwise. $t$ indicates the starting time of this job; then, to which segment job is assigned becomes trivial and the decision variable $x_{i,t}$ represent a segment. Here, we can refer to some proposed $MILP$ for other different problems and mainly the single machine scheduling problem (see i.g. [14, 15]).

If we want modeling the scheduling problem as $MILP$, the model is:

$$\begin{aligned}&Min\,\sum _{i}U_{i} \end{aligned}$$

(1)

$$\begin{aligned}&s.t\;\;\;\underset{t}{\sum }x_{i,t}=1\,\quad \forall i \end{aligned}$$

(2)

$$\begin{aligned}&x_{i,t}+x_{\overline{i},\overline{t}}\le 1\, \quad for\, all\, i,\, t,\overline{\, i}\, and\,\overline{t}=t,\ldots ,t+p_{i}-1 \end{aligned}$$

(3)

$$\begin{aligned}&x_{i,t}=0\;\forall t\le r_{i}\, \quad and\, \quad t\ge y_{j+1}-p_{i}\,\quad \forall i \end{aligned}$$

(4)

$$\begin{aligned}&\underset{t}{\sum }(t+p_{i})\, x_{i,t}-d_{i}\le NU_{i}\;\quad \forall i \end{aligned}$$

(5)

$$\begin{aligned}&U_{i}\ge 0\;\quad \forall i \end{aligned}$$

(6)

$$\begin{aligned}&x_{i,t}\in \{0,\,1\}\quad \forall i,\, t \end{aligned}$$

(7)

The objective (1) is to minimize the total number of tardy jobs ${(\sum _{i}}U_{i})$ where $U_{i}$ is a binary variable equal to 1 if the job is tardy and 0 else. Each job has to be assigned to only one time interval is represented in constraints (2). Equation (3) prevents overlap from one segment to another one. Constraints (4) state that a job $i$ can’t start executing before its release date and cannot exceed the limit of the associated segment. Tardy jobs are defined in (5) where $N$ is the number of discrete times starting with 0. Constraints (6) state that $U_{i}$ is a non negative variable. Constraints (7) specify $x_{i,t}$ as a binary variable.

4.1.3 Constraint programming formulation

Recently, the constraint programming became a leading technique for solving complex decision support problems. In general, systems based on $CP$ are much more expressive and hence easy to understand. It is increasingly used for solving scheduling problems as its flexibility is well suited for real-life scheduling problems. It works by incorporating some restrictions on the possible solution into a programming environment. Some recent works emphasize the $CP$ application for different scheduling problems and mainly the single machine problem (see e.g. [13, 14]).

Here, new decision variables are introduced: $z_{i}$ is a decision variable representing the time interval of job’s execution on the time segment, this definition is same of the processing time’s job definition. $Q_{j}$ is another decision variable defining the sequence of $z_{i}$ time intervals at time segment $j.$ It’s known that this variable can be found easily with some software used to solve the $CP$. For example, jobs 2 and 3 are assigned to the segment $j=2$ described by a start time $y_{2}$ and a finish time $y_{3}$; then $Q_{2}$ is defined as the sequence $Q_{2}=2,\,3$. The $CP$ for the problem can be formulated as follows:

$$\begin{aligned}&Min\, sum\,(i\, in\, Jobs)U_{i}\end{aligned}$$

(8)

$$\begin{aligned}&s.t\;\;\; StartOf(z_{i})\ge r_{i}\; forall\, i\end{aligned}$$

(9)

$$\begin{aligned}&noOverlap\,(Q_{j})\, forall\, j\,\end{aligned}$$

(10)

$$\begin{aligned}&(endOf\,(z_{i})-d_{i})\le NU_{i}\, forall\, i \end{aligned}$$

(11)

Minimizing the total number of tardy jobs is formulated by (8). Constraints (9) state that a job $i$ can start only after its completion time on the precedent machines. By constraints (10) the sequence of jobs’ time intervals cannot overlap on each machine as only one job have to be processed at a time. Constraints (11) define the tardy jobs. Some constraint-based tools are provided for imperative languages in the form of libraries. ILOG is one of the most successful companies to produce such tools. High level modeling languages exist for model constraint problems and specifying search strategies such that the OPL language.

4.1.4 The hybrid method

Logic-based Benders decomposition applies to problems of the form:

$$\begin{aligned}&Min\, f(x,y)\nonumber \\&s.t\, c(x,\, y)\nonumber \\&x\in D_{x},\, y\in D_{y} \end{aligned}$$

(12)

$C(x,\, y)$ is a set of constraints containing variables $x,\, y$. $D_{x}$and $D_{y}$ denotes the domains of $x$ and $y$ respectively. A general Benders algorithm begins by fixing $x$ at some trial value $\overline{x}\in D_{x}$. This results in the subproblem:

$$\begin{aligned}&Min\, f(\overline{x},\, y)\nonumber \\&s.t\,\; c(\overline{x},\, y)\nonumber \\&y\in D_{y} \end{aligned}$$

(13)

The inference dual is the problem of inferring the tightest possible lower bound on $f(\overline{x},\, y)$ from $c(\overline{x},\, y)$. The inference dual of the subproblem is:

$$\begin{aligned}&Max\,\nu \nonumber \\&s.t\,\;\; c(\overline{x},\, y)\rightarrow f(\overline{x},\, y)\ge \nu \end{aligned}$$

(14)

The dual problem is to find the best possible lower bound $\nu ^{*}$ on the optimal cost that can be inferred from the constraints, assuming $x$ is fixed to $\overline{x}$. This bound is expressed as a function $\nu _{\overline{x}}(x)$ of $x$ yielding a Benders cut $z\ge \nu _{\overline{x}}(x)$. The algorithm proceeds as follows. At each iteration h, we solve a master problem where its constraints are the Benders cuts so far generated.

$$\begin{aligned}&Min\, z\nonumber \\&s.t\,\;\nu _{x^{h}}(x),\, h=1,\ldots ,H\nonumber \\&x\in D_{x} \end{aligned}$$

(15)

For each iteration $h$, we define $x^{h}$ the solution of the $h$ master problem from iteration 1 until $H-1$ to provide $\nu _{1}^{*},\ldots ,\nu _{H-1}^{*}$ optimal solutions. Then the solution $\overline{x}$ of the previous subproblem to define the next one. $z_{h}^{*}$ provides the lower bound of the optimal value of the problem and $\nu ^{*}=min\{\nu _{1}^{*},\ldots ,\nu _{H-1}^{*}\}$. Then, the algorithm continues until $z_{h}^{*}=\nu ^{*}$.

For this hybrid method, the scheduling problem which is the subproblem separates into several independent scheduling problems according to the number of the time segments. Let $Y_{j}$ is the set of time intervals for $J$ segments where $Y_{j}=\{t:\, y_{j}\le \, t\,\le y_{j+1}-1\}$. The Benders approach formulates a master problem that assigns jobs to time segment $j$ and a subproblem that schedules the jobs assigned to time segments. We write the master problem using an $MILP$ model that minimizes the number of tardy jobs. New decision variables are introduced in the master problem $U_{i,j}$ and $U$ which represent the number of tardy jobs in the segment $j$ and the total number of tardy jobs respectively. In iteration $h$ of the Benders algorithm, the master problem is:

$$\begin{aligned}&Min\, U\end{aligned}$$

(16)

$$\begin{aligned}&s.t\,\underset{t}{\;\;\;\sum }x_{i,t}=1\,\quad \forall i \end{aligned}$$

(17)

$$\begin{aligned}&x_{i,t}=0,\,\forall t\le r_{i}\, \quad and\, t\ge y_{j+1}-p_{i}\;\forall i \end{aligned}$$

(18)

$$\begin{aligned}&\underset{t\in Y_{j}}{\sum }(t+p_{i}-d_{i})\, x_{i,t}\le N\, U_{i,j}\,\quad \forall i,\, j \end{aligned}$$

(19)

$$\begin{aligned}&U\ge \sum _{i}\underset{j}{\sum }U_{i,j}\,\quad \forall i,\, j\end{aligned}$$

(20)

$$\begin{aligned}&x_{i,t}\in \{0,\,1\}\,\quad \forall i,\, t\end{aligned}$$

(21)

$$\begin{aligned}&U_{i,j}\ge 0\quad \forall i,\, j \end{aligned}$$

(22)

$$\begin{aligned}&Benders\, cuts\, in\, iterations\,1,\ldots ,h-1\end{aligned}$$

(23)

$$\begin{aligned}&relaxation\, of\, subproblem \end{aligned}$$

(24)

The objective function (16) is minimizing the total number of tardy jobs. (17), (18), and (19) are same as the constraints of the MILP defined previously where $Y_{j}$ is the set of job’s time intervals. (20) and (22) are used to define the number of tardy jobs in the segment $j$. The main idea is to determine optimal assignments of jobs to time segments $t\in Y_{j}$, and then perform feasible sequencing of the jobs for the given assignments at a lower level. The binary variable $x_{i,t}=1$ when a job $i$ is assigned to the time interval $t$. Once, an assignment of jobs to time intervals is determined by solving the master problem; then, the scheduling subproblem is solved by $CP$. The subproblem decouples into a single-segment scheduling problem. Let $J_{hj}$ the set of jobs assigned to segment $j$ in the iteration $h.$ Then, the subproblem becomes:

$$\begin{aligned}&Min\, sum\,(i\in J_{hj})\, U_{i}\end{aligned}$$

(25)

$$\begin{aligned}&s.t\, startOf\,(z_{i})\ge r_{i}\, \quad forall\, i\in J_{hj}\end{aligned}$$

(26)

$$\begin{aligned}&startOf\,(z_{i})\ge y_{j}\, \quad forall\, i\in J_{hj} \end{aligned}$$

(27)

$$\begin{aligned}&endOf\,(z_{i})\le y_{j+1}\, \quad forall\, i\in J_{hj} \end{aligned}$$

(28)

$$\begin{aligned}&noOverlap\,(Q_{j})\, \quad forall\, j \end{aligned}$$

(29)

$$\begin{aligned}&(endOf(z_{i})-d_{i})\le NU_{i}\, \quad forall\, i\in J_{hj} \end{aligned}$$

(30)

For each segment $j$, $CP$ is solved separately. (25) and (26) are same as in the previous formulated $CP$. (27) and (28) state that the start and the end of each job’s time interval have to respect the time limits of the respective segment. Constraints (36) and (37) are same as defined previously. $LetU=\{U(i)\}$, if $U_{hj}^{*}$is the optimal value of the previous problem, then ${\sum _{j}}U_{hj}^{*}$is the minimum number of tardy jobs for all the time segments.

We note $\underline{U_{hj}}$a valid lower bound on the number of tardy jobs. Since $x_{i,t}=0$ when job $i$ is not assigned to the time segment $t$ we have

$$\begin{aligned}&\underline{U_{hj}}\ge U_{hj}^{*}-U_{hj}^{*}\underset{i\in J_{hj}}{\sum }(1-x_{i,t})\,\quad \forall \, j \end{aligned}$$

(31)

$$\begin{aligned}&\underline{U_{hj}}\ge 0,\, all\, j \end{aligned}$$

(32)

Over all the time intervals, we have a lower bound on the total number of tardy jobs:

$$\begin{aligned} U\ge \underset{j}{\sum }\underline{U_{hj}} \end{aligned}$$

(33)

Then, the benders cuts (23) in the master problem for the iteration $h$ consist of the inequalities (31), (32), and (33) obtained in the iterations $1,\ldots ,h-1$. It is straightforward to relax the subproblem when minimizing the number of tardy jobs. As we described and defined above, let $r_{i}$ considered as a lower bound on the completion time of job $i$ on machines from 1 until $m-1$. When executed on the time interval $j$, these jobs span a time interval at least: $M=y_{j}+{{\sum _{i\in \{y_{j},\, y_{j+1}\}}^{n}}}(r_{i}+p_{i})$. We added $y_{j}$as each job $i$ can’t start earlier than the start time of the time segment.

If $M>y_{j+1}-y_{j}$ then at least one task is tardy, and the number of tardy jobs in the time interval $k$ is at least

$$\begin{aligned} \frac{M-(y_{j+1}-y_{j})}{\underset{i\in \{y_{j},\, y_{j+1}\}}{max}\{r_{i}+p_{i}\}} \end{aligned}$$

(34)

rounded up to the nearest integer. As the same way we determine the number of tardy jobs for each time segment. Then, a lower bound on the number of tardy jobs can be obtained for all the horizon.

The jobs have to be indexed according to their deadline $(d_{1}\le d_{2}\le \cdots \le d_{n})$, $l=1,\,2\ldots ,\, n$ . $J(0,\, d_{l})$ is a set of jobs with time interval between 0 and $d_{l}$. For any $j$, the last scheduled job in this set can finish no sooner than time $t={\sum _{i\in J(0,\, d_{l})}}(r_{i}+p_{i})$ and the last job has due date no later than $d_{l}$. Then, we can obtain the following relaxation:

$$\begin{aligned} U&\ge \sum _{i}U_{i}\\ U_{i}&\ge \frac{{\sum _{i\in J(0,\, d_{l})}^{n}}(r_{i}+p_{i})-d_{l}}{{max}_{i\in J(0,\, d_{l})}\{r_{i}+p_{i}\}}\quad \forall \, i \end{aligned}$$

which becomes (24) in the master problem.

4.2 Moore’s algorithm based-lower bound (LB2)

Moore’s algorithm is known to define the sets of tardy jobs and early jobs for the single machine scheduling. We adopt this algorithm to the studied problem to minimize the total number of tardy jobs. We define a sequence of early jobs $\sigma$and a set $S$ of jobs not yet sequenced. $C(\sigma ,\, k)$ is the earliest time at which machine $k$ is available to process jobs of $S$. As we aim to define a single machine scheduling, we desaggregate the processing of jobs of $S$ on machines $l=1,2,\ldots ,k-1$ and we relax the constraints that machines $l=k+1,\ldots ,m$ can process only job at a time. By considering a subproblem $P_{k}$on machine $k\in \{1,2,\ldots ,m\}$, each job $i\in S$ is available for processing at time $C(\sigma ,\, k)={\min _{i\in S}}\{{{\sum _{l=1}^{k-1}}}(p_{i,l}+\theta _{i,l}^{min})\}$, requires $p_{i,k}$ processing time on machine $k$, and requires time $t={{\sum _{l=k+1}^{{m-1}}}}(p_{i,l}+\theta _{i,l}^{min})$ for its completion and has a due date $d_{i}$. Then, Moore’s algorithm can be applied to generate a list of the tardy jobs $|T|$. It states to begin by sequencing jobs in increasing order of due dates, and then removing jobs with larger processing times. By applying the procedure to each machine, the lower bound on the total number of tardy jobs can be defined as $LB 2 = max\{|T_{1}|,\,|T_{2}|,\ldots ,|T_{m}|\}$. Then, the Moore’s algorithm is applied as follows:

Step 1: sequence the jobs according to the Earliest Due Date rule to find the current sequence $(i_{\pi (1)},\, i_{\pi (2)},\ldots ,i_{\pi (n)})$ such that $d_{\pi (1)}\le \, d_{\pi (2)}\le \cdots \le d_{\pi (n)}$

Step 2: find the first tardy job, say $i_{\pi (i)}$ in the current sequence. If no such job is found. Go to step 4.

Step 3: reject longest job in $1-i_{\pi (i)}$. Return to step 2 with a current sequence on job shorter than before.

Step 4: form an optimal schedule by taking the current sequence and appending to it the rejected jobs which may be sequenced in any order.

5 Computational results

In order to assess the quality of the proposed upper and lower bounds, we carry out series of experiments. Random instances are generated as follows: The processing times and the minimal time lags are generated as the same way in [6] from a uniform distribution between 20 and 50 and $[0,\,\theta ^{min}]$ respectively where $\theta ^{min}\in \{0,\,7,\,14\}$. The due dates are generated as $d_{i}=P_{i}\times D_{range}$, where $P_{i}={{\sum }_{j=1}^{m-1}}(p_{i,j}+\theta _{i,j})+p_{i,m}$ and $D_{range}=[0.8-1.2]$. The experimentations conducted in this research are run on a DELL PC/2.20GHz with 4.00Go RAM. The heuristic algorithms and the $LB2$ are implemented with MATLAB 7.6.

First experiments are done to test the performance of the proposed heuristic algorithms used to provide the upper bounds. We classify 7 different sizes of test problems, and we solve 10 problems for each size then the average value is considered. The 7 test problems consist of two different values of the number of machines (5 and 10) and 6 different values of the number of jobs (10, 15, 20, 30, 40, and 50). Here, the time lags interval is fixed to [0, 7]. The number of tardy jobs for each problem size and for each heuristic algorithm are shown in the following Table 2.

Table 2 Performance of the upper bounds

According to the results shown in Table 2, the three algorithms prove their efficiency to provide good results for different size problems. The three algorithms are almost similar for the different tested problems just the one based on the $ABM$ rule is the best one. As its principle consists in adjusting the number of tardy jobs in the bottleneck machine, it is not surprising to obtain the best found sequence. The algorithms are solved in less than 1 second and we could not distinguish a meaningful difference between all problems in the $CPU$ time.

Second experiments are done to assess the performance of the proposed lower bounds. Let $H$ be the long time horizon. The length of each segment is generated between $[10,\, H\times \alpha ]$ where $\alpha$ is a small coefficient generated between [0.1, 0.5]. We set four different configurations of number of jobs $n\in \{10,\,15,\,20,\,25\}$, and two different configurations for number of machines $m\in \{5,\,10\}$.

15 problems classified according to the problem sizes and the time lags intervals are presented. 10 instances are tested for each problem and the average value is considered. The results are summarized in Table 3. To evaluate the proposed lower bounds, we determine the relative deviation (%) for each found solution from the upper bound $(UB)$ provided by the $ABM$ algorithm (as it is the best one) as follows $\%=\frac{UB-LB}{LB}\times 100$. ($Nb=$ Number of tardy jobs). The Table 3 is described as follows: the first column indicates the problem size ($n$, $m$) where $n$ is the number of jobs and $m$ is the number of machines. The second column corresponds to the time lags interval [0, $\theta ^{min}$] where $\theta ^{min}\in \{0,\,7,\,14\}$. The columns 3 and 4 correspond to the result of the upper bound for the different problem sizes and the $CPU$ time needed to solve it respectively. The next columns from 4 to 10 indicate the deviation percentage of the lower bounds from the upper bound for the three methods $CP$, $MILP$, and the $hybrid$ one respectively where each of them is followed by a column indicating the corresponding $CPU$ time needed to solve it. We note $LB1$ for all of them. Column 11 presents the speedup factor of the $MILP$ method relative to the hybrid one which is determined as $\frac{Time\,(MILP)}{Time\,(hybrid)}$. The two last columns deal with the second developed lower bound based on Moore’s algorithm and the corresponding $CPU$ time respectively. (The $CPU$ time is given in seconds).

Table 3 Performance of the lower bounds

We use IBM ILOG CPLEX Optimization Studio to solve the $MILP$ (using CPLEX Optimizer), the $CP$ (using ILOG CPLEX CP Optimizer), and the logic-based Benders method. All three methods are implemented using the OPL script language. We fix the time limit at 3600 s; then if the execution time overcomes this limit, we consider the value reached already at this time.

For each problem size, the number of tardy jobs increases with the increasing time lags intervals. It is an expected result as it is due to the increasing value of the completion times. In spite that the $CP$, the $MILP$, and the $hybrid\, method$ consume more $CPU$ time than the $LB2$, they generate very tight lower bounds for some problems. We can confirm that the $CP$ can provide the optimal solution with a percentage 47 %, the $MILP$ with a percentage equal to 40 %, and the hybrid method with 40 % too. For these three methods, the quality of the generated lower bounds is very interesting. The results of the hybrid method are obtained as the coincidence of both master and subproblem results developed for this method. According to Hooker [15], by linking $MILP$ and $CP$, we obtained substantial speedups relative to the existing state of the art in both $MILP$ and $CP$. The hybrid method is shown to be faster than the $MILP$ which is in turn faster than the $CP$. It is characterized by its ability to solve problems until the size (25, 5). Its fastness is proved by the speedup factor relative to the MILP which range between 1.11 and >$41.31$ as it is shown in the table above. The $LB2$ consume more less $CPU$ time but the relative deviation is larger.

6 Conclusion

The permutation flowshop scheduling problem with minimal time lags to minimize the total number of tardy jobs is considered in this paper. Upper and lower bounds are developed. The upper bounds are given by three proposed heuristic algorithms based on different rules. The best one is used then to evaluate the quality of the developed lower bounds. $MILP$ and $CP$ are proposed and then integrated through a logic-based Benders decomposition. They are shown to be efficient to provide tight lower bounds and the hybrid method is specified by its fastness against the $CP$ and $MILP$ methods. The lower bound based on Moore’s algorithm is shown to be easiest to be found. However, its quality is less interesting.