Solving multi-scenario hybrid flow shop scheduling problem based on an improved probe machine model

Abstract

The hybrid flow-shop scheduling problem is widely present and applied in industries such as production, manufacturing, transportation, and aerospace. In recent years, due to the advantages of nonlinear access and fully parallel processing, the probe machine has shown powerful computing capabilities and promising applications in solving various combinatorial optimization problems. This work firstly proposes an Improved Probe Machine with Multi-Level Probe Operations (IPMMPO) and ingeniously designs general data libraries and probe libraries tailored for multi-scenario HFS problems, including HFS with identical parallel machines and HFS with unrelated parallel machines, no-wait scenario, and standard scenario. Secondly, based on the data libraries of the IPMMPO, two tuple sets suitable for constraint programming modeling are further designed as data preprocessing. Next, a CP model (IPMMPO-CP) applicable to multi-scenario HFS problems is proposed. Finally, based on a large number of instances and real cases, IPMMPO-CP is compared with 9 representative algorithms and 2 latest CP models. The results demonstrate that the proposed IPMMPO-CP outperforms the compared algorithms and models.

1 Introduction

Nowadays, the hybrid flow-shop scheduling (HFS) problem, which is widely existing and applied in the steel [1,2], textile [3], glass manufacturing [4] and plastic manufacturing [5] industries, can be traced back to the flow-shop scheduling (FS) problem proposed by [6]. The original FS problem is to consider only one machine at each processing stage of the job. In other words, the number of processing stages in the FS problem is strictly equal to the total number of machines. Different jobs have the same operation sequence, which makes the job sequence the only problem that FS needs to solve. This production method is obviously difficult to adapt to the needs of today’s large-scale flexible process and parallel manufacturing. In contrast, the HFS problem considers at least two parallel machines to choose from in at least one of the processing stages. This forces HFS to solve machine allocation and job sequencing problems simultaneously at each processing stage [7]. Compared with FS, HFS can better relieve bottleneck constraints and improve the production capacity and efficiency of enterprises. Since the HFS problem is flexible with the machines available over each processing stage, it is also called a flexible flow-shop [8] or multiprocessor flow-shop [9].

According to the type of parallel machine in the processing stage, it can be roughly divided into two categories: HFS with identical parallel machines (HFS-IPM) and HFS with unrelated parallel machines (HFS-UPM) [10]. The first means that in each stage, the processing time of the same job on all available parallel machines is equal, i.e., the processing time of each stage depends only on the job itself. The second means that in each stage, the processing time of the same job on any two parallel machines is independent of each other, that is, the processing time of each stage depends on both the job and the machine. The HFS problem involving only two stages has been shown to be NP (non-deterministic polynomial time) -hard [11]. Approaches to solving HFS problems are roughly divided into two categories: exact methods and approximate methods.

Exact methods mainly include mixed integer programming (MIP), Lagrangi-an relaxation (LR) method, decomposition method and branch and bound (B&B) method, constraint programming (CP), etc. [12] proposed a B&B algorithm based on energetic inference and global operations to solve the HFS problem. [13] used the B&B algorithm to solve the two-stage HFS problem aiming at the shortest total delay time. [14] developed an LR algorithm incorporating a speed-up strategy for solving the HFS problem with limited buffer capacity. More researchers tend to develop MIP models and solve them with the help of the commercial solver. [15] developed four different MIP models and compared their performance. [16] proposed a MIP model for the reentrant HFS problem and solved it using CPLEX. [17] proposed a MIP model to solve the complex HFS problem arising from a bio-process industry, which took into account constraints such as limited waiting time between processing stages. Represented by MIP, exact algorithms can obtain optimal solutions for small-scale problems, but their solving time also increases exponentially with problem size. Therefore, it is usually only suitable for solving small-scale problems. Based on the viewpoints of existing research [15,16,18], even a reasonably good MIP model can only ensure that the size of the HFS problem where it is effectively solved is within 15 jobs and 5 stages.

Approximation methods can be further subdivided into heuristics and meta-heuristics, among which heuristics are mainly based on dispatching rules and local search. [19] adopted the shortest processing time and first available machine rules to solve the scheduling problem of computer systems. There are also the well-known Nawaz-Enscore-Ham (NEH) [20] and longest processing time [5]. [21] used a modified NEH to generate high-quality initial populations for the discrete artificial bee colony (DABC) algorithm. In addition, there are local search heuristics that aim to tune critical operations on the critical path, such as variable neighbourhood search [22], iterated local search [23], iterated greedy (IG) [9], etc. For the distributed assembly shop hybrid flow shop (HFS) problem with dual resource constraints, some scholars have proposed a mixed-integer linear programming (MILP) model and a knowledge-based iterative greedy (KBIG) algorithm, aiming to minimize the total tardiness [24]. For the HFS problem with consistent sublots and dual objectives of minimizing the makespan and the total number of sublots, Zhang et al. [25] formulated a MIP model and proposed an automatic algorithm design approach to solve it. Bio-inspired meta-heuristics incorporating random diversity search have become a hotspot for efficiently solving scheduling problems in recent years. The more mature swarm intelligence meta-heuristics and their improved versions include particle swarm optimization (PSO) algorithms [4], artificial bee colony algorithms [1,21,26], simulated annealing (SA) [27,28], genetic algorithms (GA) [29], tabu search (TS) [7,30] and ant colony optimization (ACO) [31], etc. However, a single meta-heuristic has more or less defects such as premature or local convergence. Therefore, more and more researches tend to organically combine different intelligent algorithms to make up for their own shortcomings, thereby improving search efficiency. [32] fused variable-depth search with SA for the multi-stage HFS problem. [33] fused GA and ACO to solve the HFS problem with time windows. [34] designed a hybrid algorithm combining TS local search and PSO to solve the batch HFS problem with setup times. [35] established a population communication mechanism between adaptive GA and discretized PSO to resist local convergence and improve search diversity. The advantage of these approximation methods is that they can construct a large number of effective solutions in a relatively short time, but their disadvantages are also obvious, that is, it is difficult to guarantee the optimality of the solutions [36]. [37] proposed an improved discrete particle swarm optimization algorithm to solve the permutation flow-shop scheduling problem. [38] proposed a wireless network GA to address a multi-objective FS system.

The probe machine (PM), proposed by [39], is the most advanced DNA computing model so far. This model breaks the two mechanisms that limit the computing power of Turing machine (TM), that is, the linear data access mode and the serial processing mode, and replaces it with the non-linear data access and the completely parallel processing mode. The linear data access mode of TM is 1D, while the nonlinear data access mode of PM is 3D [39], which makes PM show strong computing power and application prospects in dealing with problems related to graph theory.

[40,41] not only proved that TM is a special case of PM, but also explored the use of PM theory and DNA self-assembly technology to solve the graph vertex coloring problem. [42] constructed a molecular probe device based on DNA molecular computing, which has application prospects in the fields of biological imaging and disease diagnosis. Tian et al [43] solves the urban light rail route planning problem based on PM. The team of professor Yin studied the application of PM to the maximum clique problem [44], the satisfiability problem [45], and the Chinese postman problem [46]. [47,48] reported the application research of PM in the field of model checking. [49] reported the computational power of connective PM on the shortest path problem. Professor Ma’s team explored the application of PM to problems such as the traveling salesman problem [50,51] and vehicle routing with capacity constraints [52]. The above researches show that the computing performance of PM in terms of high flexibility and low complexity is far better than that of TM. However, the original PM only supports single-level probe operation, which restricts the computing power of PM in dealing with complex graph theory problems. In addition, as of now, no research on the application of PM in the field of shop scheduling has been found.

Since 2016, with the development of software and hardware technology, the CP modeling method has received more and more attention as an exact method to solve various shop scheduling problems. IBM CP Optimizer is commonly used in academia and industry to implement efficient CP modeling for scheduling problems. IBM CP Optimizer is a software library that efficiently models and solves combinatorial optimization problems [67]. It uses efficient constraint propagation algorithm and domain reduction technology as its search and reasoning engine, and supports multi-core, multi-thread parallel optimization technology. CP methods have a proprietary optimization programming language (OPL) that combines specialized variables, constraints, and keywords to efficiently express complex spatiotemporal constraints to build compact scheduling models. CP methods have been proven to be successfully applied in various scheduling fields, including but not limited to flexible job shop scheduling problem with parallel batch machines (FJSP-PBM) [57], parallel machine scheduling problem with sequence dependent setup times (SDST) [58,59], team orienteering problem [60], job shop scheduling problem (JSSP) based on DNA algorithm [61], parallel machine flexible resource scheduling (PMFRS) [62], robot scheduling in retirement home environment [63], and distributed FJSP [64]. Focusing on the characteristics of the hybrid flexible flow shop such as setup time and due dates, [56] proposed a CP approach with the objective of minimizing the total tardiness. Considering the total weighted tardiness objective of the job shop scheduling problem, [55] constructed three models using the MIP and CP methods. The experimental results show that the CP method involves a smaller number of variables and is more efficient to solve. [54] proposed a new CP model for large-sized scheduling problems in multi-product, multi-stage batch plants and verified the effectiveness of the model. [53] transformed the actual online print shop scheduling problem into FJSP with sequential flexibility and proposed the MIP and CP models with the objective of minimizing makespan. The CP methods have been proved to be effective in solving medium-scale and even large-scale scheduling problems. Not only that, CP methods can even prove that the best feasible solution found is optimal when the search automatically terminates [38,43].

In recent years, CP methods have also made some new progress in solving HFS problems. [70] developed a bi-objective CP model with makespan and total energy consumption as optimization criteria by adjusting machines to different speed levels. But this study only addressed the HFS-IPM problem. [73] established MIP and CP models for different types of scheduling problems and conducted computational evaluations. The HFS problem involved also only discussed the HFS-IPM type, and the CP model of this problem does not use “alternative” constraints. For the HFS-UPM type, [71] proposed a CP model for the no-wait HFS problem, which does not use “cumulFunction” constraints. [72] developed corresponding CP models for HFS-UPM and its several extensions, making outstanding contributions to exploring the application of CP in HFS problems. However, the excessive number of constraints in the developed CP model means that higher computational costs may be required when solving problem instances [71].

Based on the above background, this work first proposes an improved probe machine with multi-level probe operations (IPMMPO). Then the HFS problem is transformed into a graph problem by disjunctive graph, and the data library and probe library are cleverly designed to solve it. Second, based on the two data libraries designed in IPMMPO, this work constructs two sets of tuples dedicated to CP modeling. Based on the above two sets of tuples, a unified CP model (IPMMPO-CP) is established for HFS-IPM and HFS-UPM problems. The contributions of this work are summarized as below.

1. This work explores the application research of the probe machine in the field of scheduling for the first time. For two types of HFS problems (HFS-IPM and HFS-UPM), an improved probe machine model (IPMMPO) that allows multi-level probe operations is designed. The complexity analysis of IPMMPO model is given. a constraint programming model (IPMMPO-CP) is further constructed based on the data libraries in IPMMPO.

2. Based on a large number of instances and real cases, Sect 5 first investigates the performance comparison between IPMMPO-CP and nine representative heuristic algorithms under the HFS-IPM scenario. Sect 6 further explores the application comparison between IPMMPO-CP and two latest CP models under both the standard and no-wait scenarios of the HFS-UPM type. The computational results demonstrate that the proposed IPMMPO-CP outperforms the compared algorithms and models.

The framework for the remainder of this work is organized as follows. Sect 2 briefly outlines the preparatory knowledge involved in this work, including the description of the HFS problem and the introduction of the probe machine model. Sect 3 introduces the proposed IPMMPO theoretical model in detail, including its data libraries, probe libraries, model structure and complexity analysis, etc. CP modeling based on IPMMPO can be found in Sect 4. Comparative experiments based on a large number of instances, and application comparisons in real-world cases are given in Sect 5 and Sect 6, respectively. Sect 7 summarizes this work.

2 Preliminary knowledge

2.1 Problem description

The HFS problem can be described as follows. n jobs need to be processed in s stages, in which each job must be processed on stage 1 first, then on stage 2, and so on, and the last step is processed on stage s. It is required that in s stages, at least one stage has more than one machine available. As shown in Fig 1, () represents one available machine in stage k, where m_k represents the total number of available machines in this stage. As mentioned earlier, according to the type of parallel machines in the processing stage, there are two types of problems, HFS-IPM and HFS-UPM. It can also be found from Fig 1 that when only one machine is available in each stage, the HFS problem reduces to the regular flow-shop scheduling problem. When the number of stages is only one, the HFS problem can be reduced to an ordinary parallel machine scheduling problem.

[Figure omitted. See PDF.]

The processing time of the job on each stage (HFS-IPM) or each machine (HFS-UPM) is given in advance. Any machine can only handle one job at a time, and vice versa. Once machines and jobs are in working state, they are not allowed to be interrupted or preempted. A job can be processed by any machine within a processing stage. The transport time of the job or the setup time of the machine can be considered to be included in the processing time, or can be ignored. The objective of the HFS problem is to minimize the maximum completion time. The mathematical model of the HFS problem is described as follows (Eqs 1–10), with the notations and their corresponding meanings presented in Table 1. Following the rules of [66], the HFS problems studied in this work can be denoted as .

[Figure omitted. See PDF.]

(1)

Subject to:

(2)(3)(4)(5)(6)(7)(8)(9)(10)

Constraints 2, 3 and 6 ensure that each job at every stage has exactly one immediate predecessor and one immediate successor. At the same time, they enforce that each job at every stage is processed by exactly one of the available machines. Constraints 4 and 5 ensure that, on each machine at every stage, exactly one job is processed first and exactly one job is processed last, respectively. Constraint 7 represents the time constraint between two jobs with a direct predecessor-successor relationship on the same machine at the same stage. Constraint 8 imposes the precedence constraint between different processing stages of the same job. Constraint 9 states that the earliest start time for any job is zero, indicating that there is no priority constraint on the initial processing of different jobs.

2.2 Probe machine

Probe machine (PM) is defined as a nine-tuple (see Fig 2)

[Figure omitted. See PDF.]

(11)

The nine components that make up PM represent data library (X), probe library (Y), data controller (), probe controller (), probe operation (τ), computing platform (λ), detector (η), true solution storage (Q) and residue recovery (C). Data library X and probe library Y are the two most important components of PM, and they are also the two most critical designs for PM to solve various problems. The necessary introduction to these two components is given below.

Data library X can be composed of n types of data, namely

(12)

Each type of data x_i is composed of a central data body i and multiple types of data fibers attached to the data body i, namely

(13)

where the number of each data fiber may not be unique. The structural characteristics of data library X well reflect the 3-D nonlinear access mode of PM.

The probe library Y can be composed of multiple probe sub-libraries. Taking Y_it, one of the probe sub-libraries, as an example, it represents all possible probe sets between the two types of data x_i and x_t. Assuming that and are the data fibers of the two data x_i and x_t respectively, then the probe between and is , which can be formally recorded as . Obviously, is composed of complementary chains of and . According to the Watson-Crick principle, these two data fibers can be connected to realize the connection of the two data of x_i and x_t. A test tube in the probe sub-library Y_it is also called a probe pool, which contains and only contains a large number of copies of the probe .

Data fibers and probes can be divided into connection and transmission according to their functional characteristics. Connective probes and connective data fibers can only achieve spatial connections between data bodies, without considering information transfer. Transitive probes and transitive data fibers can not only realize spatial connections between data bodies, but also realize the information transfer between them. In addition, a series of probe operations performed on the computing platform λ support large-scale parallel computing. In summary, due to the advantages of nonlinear data access and complete parallel computing, the probe machine has shown strong computing power and application prospects.

3 The proposed improved probe machine (IPMMPO)

Although PM has advantages that TM cannot match, there is a fact that when dealing with some complex graph theory problems, only one probe operation may not be able to effectively solve them. In this section, an improved probe machine with multi-level probe operations (IPMMPO) will be proposed. In addition, HFS problem can be analyzed and solved from the perspective of disjunctive graph. Disjunctive graph is a powerful tool to transform scheduling problems into graph problems [7,77].

A simple instance of the HFS problem is given here to facilitate explanation. The instance data is shown in the Table 2, involving a total of 7 jobs, all of which have to go through three processing stages: Lathe, Planer, and Grinder. Among them, there are three available machines in the Lathe stage, labeled 1, 2, and 3; there are two available machines in the Planer stage, labeled 4, 5; There are three machines available for the Grinder stage, numbered 6, 7, and 8; the total number of machines involved is 8. The rest of the data in the table is the processing time of each job on the corresponding optional machine in each stage. It can be seen from the data in the table that this instance belongs to the unrelated parallel machine (HFS-UPM) problem.

[Figure omitted. See PDF.]

The construction of data library and probe library is the first and most important link in the improved probe machine, and the design of probe library is based on the data library. This section first takes the simple HFS instance shown in Table 2 as an example to build its data library and probe library, and then extends the application to the general situation in the model complexity analysis part.

3.1 Data library construction

The number of jobs in Table 2 is 7, recorded as n = 7, and i represents the job index (); the number of machines is 8, recorded as m = 8, and j represents the machine index (); the number of stages is 3, recorded as s = 3, and k represents the stage index (). Each job must go through three processing stages in turn, then the total number of operations of 7 jobs is sn = 21, and t represents the operation index (). In this work, firstly, a data library X_J about jobs is built with the operation number as the data body. The data library X_J, and data sub-libraries corresponding to the 7 jobs are as follows.

(14)(15)(16)(17)(18)(19)(20)(21)

Taking as an example (see Eq (19)), it corresponds to the three operations of job 5. Among them, represents the third operation of job 5. The subscript 15 represents the operation number corresponding to this operation, which is designed as a data body. The superscripts O_15J, J₅ and S₃ represent the three types of data fibers connected to this data body, respectively. In order to facilitate subsequent probe operations, and then construct aggregations for feasible solutions, the number of different types of data fibers is set as follows. There is only one data fiber of the O_15J type, which is used to realize the machine selection of the operation numbered 15; there are two data fibers of the J₅ type, which are used to realize the connection between the previous and subsequent operations of the same job; there is only one data fiber of type S₃, which is used to mark the processing stage of the operation. Fig 3 shows the six data types contained in (Eq (15)) and (Eq (19)) respectively.

[Figure omitted. See PDF.]

In addition, X_J can also be divided into the following three data sub-libraries according to the number of stages, that is, the type of S_k in the data fiber, and each sub-library contains 7 types of data.

(22)(23)(24)(25)

Next, build another type of data library X_M based on operations and optional machines. Three data sub-libraries corresponding to three processing stages are as follows.

(26)(27)(28)(29)

Taking as an example, it represents the data set of optional machines in the first processing stage, where each row represents a job, and different columns correspond to different optional machines. As can be seen from the data in Table 2, there are 3 machines available in the first stage (Lathe), so has 3 columns. Similarly, there are 2 optional machines in the second stage (Planer), so has 2 columns; there are 3 optional machines in the third stage (Grinder), so has 3 columns. In addition, there is a one-to-one correspondence between the data types in the data library X_M and the data in Table 2, that is, there are 21 types in the first stage; 14 types in the second stage; 21 types in the third stage; a total of 56 types of data.

Specifically, for example, , and in the last row of represent the data of three optional machines in the first stage of job 7. Taking as an example, the subscript 193 representing the data body is divided into two parts: 19 and 3. Number 3 represents optional machine 3 and corresponds to data fiber M₃. The number 19 in front means that the operation sequence of job 7 in the first stage is 19, which is exactly the same as that in . Fig 4 gives a schematic of the data construction for the first and last rows in .

[Figure omitted. See PDF.]

The construction of the data library X_J and X_M has been completed above. The following points need to be highlighted in particular.

1. There are two fibers marked J_i () in X_J, which are used to realize the constraint that the degree of conjunctive arc of any vertex is not larger than 2. Similarly, there are also two fibers labeled M_j () in X_M, which will be used to realize the constraint that the degree of the disjunctive arc of any vertex does not exceed 2. Furthermore, such two fibers have the property of repelling the same kind of probes. In other words, any probe that can be matched with it can only connect to one of the two identical data fibers, and vice versa.

2. The fiber marked as S_k in X_J is only used for data identification, and does not participate in any node connection and data transmission. Apart from this, all other fibers in X_J and X_M adopt transitive fibers and participate in data transfer.

3. Since there is a one-to-one mapping relationship between the data types in X_M and the data in Table 2, each data body can store the unique processing time corresponding to it. In addition, the length of the data fiber marked as M_j in X_M is also proportional to the processing time corresponding to this data.

3.2 Probe library construction

Based on the above-mentioned defined data libraries, in order to further construct the acyclic feasible solution D_S of the disjunctive graph G, it is necessary to construct three types of probe libraries to realize the following three-step probe operations respectively.

1. Firstly, realize the machine selection operation of each operation in the same processing stage.

2. Secondly, realize the connection and transmission of different operations on the same machine in the same stage.

3. Finally, for different processing stages, realize the connection and transmission between the previous and subsequent operations of the same job.

First, the probe library Y_S is constructed to realize the machine selection of each operation in the same stage, and is divided into the following three sub-libraries according to the processing stage.

(30)(31)(32)(33)

In the data libraries X_J and X_M, there are a class of transitive fibers marked as O_tJ and O_tM (), and these two types of fibers will be connected by specific probes in probe library Y_S. Taking as an example, this probe sub-library will be used to implement the operation data sub-library of the first stage to perform machine selection from the corresponding candidate machine data sub-library . The functions of the probe sub-libraries and can be deduced by analogy. Under the action of probe library Y_S, the data in data libraries X_J and X_M will form an aggregation containing two data bodies, referred to as 2-aggregation. Subsequent probe operations can continue to be executed according to any data body or any type of data fiber in the formed 2-aggregation.

Next, the probe library Y_M is constructed to enable the connection of operations on the same machine within the same stage. Similarly to Y_S, it is divided into the following three probe sub-libraries according to the processing stage.

(34)(35)(36)(37)

Take the probe in as an example, where can locate and identify a 2-aggregation A, which contains both the data body 4 representing the operation code and the data fiber M₁. Specifically, this 2-aggregation A is formed by aggregation of data in and data in via probe . The subscript of corresponds to the data body 4 of in A, and the superscript M₁ corresponds to the data fiber M₁ of in A. Similarly, can be used to identify and locate a 2-aggregation B aggregated by and . In summary, the probe will connect the above two 2-aggregations A and B through their data fiber M₁, and further aggregate them into a 4-aggregation. This means that operations numbered 4 and 7 are both processed on machine M₁.

Finally, construct the probe library Y_J to realize the connection between the previous and subsequent operations of the same job at all stages. It is divided into 7 sub-libraries according to different jobs, and the following expression can be written uniformly.

(38)

There are 14 types of probes in probe library Y_J. Take as an example, where connects the operation data and belonging to the same job J₂ but at different stages through its transitive data fiber J₂, so as to realize the sequence constraints between the previous and subsequent operations.

Library design principles:

1. Isomorphism: The construction of data libraries is the first and most important. X_J and X_M strictly mirror the binary structures of the conjunctive graph and disjunctive graph, respectively.

2. Completeness: For any instance of size (n,m,s), , (see Sect 3.4 Theorem 1 for details).

3. Probe-targeted: The construction of probe libraries is completely dependent on data libraries. Each probe library addresses a specific scheduling sub-decision.

3.3 Structure and computational framework of IPMMPO

After the data library and probe library for the HFS problem are constructed, this section will give the structure and computational framework of IPMMPO (see Fig 5). The specific computation steps are as follows.

[Figure omitted. See PDF.]

1. First level probe operation. Through three parallel probe operations, the random selection of machines for each operation in the three stages is realized respectively. Under the action of , the operation data sub-library and the machine data sub-library perform the first-level probe operation, . Specifically, each data in and has a large number of copies, and the number of copies of the data in must be an integer multiple of the number of optional machines in this stage to ensure the randomness of machine selection for operations. Fig 6 gives an example of a 2-aggregation that may occur after and perform the first-level probe operation under the action of , which means that the first stage of job 1 chooses to be processed on machine 1.

2. Second level probe operation. After executing the above probes, all possible 2-aggregation sets formed in each stage are denoted as (). Introduce the probe library Y_M to perform the second-level probe operation. Under the action of , operations in that are processed on the same machine will be chained in random order. Since the number of M_j-type data fibers in is 2, it can ensure that the degree of each operation node in the generated feasible solution is at most 2. According to the characteristics of the data fiber expressed at the end of Sect 3.1, after the second-level probe operation, it is impossible to form a ring similar to “7-13-7", but it is possible to form a ring similar to “7-13-10-7”. The operation sequences generated in the three stages exist in the form of rings, and each ring structure corresponds to a machine.

3. Detect and filter operations. Probes that do not participate in the probe operation are filtered out. Detect the generated multi-aggregation, and filter out the multi-aggregation that contains more than(39)

data bodies, that is, the number of 2-aggregation exceeds(40)

so as to achieve machine load balancing. Here M_k represents the number of available machines in stage k.

4. Cut and mark operations. After the operation of Step 3, the rest are valid ring structures. The cutting operation is carried out at the longest connection point of the data fiber M in the ring structure, and the starting and ending point markings are attached while the original probe is removed. For example, for three-stage multi-aggregation, their start and end points are marked as S₀ and S₁₂, S₂₁ and S₂₃, and S₃₂ and , respectively. Fig 7 shows the schematic diagram of the ring structure “7-13-10-7” after cutting-marking operation. This means that in the first stage, operations numbered 7, 13, and 10 are all on machine M₂ and processed in the order 7-13-10.

5. Third level probe operation. This operation is responsible for connecting the operations of each stage. Consider the following two points: (1) There is no intersection between machines in different stages and they are independent of each other; (2) However, the same job has operational priority constraints between different stages, that is, the successive operations of the same job closely link different stages. Therefore, the probe library Y_J is introduced, the third-level probe operation is performed based on the data fiber J_i (), and a set of conjunctive arcs related to the operation is established, and then the three stages are associated. Apparently, no ring structure was generated after the third-level probe operation.

6. Detect and identify operations. Assume that the length between any two operations t and h () is denoted as L(t,h). Then, the value of the finally generated multi-aggregation is detected by transitive fibers and probes, which is regarded as the feasible solution corresponding to the multi-aggregation. S₀ and here correspond to the virtual start and end points 0 and in the disjunctive graph model, respectively. Finally, the multi-aggregation with the smallest value is filtered into the true solution storage Q, which is the optimal solution of the problem.

[Figure omitted. See PDF.]

[Figure omitted. See PDF.]

Fig 8 shows an optimal solution for this instance. Specifically, the colored disjunctive arcs between operation nodes coded by numbers are realized through Steps 2 to 4 above, while the black conjunctive arcs are realized through Step 5. The nodes in Fig 8 have 7 rows and 3 columns. Each row represents three sequential operations of the same job from left to right. Each column then corresponds to a processing stage. Acyclic structures marked with the same color in each column correspond to processing sequences on the same machine at that stage. Correspondingly, Fig 9 shows the scheduling Gantt chart corresponding to the optimal solution.

[Figure omitted. See PDF.]

[Figure omitted. See PDF.]

3.4 Operational complexity analysis of IPMMPO

The essence of the probe machine lies in DNA computation, and its time complexity arises from the six computational operations introduced in Sect 3.3. Since all the above operations can be completed in the laboratory through a constant number of biological experiments, it is reasonable to assume that the time complexity of these operations is O(1) [75]. In previous studies [44,61,75,76], the same method has been used to analyze the time complexity of DNA computation, so this study also adopts the same approach. The following content will focus on space complexity.

Compared with jobs, machines are relatively scarce resources, meaning that the number of machines m is typically much smaller than the number of jobs n. This is also a premise for studying various scheduling problems. Additionally, the number of available machines in each stage is at least 1, which means that the number of machines m is always greater than the number of stages s. In typical scenarios, s is generally considered to be a constant much smaller than n. Therefore, in the worst-case scenario, we may consider n as an upper bound for both m and s.

Theorem 1. Without loss of generality, is assumed. The total number of data types in two data libraries is bounded by O(n²).

Proof 1. The data types in the data library X_J correspond to the total operations of the HFS problem one-to-one, and the total number of operations are jointly determined by n and s. So the total number of data types in X_J is bounded by O(n²). The total number of data types in data libraries X_M, denoted as , can be abbreviated as n². So the total number of data types in X_M is bounded by O(n²). Therefore, the total number of data types in data libraries X_J and X_M is bounded by .

Theorem 2. Without loss of generality, is assumed. The total number of probe types in the three probe libraries is bounded by O(n³).

Proof 2. The probe types in the probe library Y_S are determined by n and s, and the total number is , so the total number in Y_S is bounded by O(n²). The total number of types in the probe library Y_M is , so it is bounded by O(n³). Finally, the total number of types in Y_J is s, so it is bounded by O(n). Therefore, the total number of probe types in the three probe libraries is bounded by .

To sum up, the space complexity is bounded by O(n³).

4 Constraint programming simulation modeling based on IPMMPO (IPMMPO-CP)

4.1 Data preprocessing based on IPMMPO

This section preprocesses the HFS instance data completely according to data libraries constructed in IPMMPO. Corresponding to the two databases X_J and X_M designed in Sect 3.1, the tuple set P_OId,i,k based on ‘operation-job’ and the tuple set M_OId,j,pt based on ‘operation-optional machine’ are respectively constructed here.

P_OId,i,k is a set of tuples corresponding to X_J, in the form of , where the operation number t corresponds to the data body of X_J, and the job number i corresponds to the data fiber J_i of X_J. The stage k where t is located corresponds to the data fiber S_k of X_J. Taking the three data in shown in Fig 3 as an example, , , and correspond to the three tuples of <1,1,1>, <2,1,2>, and <3,1,3> in P_OId,i,k, representing the three operations of job 1. Similarly, the three data , , and in correspond to the three tuple sets of <13,5,1>, <14,5,2>, and <15,5,3> in P_OId,i,k, representing the three operations of job 5, and so on. The data in X_J is in a one-to-one mapping relationship with the tuples in P_OId,i,k.

M_OId,j,pt is a set of tuples corresponding to X_M, in the form of , where pt represents the processing time given in advance, depending on the specific instance. t and j correspond to operation codes and optional machines in X_M, respectively. Taking the data in shown in Fig 4 as an example, , , and correspond to the three tuple sets of <1,1,24>, <1,2,75>, and <1,3,51> in M_OId,j,pt, respectively. Similarly, the three data , , and correspond to the three tuple sets of <19,1,33>, <19,2,84>, and <19,3,21> in M_OId,j,pt, and so on. The data in X_M is also in a one-to-one mapping relationship with the tuples in M_OId,j,pt.

The tuple sets P_OId,i,k and M_OId,j,pt are completely consistent with data libraries X_J and X_M not only in their tuple content but also in the number of tuples they contain. That is, the number of tuples in P_OId,i,k and M_OId,j,pt are also ns and nm, respectively. P_OId,i,k and M_OId,j,pt can be related by a common operation index OId.

Data preprocessing contributes to enhancing the interpretability of data, thereby providing a more reliable and effective foundation for subsequent modeling process. The data structure M_OId,j,pt proposed in this work can be effectively compatible with both HFS-IPM and HFS-UPM data types. The tuples mentioned above, <1,1,24>, <1,2,75>, and <1,3,51>, serve as examples. They indicate that for operation 1, the optional machines are 1, 2, and 3, with corresponding processing times of 24, 75, and 51 respectively. It is evident that the processing time of the same operation on different optional machines is not the same, which constitutes an HFS-UPM problem. For the HFS-IPM problem, the possible tuples are in the form of <1,1,24>, <1,2,24> and <1,3,24>. That is, the processing time of the same operation on different optional machines is the same. In summary, the data structure M_OId,j,pt can satisfy the data feeding of these two types of HFS at the same time without affecting the construction of the model.

4.2 The proposed IPMMPO-CP

CP method can not only obtain high-quality feasible solutions for large-scale problems in a reasonable time, but also prove that the best feasible solution found is optimal when the search automatically terminates [59,64]. The two types of decision variables that may be involved in scheduling problems are interval variables and interval sequence variables. The three attributes start, end and length of the interval variable correspond to the start time, end time and size of a time interval, respectively. Based on the tuple set P_OId,i,k, this work defines an interval variable PRO to represent the time interval associated with all jobs and processing stages that must appear in the final solution. Based on the tuple set M_OId,j,pt, an optional interval variable Itvs is defined to represent an optional machine-dependent time interval that does not necessarily appear in the final solution.

Parallel machine scenario adaptability: The unified data structure M_OId,j,pt inherently supports both HFS-IPM and HFS-UPM scenarios. For HFS-IPM, processing times satisfy ; for HFS-UPM, pt(t,j) varies arbitrarily. This design eliminates scenario-specific modeling.

Scenario switching mechanism: The transition between standard and no-wait scenarios requires only one constraint change: Replace endBeforeStart (Eq (44)) with endAtStart (Eq (48)), demonstrating extreme flexibility in multi-scenario adaptation.

Further, based on the interval variable Itvs above, an interval sequence variable Seq is defined to represent the possible ordering of this interval variable. The dedicated notations involved in the IPMMPO-CP model and their meanings are shown in Table 3.

[Figure omitted. See PDF.]

After the interval variables and interval sequence variables are properly defined, the functions based on these decision variables can further express constraints on the scheduling problem, which makes the constraint expression of CP modeling both concise and rich. The proposed IPMMPO-CP will be explained in detail below. Eq (41) gives the objective function for the HFS problem. The function is used here, which is an integer expression based on an interval variable to return the end time of the last operation of all jobs.

(41)

Subject to:

(42)

Eq (42) first defines the cumulative function of the machine occupied in each processing stage, where cumulFunction is the cumulative function, which is constructed by the algebraic sum of the atomic function . Fig 10 shows the schematic diagram of this atomic function, where PRO is the defined interval variable, and e represents the number of resources (i.e., machines) occupied by the interval variable.

[Figure omitted. See PDF.]

In short, in stage k, as long as there is a machine allocated and not occupied repeatedly, its pulse value is recorded as 1. The cumulative function f(k) only counts the total number of different parallel machines occupied in stage k.

(43)

Eq (43) uses the cumulative function defined in Eq (42) to impose specific constraints on the available machine capacity in each stage. In other words, Eqs (42), (43) are a set of capacity constraints for a limited total number of machines available over each processing stage.

(44)

Eq (44) implements the precedence constraint over the sequential operation order of the same job, where the function is a temporal constraint based on interval variables.

(45)

Eq (45) is an alternative constraint to ensure that each operation is processed on only one of its corresponding available machines. The function used here is a alternative constraint over interval variables, specifically for modeling discrete selections in scheduling.

(46)

Eq (46) is a non-overlapping constraint based on interval sequence variables, which means that, on any machine in any stage, any two operations cannot overlap in the time domain.

5 The experimental comparison based on HFS-IPM instances

In order to fully verify the performance of IPMMPO-CP, this section first conducts comparative experiments based on a large number of HFS-IPM instances. This section involves a total of 168 instances of different scales, and 9 representative or state-of-the-art algorithms. The hardware environment of the experiments is: Intel Core i5, 2.9GHz, and the running memory is 16GB.

5.1 Experiment 1: Small and medium scale

This subsection first selects 18 difficult instances (see Table 4) from the benchmark published by [79]. Take “j15c5d2” as an example to explain this benchmark, where the letters “j” and “c” represent “job” and “stage” respectively. And “d” represents the type of available machine distribution in all stages, which is one of the four types a, b, c, and d. It should be noted that in both types “a” and “b”, there is such a stage, in which only one machine is available. That is, in a stage where there is only one available machine, there is no need to consider the problem of machine allocation, so instances with types a, b are easier to solve. Whereas for types “c” and “d”, there are more than two machines available at any stage, that is, machine allocation needs to be considered for each stage. So we use instances with types “c” and “d” for comparison and discussion. The comparison algorithms involved are hybrid evolutionary algorithm (HEA, [7]), discrete artificial bee colony (DABC, [21]), particle swarm optimization (PSO, [4]) and artificial immune system (AIS, [78]).

[Figure omitted. See PDF.]

The last two columns of Table 4 present the computation results () of our IPMMPO-CP and the CPU time used (in seconds). Bold data with an asterisk ( ) in the “” column indicates that the current best feasible solution for the corresponding instance was improved. The data in bold with an exclamation mark (!) in the last column means that the algorithm automatically stopped at that time, which means that the best feasible solution found is proved to be optimal. It is clear from Table 4 that the solution for all instances can be automatically stopped within 5 seconds. Therefore, the current best feasible solutions for these 18 hard instances are also proved to be optimal for the first time. Fig 11 shows the optimal Gantt chart of instance j10c10c6.

[Figure omitted. See PDF.]

We next select another 110 small and medium-sized instances from the newly released benchmark instances [65] for test comparison. The comparison algorithms involved in this round of experiments are HEA [7], simulated annealing (SA) [28], and chaos-enchanced simulated annealing (CSA) [28]. In addition, the upper bound (UB) is the result obtained by the publisher of this series of benchmark instances according to the improved iterative greedy algorithm (IG) described by [68]. The detailed experimental results and comparisons are presented in Table 5.

[Figure omitted. See PDF.]

The last two columns of Table 5 present the computation results () of our IPMMPO-CP and the CPU time used (in seconds). Among them, “” is the best feasible solution found by IPMMPO-CP. As mentioned earlier, the data marked with an exclamation mark (!) in the last column indicates that IPMMPO-CP automatically stops searching at that moment, which means that the optimal solution for the corresponding instance is found. Solving for all instances either stops automatically because an optimal solution is found, or terminates when the time limit (900s) is reached. Take “20_15_9” as an example, the first number “20” means the number of jobs is 20, the second number “15” represents a total of 15 processing stages, and the last number “9” represents the serial number of the series of instances.

The following conclusions can be drawn from Table 5.

* First, the best feasible solution for 60 of the 110 instances is updated, and furthermore, the best feasible solution for only one instance (20_20_3) is not as good as that found by HEA, but better than the results of the other three comparison algorithms;

* Second, from the marked data in the last column, the current best feasible solutions for 83 of the 110 instances are proved to be optimal for the first time;

* Third, as with all heuristics, the computation time will inevitably increase as the problem size increases, but it is well within acceptable and reasonable limits.

Figs 12 and 13 present the optimal scheduling Gantt charts of the two instances (namely instances 15_15_7 and 20_20_8) with the greatest improvement. The results of these two instances were reduced by 12 and 18 units of time, respectively, from the best-known solution. Moreover, the best feasible solutions for both instances are proved to be optimal for the first time.

[Figure omitted. See PDF.]

[Figure omitted. See PDF.]

5.2 Experiment 2: Large scale

To further verify and explore the performance of the proposed IPMMPO-CP on large-scale HFS problems, this subsection conducts comparative experiments on 40 benchmark instances. These 40 large-scale instances can be divided into two categories according to their published sources, among which 10 are from [4], the other 30 are from [9].

Comparative experiments are first conducted on 10 difficult instances published by [4] (see Table 6). Since its release in 2012, the best feasible solutions of these 10 benchmarks have been continuously improved by various well-known heuristics. The representative comparison algorithms involved are DABC [21], IDABC [69], and HEA [7]. All the three compared algorithms gave their best solutions on these 10 instances. To ensure the authenticity and accuracy of the data, all comparative data are derived from the literature itself.

[Figure omitted. See PDF.]

As can be seen from Table 6, the record holder of the best feasible solution so far is obtained by the HEA algorithm. However, IPMMPO-CP not only achieves the existing best-known solutions, but also improves the best feasible solutions for 3 of them. More importantly, we also prove for the first time that 6 best feasible solutions out of 10 instances are optimal. When the search does not stop automatically within the specified time (1200s), it means that it is uncertain whether the best feasible solution found is optimal.

Also, because the proposed IPMMPO-CP uses a deterministic, parallel constraint propagation algorithm that produces the same results every run, the best and average values are always equal. Figs 14 and 15 show the scheduling Gantt charts corresponding to the best feasible solution of instance j30c5e3 and j30c5e10, respectively. Fig 16 is a box plot of the four algorithms on instance j30c5e10. Tables 7 and 8 present the ANOVA results and Tukey HSD tests for several comparative algorithms, respectively. It can be clearly seen that the proposed IPMMPO-CP in this work significantly outperforms the other three comparison algorithms.

[Figure omitted. See PDF.]

[Figure omitted. See PDF.]

[Figure omitted. See PDF.]

[Figure omitted. See PDF.]

[Figure omitted. See PDF.]

The following comparative experiments continue on another 30 large-scale instances from [9] (see Table 9). The comparison algorithms involved in Table 9 are improved iterated greedy (IGT) and variable block insertion heuristic (VBIH), both of which were proposed and used by [9] when publishing these 30 large-scale instances. All comparative data in Table 9 are publicly accessible from the literature [9].The comparative data is presented in the form of relative percentage deviation (RPD), which is calculated as follows.

[Figure omitted. See PDF.]

(47)

where BFS is the best feasible solution found by the algorithms IGT and VBIH, and BC_m is the currently known best solution published in the literature [9]. The time limit of IPMMPO-CP is set to 200s. The “” column is the best feasible solution found by IPMMPO-CP.

In Table 9, all CPU times are in seconds. The bold data in the last column means that IPMMPO-CP can automatically stop the search, which indicates that the best feasible solution found is also the optimal solution for the corresponding instance. It can be seen that IPMMPO-CP proves for the first time that the current best feasible solution for 27 instances is optimal within the specified time, except for only three instances (i.e., j50c5e3, j60c5e2, and j60c5e4). Although different from the computing environment used for the comparison data, the computation time consumed by IPMMPO-CP is well within acceptable limits, with an average CPU time of 44 seconds.

In addition, we also updated the current best feasible solutions for three instances, see bold data with asterisks in Table 9, and two of them (j40c5e6 and j60c5e6) proved to be optimal. Taking “j40c5e6” as an example, when the CPU time is 1.25s, the feasible solution 781 published in the literature [9] has been searched. Then, the search converges to 780 at 6.8s and stops automatically. Finally, Fig 17 presents the optimal scheduling Gantt chart for “j60c5e6”. In conclusion, the experiments in this subsection show that the proposed IPMMPO-CP is efficient and excellent in solving large-scale HFS-IPM problems.

[Figure omitted. See PDF.]

In this section, we mainly compare our approach with nine representative approximation methods. The experimental results demonstrate that IPMMPO-CP outperforms the competing algorithms in both solution time and solution accuracy. This advantage is attributed to the CP model’s use of efficient constraint propagation algorithms and domain reduction techniques as its search and inference engine, as well as its support for multi-core and multi-threaded parallel optimization. Not only that, CP methods can even prove that the best feasible solution found is optimal when the search automatically terminates [59,64].

6 Application comparison based on HFS-UPM instances and real cases

In real industrial manufacturing, HFS-UPM is closer to the actual production and has more practical significance than HFS-IPM. This section aims to explore the performance of IPMMPO-CP in solving HFS-UPM type problems. We compare IPMMPO-CP with two existing CP models on several instances and real cases. All instances and cases involved in this section belong to the HFS-UPM type. The time limit for the IPMMPO-CP model is set to 600s to ensure consistency with the compared CP models.

First, the proposed IPMMPO-CP is compared with CP1 [71] in the no-wait HFS scenario, involving 4 instances from reference [74]. To ensure the validity of the comparison, we fine-tune a constraint of IPMMPO-CP as follows. The constraint Eq (44) in the Sect 4.2 is replaced by the following Eq (48) to make it applicable for the no-wait HFS scenario. The no-wait constraint can be satisfied by replacing the keyword “endBeforeStart” with “endAtStart”, that is, each job must be processed continuously in all stages without interruption. Table 10 shows the comparative analysis with model CP1 on 4 instances in the no-wait HFS scenario.

[Figure omitted. See PDF.]

(48)

The bold data in the “Best” column of Table 10 represents the optimal solution found by CP1 and IPMMPO-CP in the corresponding “CPU” solution time. The data from Table 10 indicates that both compared CP models can find the optimal solution to the problem within the specified time. However, it is evident that CP1 requires higher time costs.

Second, the proposed IPMMPO-CP is compared with CP2 [72] on 2 instances and 2 real cases. The comparison here is divided into two categories: the standard HFS scenario and the no-wait HFS scenario. The instances and real cases involved in this comparison are all from the literature [10]. Table 11 shows the comparative analysis with model CP2 in standard HFS scenario. As both models involve the same number of variables, Table 11 shows a comparison in terms of the constraint count “#Cstr”, the best solution “Best”, and the solving time “CPU”. RealCase1∼2 are two real cases from a water meter manufacturer. The last RealCase2 is a large-scale case involving 50 jobs, 22 machines, and 6 stages. The following conclusions can be drawn from the comparative data in Table 11.

[Figure omitted. See PDF.]

* Both CP models achieved the optimal solution in the first three cases. The IPMMPO-CP model updated the current best feasible solution for RealCase2. In all cases, the computational time used by IPMMPO-CP is less than that of CP2.

* From the perspective of model constraint count “#Cstr”, it is evident that IPMMPO-CP is more concise than CP2. This is also a crucial factor contributing to the lower computational time cost required by IPMMPO-CP.

Table 12 shows the comparative analysis with model CP2 on the same instances in the no-wait HFS scenario. Compared with standard HFS, the number of variables and constraints in the no-wait HFS scenario have not changed. IPMMPO-CP obtains the optimal solutions for the first three cases, and the time consumption is less than CP2. In addition, IPMMPO-CP also updates the current best feasible solution of RealCase2 in the no-wait scenario. The comparison results indicate that the proposed IPMMPO-CP model has fewer constraints and requires shorter computational time. Fig 19 and Fig 18 give the scheduling Gantt charts corresponding to the best feasible solutions of RealCase2 in the standard and no-wait HFS scenario, respectively.

[Figure omitted. See PDF.]

[Figure omitted. See PDF.]

[Figure omitted. See PDF.]

In this section, we mainly compare our approach with two recent and representative CP models, namely CP1 and CP2. The CP1 model lacks cumulative constraints, which may result in a less compact search space and consequently higher computational time. Although the CP2 model employs cumulative constraints, they are fundamentally different from those used in our study. As shown in Tables 11 and 12, the number of constraints in the CP2 model (see the “#Cstr” indicator) is 2–3 times greater than that of IPMMPO-CP, which significantly increases the model’s complexity. In summary, in terms of solution time, solution accuracy, and model compactness, IPMMPO-CP outperforms both CP1 and CP2.

7 Conclusions

This work explores the application research of the probe machine in the field of scheduling for the first time. First, considering the problem characteristics of HFS and the computational advantages of PM, an improved PM model allowing multi-level probe operations is proposed. This model can universally address both HFS-IPM and HFS-UPM problems. Second, inspired by the data libraries of IPMMPO, two tuple sets were further constructed, laying the foundation for the subsequent construction of the IPMMPO-CP model. In order to verify and explore the performance of the IPMMPO-CP model, we first conducted a large number of experimental comparisons with 9 representative algorithms on HFS-IPM problems. The results indicate that the IPMMPO-CP method outperforms the comparison algorithms on instances of various sizes. Subsequently, we compared it with the two latest CP models on HFS-UPM problems. These comparisons include benchmark instances, real cases, the standard HFS scenario, and the no-wait HFS scenario. The results show that the proposed IPMMPO-CP outperforms the two compared CP models.

Practical deployment considerations: While IPMMPO-CP demonstrates computational advantages, its industrial implementation requires: (a) Reliable sensor networks for real-time job tracking (e.g., RFID/IIoT devices); (b) Edge computing infrastructure to handle data collection delays; (c) Middleware integration with existing MES/ERP systems via OPC-UA or API gateways.

The existing shortcomings of this study, which can also be used as directions for continuous improvement in follow-up work, are summarized as follows. (1) In CP modeling, a question often troubles us, that is, is there a measurable trade-off between the number of constraints in the model and its solving efficiency? How to evaluate and balance this contradiction will become an important guide for studying the compactness and effectiveness of CP models. (2) In addition to the OPL keywords involved in this study, do other keywords help improve the compactness and effectiveness of the CP model? (3) The proposed IPMMPO-CP only involves single-objective optimization. However, under the needs of the green and low-carbon era, future research can consider multi-objective CP modeling of green scheduling problems with energy-saving and emission reduction. (4) We fully acknowledge the importance of computational efficiency in solving large-scale, multi-scenario problems. In future work, we plan to integrate the Rolling Horizon Decomposition (RHD) approach to further enhance the timeliness of the proposed method.

Supporting information

S1 File.

https://doi.org/10.1371/journal.pone.0330020.s001

(RAR)

Acknowledgments

We would like to thank Professor Jin Xu from Peking University for pioneering research in the field of DNA computing.

References

1. 1. Pan Q-K, Wang L, Mao K, Zhao J-H, Zhang M. An effective artificial bee colony algorithm for a real-world hybrid flowshop problem in steelmaking process. IEEE Trans Automat Sci Eng. 2013;10(2):307–22.

* View Article

* Google Scholar

2. 2. Peng K, Pan Q-K, Gao L, Zhang B, Pang X. An improved artificial bee colony algorithm for real-world hybrid flowshop rescheduling in Steelmaking-refining-Continuous Casting process. Computers & Industrial Engineering. 2018;122:235–50.

* View Article

* Google Scholar

3. 3. Grabowski J, Pempera J. Sequencing of jobs in some production system. European Journal of Operational Research. 2000;125(3):535–50.

* View Article

* Google Scholar

4. 4. Liao C-J, Tjandradjaja E, Chung T-P. An approach using particle swarm optimization and bottleneck heuristic to solve hybrid flow shop scheduling problem. Applied Soft Computing. 2012;12(6):1755–64.

* View Article

* Google Scholar

5. 5. Dios M, Fernandez-Viagas V, Framinan JM. Efficient heuristics for the hybrid flow shop scheduling problem with missing operations. Computers & Industrial Engineering. 2018;115:88–99.

* View Article

* Google Scholar

6. 6. Johnson SM. Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics. 1954;1(1):61–8.

* View Article

* Google Scholar

7. 7. Fan J, Li Y, Xie J, Zhang C, Shen W, Gao L. A hybrid evolutionary algorithm using two solution representations for hybrid flow-shop scheduling problem. IEEE Trans Cybern. 2023;53(3):1752–64. pmid:34710048

* View Article

* PubMed/NCBI

* Google Scholar

8. 8. Wang F, Tang Q, Rao Y, Zhang C, Zhang L. Efficient estimation of distribution for flexible hybrid flow shop scheduling. Acta Automatica Sinica. 2017;43:280–93.

* View Article

* Google Scholar

9. 9. Öztop H, Fatih Tasgetiren M, Eliiyi DT, Pan Q-K. Metaheuristic algorithms for the hybrid flowshop scheduling problem. Computers & Operations Research. 2019;111:177–96.

* View Article

* Google Scholar

10. 10. Cao C, Zhang Y, Gu X, Li D, Li J. An improved gravitational search algorithm to the hybrid flowshop with unrelated parallel machines scheduling problem. International Journal of Production Research. 2020;59(18):5592–608.

* View Article

* Google Scholar

11. 11. Gupta JND. Two-stage, hybrid flowshop scheduling problem. Journal of the Operational Research Society. 1988;39(4):359–64.

* View Article

* Google Scholar

12. 12. Néron E, Baptiste P, Gupta JND. Solving hybrid flow shop problem using energetic reasoning and global operations. Omega. 2001;29(6):501–11.

* View Article

* Google Scholar

13. 13. Lee G-C, Kim * Y-D. A branch-and-bound algorithm for a two-stage hybrid flowshop scheduling problem minimizing total tardiness. International Journal of Production Research. 2004;42(22):4731–43.

* View Article

* Google Scholar

14. 14. Tang L, Xuan H. Lagrangian relaxation algorithms for real-time hybrid flowshop scheduling with finite intermediate buffers. Journal of the Operational Research Society. 2006;57(3):316–24.

* View Article

* Google Scholar

15. 15. Naderi B, Gohari S, Yazdani M. Hybrid flexible flowshop problems: Models and solution methods. Applied Mathematical Modelling. 2014;38(24):5767–80.

* View Article

* Google Scholar

16. 16. Zhang XY, Chen L. A re-entrant hybrid flow shop scheduling problem with machine eligibility constraints. International Journal of Production Research. 2017;56(16):5293–305.

* View Article

* Google Scholar

17. 17. Gicquel C, Hege L, Minoux M, van Canneyt W. A discrete time exact solution approach for a complex hybrid flow-shop scheduling problem with limited-wait constraints. Computers & Operations Research. 2012;39(3):629–36.

* View Article

* Google Scholar

18. 18. Li Y, Li X, Gao L. Review on hybrid flow shop scheduling problem. China Mechanical Engineering. 2020;31:2798–813.

* View Article

* Google Scholar

19. 19. Guirchoun S, Martineau P, Billaut J-C. Total completion time minimization in a computer system with a server and two parallel processors. Computers & Operations Research. 2005;32(3):599–611.

* View Article

* Google Scholar

20. 20. Nawaz M, Enscore EE Jr, Ham I. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega. 1983;11(1):91–5.

* View Article

* Google Scholar

21. 21. Pan Q-K, Wang L, Li J-Q, Duan J-H. A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespan minimisation. Omega. 2014;45:42–56.

* View Article

* Google Scholar

22. 22. Wang S, Wu R, Chu F, Yu J. Variable neighborhood search-based methods for integrated hybrid flow shop scheduling with distribution. Soft Comput. 2019;24(12):8917–36.

* View Article

* Google Scholar

23. 23. Schulz S, Neufeld JS, Buscher U. A multi-objective iterated local search algorithm for comprehensive energy-aware hybrid flow shop scheduling. Journal of Cleaner Production. 2019;224:421–34.

* View Article

* Google Scholar

24. 24. Yu F, Lu C, Zhou J, Yin L. Mathematical model and knowledge-based iterated greedy algorithm for distributed assembly hybrid flow shop scheduling problem with dual-resource constraints. Expert Systems with Applications. 2024;239:122434.

* View Article

* Google Scholar

25. 25. Zhang B, Pan Q, Meng L, Lu C, Mou J, Li J. An automatic multi-objective evolutionary algorithm for the hybrid flowshop scheduling problem with consistent sublots. Knowledge-Based Systems. 2022;238:107819.

* View Article

* Google Scholar

26. 26. Li Y, Li X, Gao L, Meng L. An improved artificial bee colony algorithm for distributed heterogeneous hybrid flowshop scheduling problem with sequence-dependent setup times. Computers & Industrial Engineering. 2020;147:106638.

* View Article

* Google Scholar

27. 27. Wang H-M, Chou F-D, Wu F-C. A simulated annealing for hybrid flow shop scheduling with multiprocessor tasks to minimize makespan. Int J Adv Manuf Technol. 2010;53(5–8):761–76.

* View Article

* Google Scholar

28. 28. Lin S-W, Cheng C-Y, Pourhejazy P, Ying K-C, Lee C-H. New benchmark algorithm for hybrid flowshop scheduling with identical machines. Expert Systems with Applications. 2021;183:115422.

* View Article

* Google Scholar

29. 29. Oĝuz C, Ercan MF. A genetic algorithm for hybrid flow-shop scheduling with multiprocessor tasks. J Sched. 2005;8(4):323–51.

* View Article

* Google Scholar

30. 30. Nowicki E, Smutnicki C. The flow shop with parallel machines: a tabu search approach. European Journal of Operational Research. 1998;106(2–3):226–53.

* View Article

* Google Scholar

31. 31. Alaykýran K, Engin O, Döyen A. Using ant colony optimization to solve hybrid flow shop scheduling problems. Int J Adv Manuf Technol. 2007;35(5–6):541–50.

* View Article

* Google Scholar

32. 32. Jin Z, Yang Z, Ito T. Metaheuristic algorithms for the multistage hybrid flowshop scheduling problem. International Journal of Production Economics. 2006;100(2):322–34.

* View Article

* Google Scholar

33. 33. Chamnanlor C, Sethanan K, Gen M, Chien C-F. Embedding ant system in genetic algorithm for re-entrant hybrid flow shop scheduling problems with time window constraints. J Intell Manuf. 2015;28(8):1915–31.

* View Article

* Google Scholar

34. 34. Shahvari O, Logendran R. A comparison of two stage-based hybrid algorithms for a batch scheduling problem in hybrid flow shop with learning effect. International Journal of Production Economics. 2018;195:227–48.

* View Article

* Google Scholar

35. 35. Tian X, Liu X. Improved Hybrid Heuristic Algorithm Inspired by Tissue-Like Membrane System to Solve Job Shop Scheduling Problem. Processes. 2021;9(2):219.

* View Article

* Google Scholar

36. 36. Wang S, Wang L, Liu M, Xu Y. An enhanced estimation of distribution algorithm for solving hybrid flow-shop scheduling problem with identical parallel machines. Int J Adv Manuf Technol. 2013;68(9–12):2043–56.

* View Article

* Google Scholar

37. 37. Chen C-L, Huang S-Y, Tzeng Y-R, Chen C-L. A revised discrete particle swarm optimization algorithm for permutation flow-shop scheduling problem. Soft Comput. 2013;18(11):2271–82.

* View Article

* Google Scholar

38. 38. Wang F, Wu S. Retracted article: multi-objective flow shop scheduling system based on wireless network genetic algorithm from perspective of artificial intelligence. Soft Comput. 2023;28(S2):557–557.

* View Article

* Google Scholar

39. 39. Xu J. Probe machine. IEEE Trans Neural Netw Learn Syst. 2016;27(7):1405–16. pmid:28113730

* View Article

* PubMed/NCBI

* Google Scholar

40. 40. Xu J, Qiang X, Zhang K, Zhang C, Yang J. A DNA computing model for the graph vertex coloring problem based on a probe graph. Engineering. 2018;4(1):61–77.

* View Article

* Google Scholar

41. 41. Xu J, Chen C, Shi X. Graph computation using algorithmic self-assembly of DNA molecules. ACS Synth Biol. 2022;11(7):2456–63. pmid:35703038

* View Article

* PubMed/NCBI

* Google Scholar

42. 42. Wang Y, Lv Q, Zhang Y, Wang L, Dong Y. Probe computing model based on small molecular switch. BMC Bioinformatics. 2019;20(Suppl 8):285. pmid:31182004

* View Article

* PubMed/NCBI

* Google Scholar

43. 43. Tian X, Liu X. Solving urban light rail route planning based on probe machine. In: Bio-inspired computing: Theories, applications - 15th International Conference and BIC-TA 2020, 2021. 611–23.

44. 44. Cui J, Yin Z, Tang Z, Yang J. Probe machine based computing model for maximum clique problem. Chinese J of Electronics. 2022;31(2):304–12.

* View Article

* Google Scholar

45. 45. Cui J, Yin Z, Yang J, Geng X, Zhang Q. Probe machine based computing model for solving satisfiability problem. In: Bio-inspired computing: theories, applications - 14th International Conference and BIC-TA 2019, 2020. p. 79–92. https://doi.org/10.1007/978-981-15-3415-7

46. 46. Yang J, Yin Z, Cui J, Zhang Q, Tang Z. The Chinese postman problem based on the probe machine model. In: Bio-inspired Computing: Theories, Applications - 13th International Conference and BIC-TA 2018, 2018. p. 55–62. https://doi.org/10.1007/978-981-13-2829-9

47. 47. Wang D, Liu J, Sun H, Xu J, Kang J. A fully parallel approach of model checking via probe machine. Int J Soft Eng Knowl Eng. 2021;31(11n12):1761–81.

* View Article

* Google Scholar

48. 48. Wang D. A novel approach of CTL model checking based on probe machine. In: International Conferences on Software Engineering and Knowledge Engineering. 2021. p. 183–8. https://doi.org/10.18293/seke2021-139

49. 49. Sun J, Dong H, Kong Y, Fang Y. Solution to shortest path problem using a connective probe machine. Mathematical Problems in Engineering. 2019;2019(1):8709042.

* View Article

* Google Scholar

50. 50. Rahman MdA, Ma J. Probe machine based consecutive route filtering approach to symmetric travelling salesman problem. IFIP Advances in Information and Communication Technology. Springer; 2018. p. 378–87. https://doi.org/10.1007/978-3-030-01313-4_41

51. 51. Huang D-S, Bevilacqua V, Premaratne P. Intelligent computing theories and application. Springer; 2019. https://doi.org/10.1007/978-3-030-26763-6

52. 52. Rahman MdA, Ma J. Probe machine based optimization approach for capacitated vehicle routing problem. In: 2019 IEEE International Conference on Signal, Information and Data Processing (ICSIDP). 2019. p. 1–6. https://doi.org/10.1109/icsidp47821.2019.9173199

53. 53. Lunardi WT, Birgin EG, Laborie P, Ronconi DP, Voos H. Mixed Integer linear programming and constraint programming models for the online printing shop scheduling problem. Computers & Operations Research. 2020;123:105020.

* View Article

* Google Scholar

54. 54. Novara FM, Novas JM, Henning GP. A novel constraint programming model for large-scale scheduling problems in multiproduct multistage batch plants: Limited resources and campaign-based operation. Computers & Chemical Engineering. 2016;93:101–17.

* View Article

* Google Scholar

55. 55. Sahraeian R, Namakshenas M. On the optimal modeling and evaluation of job shops with a total weighted tardiness objective: constraint programming vs. mixed integer programming. Applied Mathematical Modelling. 2015;39(2):955–64.

* View Article

* Google Scholar

56. 56. Oujana S, Amodeo L, Yalaoui F, Brodart D. Solving a realistic hybrid and flexible flow shop scheduling problem through constraint programming: industrial case in a packaging company. In: 2022 8th International Conference on Control, Decision and Information Technologies (CoDIT). 2022. https://doi.org/10.1109/codit55151.2022.9803972

57. 57. Ham AM, Cakici E. Flexible job shop scheduling problem with parallel batch processing machines: MIP and CP approaches. Computers & Industrial Engineering. 2016;102:160–5.

* View Article

* Google Scholar

58. 58. Gedik R, Rainwater C, Nachtmann H, Pohl EA. Analysis of a parallel machine scheduling problem with sequence dependent setup times and job availability intervals. European Journal of Operational Research. 2016;251(2):640–50.

* View Article

* Google Scholar

59. 59. Gedik R, Kalathia D, Egilmez G, Kirac E. A constraint programming approach for solving unrelated parallel machine scheduling problem. Computers & Industrial Engineering. 2018;121:139–49.

* View Article

* Google Scholar

60. 60. Gedik R, Kirac E, Bennet Milburn A, Rainwater C. A constraint programming approach for the team orienteering problem with time windows. Computers & Industrial Engineering. 2017;107:178–95.

* View Article

* Google Scholar

61. 61. Tian X, Liu X, Zhang H, Sun M, Zhao Y. A DNA algorithm for the job shop scheduling problem based on the Adleman-Lipton model. PLoS One. 2020;15(12):e0242083. pmid:33264317

* View Article

* PubMed/NCBI

* Google Scholar

62. 62. Edis EB, Oguz C. Parallel machine scheduling with flexible resources. Computers & Industrial Engineering. 2012;63(2):433–47.

* View Article

* Google Scholar

63. 63. Tran TT, Vaquero T, Nejat G, Beck JC. Robots in retirement homes: applying off-the-shelf planning and scheduling to a team of assistive robots. JAIR. 2017;58:523–90.

* View Article

* Google Scholar

64. 64. Meng L, Zhang C, Ren Y, Zhang B, Lv C. Mixed-integer linear programming and constraint programming formulations for solving distributed flexible job shop scheduling problem. Computers & Industrial Engineering. 2020;142:106347.

* View Article

* Google Scholar

65. 65. Fernandez-Viagas V, Framinan JM. Design of a testbed for hybrid flow shop scheduling with identical machines. Computers & Industrial Engineering. 2020;141:106288.

* View Article

* Google Scholar

66. 66. Graham RL, Lawler EL, Lenstra JK, Kan AHGR. Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of discrete mathematics. Elsevier; 1979. p. 287–326. https://doi.org/10.1016/s0167-5060(08)70356-x

67. 67. Laborie P, Rogerie J, Shaw P, Vilím P. IBM ILOG CP optimizer for scheduling. Constraints. 2018;23(2):210–50.

* View Article

* Google Scholar

68. 68. Vallada E, Ruiz R, Framinan JM. New hard benchmark for flowshop scheduling problems minimising makespan. European Journal of Operational Research. 2015;240(3):666–77.

* View Article

* Google Scholar

69. 69. Cui Z, Gu X. An improved discrete artificial bee colony algorithm to minimize the makespan on hybrid flow shop problems. Neurocomputing. 2015;148:248–59.

* View Article

* Google Scholar

70. 70. Öztop H, Tasgetiren MF, Kandiller L, Eliiyi DT, Gao L. Ensemble of metaheuristics for energy-efficient hybrid flowshops: makespan versus total energy consumption. Swarm and Evolutionary Computation. 2020;54:100660.

* View Article

* Google Scholar

71. 71. Meng L, Lu C, Zhang B, Ren Y, Lv C, Sang H, et al. Constraint programing for solving four complex flexible shop scheduling problems. IET Collab Intel Manufact. 2021;3(2):147–60.

* View Article

* Google Scholar

72. 72. Işık EE, Topaloglu Yildiz S, Şatır Akpunar Ö. Constraint programming models for the hybrid flow shop scheduling problem and its extensions. Soft Comput. 2023;27(24):18623–50.

* View Article

* Google Scholar

73. 73. Naderi B, Ruiz R, Roshanaei V. Mixed-integer programming vs. constraint programming for shop scheduling problems: new results and outlook. INFORMS Journal on Computing. 2023;35(4):817–43.

* View Article

* Google Scholar

74. 74. Zhang H, Qin Y, Xu D. Multi-search mechanism particle swarm optimization algorithm for solving FFS problem. Journal of Frontiers of Computer Science and Technology. 2016;10(03):433–44.

* View Article

* Google Scholar

75. 75. Wu X, Wang Z, Wu T, Bao X. Solving the family traveling salesperson problem in the adleman-lipton model based on DNA computing. IEEE Trans Nanobioscience. 2022;21(1):75–85. pmid:34460379

* View Article

* PubMed/NCBI

* Google Scholar

76. 76. Wang Z, Ren X, Ji Z, Huang W, Wu T. A novel bio-heuristic computing algorithm to solve the capacitated vehicle routing problem based on Adleman-Lipton model. Biosystems. 2019;184:103997. pmid:31369836

* View Article

* PubMed/NCBI

* Google Scholar

77. 77. Huang X, Chen S, Zhou T, Sun Y. A new neighborhood structure for solving the flexible job-shop scheduling problem. Systems Engineering-Theory & Practice. 2021;41(9):2367–78.

* View Article

* Google Scholar

78. 78. Engin O, Döyen A. A new approach to solve hybrid flow shop scheduling problems by artificial immune system. Future Generation Computer Systems. 2004;20(6):1083–95.

* View Article

* Google Scholar

79. 79. Carlier J, Neron E. An exact method for solving the multi-processor flow-shop. RAIRO-Oper Res. 2000;34(1):1–25.

* View Article

* Google Scholar

Citation: Tian X, Kong Y, Liu X (2025) Solving multi-scenario hybrid flow shop scheduling problem based on an improved probe machine model. PLoS One 20(9): e0330020. https://doi.org/10.1371/journal.pone.0330020

About the Authors:

Xiang Tian

Roles: Data curation, Methodology, Resources, Visualization, Writing – original draft, Writing – review & editing

E-mail: [email protected]

Affiliation: School of Health Management, Binzhou Medical University, Yantai, Shandong, China

ORICD: https://orcid.org/0000-0001-5507-8284

Yang Kong

Roles: Funding acquisition, Supervision, Validation

Affiliation: School of Health Management, Binzhou Medical University, Yantai, Shandong, China

Xiyu Liu

Roles: Funding acquisition, Project administration, Supervision, Validation

Affiliations: School of Business, Shandong Normal University, Jinan, Shandong, China, Academy of Management Science, Shandong Normal University, Jinan, Shandong, China

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

References

1. Pan Q-K, Wang L, Mao K, Zhao J-H, Zhang M. An effective artificial bee colony algorithm for a real-world hybrid flowshop problem in steelmaking process. IEEE Trans Automat Sci Eng. 2013;10(2):307–22.

2. Peng K, Pan Q-K, Gao L, Zhang B, Pang X. An improved artificial bee colony algorithm for real-world hybrid flowshop rescheduling in Steelmaking-refining-Continuous Casting process. Computers & Industrial Engineering. 2018;122:235–50.

3. Grabowski J, Pempera J. Sequencing of jobs in some production system. European Journal of Operational Research. 2000;125(3):535–50.

4. Liao C-J, Tjandradjaja E, Chung T-P. An approach using particle swarm optimization and bottleneck heuristic to solve hybrid flow shop scheduling problem. Applied Soft Computing. 2012;12(6):1755–64.

5. Dios M, Fernandez-Viagas V, Framinan JM. Efficient heuristics for the hybrid flow shop scheduling problem with missing operations. Computers & Industrial Engineering. 2018;115:88–99.

6. Johnson SM. Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics. 1954;1(1):61–8.

7. Fan J, Li Y, Xie J, Zhang C, Shen W, Gao L. A hybrid evolutionary algorithm using two solution representations for hybrid flow-shop scheduling problem. IEEE Trans Cybern. 2023;53(3):1752–64. pmid:34710048

8. Wang F, Tang Q, Rao Y, Zhang C, Zhang L. Efficient estimation of distribution for flexible hybrid flow shop scheduling. Acta Automatica Sinica. 2017;43:280–93.

9. Öztop H, Fatih Tasgetiren M, Eliiyi DT, Pan Q-K. Metaheuristic algorithms for the hybrid flowshop scheduling problem. Computers & Operations Research. 2019;111:177–96.

10. Cao C, Zhang Y, Gu X, Li D, Li J. An improved gravitational search algorithm to the hybrid flowshop with unrelated parallel machines scheduling problem. International Journal of Production Research. 2020;59(18):5592–608.

11. Gupta JND. Two-stage, hybrid flowshop scheduling problem. Journal of the Operational Research Society. 1988;39(4):359–64.

12. Néron E, Baptiste P, Gupta JND. Solving hybrid flow shop problem using energetic reasoning and global operations. Omega. 2001;29(6):501–11.

13. Lee G-C, Kim * Y-D. A branch-and-bound algorithm for a two-stage hybrid flowshop scheduling problem minimizing total tardiness. International Journal of Production Research. 2004;42(22):4731–43.

14. Tang L, Xuan H. Lagrangian relaxation algorithms for real-time hybrid flowshop scheduling with finite intermediate buffers. Journal of the Operational Research Society. 2006;57(3):316–24.

15. Naderi B, Gohari S, Yazdani M. Hybrid flexible flowshop problems: Models and solution methods. Applied Mathematical Modelling. 2014;38(24):5767–80.

16. Zhang XY, Chen L. A re-entrant hybrid flow shop scheduling problem with machine eligibility constraints. International Journal of Production Research. 2017;56(16):5293–305.

17. Gicquel C, Hege L, Minoux M, van Canneyt W. A discrete time exact solution approach for a complex hybrid flow-shop scheduling problem with limited-wait constraints. Computers & Operations Research. 2012;39(3):629–36.

18. Li Y, Li X, Gao L. Review on hybrid flow shop scheduling problem. China Mechanical Engineering. 2020;31:2798–813.

19. Guirchoun S, Martineau P, Billaut J-C. Total completion time minimization in a computer system with a server and two parallel processors. Computers & Operations Research. 2005;32(3):599–611.

20. Nawaz M, Enscore EE Jr, Ham I. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega. 1983;11(1):91–5.

21. Pan Q-K, Wang L, Li J-Q, Duan J-H. A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespan minimisation. Omega. 2014;45:42–56.

22. Wang S, Wu R, Chu F, Yu J. Variable neighborhood search-based methods for integrated hybrid flow shop scheduling with distribution. Soft Comput. 2019;24(12):8917–36.

23. Schulz S, Neufeld JS, Buscher U. A multi-objective iterated local search algorithm for comprehensive energy-aware hybrid flow shop scheduling. Journal of Cleaner Production. 2019;224:421–34.

24. Yu F, Lu C, Zhou J, Yin L. Mathematical model and knowledge-based iterated greedy algorithm for distributed assembly hybrid flow shop scheduling problem with dual-resource constraints. Expert Systems with Applications. 2024;239:122434.

25. Zhang B, Pan Q, Meng L, Lu C, Mou J, Li J. An automatic multi-objective evolutionary algorithm for the hybrid flowshop scheduling problem with consistent sublots. Knowledge-Based Systems. 2022;238:107819.

26. Li Y, Li X, Gao L, Meng L. An improved artificial bee colony algorithm for distributed heterogeneous hybrid flowshop scheduling problem with sequence-dependent setup times. Computers & Industrial Engineering. 2020;147:106638.

27. Wang H-M, Chou F-D, Wu F-C. A simulated annealing for hybrid flow shop scheduling with multiprocessor tasks to minimize makespan. Int J Adv Manuf Technol. 2010;53(5–8):761–76.

28. Lin S-W, Cheng C-Y, Pourhejazy P, Ying K-C, Lee C-H. New benchmark algorithm for hybrid flowshop scheduling with identical machines. Expert Systems with Applications. 2021;183:115422.

29. Oĝuz C, Ercan MF. A genetic algorithm for hybrid flow-shop scheduling with multiprocessor tasks. J Sched. 2005;8(4):323–51.

30. Nowicki E, Smutnicki C. The flow shop with parallel machines: a tabu search approach. European Journal of Operational Research. 1998;106(2–3):226–53.

31. Alaykýran K, Engin O, Döyen A. Using ant colony optimization to solve hybrid flow shop scheduling problems. Int J Adv Manuf Technol. 2007;35(5–6):541–50.

32. Jin Z, Yang Z, Ito T. Metaheuristic algorithms for the multistage hybrid flowshop scheduling problem. International Journal of Production Economics. 2006;100(2):322–34.

33. Chamnanlor C, Sethanan K, Gen M, Chien C-F. Embedding ant system in genetic algorithm for re-entrant hybrid flow shop scheduling problems with time window constraints. J Intell Manuf. 2015;28(8):1915–31.

34. Shahvari O, Logendran R. A comparison of two stage-based hybrid algorithms for a batch scheduling problem in hybrid flow shop with learning effect. International Journal of Production Economics. 2018;195:227–48.

35. Tian X, Liu X. Improved Hybrid Heuristic Algorithm Inspired by Tissue-Like Membrane System to Solve Job Shop Scheduling Problem. Processes. 2021;9(2):219.

36. Wang S, Wang L, Liu M, Xu Y. An enhanced estimation of distribution algorithm for solving hybrid flow-shop scheduling problem with identical parallel machines. Int J Adv Manuf Technol. 2013;68(9–12):2043–56.

37. Chen C-L, Huang S-Y, Tzeng Y-R, Chen C-L. A revised discrete particle swarm optimization algorithm for permutation flow-shop scheduling problem. Soft Comput. 2013;18(11):2271–82.

38. Wang F, Wu S. Retracted article: multi-objective flow shop scheduling system based on wireless network genetic algorithm from perspective of artificial intelligence. Soft Comput. 2023;28(S2):557–557.

39. Xu J. Probe machine. IEEE Trans Neural Netw Learn Syst. 2016;27(7):1405–16. pmid:28113730

40. Xu J, Qiang X, Zhang K, Zhang C, Yang J. A DNA computing model for the graph vertex coloring problem based on a probe graph. Engineering. 2018;4(1):61–77.

41. Xu J, Chen C, Shi X. Graph computation using algorithmic self-assembly of DNA molecules. ACS Synth Biol. 2022;11(7):2456–63. pmid:35703038

42. Wang Y, Lv Q, Zhang Y, Wang L, Dong Y. Probe computing model based on small molecular switch. BMC Bioinformatics. 2019;20(Suppl 8):285. pmid:31182004

43. Tian X, Liu X. Solving urban light rail route planning based on probe machine. In: Bio-inspired computing: Theories, applications - 15th International Conference and BIC-TA 2020, 2021. 611–23.

44. Cui J, Yin Z, Tang Z, Yang J. Probe machine based computing model for maximum clique problem. Chinese J of Electronics. 2022;31(2):304–12.

45. Cui J, Yin Z, Yang J, Geng X, Zhang Q. Probe machine based computing model for solving satisfiability problem. In: Bio-inspired computing: theories, applications - 14th International Conference and BIC-TA 2019, 2020. p. 79–92. https://doi.org/10.1007/978-981-15-3415-7

46. Yang J, Yin Z, Cui J, Zhang Q, Tang Z. The Chinese postman problem based on the probe machine model. In: Bio-inspired Computing: Theories, Applications - 13th International Conference and BIC-TA 2018, 2018. p. 55–62. https://doi.org/10.1007/978-981-13-2829-9

47. Wang D, Liu J, Sun H, Xu J, Kang J. A fully parallel approach of model checking via probe machine. Int J Soft Eng Knowl Eng. 2021;31(11n12):1761–81.

48. Wang D. A novel approach of CTL model checking based on probe machine. In: International Conferences on Software Engineering and Knowledge Engineering. 2021. p. 183–8. https://doi.org/10.18293/seke2021-139

49. Sun J, Dong H, Kong Y, Fang Y. Solution to shortest path problem using a connective probe machine. Mathematical Problems in Engineering. 2019;2019(1):8709042.

50. Rahman MdA, Ma J. Probe machine based consecutive route filtering approach to symmetric travelling salesman problem. IFIP Advances in Information and Communication Technology. Springer; 2018. p. 378–87. https://doi.org/10.1007/978-3-030-01313-4_41

51. Huang D-S, Bevilacqua V, Premaratne P. Intelligent computing theories and application. Springer; 2019. https://doi.org/10.1007/978-3-030-26763-6

52. Rahman MdA, Ma J. Probe machine based optimization approach for capacitated vehicle routing problem. In: 2019 IEEE International Conference on Signal, Information and Data Processing (ICSIDP). 2019. p. 1–6. https://doi.org/10.1109/icsidp47821.2019.9173199

53. Lunardi WT, Birgin EG, Laborie P, Ronconi DP, Voos H. Mixed Integer linear programming and constraint programming models for the online printing shop scheduling problem. Computers & Operations Research. 2020;123:105020.

54. Novara FM, Novas JM, Henning GP. A novel constraint programming model for large-scale scheduling problems in multiproduct multistage batch plants: Limited resources and campaign-based operation. Computers & Chemical Engineering. 2016;93:101–17.

55. Sahraeian R, Namakshenas M. On the optimal modeling and evaluation of job shops with a total weighted tardiness objective: constraint programming vs. mixed integer programming. Applied Mathematical Modelling. 2015;39(2):955–64.

56. Oujana S, Amodeo L, Yalaoui F, Brodart D. Solving a realistic hybrid and flexible flow shop scheduling problem through constraint programming: industrial case in a packaging company. In: 2022 8th International Conference on Control, Decision and Information Technologies (CoDIT). 2022. https://doi.org/10.1109/codit55151.2022.9803972

57. Ham AM, Cakici E. Flexible job shop scheduling problem with parallel batch processing machines: MIP and CP approaches. Computers & Industrial Engineering. 2016;102:160–5.

58. Gedik R, Rainwater C, Nachtmann H, Pohl EA. Analysis of a parallel machine scheduling problem with sequence dependent setup times and job availability intervals. European Journal of Operational Research. 2016;251(2):640–50.

59. Gedik R, Kalathia D, Egilmez G, Kirac E. A constraint programming approach for solving unrelated parallel machine scheduling problem. Computers & Industrial Engineering. 2018;121:139–49.

60. Gedik R, Kirac E, Bennet Milburn A, Rainwater C. A constraint programming approach for the team orienteering problem with time windows. Computers & Industrial Engineering. 2017;107:178–95.

61. Tian X, Liu X, Zhang H, Sun M, Zhao Y. A DNA algorithm for the job shop scheduling problem based on the Adleman-Lipton model. PLoS One. 2020;15(12):e0242083. pmid:33264317

62. Edis EB, Oguz C. Parallel machine scheduling with flexible resources. Computers & Industrial Engineering. 2012;63(2):433–47.

63. Tran TT, Vaquero T, Nejat G, Beck JC. Robots in retirement homes: applying off-the-shelf planning and scheduling to a team of assistive robots. JAIR. 2017;58:523–90.

64. Meng L, Zhang C, Ren Y, Zhang B, Lv C. Mixed-integer linear programming and constraint programming formulations for solving distributed flexible job shop scheduling problem. Computers & Industrial Engineering. 2020;142:106347.

65. Fernandez-Viagas V, Framinan JM. Design of a testbed for hybrid flow shop scheduling with identical machines. Computers & Industrial Engineering. 2020;141:106288.

66. Graham RL, Lawler EL, Lenstra JK, Kan AHGR. Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of discrete mathematics. Elsevier; 1979. p. 287–326. https://doi.org/10.1016/s0167-5060(08)70356-x

67. Laborie P, Rogerie J, Shaw P, Vilím P. IBM ILOG CP optimizer for scheduling. Constraints. 2018;23(2):210–50.

68. Vallada E, Ruiz R, Framinan JM. New hard benchmark for flowshop scheduling problems minimising makespan. European Journal of Operational Research. 2015;240(3):666–77.

69. Cui Z, Gu X. An improved discrete artificial bee colony algorithm to minimize the makespan on hybrid flow shop problems. Neurocomputing. 2015;148:248–59.

70. Öztop H, Tasgetiren MF, Kandiller L, Eliiyi DT, Gao L. Ensemble of metaheuristics for energy-efficient hybrid flowshops: makespan versus total energy consumption. Swarm and Evolutionary Computation. 2020;54:100660.

71. Meng L, Lu C, Zhang B, Ren Y, Lv C, Sang H, et al. Constraint programing for solving four complex flexible shop scheduling problems. IET Collab Intel Manufact. 2021;3(2):147–60.

72. Işık EE, Topaloglu Yildiz S, Şatır Akpunar Ö. Constraint programming models for the hybrid flow shop scheduling problem and its extensions. Soft Comput. 2023;27(24):18623–50.

73. Naderi B, Ruiz R, Roshanaei V. Mixed-integer programming vs. constraint programming for shop scheduling problems: new results and outlook. INFORMS Journal on Computing. 2023;35(4):817–43.

74. Zhang H, Qin Y, Xu D. Multi-search mechanism particle swarm optimization algorithm for solving FFS problem. Journal of Frontiers of Computer Science and Technology. 2016;10(03):433–44.

75. Wu X, Wang Z, Wu T, Bao X. Solving the family traveling salesperson problem in the adleman-lipton model based on DNA computing. IEEE Trans Nanobioscience. 2022;21(1):75–85. pmid:34460379

76. Wang Z, Ren X, Ji Z, Huang W, Wu T. A novel bio-heuristic computing algorithm to solve the capacitated vehicle routing problem based on Adleman-Lipton model. Biosystems. 2019;184:103997. pmid:31369836

77. Huang X, Chen S, Zhou T, Sun Y. A new neighborhood structure for solving the flexible job-shop scheduling problem. Systems Engineering-Theory & Practice. 2021;41(9):2367–78.

78. Engin O, Döyen A. A new approach to solve hybrid flow shop scheduling problems by artificial immune system. Future Generation Computer Systems. 2004;20(6):1083–95.

79. Carlier J, Neron E. An exact method for solving the multi-processor flow-shop. RAIRO-Oper Res. 2000;34(1):1–25.