New formulation for scheduling flexible flow shop problems

Abstract

This research extends the constrained vehicle routing problem concept to solve flexible flow shop scheduling problems. Mixed-integer linear programming and constraint programming formulations are developed for a flow shop problem with no-wait, time lags and release time restrictions to minimize the makespan in both permutation and non-permutation schedules. The comparative analysis of various models reveals that constraint programming models have superior computational performance than mixed-integer linear programming models. However, the mixed-integer linear programming models are also timely-efficient. Moreover, the efficiency of developed models is also represented in comparison with several benchmark datasets. Based on the findings, while the objective function values of the mixed-integer linear programming and constraint programming models in non-permutation schedules exhibit lower values than their respective equivalents in permutation schedules, both models demonstrate longer runtime in non-permutation schedules. Results represent that the proposed constraint programming and mixed-integer linear programming models are among the top three models of the benchmark datasets in terms of the number of decision variables and computational performance. One of the limitations of the research is that there is no comprehensive dataset in the literature considering all the restrictions in permutation and non-permutation schedules.

1 Introduction

Production and operations scheduling is one of the most significant factors that may lead to the failure or success of a manufacturing company [1, 2]. The job scheduling problem is regarded as arranging operation tasks (jobs) in a production system and focuses on specifying the orders of jobs on a pre-defined set of machines. These job orders are usually determined so that the operational or financial performance of the given production system is optimized. The job scheduling problem is known as the flow shop problem when all jobs have the same sequence on machines, and each job requires only one operation on each machine [3]. The flexible flow shop (FFS) problem is a generalization of the flow shop where every job can be processed by one of the machines in each station [4]. In the FFS problem, the production system has a fixed sequence of stations, and each station includes a set of machines. So far, FFS problems are widely applied in different industries such as chemical, logistics and semiconductors. [5].

In the related literature, flow shop problems are usually categorized into two main groups: Cyclic and Non-cyclic [3, 6, 7]. Each category considers different production settings (assumptions) such as no-wait [8], time lags [9], blocking [10, 11], and limited or unlimited intermediate storage levels [12]. In no-wait flow shop problems, each job must be processed without interruption between machines [13, 14]. In the flow shop problems with time lags, practitioners consider the minimum and maximum wait time between every two consecutive operations which are required for completing a job on machines [15,16,17]. Both cyclic and non-cycle flow shop problems can be formulated to provide permutation and non-permutation schedules for jobs. In permutation flow shop scheduling, the sequence of jobs must be the same on all machines [18, 19]. However, this sequence can be different when the flow shop problem considers non-permutation orders for jobs. [20, 21].

From the computational point of view, flow shop problems are usually NP-hard combinatorial optimization problems resulting in high dimension solution regions with many locally optimal solutions [22]. Therefore, scholars employ different heuristics and non-heuristics modeling methods to estimate the optimal or near-optimal schedules for the production [23]. Mixed Integer Programming (MILP) and Constraint Programming (CP) are recognized as mature optimization techniques to solve both NP-hard and non-NP-hard problems. Both techniques may enable users to model scheduling problems and reach specific values for their decision variables, known as "exact" optimal solutions [24,25,26]. CP is a programming paradigm that models the relation between decision variables in the form of constraints [26]. This technique, originated from artificial intelligence, aims to efficiently estimate optimal solutions using constraints in an optimization problem [27]. In general, CP models have several advantages in solving optimization problems: 1) CP models can find infeasibilities immediately, 2) CP models can obtain the initial feasible solutions quickly, 3) CP models can obtain the optimal solution in low computational times, and 4) CP languages assist in the model development because they are declarative [28]. Due to these advantages, a remarkable trend of attention has been attracted to the CP models, particularly for scheduling problems.

FFS problems have received increasing research attempts during the last decade due to their real-world application in manufacturing industries. However, some notable aspects of the FFS problem have received less attention. Some of the most related studies in this area are reviewed in the following. Mucha and Sviridenko [8] worked on the classical problem of no-wait flow shop scheduling with makespan objective and considered this problem as a particular case of the asymmetric traveling salesman problem. Dorfeshan et al. [9] considered transportation lags and a weighted distance-based approximation method to arrange jobs in flow shop scheduling problems. Rossit et al. [29] presented a combinatorial analysis of the permutation and non-permutation flow shop scheduling problems with unknown processing times. A systematic literature review on permutation and non-permutation flow shop problems is provided by Singh et al. [30]. They worked on the multi-objective flexible flow shop scheduling with no-wait constraints. Samarghandi [31] developed constraint programming and MILP models for a flow shop environment under minimum and maximum time-lag constraints in which the makespan is minimized. Furthermore, Qin et al. [32] studied the integrated CP and mixed-integer programming to solve the hybrid flow shop scheduling problem. Xiao et al. [33] formulated the non-permutation flow shop scheduling problem with order acceptance as a MILP model. Moreover, Xin et al. [34] proposed a MILP model for the flow shop scheduling problem with sequence-dependent setup time to minimize the makespan and total energy consumption. Table 1 demonstrates methods, objective functions, and features of flow shop problems considered in the literature to schedule jobs.

Table 1 Common features of articles in flow shop problems

The main contribution of the present study is to extend the CVRP formulations for FFS with no-wait, time lags, and release time restrictions and the makespan ($C_{\max }$) function in both permutation and non-permutation schedules. In addition to presenting MILP models for different FFS problems, the constraint programming (CP) models corresponding to the underlying FFS problems are also proposed, and the results of developed models are compared. However, the literature review reveals that scholars usually apply MILP methods for specific flow shop scheduling problems. Their MILP formulations were developed to consider only permutation or non-permutation schedules for given flow shop problems. In other words, their MILP methods cannot be applied to solve both permutation and non-permutation scheduling problems. Developing MILP formulation according to Capacitated Vehicle Routing Problem (CVRP) concept would be one of the modeling approaches to remove the above limitations in creating a generalized method to solve flow shop job scheduling problems. To the best knowledge of the authors, there is no such modeling approach for flexible flow shop problems.

2 Proposed mixed-integer linear programming model

The FFS problem considered in this study is described as a set of n jobs (tasks) that should be processed on a set of stations $\left( {l = 1,...,c} \right)$ containing $M_{l} \ge 1$ identical parallel machines. A function $\pi_{i} = \left[ {p_{i}^{1} , \, p_{i}^{2} , \, . \, . \, ., \, p_{i}^{c} } \right]$ demonstrates the required processing times of the $i^{th}$ job in different stations. Each job can be processed by any of the $M_{l}$ parallel machines in $l^{th}$ station (Fig. 1). The FFS problem is solved to find a sequence of n jobs that should be processed so that some objectives such as the total required time for completing all jobs, the maximum lateness, or the tardy job count are optimized. The MILP models of the present study are generalized based on the CVRP formulation for the FFS problem with no-wait, time lags, and release time restrictions on time-capacitated machines with permutation and non-permutation schedules.

Fig. 1

A flexible flow shop layout

CVRP is defined on a graph $G = \left( {N,D} \right)$ where $N = \{ 0,1,2,...,n\}$ is the vertex (node) set and D is the edge (arc) set where $D = \{ \left( {i,j} \right):i,j \in N,i \ne j\}$. Vertex $i\,\,(i = 1,...,n)$ represents customers, while vertex 0 is defined as the depot (dummy) node. This node is considered as the depot of $m$ identical vehicles with a specific capacity level. Each customer $i\,\,(i = 1,...,n)$ is associated with a positive integer demand, and each set of $\left( {i,j} \right)$ edge is associated with a travel cost or travel time. The CVRP aims to determine a set of (at most) $m$ vehicle routes such that: a) each route must start and end at the depot vertex (node 0), b) each customer (vertex) must belong to exactly one route, c) the total load on each route does not exceed the capacity level of the vehicle, and, finally, d) the total cost (or time) of all $m$ routes is minimized. FFS problem with $n$ jobs, c stations, and $M_{l}$ machines in $l^{th}$ station is equivalent to c successive CVRP models with $n$ customers and $M_{l}$ time-capacitated machines in $l^{th}$ station. Figure 2 shows a simple adoption of non-permutation FFS with two successive CVRPs, scheduling eight jobs processed on two stations with two and three identical parallel machines, respectively.

Fig. 2

A simple correspondence of FFS with CVRP

The following assumptions are considered in formulating the FFS problem: a) All machines in each station are parallel and identical with the same capabilities in job processing; b) If a job is assigned to a machine, the entire job is completely accomplished on this machine. There exist no possibility of breaking a job and accomplishing a part of it in another time on the same machine. c) Each machine is capable of completing the processing of a job in a given time; d) Each job can be processed after completing the other job, with no precedence constraints, e) All machines are available through the scheduling process and can continuously perform operations at time zero, and f) The processing time of each job on each station is pre-determined.

To specify scheduling problems economically and precisely, Graham et al. [51] introduced a shorthand notation. The classification system comprises three fields separated by bars: $\alpha |\beta |\gamma$. In the field $\alpha$, the type and size of the shop are entered. For example, $FF_{c}$ denotes the flexible flow shop with c stages (or stations). In the field $\beta$, the special features of the shop are listed. For example, $prmu$ represents permutation schedules (where the sequence of job processing on all stages is the same), $r$ represents the release time restriction (the earliest time that a job is available to be processed), $l$ represents the lag time restriction (the possibility that an additional time delay should elapse between completing a job at one station and starting it at the next), $nwt$ represents the no-wait restriction (where a job, once started, must flow through every station to completion without any delay). In the field $\gamma$, the objective function or criterion that should be maximized or minimized is entered. For example, $C_{\max }$ denotes the maximal or latest completion time of any job (this criterion commonly is called the makespan) [52].

In this study, the CVRP formulations for FFS with no-wait ($FF_{c} \left| {nwt} \right|C_{max}$, $FF_{c} \left| {nwt,prmu} \right|C_{max}$), time lags ($FF_{c} \left| {\,l\left| {C_{\max } } \right.} \right.$, $FF_{c} \left| {\,l,prmu\left| {C_{\max } } \right.} \right.$) and release time restrictions ($FF_{c} \left| {\,r\left| {C_{\max } } \right.} \right.$, $FF_{c} \left| {\,r,prmu\left| {C_{\max } } \right.} \right.$) and $C_{\max }$ function in both permutation and non-permutation schedules are extended. Minimizing the makespan ($C_{\max }$) is the objective function of the developed optimization models. The constraint programming (CP) models corresponding to the underlying FFS problems are also proposed.

2.1 Parameter

$n$: Number of jobs $\left( {i = 1,...,n} \right)$$c$: Number of stations $\left( {l = 1,...,c} \right)$$p_{i}^{l}$: Processing time of $i^{th}$ job in $l^{th}$ station

$M_{l}$: The number of machines in $l^{th}$ station .

$R_{i}$: Release time of $i^{th}$ job.

$H$: A large constant value ($H \to \infty$).

In the CVRP model, a dummy job ($i = 0$) with zero processing time is added to the list of jobs, which determines the beginning and the end of the turn in the CVRP problem.

(expressed as $i = 0,1,...,n$).

2.2 Variables

$x_{{_{ij} }}^{l}$: If the $j^{th}$ job is performing immediately after the $i^{th}$ job in $l^{th}$ station (1), otherwise (0).

$v_{{_{i} }}^{l}$: Cumulative time of the jobs processed on each machine until completion of the processing of the $i^{th}$ job in the $l^{th}$ station. Variable $v_{{_{i} }}^{l}$ is defined to eliminate sub-tours in each station.

$u_{{_{i} }}^{l}$: Cumulative time of the jobs processed on each machine until completion of the $i^{th}$ job from first to the $l^{th}$ station. The completion time of the $i^{th}$ job in the $l^{th}$ station is determined by $u_{{_{i} }}^{l}$. For the last station, $u_{{_{i} }}^{c}$ is equivalent to the flow time completion of $i^{th}$ job. Therefore, the makespan or maximum flow time of jobs in the last station is calculated as $C_{\max } = \mathop {\mathop {Max}\limits^{n} }\limits_{i = 1} (u_{i}^{c} )$.

$s_{i}^{{}}$: Start time of jobs' processing in the first station. In the presented model, it is unnecessary to start processing jobs on the first station at time zero. The variable $s_{i}$ is defined for all jobs at the first station, and if $i^{th}$ job is the first job on any of the machines, then the start time of processing of this job $\left( {u_{{_{i} }}^{l} - p_{i}^{l} } \right)$ is calculated from time $s_{{_{i} }}^{{}}$ as $u_{{_{i} }}^{l} - p_{i}^{l} = s_{i}$.

Some pre-defined time lags exist between the same jobs in successive stations in the flow shop problem with time lag restriction. Processing of $i^{th}$ job is completed at $u_{i}^{1}$ in station one, and it should be resumed at $\left( {u_{i}^{2} - p_{i}^{2} } \right)$ in station two after elapsing time lag $\left( {lag_{i}^{1} = u_{i}^{2} - p_{i}^{2} - u_{i}^{1} } \right)$.

2.3 MILP model

The MILP model for $FF_{c} \left| {\,\left| {C_{\max } } \right.} \right.$(FFS non-permutation model) is formulated as follows:

2.3.1 Non-Permutation MILP model (MILP-NP)

$$Minimize\,\,\,C_{\max }$$

(1)

$$\sum_{i = 1}^{n} {x_{0i}^{l} } = \sum_{i = 1}^{n} {x_{i0}^{l} = M_{l} ;\,\,\,\,\,\,l = 1,...,c}$$

(2)

$$\sum_{\begin{subarray}{l} j = 0 \\ i \ne j \end{subarray} }^{n} {x_{{_{ij} }}^{l} } = \sum_{\begin{subarray}{l} j = 0 \\ i \ne j \end{subarray} }^{n} {x_{{_{ji} }}^{l} = 1;\,\,\,\,\,\,l = 1,...,c} ;\,\,\,\,\,i = 1,...,n$$

(3)

$$v_{i}^{l} - v_{j}^{l} + Hx_{{_{ij} }}^{l} + (H - \,p_{{_{i} }}^{l} - \,p_{{_{j} }}^{l} )\,x_{{_{ji} }}^{l} \le H - p_{{_{j} }}^{l} ;\,\,\,\,\,\,l = 1,...,c\,;\,\,\,\,1 \le i \ne j \le n$$

(4)

$$v_{i}^{l} \ge p_{i}^{l} ;\,\,\,\,\,\,l = 1,...,c;\,\,\,\,\,\,\,i = 1,...,n$$

(5)

$$v_{{_{i} }}^{l} + (H - \,p_{{_{i} }}^{l} )x_{0i}^{l} \le H;\,\,\,\,\,\,\,\,i = 1,...,n;\,\,\,\,\,l = 1,...,c$$

(6)

$$u_{i}^{l} - p_{i}^{l} \ge u_{i}^{l - 1} ;\,\,\,\,\,\,\,l = 2,...,c;\,\,\,\,\,\,i = 1,...,n$$

(7)

$$u_{{_{i} }}^{1} + (H - \,p_{{_{i} }}^{1} )x_{0i}^{1} \le H;\,\,\,\,\,\,\,\,i = 1,...,n$$

(8)

$$u_{i}^{1} \ge p_{i}^{1} \,;\,\,\,\,\,\,\,\,\,i = 1,...,n$$

(9)

$$u_{j}^{l} - p_{j}^{l} \ge u_{i}^{l} - H(1 - x_{ij}^{l} {)};\,\,\,\,\,\,\,\,\,\,l = 1,...,c;\,\,\,\,\,\,1 \le i \ne j \le n$$

(10)

$$\,C_{\max } \ge u_{i}^{c} \,;\,\,\,\,\,\,\,i = 1,...,n$$

(11)

$$u_{i}^{l} ,v_{i}^{l} \ge 0; \, i = 1,...,n\,;\,\,\,\,\,\,\,l = 1,...,c$$

(12)

$$x_{ij}^{l} \in \left\{ {0,1} \right\}{;}\,\,\,\,\,\,\,\,\,\,\,\,\,{0} \le i \ne j \le n;\,\,\,\,\,\,\,l = 1,...,c$$

(13)

Equation (1) is the objective function that minimizes the makespan. Equation (2) assures that each turn (machine) in the first station starts and ends with the dummy node 0. Equation (3) is the usual balancing constraint for CVRP. Equation (4) assures the sub-tour elimination for each machine in each station. This inequality for all jobs $1 \le i \ne j \le n$ ensures that $v_{i}^{l} = v_{j}^{l} + p_{j}^{l}$ only if $x_{ij}^{l} = 1$ and $v_{j}^{l} = v_{i}^{l} + p_{i}^{l}$ only if $x_{ji}^{l} = 1$. In the original CVRP model, the variable $v_{j}^{l}$ is computed cumulatively and continuously; in other words, if the $j^{th}$ job is processed immediately after the $i^{th}$ job, then $v_{j}^{l} = p_{j}^{l} + v_{i}^{l}$. This computation is not valid for the cumulative time because in the optimal scheduling solution, for two successive jobs, the start time of the following job is not immediately after the finish time of the before job, and it is possible to have idle time between two jobs. The variable $v_{j}^{l}$ does not have this condition, while by defining the variable $u_{i}^{l}$ and adding Eq. (5)-(10), the start and finish time of successive jobs on a machine is computed correctly. Equation (11) ensures that the makespan must be greater than (or equal to) the cumulative time of the jobs processed on the last station. Equation (12) and Eq. (13) assure the positive and binary conditions of variables, respectively.

By converting Eq. (7) into $u_{i}^{l} - p_{i}^{l} = u_{i}^{l - 1}$, the MILP model for $FF_{c} \left| {nwt} \right|C_{max}$ (no-wait FFS model) is formed. The FFS will be formed with minimum time lags by adding the parameter $Lag_{i}^{l}$ to Eq. (7) as $u_{i}^{l} - p_{i}^{l} \ge u_{i}^{l - 1} + Lag_{i}^{l}$. By converting this inequality to $u_{i}^{l} - p_{i}^{l} = u_{i}^{l - 1} + Lag_{i}^{l}$, the model for FFS with time lags restriction and by adding $u_{i}^{l} - p_{i}^{l} \le u_{i}^{l - 1} + Lag_{i}^{l}$ to the model, the FFS with maximum time lags is formulated.

Through changing Eq. (8) and Eq. (9) to $u_{{_{i} }}^{1} + (H - \,p_{{_{i} }}^{1} )x_{0i}^{1} - s_{i}^{{}} \le H$ and $u_{i}^{1} \ge p_{i}^{1} + s_{i}^{{}}$, and adding Eq. (14), Eq. (15) and Eq. (16), the MILP model for FFS with the release time restriction ($FF_{c} \left| {\,r\left| {C_{\max } } \right.} \right.$) is formed.

$$s_{i}^{{}} \le Hx_{0i}^{1} ;\,\,\,\,\,\,\,i = 1,...,n$$

(14)

$$u_{i}^{1} - p_{i}^{1} \ge R_{i} ;\,\,\,\,\,\,\,i = 1,...,n$$

(15)

$$s_{i}^{{}} \ge 0; \, \,\,i = 1,...,n\,$$

(16)

The MILP model can be extended for $FF_{c} \left| {prmu\left| {C_{\max } } \right.} \right.$(FFS with permutation). In the permutation schedule, the job permutation in all stations is the same. Therefore, the variable $x_{{_{ij} }}^{{}}$ is defined as if the $j^{th}$ job performs immediately after $i^{th}$ job (1), otherwise (0).

In the permutation schedule, sub-tours elimination is only needed in the first station. Therefore, variable $v_{{_{i} }}^{{}}$ is defined as a cumulative time of the jobs processed on each machine until completion of the processing of the $i^{th}$ job in the first station. In the permutation schedule, the number of machines in all stations is equal. The MILP model for $FF_{c} \left| {prmu\left| {C_{\max } } \right.} \right.$ is formulated as follows:

2.3.2 Permutation MILP model (MILP-P)

$$Minimize\,\,\,C_{\max }$$

(17)

$$\sum_{i = 1}^{n} {x_{0i}^{{}} } = \sum_{i = 1}^{n} {x_{i0}^{{}} = M}$$

(18)

$$\sum_{\begin{subarray}{l} j = 0 \\ i \ne j \end{subarray} }^{n} {x_{{_{ij} }}^{{}} } = \sum_{\begin{subarray}{l} j = 0 \\ i \ne j \end{subarray} }^{n} {x_{{_{ji} }}^{{}} = 1\,;\,\,\,} \,\,\,\,i = 1,...,n$$

(19)

$$v_{i}^{{}} - v_{j}^{{}} + Hx_{{_{ij} }}^{{}} + (H - \,p_{{_{i} }}^{1} - \,p_{{_{j} }}^{1} )\,x_{{_{ji} }}^{{}} \le H - p_{{_{j} }}^{1} ;\,\,\,\,\,\,\,\,\,\,1 \le i \ne j \le n$$

(20)

$$v_{i}^{{}} \ge p_{i}^{1} ;\,\,\,\,\,\,\,i = 1,...,n$$

(21)

$$v_{i}^{{}} + (H - \,p_{{_{i} }}^{1} )x_{0i}^{{}} \le H;\,\,\,\,\,\,\,i = 1,...,n$$

(22)

$$u_{i}^{l} - p_{i}^{l} \ge u_{i}^{l - 1} ;\,\,\,\,\,\,\,l = 2,...,c;\,\,\,\,\,i = 1,...,n$$

(23)

$$u_{{_{i} }}^{1} + (H - \,p_{{_{i} }}^{1} )x_{0i}^{{}} \le H;\,\,\,\,\,\,\,i = 1,...,n$$

(24)

$$u_{i}^{1} \ge p_{i}^{1} ;\,\,\,\,\,\,\,\,i = 1,...,n$$

(25)

$$u_{j}^{l} - p_{j}^{l} \ge u_{i}^{l} - H(1 - x_{ij}^{{}} {);}\,\,\,\,\,\,\,\,\,\,l = 1,...,c;\,\,\,\,\,1 \le i \ne j \le n$$

(26)

$$\,C_{\max } \ge u_{i}^{c} ;\,\,\,\,\,\,\,\,i = 1,...,n$$

(27)

$$u_{i}^{l} ,v_{i}^{{}} \ge 0; \, i = 1,...,n;\,\,\,\,\,\,\,l = 1,...,c$$

(28)

$$x_{ij}^{{}} \in \left\{ {0,1} \right\}{; }\,\,\,{ 0} \le i \ne j \le n$$

(29)

The description of Eq. (17)-(29) is the same as Eq. (1)-(13), respectively. The only difference between permutation and non-permutation models is the definition of $x_{{_{ij} }}^{{}}$ and $v_{{_{i} }}^{{}}$ variables (explained at the end of Sect. 2.3.1). No-wait, time lags, and release time restrictions can be considered in the model for $FF_{c} \left| {prmu\left| {C_{\max } } \right.} \right.$ as described for the model $FF_{c} \left| {\,\left| {C_{\max } } \right.} \right.$.

The proposed FFS with different restrictions can be modeled through CP properties. The CP models differ from the corresponding MILP representation and are described in Sect. 3.

3 Constraint programming models

Constraint programming is a tool for solving combinatorial search problems and has been addressed in various techniques such as artificial intelligence, computer science, and operations research. Earlier, CP models were used to assign values from the variables' domain which satisfies all the constraints of a constraint satisfaction problem. Later, CP search procedures were extended to efficiently estimate optimal solutions using constraints in a constraint optimization problem [27]. In this part, some notable features of the CP in both problem formulation and solving algorithms are mentioned. First of all, CP can deal with different types of decision variables such as interval and sequence-based variables and also integer variables [53]. Second, CP benefits from general constraints to develop models compactly [26]. Third, CP models have no limitation using different types of problem constraints and objective functions (e.g., linear, nonlinear, convex), which are challenging in developing MILP models. Moreover, from solving algorithms points of view, CP usually uses the propagation technique to remove unfeasible regions of the search space [54, 55]. CP benefits from this technique to tackle large optimization problems that may not be solvable by MILP models in a reasonable time frame [56].

In the present study, the Optimization Programming Language (OPL) and IBM ILOG CP optimizer platform are used to model and solve the problem. OPL is a modeling language for combinatorial optimization, designed to simplify optimization problems substantially. This language increases the applicability of modeling languages by incorporating techniques from constraint programming. The remainder of this part discusses how to formulate the CP models.

3.1 Variables

Two types of variables are defined:

• 1. Interval variables: these variables represent an interval of time during which something happens (a task or an activity is carried out). An interval is characterized by beginning, ending, and size values, which OPL offers some functions to retrieve these features. Interval variables are optional; that is, one can decide not to consider them in the solution schedule. According to this definition, an optional interval variable $x_{im}^{l}$ is defined, representing the $i^{th}$ job on $m^{th}$ machines in $l^{th}$ station $(i = 1,...,n,\,m \in M_{l} \,,\,l = 1,...,c)$.

• 2. Interval sequence variable: these variables represent a total order over a set of interval variables. In this newly proposed model, there exist some stations which can be mapped as sequence variables. Also, each of these variables can be divided into some sub-sequence variables that represent the machines in each station. Every station includes all the interval variables distributed on its machines. According to this definition, an interval sequence variable $q_{m}^{l}$ is defined, which represents the $m^{th}$ machine in $l^{th}$ station $\left( {m \in M_{l} } \right)$.

3.2 CP model

This section presents the corresponding CP models for $FF_{c} \left| {\,\left| {C_{\max } } \right.} \right.$ (FFS system with permutation) and $FF_{c} \left| {prmu\left| {C_{\max } } \right.} \right.$ (non-permutation FFS). The required parameters and variables are the same as defined in sub-Sects 2.1 and 3.1, respectively.

3.2.1 Non-Permutation CP model (CP-NP)

The CP model for $FF_{c} \left| {\,\left| {C_{\max } } \right.} \right.$ is formulated as below:

$$Minimize\,\,C_{\max } = \max \,(end\;Of(x_{im}^{c} ));\,\,\,\,\,i = 1,...,n,\,m \in M_{c}$$

(30)

Subject to:

$$\sum_{{m \in M_{l} }}^{{}} {presence\;Of(x_{im}^{l} )} = 1;\,\,\,\,\,\,i = 1,...,n;\,\,\,\,\,l = 1,...,c$$

(31)

$$(q_{m}^{l} ); for all m \in M_{l} l = 1,...,c$$

(32)

$$startOf\,(x_{{im_{2} }}^{{l_{2} }} ) \ge end\;Of(x_{{im_{1} }}^{{l_{1} }} );\,\,\,\,\,\,i = 1,...,n,\,l_{1} = l_{2} = 1,...,c,\,\,m_{1} \in M_{{l_{1} }} ,\,\,m_{2} \in M_{{l_{2} }} \,|\,l_{2} > l_{1}$$

(33)

$$L_{m} \le \max \,(end\;Of(x_{im}^{l} )) \le U_{m} ;\,\,\,\,\,\,i = 1,...n,\,\,l = 1,...,c,\,\,m \in M_{l}$$

(34)

The objective function is defined as the maximum finish time of jobs in the last station and expressed as Eq. (30). Due to the optionality feature of interval variables, a function (called $presenceOf$) could be used to indicate whether an interval variable is absent or present. By considering this, Eq. (31) is defined to assure that all jobs are carried out in each station, and only one job appears on only one machine in each station. OPL has some pre-defined functions which indicate the flexibility of the CP model. One of them is $noOverlap$, which guarantees that there is no overlap between any two interval variables which exist in a sequence. This constraint is applied to interval sequence variables, expressed as Eq. (32). This constraint states that the machines in all stations define a chain of non-overlapping jobs. Equation (33) assures that the same variable placed in the successive stations starts after the previous stations. Moreover, Eq. (34) is applied to ensure the upper and lower bounds of the time capacity of each machine.

By converting Eq. (33) to $startOf\,(x_{{im_{2} }}^{l} ) = = end\;Of(x_{{im_{1} }}^{l - 1} )$, the CP model for $FF_{c} \left| {nwt} \right|C_{max}$ is formed. Adding the parameter $Lag_{i}^{l}$ to the EQ.(33) as $start\;Of\,(x_{{im_{2} }}^{l} ) \ge end\;Of(x_{{im_{1} }}^{l - 1} ) + Lag_{i}^{l}$, the FFS will be formed with minimum time lags. Adding the parameter $Lag_{i}^{l}$ to the Eq. (33) as $start\;Of\,(x_{{im_{2} }}^{l} ) = = end\;Of(x_{{im_{1} }}^{l - 1} ) + Lag_{i}^{l}$, the FFS will be formed with a time lag restriction. Finally, by adding $startOf\,(x_{{im_{2} }}^{l} ) \le end\;Of(x_{{im_{1} }}^{l - 1} ) + Lag_{i}^{l}$ to the model, the FFS with maximum time lags is formulated.

By adding $startOf(x_{im}^{1} ) \ge R_{i}$, the CP model for FFS with release times restriction, $FF_{c} \left| {\,r\left| {C_{\max } } \right.} \right.$, is formed. This constraint states that the processing of all jobs in the first station occurs after the released time ($R_{i}$).

3.2.2 Permutation CP model (CP-P)

CP model for $FF_{c} \left| {\,\left| {C_{\max } } \right.} \right.$ can be extended to $FF_{c} \left| {prmu\left| {C_{\max } } \right.} \right.$ by adding a constraint to assure that every machine in all stations has the same job permutation. Equation (35) provides such that constraint. The OPL function $type\;Of\;Next\,(q_{{_{m} }}^{l} ,x_{im}^{l} )$ in this constraint refers to the following interval variable from $x_{im}^{l}$ in machine $q_{m}^{l}$.

$$type\;Of\;Next\,(q_{{m_{1} }}^{{l_{1} }} ,x_{{_{{im_{1} }} }}^{{l_{1} }} )\, = \,typeOfNext\,(q_{{_{{m_{2} }} }}^{{l_{2} }} ,x_{{_{{im_{2} }} }}^{{l_{2} }} );\,\,\,\,\,i = 1,...,n;\,\,\,\,m_{1} \in M_{{l_{1} }} ;\,\,\,\,m_{2} \in M_{{l_{2} }} \,$$

(35)

No-wait, time lags, and release time restrictions can be considered in $FF_{c} \left| {prmu\left| {C_{\max } } \right.} \right.$ as described for model $FF_{c} \left| {\,\left| {C_{\max } } \right.} \right.$.

4 Results of the models and efficiency comparison

For computational analysis purposes, several test problems are selected from the literature available for $FF_{c} \left| {nwt,prmu} \right|C_{max}$. These test problems include Car problems (Car01-08) [57] and Rec problems (Rec01, 03, 05, 41) [58], which are available in the OR-Library.¹Car problems generally contain a small number of jobs and stations (Sect. 4.1), while Rec problems correspond to real dimensions of industrial problems, which contain many jobs and stations (Sect. 4.2).

4.1 Problems with optimal solutions for $\left( {FF_{c} \left| {nwt,prmu} \right|C_{max} } \right)$

Conducting numerical experiments is a practical approach to compare the performance of the developed models. To verify the performance of the proposed models on the test problems, the results of the model obtained in Manne [59] and Samarghandi [50] are considered for comparison purposes. The numerical results of the following models are considered: 1) No-wait version of the Manne model; Manne model is one of the best and most commonly used models, 2) Original formulation of Model I of Samarghandi at relaxed due date constraints, 3) Model I of Samarghandi with indicator constraints and without due date constraints, 4) Model II of Samarghandi, which includes two dummy jobs that should be located in the first and the last positions in the sequence, 5) Model IV of Samarghandi, unlike previous models, is formulated based on properties of CP, 6) Model V of Samarghandi, is formulated based on CP. Due date constraints are relaxed in Model II, IV, and V. The newly proposed models of MILP-P and CP-P constitute the last two columns of Table 2.

Table 2 Computational results of the $FF_{c} \left| {nwt,prmu} \right|C_{max}$ problems with the optimal solution

The large number (H) is applied in the formulation of MILP models for either-or constraints. Although this is a proper manner to prototype either-or constraints, the numerical value of H may result in complexity in running the model in IBM CPLEX and any other software package. If the value of H is not selected accurately, the CPLEX may eliminate H in the pre-solve phase. Consequently, it is recommended² that either-or constraints should be formulated through indicator constraints instead of implementing the large number H. Whereas, applying indicator constraints would decrease the effectiveness of the branching algorithm, which in turn could increase the solution time. Based on solving different models through indicator constraints and the large number H, it was found that considering $H = \sum_{i = 1}^{n} {p_{i}^{l} } ;\,\,\,\,l = 1,...,c$ in constraints of each station is more efficient. Therefore, the large number H is applied in solving MILP models.

The IBM ILOG CPLEX V12.3 is applied to solve the newly developed MILP and CP models (maximum time limit 600Sec). All the numerical experiments are run on a PC with CPU- Intel Cori 7. 1.6 GHz and RAM-6 GB. In Table 2, OFV represents the objective function value and all of the CPU times are represented in seconds. The time when the optimal solution is found is reported. For instance, the optimal solution of Car03 is 8866; the MILP-P finds this solution after 173 s and the CP-P after 30 s. Instances without time show the objective function value at the maximum allowed CPU time (600Sec). The figures in boldface demonstrate the optimal solution in the time limit.

Based on Table 2, in all eight studied problems, the proposed MILP and CP models of the present study achieve the optimal solution. From the runtime point of view, MILP Model II of Samarghandi & Behrooz (2017), the proposed CP, and MILP models are ranked first, second, and third, respectively. Since all the models of Samarghandi & Behrooz (2017) are presented for $FF_{c} \left| {nwt,prmu} \right|C_{max}$ problems, the performance comparison is not possible for $FF_{c} \left| {nwt} \right|C_{max}$ problems. However, in Table 3, the values of the objective function and runtime are compared in various permutation and non-permutation schedules. The results of the presented models in the non-permutation schedule adopting MILP-NP and CP-NP are tabulated in Table 3. The results of non-permutation models are presented considering three machines in all stations.

Table 3 Computational results of the $FF_{c} \left| {nwt} \right|C_{max}$ for problems with optimal solutions

Although the objective function values in the MILP and CP models in non-permutation schedules are less than the objective function values of the equivalent model in the permutation schedules, the runtime of both MILP and CP models in the non-permutation schedule is longer than the runtime in permutation schedules. Note that in all the studied Car problems, permutation scheduling models have been solved at the time limit (600Sec), but in five non-permutation schedule problems, the models have not reached the optimal solution within the specified time limit.

4.2 Problems without optimal solutions $FF_{c} \left| {nwt,prmu} \right|C_{max}$

A set of 21 Rec problems are solved through the proposed models. The results are compared with the results obtained through other studies available in the literature that developed for $FF_{c} \left| {nwt,prmu} \right|C_{max}$. The computational results of the proposed MILP-P and CP-P for the problems without optimal solutions are tabulated in Table 4. Since the optimal solution cannot be found in less time through MILP-P and CP-P, both models are solved in 1800s. The feasible solution for Rec 37, 39, and 41 in the time limit cannot be found through MILP-P.

Table 4 Computational results of the $FF_{c} \left| {nwt,prmu} \right|C_{max}$ for problems without optimal solutions

In this Table, the first two columns represent the name and size of test problems. The third column presents the makespan of the model of Rajendran [60] for comparison. The next two columns represent the objective function value of the MILP-P and the deviation percentage between the reported objective function and the makespan values of Rajendran [60]. The deviation percentage between the objective function value of these proposed models and the model of Rajendran [60] is computed through Eq. (36):

$$Deviation\,Percentage = \left( {\frac{{OFV_{{}}^{Method} - OFV_{{}}^{Rajendran} }}{{OFV_{{}}^{Rajendran} }}} \right) \times 100$$

(36)

In this context, the more negative deviation percentage, the more efficient the method. This fact assures the competitiveness of these proposed models. The next two columns represent the best solution obtained in five runs for the test problem in $FF_{c} \left| {nwt,prmu} \right|C_{max}$ through the PSO algorithm of Samarghandi [61] and the TS + PSO algorithm (a hybrid of the Tabu search and PSO) of Samarghandi & ElMekkawy [62].

The MILP is compared with the three best models of Manne [59], Wilson [63], and Wagner [64] as mentioned in the study of Pan [65], in addition to three methods introduced by Stafford [66], Šeda [67] and Samarghandi & Behroozi [50] in Table 5.

Table 5 Comparison of MILP models for $FF_{c} \left| {prmu\left| {C_{\max } } \right.} \right.$

In Table 6 and Fig. 3, the number of decision variables of different models is compared in terms of different numbers ​​of jobs and stations. The lowest average number of decision variables in all problems belongs to Model I of Samarghandi, and the proposed model of this research is in the second rank with only 1% more variables.

Table 6 Comparison of the number of decision variables of different models

Fig. 3

Number of decision variables

Figure 3 represents that the number of decision variables of the proposed MILP-P model, Model I of Samarghandi and models of Stafford and Seda is much less than models of Wagner, Manne and Wilson.

Moreover, in Table 7, the number of constraints of different models is compared in different numbers ​​of jobs and stations. The lowest average number of constraints in all problems belongs to the Stafford model.

Table 7 Comparison of the number of constraints of different models

5 Conclusions and future research directions

This study extended the CVRP model for the FFS problem which involves no-wait, time lags, and release time restrictions and the objective of minimizing the makespan. Most of the available MILP models introduced by scholars for flow shop are tailored to handle either permutation or non-permutation schedules with specific restrictions. In other words, their MILP methods cannot be applied to solve both permutation and non-permutation scheduling problems. Developing MILP formulation according to the CVRP concept would be one of the modeling approaches to remove the above limitations. The significance of this study lies in its contribution to the literature by presenting a new and efficient approach based on the CVRP problem to solve FFS scheduling problems which is the first attempt in the related literature. Therefore, the models of the present study are versatile enough to be adapted to both types of permutation and non-permutation schedules in FFS, which can be used to optimize industrial activities. This research not only proposes multiple MILP models for various FFS problems but also presents corresponding CP models for these MILP models. Moreover, the computational performance of these parallel models is compared in various sizes.

The comparative analysis of various models reveals that CP models have superior computational performance than MILP models. However, the MILP models are also timely-efficient. Moreover, the efficiency of developed models is also represented in comparison with several benchmark datasets. Computational results from the available test problems in the literature reveal the efficiency of developed models in achieving solutions of high quality for the given problems in a reasonable time. The extended models can improve many solutions of the small and large best-known test problems. Based on the findings, while the objective function values of the MILP and CP models in non-permutation schedules exhibit lower values than their respective equivalents in permutation schedules, both models demonstrate longer runtime in non-permutation schedules. Therefore, enterprises should assess the computational performance of various models and select the most appropriate one (case-by-case) based on the problem size and complexity. The extended models can be utilized for a wide range of real-world FFS scheduling problems in manufacturing processes by inputting the related parameters into the MILP or CP model. The models can also assist the enterprise to evaluate various production scenarios (like changing the number of machines) and compare their impact on the makespan. This research provides significant insights for decision-makers and managers in industries that require efficient scheduling methods. However, a limitation of the research is the lack of a comprehensive dataset in the literature that considers all the restrictions in permutation and non-permutation schedules.

Future studies may focus on applying these proposed models to various scheduling problems like the blocking flow shop scheduling problem or the problems with other objectives or restrictions, like the precedence relations. The flow shop models presented in the current study are categorized into identical Parallel Machine Scheduling (PMS) problems. A future study could be conducted by extending the modeling approach proposed in this research to solve uniform and unrelated PMS problems. Moreover, other time performance criteria such as flow time, maximum tardiness and mean tardiness (or earliness) could be taken into account instead of the makespan or as a new objective function. It would be interesting to extend this research to other manufacturing settings like job shops and open shops.