1 Introduction

Scheduling is one of the most crucial research issues in various manufacturing fields. Effective scheduling reduces production costs and times and improves enterprises’ economic efficiency (Liu et al. 2023). The flow shop scheduling problem is a complex combinatorial optimization problem widely studied recently (Maciel et al. 2022). The problem involves sequencing all operations performed on all jobs with the same machine order. With the development of production systems, the flow shop environment has evolved to fulfill the increased demand for products and balance the production capacity, and the hybrid flow shop environment has emerged with parallel machines at each stage of production. Therefore, the hybrid flow shop scheduling problem (HFSP) has become prominent, which is a generalization of the classical flow shop.

The HFSP was first addressed by Arthanari and Ramamurthy (1971). The HFSP extends the flow shop scheduling problem by processing a job on any machine in a given stage. In the HFSP, j jobs are to be processed in a series of s stages, each comprising several parallel machines. This type of layout increases the production capacity and achieves flexibility (Ribas et al. 2010). The HFSP can be classified based on the characteristics of the parallel machines used; the HFSP with identical parallel machines, the HFSP with uniform parallel machines, and the HFSP with unrelated parallel machines (Meng et al. 2020a). The main difference between identical and uniform machines is the processing speed. While identical machines process the jobs at the same speed, uniform machines process the jobs at different speeds at a given rate.

However, unrelated machines have different speeds for different jobs. If the machines are identical, the particular machine that processes a job is not significant; however, for unrelated machines, assigning jobs to specific machines must be explicitly modeled (Ünal et al. 2020). Within the context of this study, we handle the HFSP with unrelated parallel machines and its extended problems, namely, the no-wait HFSP (HFSP-NW), the HFSP with blocking (HFSP-B), the HFSP with sequence-dependent setup times (HFSP-SDST), the no-wait HFSP with sequence-dependent setup times (HFSP-SDST-NW) and the blocking HFSP with sequence-dependent setup times (HFSP-SDST-B). Machine eligibility restrictions are also considered in all problem types. In this way, the knowledge that not all machines can perform each operation, i.e., that specific machines cannot be used for certain tasks, is included in the problem.

HFSP appears in various industries: Sherali et al. (1990) considered the HFSP-SDST for a two-stage paper products plant. Tsubone et al. (1993) studied a two-stage HFSP for photographic film manufacturing industries. Grabowski and Pempera (2000) considered a production problem of concrete blocks in a building factory. They modeled the problem as an HFSP-NW. Kurz and Askin (2004) examined the HFSP-SDST in the electronics and automobile industries. Ruiz and Maroto (2006) presented an HFSP including unrelated parallel machines at each stage, sequence-dependent setup times, and machine eligibility restrictions for the ceramic tile manufacturing sector. Chen et al. (2006, 2007) considered a three-stage HFSP with unrelated parallel machines, precedence constraints, sequence-dependent setup times, and blocking for container handling systems. Pan et al. (2013) provided a real-world HFSP application in the iron and steel industry in another study. This study considered a complex hybrid flow shop including multi-stages with multiple parallel machines. Their proposed model also involved the setup time and transfer time of jobs.

The contributions of this paper can be stated as follows:

  1. 1.

    For the first time, three new constraint programming (CP) models have been developed for the HFSP-B, HFSP-SDST-NW, and HFSP-SDST-B with unrelated machines and eligibility constraints.

  2. 2.

    For the first time, two new MILP models have been proposed for the HFSP-SDST-NW and HFSP-SDST-B with unrelated machines and eligibility constraints.

  3. 3.

    Alternative CP models for the HFSP and HFSP-SDST have also been developed for comparison purposes.

  4. 4.

    A comprehensive analysis of all CP models for all mentioned versions of the HFSP has been performed against the recently developed MILP models by Meng et al. (2020a), using small-scale benchmark instances from the literature and newly generated 90 larger-size problem instances. In this regard, this study is novel in that it has incorporated many variants of the HFSP that have not previously been studied in one paper.

  5. 5.

    The optimality of benchmark instances has been verified, providing novel confirmation in the field and yielding new optimal solutions for diverse variants of the HFSP.

  6. 6.

    The computational results can be used for comparison purposes in designing new solution techniques because we share all the instances, codes, and solutions obtained.

The remainder of this paper is organized as follows. Section 2 presents the literature review of the HFSP and its extensions. The developed MILP models for the HFSP-SDST-B and HFSP-SDST-NW are described in Sect. 3. Section 4 provides an in-depth explanation of the proposed CP models. Section 5 gives the computational results for evaluating the efficiency of the CP models. Finally, Sect. 6 presents concluding remarks and further research directions.

2 Literature review

In the existing literature, many exact and approximate solution methods have been proposed for the HFSP. For a comprehensive review of models and solution algorithms in general HFSPs, readers can refer to the survey papers of Ribas et al. (2010), Ruiz and Vázquez-Rodríguez (2010), Lin and Gen (2018) and Çolak and Aydın Keskin (2022).

Exact solution methods include MILP (Meng et al. 2019, 2020a), branch-and-cut method (Naderi et al. 2014), Lagrangian relaxation-based algorithms (Brah et al. 1991; Martello et al. 1997) and CP (Oztop et al. 2019; Meng et al. 2021). The effectiveness of the CP method on the HFSP problem has been proven by Oztop et al. (2019). In the related study, they used CP to optimize the makespan and energy consumption of the HFSP. Meng et al. (2022) focused on a distributed version of the HFSP. The authors proposed three new MILP models and a CP model to solve the problem. Naderi et al. (2023) highlighted the development of CP in recent years. The authors compared 12 scheduling problems to reveal the advantages and disadvantages of the new developments in comparison with the MILP model. Oujana et al. (2023) formulated the scheduling of production orders in a packaging plant as a hybrid flexible flow shop scheduling problem. The authors presented MILP, CP, and a novel dedicated heuristic to solve the defined problem.

Gupta (1988) has proved that a two-stage flow shop scheduling problem with multiple processors is NP-hard even when one of the two stages contains a single machine. Other studies in the literature also prove that HFSP is an NP-hard problem, such as Pessoa et al. (2019), Shao et al. (2020), Zhang et al. (2022), and Liu et al. (2023). Due to the NP-hard nature of the problem, exact solution methods can only solve small-sized instances efficiently (Carlier and Neron 2000; Néron et al. 2001). Therefore, many approximate solution methods were proposed to solve large-size HFSP instances efficiently. However, they do not guarantee the optimal solution. Approximate methods mainly include heuristic methods and metaheuristic algorithms. Since 1996, several heuristic algorithms have been proposed according to the characteristics of the HFSP. These algorithms can be divided into two categories: local search (Piersma and Van Dijk 1996; Fanjul-Peyro and Ruiz 2010) and heuristic strategies (Kim and Lee 2009; Yang-Kuei and Chi-Wei 2013) are commonly used.

Metaheuristic algorithms are more efficient methods for solving the HFSP, such as tabu search (Shahvari and Logendran 2016), genetic algorithm (GA) (Cui et al. 2005; Jungwattanakit et al. 2008; Zhou and Tang 2009; Yu et al. 2018; Meng et al. 2019), simulated annealing (Low 2005), ant colony optimization algorithm (Lin et al. 2013; Qin et al. 2018), discrete differential evolution algorithm (Zhang and Chen 2018), differential evolution with local search algorithm (Xu and Wang 2011), artificial bee colony algorithm (Wang et al. 2012), particle swarm optimization algorithm (Torabi et al. 2013), fruit fly optimization algorithm (Zheng and Wang 2016) and neighborhood search algorithms (Lei and Zheng 2017; de Siqueira et al. 2020).

Additionally, non-classical methods such as intelligence/learning algorithms and neural network methods exist. For example, Lei et al. (2018) presented a teaching–learning-based optimization algorithm to solve the energy-efficient HFSP with unrelated machines. Han et al. (2019) developed a reinforcement learning method, whereas Zacharias et al. (2019) applied a machine learning-based approach to the HFSP with unrelated machines considering makespan minimization. Another study was carried out by Cao et al. (2020) that proposed an improved gravitational search algorithm for the HFSP with unrelated parallel machines. Gil and Lee (2022) pointed out that some conditions critical to the material scheduling problem are not considered in practice, which is challenging for learning. The authors proposed deep Q-network and proximal policy optimization as deep reinforcement learning approaches for solving the HFSP.

2.1 Literature review on the HFSP-SDST

The best-known extension of the HFSP is the inclusion of sequence-dependent setup times into the problem. The HFSP-SDST is based on the idea that a particular preparation time passes between different job types successively processed on the same machine. Scheduling with setup times is vital in a manufacturing environment where high-quality products are guaranteed and delivered on time. The studies of Allahverdi et al. (2008) and Allahverdi and Soroush (2008) emphasized the importance of consideration of setup times in scheduling problems, including the HFSPs.

In the related literature, various solution approaches have been proposed for the HFSP-SDST. Solution approaches developed for the HFSP-SDST with identical machines are mostly heuristics (Lin and Liao 2003; Tang and Zhang 2005; Zandieh et al. 2006; Mousavi et al. 2011; Naderi and Yazdani 2014; Wang et al. 2019; Fernandez-Viagas et al. 2020; Zhang et al. 2020), metaheuristics (Davoudpour and Ashrafi 2009; Gholami et al. 2009; Naderi et al. 2009; Zandieh et al. 2009; Karimi et al. 2011; Gómez-Gasquet et al. 2012; Javadian et al. 2012; Pargar and Zandieh 2012; Ebrahimi et al. 2014; Pan et al. 2017; Zhang et al. 2019) and simulation-based solution approaches (Gheisariha et al. 2021).

For solving the HFSP-SDST considering unrelated parallel machines, different solution approaches such as the linear programming approach (Oujana et al. 2021), constructive and iterative-based heuristics (Jungwattanakit et al. 2009; Urlings et al. 2010), metaheuristics (Ruiz and Maroto 2006; Jungwattanakit et al. 2008; Yaurima et al. 2009; Zandieh et al. 2010; Garavito-Hernández et al. 2019; Qin et al. 2019; Aqil and Allali 2020), and hybrid algorithms (Shahvari and Logendran 2018) have been developed. In addition, these studies (Ruiz and Maroto 2006; Yaurima et al. 2009; Urlings et al. 2010; Zandieh et al. 2010; Shahvari and Logendran 2018; Oujana et al. 2021) also considered the machine eligibility restrictions. Some studies employ exact solution methods. For instance, Ruiz et al. (2008) presented a MILP model for a more realistic version of the HFSP-SDST to fill the gap between theory and practice. Meng et al. (2020a) presented many MILP models with different characteristics for the HFSP-SDST and its extensions. Later, Meng et al. (2021) applied CP to the HFSP-SDST; however, their computational analysis did not provide a comparison with the MILP solutions. Yong et al. (2022) proposed NEH-based constructive heuristic algorithms to solve the HFSP-SDST. The authors considered two cases of the problem and aimed to minimize the total energy consumption cost. Missaoui and Ruiz (2022) focused on the HFSP-SDST with due date windows and presented an algorithm; the parameter-less iterated greedy method, that combined the ideas of local search methods and iterated greedy.

2.2 Literature review on the HFSP-NW and HFSP-SDST-NW

Another extension is achieved by adding no-wait constraints to the HFSP. In some real-life applications, jobs must be processed without delay so that the products manufactured in industries like steel, food, chemicals, and plastic molding are not damaged or spoiled. Sriskandarajah (1993) was among the early researchers to study this problem and employed a sorting algorithm that considers worst-case bounds for its solution.

The HFSP-NW has been studied in a two-stage environment (Liu et al. 2003; Xie et al. 2004; Haouari et al. 2006; Cheng et al. 2000; Huang et al. 2009; Carpov et al. 2012; Moradinasab et al. 2013; Wang and Liu 2013; Rabiee et al. 2014; Wang et al. 2015, 2020; Zhong and Shi 2018).

The HFSP-NW has also been studied in a multi-stage environment. Chang et al. (2006) proposed a heuristic approach to minimize makespan. Later, Jolai et al. (2009) addressed the problem with due window constraints and job rejection options and presented a GA for its solution. Zhang and Chen (2014) developed a hybridized solution approach based on the particle swarm optimization and Nawaz, Enscor, and Ham algorithms to minimize makespan. Meng et al. (2020a) proposed a MILP model for the HFSP-NW.

The HFSP-SDST-NW version has been studied in past research. Jolai et al. (2012) developed a population-based simulated annealing, an imperialist competitive algorithm, and hybridization of these algorithms to minimize makespan. Asefi et al. (2014) simultaneously considered makespan and tardiness objectives and proposed a hybrid non-dominated sorting GA II and variable neighbourhood search algorithm. Ramezani et al. (2015) handled the HFSP-SDST-NW with uniform machines to minimize makespan. They hybridized invasive weed optimization, variable neighbourhood search, and simulated annealing algorithms to solve the problem. Rabiee et al. (2016) proposed a biogeography-based optimization algorithm to solve the HFSP-SDST-NW considering unrelated parallel machines at each stage, machine eligibility restrictions, and different ready times to minimize the mean tardiness. In another study, Harbaoui et al. (2017) studied the HFSP-SDST-NW motivated by a real industrial application.

2.3 Literature review on the HFSP-B and HFSP-SDST-B

A finite intermediate buffer (limited buffer) always exists in realistic flow shop scheduling problems. A finished part remains on a machine and blocks it until a downstream machine becomes available when limited intermediate buffers exist between the stages. The HFSP-B is a typical scheduling problem with a solid industrial background in many industries, such as steel.

In the literature, fewer studies have focused on the HFSP-B. Sawik (2002) proposed a MILP model, and Tang and Xuan (2006) developed a Lagrangian relaxation algorithm as an exact solution approach for the HFSP-B with identical machines. Wang and Tang (2009) proposed a hybrid algorithm combining the tabu search and scatter search algorithms as an approximate solution to solve the same problem. Tavakkoli-Moghaddam et al. (2009) solved the same problem using a memetic algorithm combined with nested variable neighbourhood search. Later, Tao et al. (2014) developed a hybrid algorithm for the HFSP-B with unrelated machines based on GA and simulated annealing, and Li and Pan (2015) hybridized the Artificial Bee Colony and tabu search algorithms. Tao and Zhou (2017) addressed an HFSP-B with unrelated parallel machines. They proposed a multi-objective GA to obtain the optimal solutions. Missaoui and Boujelbene (2021) recently proposed an iterated greedy approach for the HFSP-B with identical parallel machines. Zhang et al. (2021) proposed a discrete whale swarm algorithm for HFSP-B with uniform machines and two process routes. They validated the effectiveness of the proposed algorithm in a real-world industrial case. Wang et al. (2023) also presented a heuristic algorithm to solve the HFSP-B. The authors integrated a variant of an iterated greedy algorithm with various decoding rules. Unlike other studies, Elmi and Topaloglu (2013, 2014) considered the HFSP-B with robots as transport resources. They modeled a MILP model for the problem considering unrelated parallel machines at each stage, multiple part types, and machine eligibility constraints to minimize the makespan. Then, they proposed two simulated annealing-based algorithms to obtain good-quality solutions.

The problem is also studied with the HFSP-SDST-B version. Chen et al. (2007) considered a three-stage HFSP-SDST-B with unrelated parallel machines and precedence constraints for container handling systems. They improved the coordination among the equipment and increased the terminal’s productivity. They proposed a tabu search-based algorithm to solve the related problem. Rezaie et al. (2009) presented a MILP model for the HFSP-SDST-B with unrelated parallel machines for fuzzy due dates, while Yaurima et al. (2009) considered the problem with eligibility constraints. They proposed a modified and extended version of the GA approach developed for a real-world problem for a television production line with limited buffers. Zandieh and Rashidi (2009) studied the HFSP-SDST with processor blocking. They proposed a hybrid GA to solve the problem. Rashidi et al. (2010) addressed the HFSP-SDST-B with unrelated parallel machines to minimize the makespan and maximum tardiness criteria. They proposed a GA algorithm to tackle the problem. Fereidoonian and Mirzazadeh (2012) proposed a GA algorithm for solving the HFSP-SDST-B with unrelated parallel machines, precedence relationships, and machine eligibility as additional constraints. Moccellin et al. (2018) proposed heuristic algorithms and priority rules based on the traditional shortest processing time and longest processing time rules for the HFSP-B, considering sequence-independent and independent setup times.

Mollaei et al. (2019) studied the HFSP-B considering uncertain sequence‐dependent setup times. They presented a bi-objective mathematical model and proposed a robust possibilistic programming approach for the problem. Qin et al. (2020) tackled the scheduling problem of the container unloading/loading process as an HFSP-SDST-B. They proposed a hybrid MIP/CP solution method that combines the strengths of the branch-and-cut algorithm for MIP and the branch-and-prune algorithm for CP. Aqil and Allali (2021) recently presented the HFSP-SDST-B to minimize tardiness and earliness with uniform parallel machines. They proposed two nature-inspired metaheuristics based on the migratory bird and water wave optimization algorithms. Maciel et al. (2022) recently addressed the HFSP-SDST-B, considering identical parallel machines per stage. They proposed a hybrid GA to obtain feasible solutions for large-sized problems.

3 Problem definition and mathematical model

The HFSP can be defined as follows; there are s stages in sequence, where s > 1. For stage s (s = 1, 2, …, S), there are \(\left|{M}_{s}\right|\) (\(\left|{M}_{s}\right|\) ≥1) unrelated parallel machines. A set of \(\left|J\right|\) jobs should be sequentially processed in these stages following the same production flow. Each job \(j\in J\) has a non-negative processing time \(\text{Pt}_{j,m}\) for each machine \(m\in M\). A machine can process only one job, and a job can be processed by only one machine. All machines and jobs can be processed at zero; job preemption is prohibited. Related to the eligibility aspect, describing \({E}_{j,m}\), each job cannot be processed on any parallel machine of a stage. If machine m is capable of processing job j, the parameter \({E}_{j,m}\) takes one. For the extensions of the HFSP, we consider the following assumptions. For the HFSP-SDST, setup times must be considered. \(\text{St}_{j,j^{\prime},m}\) indicates the setup time of job j’ on machine m, where j indicates the immediately preceding job. For another extension of the HFSP, the HFSP-NW, we assume that there is no idle time between each job’s operations at two consecutive stages. For the last extension, the HFSP-B, we assume no intermediate buffer between two adjacent processing stages. The HFSP finds a schedule that optimizes a given objective. This study considers minimizing the maximum completion time (makespan).

3.1 Mathematical model

This section gives the sets, parameters, decision variables, and deterministic MILP models developed for the HFSP-SDST-NW and HFSP-SDST-B. The MILP models for other variants studied of the HFSP are taken from Meng et al.’s (2020a) study and used for comparative computational analysis. These models are given in Appendix.

3.1.1 Indices and sets

\(j,j^{{\prime}}\)

Index for jobs

\(s,{s}^{{{\prime}}}\)

Index for stages

\(m\)

Index for machines

\(t\)

Index for positions

\(J\)

Set of jobs where \(j,j^{{\prime}}\in \left\{1,\ldots ,\left|J\right|\right\}\)

\(S\)

Set of stages where \(s,{s}^{{{\prime}}}\in \left\{1,\ldots ,\left|S\right|\right\}\)

\(M\)

Set of machines where \(m\in \left\{1,\ldots ,\left|M\right|\right\}\)

\({M}_{s}\)

Set of parallel machines that belong to stage s where \(m\in \left\{1,\ldots ,\left|{M}_{s}\right|\right\}\)

\({P}_{m}\)

Set of positions for machine m where \(t\in \left\{1,\ldots ,\left|J\right|\right\}\)

3.1.2 Parameters

\({O}_{j,s}\)

sth operation of job j

\({\text{Pt}}_{j,m}\)

Processing time of job j on machine m

\({\text{St}}_{j,j^{{\prime}},m}\)

Setup time from job j to job j′ on machine m

\({E}_{j,m}\)

Equals to one if machine m is capable of processing job j and 0 otherwise

\({\text{Big}}\,M\)

A very large positive integer

3.1.3 Decision variables

\({X}_{j,m}\)

The binary variable that is equal to one if job j is processed on machine m and 0 otherwise

\({Y}_{j,m,t}\)

The binary variable that is equal to one if job j occupies position t of machine m and 0 otherwise

\({B}_{j,s}\)

The continuous decision variable that represents the starting time of operation \({O}_{j,s}\)

\({Y}_{j,j^{{\prime}},s}\)

The binary decision variable equals one if job j is processed (directly or indirectly) before job j\(^{{\prime}}\) at stage s, and 0 otherwise, where \(j<j^{{\prime}}\)

\({C}_{{\rm max}}\)

Makespan

3.1.4 Objective function

$$\text{Min}\,Z= {C}_{{\rm max}}.$$
(1)

The objective function (1) minimizes the \({C}_{{\rm max}}\).

3.1.5 Constraints of the HFSP-SDST-NW model

$$\sum_{m\in {M}_{s}, { E}_{j,m}=1}{X}_{j,m}=1 \quad\forall j\in J,\ m\in M$$
(2)
$$\sum_{t\in {P}_{m}}{Y}_{j,m,t}={X}_{j,m}\quad \forall j\in J,\ m\in M,\ {E}_{j,m}=1$$
(3)
$${C}_{{\rm max}}\ge {B}_{j,S}+\sum_{m\in {M}_{S}, { E}_{j,m}=1}\sum_{t\in {P}_{m}}\text{Pt}_{j,m}{Y}_{j,m,t}\quad \forall j\in J$$
(4)
$$\begin{aligned}&{B}_{j,s}+\sum_{m\in {M}_{s}, {E}_{j,m}=1}\text{Pt}_{j,m}{X}_{j,m} +\text{St}_{j,j^{\prime},m}\\ &\quad\le {B}_{{j}^{\prime},s}+ {\text{Big}}\,M\left(3-{Y}_{j,{j}^{\prime},s}-{X}_{j,m}-{X}_{{j}^{\prime},m}\right)\\ &\qquad \forall j,j^{\prime}\in J,\ j<j^{\prime},\ s\in S,\ m\in {M}_{s},\ {E}_{j,m}=1\end{aligned}$$
(5)
$$\begin{aligned}&{B}_{j^{\prime},s}+\sum_{m\in {M}_{s}, { E}_{j^{\prime},m}=1}\text{Pt}_{j^{\prime},m}{X}_{j^{\prime},m} +\text{St}_{j^{\prime},j,m}\le {B}_{j,s}+ {\text{Big}}\,M\left(2+{Y}_{j,{j}^{\prime},s}-{X}_{j,m}-{X}_{{j}^{\prime},m}\right),\\ &\quad \forall j,j^{\prime}\in J,\ j<j^{\prime},\ s\in S,\ m\in {M}_{s},\ {E}_{j^{\prime},m}=1\end{aligned}$$
(6)
$$\begin{aligned}&{B}_{j,s}+\sum_{m\in {M}_{s}, { E}_{j,m}=1}\sum_{t\in {P}_{m}}\text{Pt}_{j,m}{Y}_{j,m,t}= {B}_{j,s+1}\\ &\quad \forall j\in J,\ s\in \{1,\ldots ,S-1\}\end{aligned}$$
(7)
$${B}_{j,s} ,{C}_{{\rm max}}\ge 0\quad \forall j\in J,\ s\in S$$
(8)
$${X}_{j,m},{Y}_{j,m,t},{Y}_{j,j^{\prime},s}\in \left\{{0,1}\right\}\quad \forall j,{j}^{\prime}\in J,\ s\in S,\ m\in {M}_{j},\ t\in {P}_{m}.$$
(9)

Constraint (2) enforces that each job at each stage is assigned to exactly one machine considering eligibility aspects. Constraint (3) ensures the relationship between two binary decision variables. Constraint (4) calculates makespan. Constraints (5) and (6) guarantee that if two jobs are assigned to the same machine at a stage, the starting time of the latter job is no less than the sum of the starting time of the former job, the processing time of the former job and the setup time between these two jobs. Constraint (7) provides equality, guaranteeing that each job operation can only be started when its preceding operation is finished at the previous stage. Constraints (8) and (9) define integer and binary decision variables.

3.1.6 Constraints of the HFSP-SDST-B model

$$\sum_{m\in {M}_{s}, { E}_{j,m}=1}{X}_{j,m}=1\quad \forall j \in J,\ m\in M$$
(10)
$$\sum_{t\in {P}_{m}}{Y}_{j,m,t}={X}_{j,m} \quad\forall j\in J,\ m\in M,\ { E}_{j,m}=1$$
(11)
$${B}_{j,s}+\sum_{m\in {M}_{s}, { E}_{j,m}=1}\sum_{t\in {P}_{m}}\text{Pt}_{j,m}{Y}_{j,m,t} \le {B}_{j,s+1} \quad\forall j\in J,\ s\in \{1,\ldots ,S-1\}$$
(12)
$${C}_{{\rm max}}\ge {B}_{j,S}+\sum_{m\in {M}_{S}, { E}_{j,m}=1}\sum_{t\in {P}_{m}}\text{Pt}_{j,m}{Y}_{j,m,t}\quad \forall j\in J$$
(13)
$$\begin{aligned}&{B}_{j,s}+\sum_{m\in {M}_{s}, { E}_{j,m}=1}\text{Pt}_{j,m}{X}_{j,m}+\text{St}_{j,{j}^{\prime},m}\\ &\quad\le {B}_{{j}^{\prime},s}+ {\text{Big}}\,M\left(3-{Y}_{j,{j}^{\prime},s}-{X}_{j,m}-{X}_{{j}^{\prime},m}\right),\\ &\qquad \forall j,{j}^{\prime}\in J,\ j<{j}^{\prime},\ s\in S,\ m\in {M}_{s},\ {E}_{j,m}=1\end{aligned}$$
(14)
$$\begin{aligned}&{B}_{j^{\prime},s}+\sum_{m\in {M}_{s}, {E}_{j^{\prime},m}=1}\text{Pt}_{j^{\prime},m}{X}_{j^{\prime},m}+\text{St}_{j^{\prime},j,m}\le {B}_{j,s}+ {\text{Big}}\,M\left(2+{Y}_{j,{j}^{\prime},s}-{X}_{j,m}-{X}_{{j}^{\prime},m}\right),\\ &\quad \forall j,j^{\prime}\in J,\ j<j^{\prime},\ s\in S,\ m\in {M}_{s},\ {E}_{j^{\prime},m}=1\end{aligned}$$
(15)
$$\begin{aligned}&{B}_{j,s+1}\le {B}_{j^{\prime},s}+{\text{Big}}\,M\left(3-{Y}_{j,{j}^{\prime},s}-{X}_{j,m}-{X}_{{j}^{\prime},m}\right),\\ &\quad \forall j,j^{\prime}\in J,\ j<j^{\prime},\ s\in \left\{1,\ldots , S-1\right\},\ m\in {M}_{s},\ {E}_{j,m}=1\end{aligned}$$
(16)
$$\begin{aligned}&{B}_{j^{\prime},s+1}\le {B}_{j,s}+{\text{Big}}\,M\left(2+{Y}_{j,{j}^{\prime},s}-{X}_{j,m}-{X}_{{j}^{\prime},m}\right),\\ &\quad \forall j,j^{\prime}\in J,\ j<j^{\prime},\ s\in \left\{1,\ldots , S-1\right\},\ m\in {M}_{s},\ {E}_{j^{\prime},m}=1\end{aligned}$$
(17)
$${B}_{j,s} ,{C}_{{\rm max}}\ge 0\quad \forall j\in J,\ s\in S$$
(18)
$${X}_{j,m},{Y}_{j,m,t},{Y}_{j,j^{\prime},s}\in \left\{\text{0,1}\right\}\quad \forall j,{j}^{\prime}\in J,\ s\in S,\ m\in {M}_{j},\ t\in {P}_{m}.$$
(19)

The model minimizes makespan. Constraint (10) represents that each job at each stage is assigned to exactly one machine considering eligibility aspects. Constraint (11) ensures the relationship between two binary decision variables. Constraint (12) describes the precedence relations for successive operations of a job. It guarantees that an operation of each job can only be started when the preceding operation is finished at the previous stage. Constraint (13) calculates makespan. Constraint sets (14) and (15) ensure that if two jobs are assigned to the same machine at a stage, the starting time of the latter job is no less than the sum of the starting time of the former job, the processing time of the former job and setup time between these two jobs. Constraint sets (16) and (17) represent the blocking constraints. They also guarantee the precedence relation of two jobs on the same machine; each machine can process only one job at any time, except for the last stage. Constraint sets (18) and (19) define integer and binary decision variables.

4 Proposed constraint programming models

4.1 An overview of constraint programming

CP, also called constraint logic programming, is a technique used for solving constraint satisfaction problems. CP provides a flexible solution environment for developing efficient and specific solution strategies by carrying information between the constraints and variables through constraint propagation algorithms. With constraint propagation, when a value is assigned to a variable, the domain of that variable is modified through all the constraints related to that variable. When all the variables in a constraint are updated, the values from the domains of the variables are removed if any inconsistencies between the variables' domains are detected, known as domain reduction. CP constructs a search tree in which each node represents a decision variable while each branch indicates the value of a variable. CP allows us to define the search tree employing variable and variable and value ordering strategies specific to the problem. When the domain of a variable is empty, the search backtracks to the recently instantiated variable and assigns another value for it. When constraint propagation terminates with unfixed variables, CP backtracks through the search tree and tries another node that has not been branched yet (Lustig and Puget 2001). If all the nodes have been branched and fathomed, then an infeasibility is detected.

The algorithms that CP uses vary according to variable types and constraint structures, and a general framework can be drawn for the CP solution approach, as given in Fig. 1.

Fig. 1
figure 1

Flow chart of a general algorithm for CP (Kanet et al. 2004)

Full size image

A CP formulation represents the problem domain features by variables, constraints, and performance measures. Moreover, complex constraints can be expressed with global constraints and effective domain-filtering algorithms to improve computational efficiency (Yunusoglu and Topaloglu Yildiz 2021). In CP, we can define decision variables as binary or integer, but we can also define specialized interval and interval sequence variables for scheduling problems. The interval variable represents a task with starting and ending times over the planning horizon and the length of the task. Once an interval variable is declared, we can specify whether it is optional or mandatory. The mandatory variable has to be in the solution, but if we define it as optional, it can be either in the solution or not. Note that for this specification, we need an additional constraint in MILP (IBM 2017). The order of the interval variables is stored in the interval sequence variables. Variable definitions can be shown visually, as in Fig. 2.

Fig. 2
figure 2

Visual representation of interval and interval sequence variables

Full size image

Recently, CP techniques have received increasing attention from researchers, specifically for scheduling problems. Scheduling is one of CP’s most successful application areas (Laborie et al. 2018). It has been successfully applied to a variety of scheduling problems, such as job shop scheduling (Meng et al. 2020b; Naderi et al. 2023; Ham and Cakici 2016), unrelated parallel machine scheduling with SDST (Yunusoglu and Topaloglu Yildiz 2021; Gedik et al. 2017), project scheduling (Kreter et al. 2018), employee scheduling (Topaloglu and Ozkarahan 2011), among others.

This study aims to achieve high-quality solutions in less computation time by enhancing constraint propagation using new CP model characterizations. No research has been conducted on CP modeling to solve all these variants of the HFSP. A CP model is developed for each problem to fulfill this gap, and the advantages of the CP solution approach to solve these scheduling problems are explored.

4.2 Formulations of the proposed CP models

In this section, the developed CP models are described in detail. The notation used for indices, sets, and parameters is identical to the MILP models. First, the decision variables and then the objective function and constraints are described.

4.2.1 Decision variables

\({X}_{j,{s}}\)

Interval variable for job j at stage s that must be present in the solution

\({Y}_{j,s,m}\)

Optional interval variable indicating whether job j is assigned to machine m at stage s

\({\text{Stg}}_{s,m}\)

Interval sequence variable for each machine m that includes the interval variables \({Y}_{j,s,m}\) assigned to machine m at stage s

4.2.2 Objective function

$$\text{Min}\,Z= {C}_{{\rm max}}.$$
(1)

4.2.3 Constraints of the HFSP-CP model

$${C}_{{\rm max}}=\underset{j\in J}{\text{max}}\left\{{\textit{endOf}}\left({X}_{j,\left|S\right|}\right)\right\}$$
(20)
$${\textit{alternative}}\left({X}_{j,s},\left\{{Y}_{j,s,m}|m\in M:{E}_{j,s,m}=1\right\}\right),\quad \forall j\in J,\ s\in S$$
(21)
$${\textit{endBeforeStart}}\left({X}_{j,s},{X}_{j,s+1}\right),\quad \forall j\in J,\ s\in 1\ldots S:s\ne \left|S\right|$$
(22)
$${\textit{noOverlap}}\left(\text{Stg}_{s,m}\right) \quad\forall s\in S,\ m\in M:{E}_{j,s,m}=1$$
(23)
$${\textit{Cumulative}}\left({X}_{j,s}|j\in J,s\in S,1,\left|{M}_{s}\right|\right).$$
(24)

4.2.4 Constraints of the HFSP-NW-CP model

$${C}_{{\rm max}}=\underset{j\in J}{\text{max}}\left\{{\textit{endOf}}\left({X}_{j,\left|S\right|}\right)\right\}$$
(25)
$${\textit{alternative}}\left({X}_{j,s},\left\{{Y}_{j,s,m}|m\in M:{E}_{j,s,m}=1\right\}\right), \quad\forall j\in J,\ s\in S$$
(26)
$${\textit{endAtStart}}\left({X}_{j,s},{X}_{j,s+1}\right),\quad \forall j\in J,\ s\in 1\ldots S:s\ne \left|S\right|$$
(27)
$${\textit{noOverlap}}\left(\text{Stg}_{s,m}\right) \quad\forall s\in S,\ m\in M:{E}_{j,s,m}=1$$
(28)
$${\textit{Cumulative}}\left({X}_{j,s}|j\in J,s\in S,1,\left|{M}_{s}\right|\right).$$
(29)

4.2.5 Constraints of the HFSP-B-CP model

$${C}_{{\rm max}}=\underset{j\in J}{\text{max}}\left\{{\textit{endOf}}\left({X}_{j,\left|S\right|}\right)\right\}$$
(30)
$${\textit{alternative}}\left({X}_{j,s},\left\{{Y}_{j,s,m}|m\in M:{E}_{j,s,m}=1\right\}\right),\quad \forall j\in J,\ s\in S$$
(31)
$${\textit{endBeforeStart}}\left({X}_{j,s},{X}_{j,s+1}\right),\quad \forall j\in J,\ s\in 1\ldots S:s\ne \left|S\right|$$
(32)
$${\textit{noOverlap}}\left(\text{Stg}_{s,m}\right)\quad \forall s\in S,\ m\in M:{E}_{j,s,m}=1$$
(33)
$$\begin{aligned}&\sum_{m\in M:{E}_{j,s,m}=1}\textit{startOfNext}\left({\text{Stg}}_{s,m},{Y}_{j,s,m},{\text{Big}}\,M,0\right)\\ &\quad \ge \sum_{m\in M:{E}_{j,s+1,m}=1}{\textit{startOf}}\left({Y}_{j,s+1,m},0\right), \quad \forall j\in J,\ s\in 1\ldots S:s\ne \left|S\right|\end{aligned}$$
(34)
$${\textit{Cumulative}}\left({X}_{j,s}|j\in J,s\in S,1,\left|{M}_{s}\right|\right).$$
(35)

4.2.6 Constraints of the HFSP-SDST-CP model

$${C}_{{\rm max}}=\underset{j\in J}{\text{max}}\left\{{\textit{endOf}}\left({X}_{j,\left|S\right|}\right)\right\}$$
(36)
$${\textit{alternative}}\left({X}_{j,s},\left\{{Y}_{j,s,m}|m\in M:{E}_{j,s,m}=1\right\}\right), \quad\forall j\in J,\ s\in S$$
(37)
$${\textit{endBeforeStart}}\left({X}_{j,s},{X}_{j,s+1}\right), \quad\forall j\in J,\ s\in 1\ldots S:s\ne \left|S\right|$$
(38)
$${\textit{noOverlap}}\left(\text{Stg}_{s,m},\text{St}_{s,m,j,j^{\prime}}\right)\quad \forall s\in S,\ m\in M:{E}_{j,s,m}=1$$
(39)
$${\textit{Cumulative}}\left({X}_{j,s}|j\in J,s\in S,1,\left|{M}_{s}\right|\right).$$
(40)

4.2.7 Constraints of the HFSP-SDST-NW-CP model

$${C}_{{\rm max}}=\underset{j\in J}{\text{max}}\left\{{\textit{endOf}}\left({X}_{j,\left|S\right|}\right)\right\}$$
(41)
$${\textit{alternative}}\left({X}_{j,s},\left\{{Y}_{j,s,m}|m\in M:{E}_{j,s,m}=1\right\}\right),\quad \forall j\in J,\ s\in S$$
(42)
$${\textit{endAtStart}}\left({X}_{j,s},{X}_{j,s+1}\right), \quad\forall j\in J,\ s\in 1\ldots S:s\ne \left|S\right|$$
(43)
$${\textit{noOverlap}}\left({\text{Stg}}_{s,m},{\text{St}}_{s,m,j,j^{\prime}}\right)\quad \forall s\in S,\ m\in M:{E}_{j,s,m}=1$$
(44)
$${\textit{Cumulative}}\left({X}_{j,s}|j\in J,s\in S,1,\left|{M}_{s}\right|\right).$$
(45)

4.2.8 Constraints of the HFSP-SDST-B-CP model

$${C}_{{\rm max}}=\underset{j\in J}{\text{max}}\left\{{\textit{endOf}}\left({X}_{j,\left|S\right|}\right)\right\}$$
(46)
$${\textit{alternative}}\left({X}_{j,s},\left\{{Y}_{j,s,m}|m\in M:{E}_{j,s,m}=1\right\}\right), \quad\forall j\in J,\ s\in S$$
(47)
$${\textit{endBeforeStart}}\left({X}_{j,s},{X}_{j,s+1}\right),\quad \forall j\in J,\ s\in 1\ldots S:s\ne \left|S\right|$$
(48)
$${\textit{noOverlap}}\left({\text{Stg}}_{s,m},{\text{St}}_{s,m,j,j^{\prime}}\right)\quad \forall s\in S,\ m\in M:{E}_{j,s,m}=1$$
(49)
$$\begin{aligned}&\sum_{m\in M:{E}_{j,s,m}=1}\textit{startOfNext}\left({\text{Stg}}_{s,m},{Y}_{j,s,m},{\text{Big}}\,M,0\right)\\ &\quad\ge \sum_{m\in M:{E}_{j,s+1,m}=1}{\textit{startOf}}\left({Y}_{j,s+1,m},0\right),\quad \forall j\in J,\ s\in 1\ldots S:s\ne \left|S\right|\end{aligned}$$
(50)
$${\textit{Cumulative}}\left({X}_{j,s}|j\in J,s\in S,1,\left|{M}_{s}\right|\right).$$
(51)

The objective function (1) minimizes the \({C}_{{\rm max}}\). Constraints (20), (25), (30), (36), (41), and (46) calculate \({C}_{{\rm max}}\) using the endOf function to obtain the ending time of an interval variable. The maximum of all ends of job intervals presents the \({C}_{{\rm max}}\). In the proposed CP models, \({C}_{{\rm max}}\) is identified as a decision expression in terms of the interval decision variables \({X}_{j,s}\). This expression reduces the number of variables and constraints, improves CP engine solution time, and reduces memory consumption (Yunusoglu and Topaloglu Yildiz 2021). Constraints (21), (26), (31), (37), (42), and (47) ensure that each job at each stage is assigned to precisely one eligible machine. Thanks to this constraint, the relationship between decision variables \({X}_{j,s}\) and \({Y}_{j,s,m}\) is established. In Constraints (22), (32), (38), and (48), the endBeforeStart function ensures that a job at a stage, \({X}_{j,s+1}\), cannot start before its preceding operation, \({X}_{j,s}\), at the previous stage, is completed. Since the stages must follow each other in the HFSP, this relationship is established between the \({X}_{j,s}\) and \({X}_{j,s+1}\) variables by these constraints. Constraints (23), (28), and (33) prevent the interval sequence variables \({\text{Stg}}_{s,m}\) assigned to a machine at a stage from overlapping. Constraints (24), (29), (35), (40), (45), and (51) are redundant constraints restricting that the total usage of machines cannot exceed the total number of available machines at each stage, \(\left|{M}_{s}\right|\). Once a machine is used, the number of machines is increased by one via the pulse function. Constraints (27) and (43) are the no-wait constraints, which provide that the job interval of any given job j at stage s will end at the starting time of the same job j at the next stage s + 1. For this purpose, the endAtStart function is used, guaranteeing that a job must start immediately after the preceding job is completed.

Constraints (34) and (50) provide the blocking structure. In the first part of the constraints, the startOfNext function is used. This function gives the start time of the optional interval variable that comes after the optional interval variable in the given interval sequence variable. When an optional interval variable is present and is the last of the given interval sequence variable, it returns the big M value. When the optional interval variable is absent, it returns 0. In the second part of the constraints, the startOf function is used. The startOf (a, b) function returns the start time of interval variable a. If the interval variable is absent, the function returns the b value. To ensure the constraint is valid for an optional interval variable \({Y}_{j,s,m}\) that is absent, and the b value is set equal to 0. Therefore, Constraints (34) and (50) guarantee that the start time of the optional interval variable \({Y}_{j,s,m}\) that comes after the optional interval variable in the sequence is greater than or equal to the start time of the optional interval variable \({Y}_{j,s+1,m}\). Constraints (39), (44), and (49) assure a feasible sequence of non-overlapping interval variables \({Y}_{j,s,m}\) on machine m at stage s and embed setup times, \({\text{St}}_{s,m,j,j^{\prime}}\), between each consecutive time interval pair.

5 Computational study

All MILP and CP models are coded in the CPLEX Optimization Studio 12.10.0 environment, and OPL codes are given at (http://dx.doi.org/10.17632/n4g8cfjg87.1). The CPLEX and CP Optimizer solvers are used for their solutions, respectively. The models are run on a PC with an Intel Core i5-7200U 2.50 GHz processor and 8.00 GB RAM for up to 600 s for all problem instances.

Given that CP is an exact solution method, there are only a few parameters to set. In our preliminary studies, we tried many tree search strategies and numerous variable and value ordering strategies and their combinations. However, for each problem type and instance size, these strategies did not improve our solutions. We also tried changing parameters such as restart fail limit in conducting the tree search, but they also did not give an advantage to the performance of the models. Therefore, we decided to proceed with the default settings of the CP optimizer; Search type is “Auto,” Restart fail limit is “100”, Restart growth factor is “1.15,” and there are no explicitly defined variable and value ordering strategies.

5.1 Experimental design

Our experiment consists of two phases. In the first phase, we used instances from the literature. We compare our results with 12 benchmark cases presented by Meng et al. (2020a) and instances from Cao et al.’s (2020) study, including two benchmarks and two real case studies. However, the comparison between their enhanced gravitational search (IGS) algorithm and the developed CP models for other variants of the HFSP has not been conducted in the first phase, as their algorithm has only been applied to solve the basic form of the HFSP problem.

The size of the problems used in the first phase is given in a coding scheme; the first digit specifies the number of jobs to be scheduled, and the following digits indicate the number of machines at each stage. For example, “6_3_3_3” represents an instance with six jobs, three stages, and three machines per stage. These instances can be considered small-sized instances. The first 12 benchmark instances taken from Meng et al.’s (2020a) study are given in the first part of Table 1, and they include six, nine, and twelve jobs with two, three, and four stages, respectively. In the second part of Table 1, Cao et al.’s (2020) instances are given with 12 and 50 jobs.

Table 1 Comparison of CP and MILP models for the HFSP problem according to benchmark instances
Full size table

Although the benchmark instances allow comparison with other previous studies, diversity and the size of the problems are insufficient. For this reason, new problem instances were produced to analyze the performance of the developed models in a more detailed manner. The second phase includes newly generated test problems to analyze the developed models in more detail and question their performance for large problems. For comparison, the best-performing Model 2.1 among the MILP models proposed by Meng et al. (2020a) is used and given for all available extensions in Appendix.

The newly generated dataset contains 90 instances; the instances are divided into 20, 30, and 40-job groups. Ten instances were provided for each group with two, three, and four stages. At each stage, the number of machines is (2_2) for two-, (2_2_3) for three- and (3_2_2_3) for four stage instances, respectively, and the processing times are generated from a uniform distribution in the range (1,99). The probability that the machine is eligible for a job is 0.25. The generated problem instances are given at http://dx.doi.org/10.17632/n4g8cfjg87.1.

The same coding system used for the benchmark instances is employed. Setup times are generated from uniform distributions within ranges (1,50) and (1,99) for instances specified with letters A and B, respectively. The models are again run for 600 s for each instance, and the results are analyzed accordingly. As the number of instances is high and the resulting tables are large, the summary tables of the results will be provided here. The detailed outcomes of all instances are presented at http://dx.doi.org/10.17632/n4g8cfjg87.1.

The first column of the summary table shows the job number of the instance group, the total number of machines, and the number of stages, respectively. The results of the CP model include the number of optimal solutions achieved, the number of feasible solutions, the average objective value, the average of the initial times the optimum/best solution is found, the average total solution time, and finally, the average optimality gap for the instance group. The results of the MILP contain the same information as the CP model except for the First Time information. The average values for the j-number job instances are given at the end of each instance group. Moreover, the overall average and total values are summarized at the end of each table. The findings are described in the following sections.

5.2 Experimental results for the benchmark instances

Tables 1 and 2 present the results achieved for the HFSP problem, relying on the benchmark instances mentioned above. The first two columns in the tables have the name and characteristics of the instance under consideration. The Lower Bound column contains the lower bound information obtained from the solvers, while the Objective Value column contains the best results obtained within the specified time limit. The #Cons and #Var columns contain the number of constraints and variables in the models. The Solve Time column includes two different solution times for the CP model: the first indicates the first time reaching the best or optimum solution, whereas the second shows the total solution time. Finally, the optimality gap values of the models are presented in the Gap% column. The gap values are obtained by calculating the percentage of deviation of the model result from the highest lower bound value obtained from any model. The formula used for the calculation is given in Eq. (52).

Table 2 Comparison of the CP model and IGS algorithm for the HFSP problem according to Cao et al.’s (2020) benchmark instances
Full size table
$$\text{Gap} \left(\%\right)=\frac{\text{Objective Value}-\text{max}\left(\text{Lower Bound}\right)}{\text{max}\left(\text{Lower Bound}\right)}*100.$$
(52)

Table 1 compares the CP model results against the best results from Meng et al.’s (2020a) study. In Table 2, the CP model results for the Cao et al. (2020) instances are also compared with the results of the IGS algorithm proposed in their study. The numbers in bold indicate the optimal objective values in the tables.

As shown in Table 1, the CP model finds optimal solutions for 13 of 16 problems, whereas the MILP model confirms the optimality of only seven problems. For the first 12 problems, the models found the same objective values. The MILP model found three worse objective values for the other three problems and did not find a feasible solution for the RealCase2 instance. The CP model has found solutions much faster than the MILP model. For all instances provided by Meng et al. (2020a), the best or optimal solution is recorded within one second or less. The CP model has much fewer constraints and variables than the MILP model.

As illustrated in Table 2, both the CP model and the IGS algorithm reached the optimal solutions for BenCase1 and RealCase1 problems. The same solutions are obtained with both approaches for the BenCase2 problem; however, optimality could not be confirmed. While similar results are obtained for the instances with 12 jobs, the CP model reaches a better solution than the IGS algorithm within the specified period for the RealCase2 instance with 50 jobs. CP demonstrates its superiority over the IGS algorithm for this large-size problem. The solutions times of the models are comparable to each other. However, note that the minimum solution value among the different runs of the IGS algorithm is selected. The solution time for the IGS algorithm is much more prolonged than the CP model due to these runs.

The comparative analysis of the models for the solution of the HFSP-NW is given in Table 3. Both models find feasible/optimal solutions to all 16 problems. The CP model found confirmed optimum solutions for 15 instances, except for the RealCase2 problem, whereas the MILP model reached an optimal objective value for 11 instances, and for four of these, the optimality has not been confirmed within the runtime. The CP model found three optimal solutions for Cao et al.’s (2020) instances, except for the RealCase2 instance, whereas the MILP found worse solutions for these solutions. While the CP model has a 6.33% gap for the RealCase2 instance, the MILP model has a 167.171% gap. The solutions can be reached much faster with the CP model.

Table 3 Comparison of CP and MILP models for the HFSP-NW problem according to benchmark instances
Full size table

Table 4 provides a comparative analysis of the models utilized for solving the HFSP-B. While the CP model achieved optimal results for 15 in 16 instances, this number remains at 11 with the MILP model. Besides, the optimality was not confirmed within the specified time for four instances. For only the RealCase2 problem, the CP model found a feasible solution with only a gap of 6.41%, whereas the MILP model did not even obtain a feasible solution.

Table 4 Comparison of CP and MILP models for the HFSP-B problem according to benchmark instances
Full size table

The comparative analysis of the models for the solution of the HFSP-SDST can be found in Table 5. While the CP model achieved optimal results for 12 in 16 instances, this number remained at 10 with the MILP model. Besides, the optimality was not confirmed within the specified computation time for four instances. The CP model found better solutions for Cao et al.’s (2020) instances than the MILP model; the optimality of the two instances was also confirmed. The MILP model failed to achieve a feasible solution for the RealCase2 problem.

Table 5 Comparison of CP and MILP models for the HFSP-SDST problem according to benchmark instances
Full size table

The results obtained for the HFSP-SDST-NW and HFSP-SDST-B are presented in Tables 6 and 7. The CP model for the HFSP-SDST-NW achieved a feasible solution in all instances and guaranteed an optimum solution in 12 of 16 instances. The MILP model obtained a feasible solution in 15 instances, found the optimum solution value for 10, and confirmed the optimality in six. The CP model found better solutions for Cao et al.’s (2020) instances and two optimally confirmed solutions. For the RealCase2 problem, a feasible solution was not even attained by the MILP model. The CP model found solutions almost three times faster than the MILP model regarding solution time.

Table 6 Comparison of CP and MILP models for the HFSP-SDST-NW according to benchmark instances
Full size table
Table 7 Comparison of CP and MILP models for the HFSP-SDST-B according to benchmark instances
Full size table

For the HFSP-SDST-B, the CP model obtained a feasible solution in all instances except for the RealCase2 problem. It guaranteed an optimum solution in 12 of 15 instances. The MILP model obtained a feasible solution in 15 instances, found the optimum solution value for 10, and only confirmed the optimality in three.

For the 16 benchmark instances discussed in this section, the CP model provides better results than the MILP model in all problem types regarding the number of optimal solutions found, objective value, solution time, and optimality gap. The optimality gap increases slightly with the insertion of sequence-dependent setup times in the other problem types with both the CP and MILP models; however, the CP model outperformed the MILP models in all these problem types. The only problem is that the CP model did not find a feasible solution is the RealCase2 for the HFSP-SDST-B. Table 8 compares the MILP and CP models for the number of test problems verified as optimal in the benchmark data sets for each problem type. Accordingly, the superiority of the CP model performance can be observed easily.

Table 8 Comparison of MILP and CP models for the number of instances verified as optimal
Full size table

Additionally, we found that the CP model has outperformed the recently proposed IGS heuristic algorithm for the benchmark instances in Cao et al. (2020). The first-time solution information specific to the CP model shows how fast the model reaches the best/optimum solution. Thus, the CP model can be used in cases where the optimal solution is not guaranteed, but good solutions are sought quickly.

5.3 Experimental results for generated instances

In this section, we present our results for our generated instances. Here the summary tables are presented and interpreted separately for all problem types. First, Table 9 summarizes the results obtained from solving the HFSP problem. Accordingly, the CP model found the optimum solution for all instances, whereas the MILP model only reached the optimum solution for one 20-job instance out of 90 problems. The difference between the CP and MILP models’ solutions increases as the number of jobs and stages in each instance group increases. The CP model finds the optimum solution within 14.151 s compared to 594.122 s for the MILP model.

Table 9 Summary table for the HFSP solutions for newly generated instances
Full size table

Table 10 summarizes the computational results for the HFSP-NW problem. While the CP model obtained 26 optimum solutions, the MILP model found only two in 90 instances. It is noticeable that the CP model outperforms the MILP model in terms of the optimality gap values (5.77% compared to 21.634%) and solution times. The CP and MILP model results for this problem are worse than those obtained for the HFSP.

Table 10 Summary table for the HFSP-NW solutions for newly generated instances
Full size table

Table 11 provides a summary of the computational results for the HFSP-B problem. The CP model found 13 optimal solutions, whereas the MILP model found only one in 90 instances. The CP Model has halved the number of optimum solutions obtained compared to the HFSP-NW. Nevertheless, it performs better regarding the optimality gap (17.319% compared to 29.486%) and solution time concerning the MILP model. In this problem, the difference between the mean objective values of the CP and MILP models increases for all instances. The difficulty of the HFSP-B problem can also be observed from the solution times. The first time and the total solution time are higher than the CP model's other problems. A similar effect can be seen in the MILP model, albeit lesser.

Table 11 Summary table for the HFSP-B solutions for newly generated instances
Full size table

Table 12 compares the results obtained with the CP and MILP models. Considering all the criteria, the CP model provides better results than the MILP model. While the MILP model could not provide an optimal solution, the CP model found nine optimal solutions. The difference between the optimality gap values of the CP and MILP models has widened more than the HFSP-NW.

Table 12 Summary table for the HFSP-SDST solutions for newly generated instances
Full size table

Tables 13 and 14 present the results for the HFSP-SDST-NW and HFSP-SDST-B, respectively. The models have the most difficulty solving these two problems among all problems. The CP model can obtain only one optimum solution, while the MILP could not find any. The difference between the optimality gap values of the CP and MILP models has widened more than the HFSP-B. The solution time and optimality gap values are higher than those obtained in all other problems for the CP and MILP models.

Table 13 Summary table for the HFSP-SDST-NW solutions for newly generated instances
Full size table
Table 14 Summary table for the HFSP-SDST-B solutions for newly generated instances
Full size table

In summary, for all instances discussed, the CP model performs better than the MILP model in terms of optimality, objective value, solution time, and optimality gap. However, as the number of jobs to be scheduled increases, the solution time and optimality gap values increase. The models have the most difficulty solving the HFSP-SDST-NW and HFSP-SDST-B, and the best solutions are found for the HFSP, which is the simplest version of the problem.

The difference between the CP and MILP model solutions increases as the problem size grows. The variation of the optimality gap values for both models according to the problem size and type is shown in Fig. 3. The red and blue columns show the MILP and CP optimality gap values. The superiority of the CP models over the MILP models can be noted easily. The difference between the optimality gaps of the CP and MILP models increases as the number of jobs increases for the same configuration and the number of stages increases for the same job number. This figure also gives an idea of the difficulty levels of the problem types. The HFSP-SDST-NW and HFSP-SDST-B graphs (Fig. 3e and f) show that higher gap values have emerged in almost all problem dimensions compared to other problem types. This situation reveals that both models have more difficulties solving these problem types.

Fig. 3
figure 3

The variation of the optimality gap value of MILP and CP models

Full size image

One must notice that as the problem size increases, CP can reach the solution quickly, looking at the overall results. However, it cannot guarantee the optimality of the solution. This occurs in almost all problem instances for the HFSP-SDST-NW and HFSP-SDST-B. CP is ineffective in ensuring optimality since it cannot use the powers of relaxation in the objective function, generating inefficient bounds that make it difficult to guarantee optimality (Lustig and Puget 2001). On the other hand, CP is quite effective at generating feasible solutions. Yet, as mentioned in Sect. 4.1, CP is an exact solution method, so in contrast to heuristics, it examines the entire solution space restricted by constraints, with increased solution time for big instances.

In summary, CP is an excellent alternative approach for solving the HFSP as it solves all instances in seconds. It is also useful for the extensions of the problem. Modern production systems need quick and reliable solutions for problems like the HFSP. Volatility in demand and other parameters makes it necessary to produce schedules continuously. Managers should make quick decisions in these situations, which should be close to the optimum. While the related literature generally focuses on heuristics and metaheuristics to help managers, our results suggest that CP is also worth considering.

6 Conclusion

This paper considered the unrelated HFSP and its extended versions; HFSP‐NW, HFSP‐B, HFSP-SDST, HFSP-SDST-NW, and HFSP-SDST-B. The problem studied, and its extensions have very active fields of research, and the results of this research will lead to the building of more efficient solution approaches in these fields. We developed new CP models to solve these problems to minimize makespan and presented new MILP models for the HFSP-SDST-B and HFSP-SDST-NW. The performance of the proposed CP models was tested with benchmark and randomly generated instances against the MILP counterparts. While the MILP models performed well in small instances, the CP models outperformed the MILP models for all problem types in medium and large instances in addition to small instances. The effectiveness and efficiency of the CP approach for the HFSP and its variants were verified by extensive computational analysis, as summarized below.

Initially, the CP models outperformed the MILP models recently developed by Meng et al.’s (2020a) in all benchmark instances ranging from four jobs and two stages to 12 jobs and four stages in size, concerning solution time, objective value, and optimality gap. Moreover, with the CP models, the optimality of 20 instances, whose optimality has not yet been confirmed, has been confirmed across all HFSP variants. CP cannot always ensure optimality as a solution approach, but its effectiveness is significant in large instances.

Secondly, the performance of CP was also measured against the IGS heuristic algorithm developed for the HFSP for another benchmark instance set by Cao et al. (2020). The smallest instance contains 12 jobs and 3 stages; the largest contains 50 jobs and 6 stages. The comparisons were made over the MILP model results for the other HFSP variants. The results for these instances also show that the CP models are superior to the MILP models and the IGS algorithm in solution time, objective value, and optimality gap.

Lastly, the CP models were also tested across all HFSP variants in newly generated 90 larger-size problem instances that contain 20, 30, and 40 jobs with 2, 3, and 4 stages. Likewise, the CP models gave better results for all problem types and sizes than the MILP models.

As a result, this paper shows that compared to existing MILP models in the literature, our CP models improve the potential of exact approaches to address problems on an industrial scale in shorter time frames. Moreover, the obtained results for newly generated instances will aid other researchers in comparing the results of their solution approaches.

Alternative CP models can be developed for other extensions of the HFSP variants in future studies, including resource constraints, batching machines, preemption, or stage skipping. Additionally, matheuristic solution approaches using CP can be devised for more effective solutions.