Mixed integer linear programming models for Flow Shop Scheduling with a demand plan of job types

Abstract

This paper presents two mixed integer linear programming (MILP) models that extend two basic Flow Shop Scheduling problems: ${\text{Fm}}$/${\text{prmu}}$/${\text{C}}_{ \hbox{max} }$ and ${\text{Fm}}$/${\text{block}}$/${\text{C}}_{ \hbox{max} }$. This extension incorporates the concept of an overall demand plan for types of jobs or products. After using an example to illustrate the new problems under study, we evaluated the new models and analyzed their behaviors when applied to instances found in the literature and industrial instances of a case study from Nissan’s plant in Barcelona. CPLEX solver was used as a solution tool and obtained acceptable results, allowing us to conclude that MILP can be used as a method for solving Flow Shop Scheduling problems with an overall demand plan.

1 Preliminaries

The Flow Shop Scheduling problem (FSP) is a sequencing problem that has received considerable attention from professionals and researchers in recent decades due in part to the wide range of production environments it can model (Pinedo 2016).

In an FSP, a set of jobs or products $J$ ($D$ elements) needs to be processed in a group of machines $K$ ($m$ elements) arranged in series. All jobs must proceed through all machines in the same order, starting with machine 1 and ending with machine $m$.

Job $j \in J \left( {j = 1,..,D} \right)$ requires a processing time $p_{j,k} \ge 0$ in machine $k \in K$$\left( {k = 1,..,m} \right)$. The overall goal of FSP is to determine a release sequence in which to process the jobs that will optimize one or more efficiency criteria.

A version of FSP, the Permutation Flow Shop Problem (PFSP), considers the storage space between two consecutive machines to be unlimited and therefore assumes that when operation $\left( {j,k} \right)$ of job $j \in J$ in machine $k > 1$ ($k \in K$) is completed, the machine is able to process the next job in the sequence from the moment the job is released by the previous machine $k - 1$. Using the notation proposed by Graham et al. (1979), this problem is known as $Fm$/$prmu$/$\gamma$, where parameter $\gamma$ symbolizes the selected efficiency measure. The following efficiency metrics are among the most common: (1) Makespan or the time required to complete all operations $\left( {j,k} \right)$ in the workshop, $C_{max}$, and (2) the average time required to complete such operations, $C_{med}$.

There are production systems, also composed of machines arranged in series, in which it is not advisable to separate products or jobs within a process due to the product size (e.g., chassis, buses), the nature of the jobs (e.g., chemical reactors), or a lack of space. Under such circumstances, when the operation on a product of machine $k < m$ is completed, the operation will release the product to the next machine $k + 1$ in order to process the next product in the sequence, but if machine $k + 1$ is busy, machine $k$ will be blocked even though it has completed its operation. Using again the notation of Graham et al. (1979), this problem is called $Fm$/$block$/$\gamma$, where $\gamma$ again symbolizes the efficiency measure considered.

The nature of these problems is highly combinatorial and the minimization of the makespan is NP-hard in the strong sense (Hoogeveen et al. 1996; Hall and Sriskandarajah 1996; Yu et al. 2004). For this reason, heuristic procedures have traditionally been used to solve these problems in both permutation versions (Nawaz et al. 1983; Osman and Potts 1989; Taillard 1990; Reeves 1995; Aggoune 2004; Ying and Liao 2004; Fernandez-Viagas et al. 2017) and in versions with interruptions between machines (Logendran and Sriskandarajah 1993; Caraffa et al. 2001; Ronconi 2004, 2005; Ribas et al. 2011; Grabowski and Pempera 2007; Han et al. 2012; Pan and Wang 2012; Lin and Ying 2013; Nouri and Ladhari 2017, Ozolins 2017; Tasgetiren et al. 2017).

After explaining the two problems of interest, we will consider the unrealistic conditions that, in our view, affect the set of jobs $J$ performed in some industrial sectors.

• Traditionally in the various versions of FSP, the elements of the set of jobs $J$ are special, with unusual qualities or more specifically are unique jobs or products.

• If we consider some industrial sectors, such as the automotive sector, it is difficult to find realistic problems whose purpose is to determine efficient sequences of 270 or more different products. In fact, it is absurd to think of a daily sequence of 270 engines or 300 car bodies or 500 chassis or 800 buses, all of which are entirely different.

• Due to the above reasons and for practical purposes, it is reasonable to believe that a typology can be naturally established on the set of jobs $J$ (products, parts, etc.), and it is therefore possible to discuss types of engines or car bodies or chassis or motors.

• In conclusion, in some industrial sectors, it makes sense to discuss types of jobs or types of products or types of parts.

After these considerations, the remainder of this paper is structured as follows: In Sect. 2, we formalize the natural extension of the FSP when jobs are replicated, which for us means that there exists a demand plan for job types. In Sect. 3, we propose using mixed integer linear programming to model these problems. In Sect. 4, we illustrate the problems under study with an example. In Sect. 5, we perform a computational experiment to analyze the behavior of the generated models. Finally, Sect. 6 is dedicated to conclusions and proposals for future research.

2 Problems $Fm$/$\beta$/$\gamma$/$d_{i}$: $Fm$/$\beta$/$\gamma$ with product types

Formalization:

$Fm$/$\beta$/$\gamma$/$d_{i}$ is a family of sequencing problems that establishes a bijective application between the elements of a set ${\mathcal{T}}$ of ordinals ($T$ elements), which correspond to positions in a sequence of releases to manufacturing: $\pi \left( {T) = (\pi_{1} ,.,\pi_{T} } \right)$, and the elements of a set $J$ of jobs or products ($D$ elements, with $D = T$).

The jobs or products in group $J$ are classified into exclusive types or classes, $J_{i}$, that satisfy: $J = \mathop {\bigcup }\nolimits_{i \in I} J_{i}$ and $J_{i} \cap J_{{i^{\prime}}} = \emptyset , \forall \left\{ {i,i^{\prime}} \right\} \in I$; where $I$ is the set of job types $\left( {i = 1,..,n} \right)$. Parameter $\beta$ can take the permutation (prmu) or blocking (block) values, parameter $\gamma$ represents the possible efficiency metrics (e.g., $C_{max} , C_{med}$), vector ${\mathbf{d}}$ represents the demand plan for the considered job types, and $d_{i}$ symbolizes the number of jobs of type $i \in I$ within $J$; $d_{i} = \left| {J_{i} } \right| \forall i \in I$, satisfying: $\mathop \sum \nolimits_{\forall i} d_{i} = D = T.$

The units of $J$ travel in order through a set $K$ of $m$ machines arranged in series. We assume that the production of a job of type $i \in I$ requires a processing time $p_{i,k}$, measured under normal operation conditions, in machine $k \in K \left( {k = 1, \ldots ,m} \right)$, and that these times are heterogeneous.

The differences between classes $J_{i}$ (e.g., 4 × 4 s, vans, trucks) indicate the heterogeneity of the processing times $p_{i,k}$, which results in natural decouplings between the processors (operators and robots) assigned to machines. In some cases, operators must wait for a product to be released from the previous machine before beginning work, and in others, when storage between machines is not possible, the operator will have to wait while “blocked” from the completion of the operation in progress in the next machine, even if his operation on the product in progress is completed. Based on the description above, in this paper we are not going to contemplate the possibility of interrupting operations and will leave this option for future work.

The purpose of problems $Fm$/$\beta$/$\gamma$/$d_{i}$ is to obtain a sequence of replicated jobs or products ($d_{i}$), in a line with $m$ machines, with the possibility of blocking or not according to $\beta$, and with the objective of optimizing the efficiency metric represented by the $\gamma$ value. To formalize this purpose, two mathematical models adapted to mixed integer linear programming (MILP) are presented here.

3 MILP models for problems $Fm$/$\beta$/$\gamma$/$d_{i}$

$J$ :

Set of jobs or products (Jobs): $j = 1,.,D$

${\mathcal{T}}$ :

Set of positions in the production sequence of products: $t = 1,.,T$

$I$ :

Set of types of jobs or products (Job Types): $i = 1,.,n$

$J_{i}$ :

Set of jobs or products of type $i \in I$

${\mathbf{d}}$; $d_{i}$:

Demand plan of a job types vector and demand of the jobs or products of type $i$$(i = 1,.,n$), with $d_{i} = \left| {J_{i} } \right| \forall i \in I$ and satisfying: $\mathop \sum \nolimits_{\forall i} d_{i} = D = T \equiv \left| {\mathcal{T}} \right|$

$K$ :

Group of machines: $k = 1,.,m$

$p_{i,k}$ :

Processing time of a job or product of type $i \in I$ in machine $k \in K$

$C_{max}^{0}$ :

Upper limit of the makespan or minimum completion time of all the jobs in all machines. This can be calculated based on a reference sequence $\pi^{0} \left( T \right)$ obtained by a heuristic algorithm

$x_{i,t}$ :

Binary variable whose value is 1 if a job or product of type $i \in I$ is released to production in the $t$-th position $\left( {t = 1,.,T} \right)$, and 0 otherwise

$\pi \left( \cdot \right)$ :

Partial sequence, $\pi \left( t \right) = \left( {\pi_{1} ,.,\pi_{t} } \right)$, and full sequence, $\pi \left( T \right) = \left( {\pi_{1} ,.,\pi_{T} } \right)$, of production of jobs or products $j \in J$

$\rho_{k,t}$ :

Processing time of the $t$-th job in production sequence $\pi \left( T \right)$ in machine $k \in K$

$C_{k,t}$ :

Time of completion of the $t$-th job $\pi_{t}$ in production sequence $\pi \left( T \right)$ in machine $k \in K$. If blocking is considered, $C_{k,t}$ symbolizes the release time of job or product $\pi_{t} \in \pi \left( T \right)$ in the machine $k \in K$

$C_{i}$ :

Time of completion of the last job or product of type $i \in I$ in the last machine $\left( {k = m} \right)$; that is:$C_{i} = \mathop {\hbox{max} }\limits_{t} \left\{ {C_{m,t} :x_{i,t} = 1} \right\}$. By convention, we will say that $C_{i}$ is the time of completion of the batch of parts of type $i \in I$, which is equivalent to the time when all jobs in group $J_{i}$ have been completed

$C_{max}$ :

Makespan: Time of completion of the last job or product $\pi_{T}$ of the production sequence $\pi \left( T \right)$ in the last machine $\left( {k = m} \right)$; that is: $C_{max} = C_{m,T}$

$C_{med}$ :

Average time of completion of batches ($\forall i \in I$): $C_{med} = \frac{1}{n}\mathop \sum \nolimits_{\forall i} C_{i}$

MILP model for the problem $Fm$/$prmu$/$C_{max}$/$d_{i}$

$$ {\text{MILP-}}1 \cdot Fm/prmu/C_{max} /d_{i} :\quad \hbox{min} C_{max} \equiv \hbox{min} C_{m,T} $$

(1)

Subject to:

$$ \mathop \sum \limits_{i = 1}^{n} x_{i,t} = 1\quad \forall t = 1, \ldots ,T $$

(2)

$$ \mathop \sum \limits_{t = 1}^{T} x_{i,t} = d_{i} \quad \forall i = 1, \ldots ,n $$

(3)

$$ \rho_{k,t} = \mathop \sum \limits_{i = 1}^{n} p_{i,k} x_{i,t} \quad \forall k = 1, \ldots ,m\quad \forall t = 1, \ldots ,T $$

(4)

$$ C_{k,t} \ge C_{k,t - 1} + \rho_{k,t} \quad \forall k = 1, \ldots ,m\quad \forall t = 1, \ldots ,T $$

(5)

$$ C_{k,t} \ge C_{k - 1,t} + \rho_{k,t} \quad \forall k = 1, \ldots ,m\quad \forall t = 1, \ldots ,T $$

(6)

$$ x_{i,t} \in \left\{ {0,1} \right\}\quad \forall i = 1, \ldots ,n\quad \forall t = 1, \ldots ,T $$

(7)

$$ C_{k,0} = 0\quad \forall k = 1, \ldots ,m $$

(8)

$$ C_{0,t} = 0\quad \forall t = 1, \ldots ,T $$

(9)

In model (MILP · $Fm$/$prmu$/$C_{max}$/$d_{i}$), objective function (1) represents the minimization of the makespan; equalities (2) help to ensure a position in the sequence of every job or product; equalities (3) are used to ensure the demand plan (vector ${\text{d}}$) is met; equalities (4) link the processing time of each type of product and machine ($p_{i,k}$) with the corresponding processing time of the $t$-th job of the sequence ($\rho_{k,t}$); restrictions (5) and (6) serve to limit the minimum completion times of the jobs ($C_{k,t}$), according to the production sequence $\pi \left( T \right)$, in the machines of group $K$; conditions (7) force the decision variables ($x_{i,t}$) to be binary; and finally (8) and (9) set the start of completion times.

MILP model for the problem $Fm$/$block$/$C_{max}$/$d_{i}$

$$ {\text{MILP-}}2 \cdot Fm/block/C_{max} /d_{i} :\quad \hbox{min} C_{max} \equiv \hbox{min} C_{m,T} $$

(10)

Subject to:

$$ \mathop \sum \limits_{i = 1}^{n} x_{i,t} = 1\quad \forall t = 1, \ldots ,T $$

(11)

$$ \mathop \sum \limits_{t = 1}^{T} x_{i,t} = d_{i} \quad \forall i = 1, \ldots ,n $$

(12)

$$ \rho_{k,t} = \mathop \sum \limits_{i = 1}^{n} p_{i,k} x_{i,t} \quad \forall k = 1, \ldots ,m\quad \forall t = 1, \ldots ,T $$

(13)

$$ C_{k,t} \ge C_{k,t - 1} + \rho_{k,t} \quad \forall k = 1, \ldots ,m\quad \forall t = 1, \ldots ,T $$

(14)

$$ C_{k,t} \ge C_{k - 1,t} + \rho_{k,t} \quad \forall k = 1, \ldots ,m\quad \forall t = 1, \ldots ,T $$

(15)

$$ C_{k,t} \ge C_{k + 1,t - 1} \quad \forall k = 1, \ldots ,m\quad \forall t = 1, \ldots ,T $$

(16)

$$ x_{i,t} \in \left\{ {0,1} \right\}\quad \forall i = 1, \ldots ,n\quad \forall t = 1, \ldots ,T $$

(17)

$$ C_{k,0} = 0\quad \forall k = 1, \ldots ,m $$

(18)

$$ C_{0,t} = 0\quad \forall t = 1, \ldots ,T $$

(19)

$$ C_{m + 1,t} = 0\quad \forall t = 1, \ldots ,T $$

(20)

In the MILP model $Fm$/$block$/$C_{max}$/$d_{i}$, it is obvious that both the objective function (10) and the constraint blocks (11–15) and (17–19) consecutively match formulas (1–9) of the MILP model $Fm$/$prmu$/$C_{max}$/$d_{i} .$ The changes that are added by considering possible blocking between machines are:

• $C_{k,t}$ here represents the release time (compared to the time of completion) of the $t$-th job $\pi_{t}$ of the production sequence $\pi \left( T \right)$ in machine $k \in K$.

• Restrictions (16) help limit the minimum release time $C_{k,t}$ through the release time of the previous job $\left( {\pi_{t - 1} } \right)$ in the next machine $\left( {k + 1} \right).$

• For convenience, equalities (20) are the release start times in virtual machine: $k = m + 1.$

4 Illustrative example

An assembly line with 21 workstations produces 9 types of engines (M1–M9) grouped into three families (4 × 4, VAN and Trucks). Figure 1 shows an M1 type engine that belongs to the 4 × 4 family. Table 1 shows the processing times, measured in seconds under normal operation conditions, for each engine type $\left( {i = 1, \ldots ,9} \right)$ in each workstation $\left( {k = 1, \ldots ,21} \right)$; these times are heterogeneous and range between 89 and 185 s (Bautista and Cano 2011). Considering a product-oriented online Flow Shop production environment, the goal is to set production sequences of 9 and 18 total engines, composed of 1 and 2 engines of each type, respectively, with the purpose of measuring the economic impact of the elimination of spaces between consecutive workstations.

Fig. 1

Nissan Pathfinder Engine. Characteristics: (i) 747 parts and 330 references, (ii) 378 elemental assembly tasks grouped in 140 production line tasks

Table 1 Processing time under normal operation $\left( {p_{i,k} } \right)$ in seconds of the 9 types of engines $\left( {i \in I} \right)$ in the 21 workstations $\left( {k \in K} \right)$ of the set of Nissan-9Ing.I instances (Bautista and Cano 2011)

The engine production sequences must meet the minimum Makespan goal, taking into account two online production configurations in a Flow Shop environment:

• Line L1 with unlimited storage space between pairs of consecutive workstations (problem $Fm$/$prmu$/$C_{max}$)

• Line L2 without storage space between pairs of consecutive workstations, with the possibility of blocking between stations (problem $Fm$/$block$/$C_{max}$)

The 4 optimal sequences of this example were obtained with implementations of the MILP-1 and MILP -2 models using IBM ILOG CPLEX code (Optimization Studio v.12.2, win-x86-64)

Table 2 shows the results for this example.

Table 2 Line (L1, L2) according to parameter $\beta$$\left( {prmu,block} \right)$, engine demand plan ($d_{i} = 1,2 \forall i$), optimal production sequence $\pi \left( T \right)$, $C_{max}$ value (sec) and CPU time (sec) for the illustrative example with 9 engine types

Table 2 shows that the elimination of storage space between the 21 workstations (L1 vs. L2) causes slow-downs in production of 10 and 27 s when engines 9 and 18 are produced, respectively.

Considering that the cost of production loss (Bautista et al. 2018) is 137.14 euros per production minute, the elimination of spaces in the assembly line results in an additional cost of 22.86 euros with 9 engines, and 61.71 euros with 18 engines.

The assembly line was designed for a fixed cycle time of 175 s, and consequently, the actual production times available for the manufacture of 9 and 18 engines are 1.42 and 1.85 h, respectively. Note that both times are greater than the corresponding $C_{max}$ values in Table 2.

5 Computational experimentation

The computational experimentation proposed is focused on analyzing the behavior of Mixed Integer Linear Programming (MILP) to solve sequencing problems in Flow Shop production environments with extensive demand. We propose two experiments. In Experiment-1 we used a selection of Taillard’s instances (Taillard 1993). For Experiment-2 we have selected 7 categorical instances of the set of industrial instances Nissan-9Eng.I (Bautista and Cano 2011).

5.1 Experiment-1

For the Experiment-1, we used Set-1 and Set-4 Taillard’s instances (${\rm E}$) from the literature that are related to the sequencing problems studied. We also adapted those instances to industrial cases with general demand for types of jobs or products (${\rm E}^{\prime}$).

In brief, the data included in this experiment are:

• Set-1 (Taillard 1993): instances $\varepsilon = 1,.,10$ ($\varepsilon \in {\rm E}$), number of job types $\left| I \right| \equiv n = 20$, number of machines $\left| K \right| \equiv m = 5$, and total demand of jobs $T \equiv D = 20$.

• Set-4 (Taillard 1993): instances $\varepsilon = 31,.,40$ ($\varepsilon \in {\rm E}$), number of job types $\left| I \right| \equiv n = 50$, number of machines $\left| K \right| \equiv m = 5$, and total demand of jobs $T \equiv D = 50$.

• Set-1d (Set-1 adapted to problem $Fm$/$\beta$/$\gamma$/$d_{i}$): instances $\varepsilon = 1,.,10$ ($\varepsilon \in {\rm E}^{\prime}$), number of job types $\left| I \right| \equiv n = 20$, number of machines $\left| K \right| \equiv m = 5$, Demand plan of job types $d_{i} = 5$$\left( {\forall i = 1,..,20} \right)$, and total demand of jobs $T \equiv D = 100$, with identical processing times $p_{i,k } \left( {\forall i \in I,\forall k \in K} \right)$, instance by instance, to those of Set-1.

• Set-4d (Set-4 adapted to problem $Fm$/$\beta$/$\gamma$/$d_{i}$): instances $\varepsilon = 31,.,40$ ($\varepsilon \in {\rm E}^{\prime}$), number of job types $\left| I \right| \equiv n = 50$, number of machines $\left| K \right| \equiv m = 5$, Demand plan of job types $d_{i} = 5$$\left( {\forall i = 1,.,20} \right)$, and total demand of jobs $T \equiv D = 250$, with identical processing times $p_{i,k } \left( {\forall i \in I,\forall k \in K} \right)$, instance by instance, to Set-4.

The compiled codes for the procedures involved were executed on a DELL Inspiron-13 (Intel(R) Core(TM) i7-7500U @ 2.70 GHz CPU 2.90 GHz, 16 GB of RAM, x64 Windows 10 Pro). The characteristics of the 2 procedures are:

• MILP-1: Model $Fm$/$prmu$/$C_{max}$/$d_{i}$: (i) Objective function for minimizing the $C_{max}$ value of the production sequence; (ii) implementation for IBM ILOG CPLEX solver (Optimization Studio v.12.2, win-x86-64); (iii) maximum CPU time of 7200 s. (40 instances) allowed for solving each instance.

• MILP-2: Model $Fm$/$block$/$C_{max}$/$d_{i}$: (i) Objective function for minimizing the $C_{max}$ value of the production sequence; (ii) implementation for IBM ILOG CPLEX solver (Optimization Studio v.12.2, win-x86-64); (iii) maximum CPU time of 7200 s. (40 instances) allowed for solving each instance.

Tables 3, 4, 5 and 6 show the results of the experiment obtained by CPLEX for the two models implemented ($Fm$/$prmu$/$C_{max}$/$d_{i}$, $Fm$/$block$/$C_{max}$/$d_{i}$). Table 3 corresponds to the instances of Set-1 (20 jobs), Table 4 corresponds to those of Set-4 (50 jobs), and Tables 5 and 6 correspond to those of Set-1d (100 jobs) and of Set-4d (250 jobs), respectively.

Table 3 Results for Set-1 instances using procedures MILP-1 and MILP-2

Table 4 Results for Set-4 instances using procedures MILP-1 and MILP-2

Table 5 Results for Set-1d instances using procedures MILP-1 and MILP-2

Table 6 Results for Set-4d instances using procedures MILP-1 and MILP-2

In the tables, the column headers represent the following characteristics:

$\varepsilon \in {\rm E}$:

Identification number of the instances for Set-1 and Set-4

$\varepsilon \in {\text{E}}^{{\prime }}$:

Identification number of the instances for Set-1d and Set-4d

$C_{max}$:

Best makespan value obtained for procedure MILP-1 or MILP-2

$C_{max}^{*}$:

Optimal value of makespan

$C_{max}^{0}$:

Best known value of makespan

$LB\_p$:

$C_{max}$ lower limit for problem $Fm$/$prmu$/$C_{max}$/$d_{i}$ obtained for MILP-1

$LB\_b$:

$C_{max}$ lower limit for problem $Fm$/$block$/$C_{max}$/$d_{i}$ obtained for MILP-1/2

$Gap_{{C^{*} }}$:

Relative gap between $C_{max}$ and $C_{max}^{*}$

$Gap_{{C^{0} }}$:

Relative gap between $C_{max}$ and $C_{max}^{0}$

$Gap_{LB\_p}$:

Relative gap between $C_{max}$ and $LB\_p$

$Gap_{LB\_b}$:

Relative gap between $C_{max}$ and $LB\_b$

The relative gap values between $C_{max}$ and the other characteristics related to makespan ($C_{max}^{*} ,C_{max}^{0} ,LB\_p,LB\_b$) are calculated using (21).

$$ Gap_{X} \left( \varepsilon \right) = \frac{{C_{max} \left( \varepsilon \right) - X\left( \varepsilon \right)}}{{C_{max} \left( \varepsilon \right)}}\quad X \in \left\{ {LB_{p} ,LB_{b} ,C_{max}^{*} ,C_{max}^{0} } \right\},\quad \forall \varepsilon \in {\rm E},\,\forall \varepsilon \in {\rm E}^{\prime } $$

(21)

where the $LB\_p$ values for the problem $Fm$/$prmu$/$C_{max}$/$d_{i}$ are obtained directly with procedure MILP-1, the $LB\_b$ values correspond to the maximum value between $LB\_p$ and the lower limit from procedure MILP-2 for problem $Fm$/$block$/$C_{max}$/$d_{i}$. Meanwhile, the values of $C_{max}^{*}$ are confirmed as optimal through procedure MILP-1, and the $C_{max}^{0}$ value originates from the literature for problem $Fm$/$block$/$C_{max}$ (Bautista et al. 2012).

An analysis of Tables 3, 4, 5 and 6 reveals the following:

• Procedure MILP-1 obtains and ensures optimal solutions in all instances with 20 jobs (Set-1), 50 jobs (Set-4) and 100 jobs (Set-1d).

• Procedure MILP-1 obtains and ensures optimal solutions in 8 of the 10 instances with 250 jobs (Set-4d). The solutions obtained with MILP-1 for instances #32 and #39 of Set-4d have $Gap_{LB\_p}$ values equal to 0.12% and 0.14%, respectively. The average $Gap_{LB\_p}$ value for Set-4d is approximately 0.03%.

• Procedure MILP-2 does not ensure optimal solutions in any of the four Sets (1, 4, 1d and 4d).

• In Set-1 (20 jobs), MILP-2 obtains 3 better solutions for 10 instances (instances #4, #8 and #10) and offers a $Gap_{{C^{0} }}$ average value of 0.5%. Meanwhile, in the instances with 50 jobs (Set-4), MILP-2 obtains a $Gap_{{C^{0} }}$ average value of approximately 3.5% and is not able to match any better known value ($C_{max}^{0}$).

• For instances with 100 and 250 jobs (Set-1d and Set-4d) and with blocking between machines, there is no information on the best known makespan value; therefore, to measure the quality of the solutions provided by MILP-2, we used the makespan lower limits offered by the procedure. Under such conditions, the average values of $Gap_{LB\_b}$ are equal to 0.146 for Set-1d and to 0.202 for Set-4d.

• The average CPU times used by MILP-1 are approximately 29, 587, 37 and 1643 s for each instance of 20, 50, 100 and 250 jobs, respectively. Note that these times do not increase progressively with the number of jobs to be sequenced ($T \equiv D$), but these times do appear to depend on the number of job types ($\left| I \right| \equiv n$) that correspond to each instance.

• The average CPU times used by MILP-2 are approximately 7093, 6699, 7099 and 4444 s for each instance of 20, 50, 100 and 250 jobs, respectively. These times are not related to the number of jobs to be sequenced ($T \equiv D$) or to the number of job types ($\left| I \right| \equiv n$).

• In summary, considering the CPU time limitation of 7200 s for each instance, the MILP-1 procedure oriented toward problem $Fm$/$prmu$/$C_{max}$/$d_{i}$ obtains and ensures 38 optimal solutions for the 40 instances studied, while procedure MILP-2, oriented toward problem $Fm/block/C_{max} /d_{i}$, obtains 3 better solutions for a total of 20 instances (Set-1 and Set-4).

5.2 Experiment-2

There are currently 23 production plans for the nine engines and one working day at the Nissan Spanish Industrial Operations (Bautista and Cano 2011). Each program corresponds to a set of operation times biased by the demand of each of the nine products. We summarize here the characteristics of each of the 23 production plans. We have grouped them into seven categories according to the type of engine demand. One representative production plan is selected for each category to be used in the computational experimentation developed in this subsection. As said, the total number of engines assembled in a working day is 270 in two shifts:

• Category-1 (plan #1): identical demand for each of the nine products (balanced demand) (30 engines per product type).

• Category-2 (plan #2): identical demand for each of the three engine families: 4x4, VAN, and trucks (90 per product family).

• Category-3 (plan #3): one of the engine families has low demand while the demand of the other two families is high and identical.

• Category-4 (plan #6): one of the engine families has high demand while the demand of the other two families is medium and identical.

• Category-5 (plan #9): one of the engine families has high demand while the demand of the other two families is low and identical.

• Category-6 (plan #12): the demand of the engine families follows an arithmetic progression.

• Category-7 (plan #18): the demand of the engine families follows a geometric progression.

Table 1 shows the processing times, measured in seconds under normal operation conditions, for each engine type $\left( {i = 1, \ldots ,9} \right)$ in each workstation $\left( {k = 1, \ldots ,21} \right)$. On the other hand, Table 7 shows daily demands by engine type and plan for the 7 instances categorical Nissan-9Eng.I.

Table 7 Daily demands by product type and plan $\left( {d_{i,\varepsilon } } \right)$ for the 7 instances categorical Nissan-9Eng.I $\left( {\varepsilon \in {\rm E}} \right)$

The compiled codes for the procedures involved were executed on a DELL Inspiron-13 (Intel(R) Core(TM) i7-7500U @ 2.70 GHz CPU 2.90 GHz, 16 GB of RAM, x64 Windows 10 Pro). The characteristics of procedures are:

• MILP-1: Model $Fm$/$prmu$/$C_{max}$/$d_{i}$: (i) Objective function for minimizing the ${\text{C}}_{ \hbox{max} }$ value of the production sequence; (ii) implementation for IBM ILOG CPLEX solver (Optimization Studio v.12.2, win-x86-64); (iii) maximum CPU time of 180 s allowed for solving each instance (7 instances).

• MILP-2: Model $Fm/block/C_{max} /d_{i}$: (i) Objective function for minimizing the ${\text{C}}_{ \hbox{max} }$ value of the production sequence; (ii) implementation for IBM ILOG CPLEX solver (Optimization Studio v.12.2, win-x86-64); (iii) maximum CPU time of 180 s allowed for solving each instance (7 instances).

Table 8 shows the results of the experiment obtained by CPLEX for the two models implemented (MILP-1 $Fm$/$prmu$/$C_{max}$/$d_{i}$, and MILP-2: $Fm/block/C_{max} /d_{i}$).

Table 8 Results for 7 Nissan-9Eng.I instances categorical using procedures MILP-1 and MILP-2 (180 s. CPU)

The analysis of Table 8 reveals the following:

• Procedure MILP-1 obtains and ensures optimal solutions in all instances with 270 jobs (7 instances categorical Nissan-9Eng.I) when we resolve the $Fm$/$prmu$/$C_{max}$/$d_{i}$ problem.

• Procedure MILP-2 does not ensure optimal solutions in any of the instances with 270 job (7 instances categorical Nissan-9Eng.I) in the $Fm/block/C_{max} /d_{i}$ problem.

• The average values of $Gap_{LB\_b}$ are equal to 1.69% for Set categorical Nissan-9Eng.I.

• The average CPU times used by MILP-1 are approximately 18.24 s for each instance of 270 jobs (7 instances categorical Nissan-9Eng.I).

• The average CPU times used by MILP-2 are approximately 180.19 s for each instance of 270 jobs (7 instances categorical Nissan-9Eng.I) when we impose a maximum CPU time of 180 s allowed for solving each instance.

• Considering that the cost of production loss (Bautista et al. 2018; Bautista-Valhondo and Alfaro-Pozo 2018) is 137.14 euros per production minute, the elimination of spaces in the assembly line (prmu vs. block) results in an additional cost average of 1972.57 euros/day with 270 engines. However, the original assembly line was designed for a fixed cycle time of 175 s, and consequently, the actual production times available for the manufacture of 270 engines is 50,770 s.

6 Conclusions

In this study, we presented and justified a natural extension of two classic sequencing problems: $Fm$/$prmu$/$C_{max}$ and $Fm$/$block$/$C_{max}$. This extension is motivated by our concern over adapting academic problems closer to reality in industrial environments related to the automotive sector.

Our extension takes into account the type of jobs or products in such problems, based on the fact that, in many highly standardized industrial sectors such as the automotive sector, it is unlikely to find productive processes where all jobs or all products (chassis, car bodies, engines, seats, etc.) are completely different. For this reason, we incorporated the concept of a demand plan of job types ($d_{i} \forall i \in I$) into the original problems, which resulted in the problems $Fm$/$prmu$/$C_{max}$/$d_{i}$ and $Fm$/$block$/$C_{max}$/$d_{i}$. The concept of a demand plan of job (product) types can be extrapolated to other variants of Flow Shop and Job Shop problems, if the circumstances are appropriate.

We formulated Mixed Integer Linear Programming models, implemented in CPLEX, for the two new problems and analyzed the quality of the procedures through a computational experiment with instances collected and adapted from the literature.

Our computational experience is composed of two experiments. In Experiment-1 we have used a selection of 20 instances (from the classic instances of Taillard), whose dimensions we have adapted to the automotive industry. In Experiment-2 we have selected 7 categorical instances (from the set of Nissan-9Eng.I instances) corresponding to 7 engine production plans in the Nissan factory in Barcelona, and whose dimensions are: 270 products, 9 types of engines and 21 work stations.

Taking into account the results of the first experiment, we conclude that it is not prudent to discard Mixed Integer Linear Programming for solving sequencing problems in Flow Shop production environments, as MILP is a competitive technique with which to solve problem $Fm$/$prmu$/$C_{max}$/$d_{i}$ for industrial instances of 250 jobs and obtains and confirms the optimal solutions in most instances with an average CPU time of less than 28 min. MILP is less effective with problem $Fm$/$block$/$C_{max}$/$d_{i}$ with industrial instances, although its results are acceptable when compared to the best solutions in the literature for problem $Fm$/$block$/$C_{max}$.

Looking at the results of Experiment-2, that are more realistic for the automotive industry, we conclude that MILP has offered very satisfactory solutions for the two new problems proposed; in effect: (i) MILP gets the 7 optimal solutions for the problem $Fm$/$prmu$/$C_{max}$/$d_{i}$ in an average CPU time of 18.24 s, and (ii) MILP gets solutions, for the problem $Fm$/$block$/$C_{max}$/$d_{i}$, with an average value that are 0.17% of the average value of the optimal solutions, when we set a maximum CPU time of 3 min.

Therefore, we conclude that MILP should be incorporated into the set of tools dedicated to solving sequencing problems in realistic production environments. The role of MILP within the set of techniques for solving such problems can be a leading role or as part of the metaheuristic procedures that combine a construction phase of one or more initial solutions, with one or several phases of local improvement of such solutions.

In future work, we intend to apply the knowledge acquired in this experimental study to various case studies related to sequencing problems of mixed models in product-oriented production systems (assembly lines and workshops with regular flow). We also intend to analyze the economic impact of the alternative of using a fixed production cycle time for all machines (processors, workstations) or allowing processors to have cycle times that depend on both products and machines.