Discrete Event Simulation-Driven Method Solving Permutation Flowshop Scheduling Problem in Digital Twins

Digital twin technology is becoming increasingly vital in intelligent production and Industry 4.0. Nevertheless, the simulation system of the digital twin frequently serves merely as a virtual representation of the actual system, neglecting its significant analytical and decision-making capabilities. This research introduces a discrete-event simulation-based digital twin optimization methodology to determine the optimal job sequence for the permutation flowshop scheduling problem (PFSP). The concept of sequence-dependent recovery time (SDRT) is brought into the PFSP for the first time, and the four subproblems of PFSP with SDRT was proposed. The computational simulation findings on a benchmark dataset indicate that the SDRT substantially influences optimization, enhancing average scheduling performance by around 14% relative to integrating recovery time into processing time. The empirical case study findings indicate that the suggested simulation-optimization strategy decreases completion time by 0.95% relative to the conventional mathematical approach while addressing the actual PFSP using SDRT. These findings validate the effectiveness of discrete event simulation-based digital twin technology for addressing PFSP with SDRT.

SECTION I. Introduction

The digital twin is an essential technology for achieving smart manufacturing and industrial digital transformation. This topic has garnered significant focus and investigation from both industry and academics [1], [2]. Within the framework of Industry 4.0, the phrase “digital twin” generally denotes a composite entity that includes a physical system, a virtual system, and a clearinghouse. The virtual system is a simulated reflection of a physical world or system throughout its lifecycle [3]. Generally, the clearinghouse utilizes a mathematical optimization algorithm for the analysis, processing, and real-time decision-making of the physical system.

In numerous domains, digital twins play a significant role [4], [5], [6], [7]. Nonetheless, the simulation system frequently serves merely as a digital replica of the actual system or as a preliminary instrument for technical validation [8]. The simulation system’s potential to deliver robust analysis and decision-making capabilities remains underutilized, especially with discrete event dynamic manufacturing systems. The application of pure mathematical optimization methods often experiences a level of simplification that inadequately represents realistic systems, resulting in suboptimal decision-making. However, the application of discrete-event dynamic simulation has demonstrated efficacy in addressing this issue [9], [10], [11].

The permutation flowshop scheduling problem (PFSP) has garnered significant research attention since the inception of the two-machine PFSP was initially examined [12], [13], [14]. Heller used the word “flowshop” to describe this kind of problem, and this word is used today [15]. PFSP is commonly seen in many industrial fields [16], [17], and it has been established that PFSP is an NP-hard problem [18].

The PFSP can be described as follows: Each of the n jobs is available at time zero and has to be processed on m machines. No machine can process more than one job at a time; no job preemptions are allowed. The order of m machines is fixed, but the sequence of n jobs is variable. The objective of PFSP is to determine a job sequence that will optimize a specific production index, such as makespan.

After extensive research on classical PFSP, numerous experts have acknowledged a significant disparity between theory and practice. An efficacious approach to diminish this disparity is to implement practical restraints. A significant constraint is the job constraint [13], which pertains to job-related constraints. The most concerned job constraints are sequence-dependent setup time (SDST) and release time (RT) [19], [20], [21], [22]. Researchers have thoroughly examined these two job restrictions; however, they have not yet explored another prevalent job constraint, sequence-dependent recovery time (SDRT). A review of the literature disclosed no instances of publications that have incorporated recovery time constraints inside the PFSP domain, nor in the wider field of production and operations research.

Therefore, there are two main issues to be addressed in this paper: 1) The permutation flowshop simulation model is constructed via digital twin technology, and a decision-making approach for discrete event optimization can direct real production. 2. Investigate the PFSP with SDRT based on the digital twin methodology.

The remainder of this work is structured as follows. Section II introduces the research methodology. In Section III, the three recovery time modes and the four sub-problems of PFSP with SDRT are presented. Part IV delineates a procedure of an optimization method for PFSP with SDRT that is based on discrete event simulation. The computational results are demonstrated in Section V. Section VI presents a real case study. Conclusions are presented in Section VII.

SECTION II. Research Methodology

This paper introduced the concept of recovery time and took this constraint into account in a discrete event simulation model. The research employs a simulation platform to consolidate all methodologies, comprising two primary components: the simulation model and the algorithm. The model attains complete automation in modelling, capable of representing the restrictions of actual plants, including the quantity of machines, buffers, processing time, and waiting times.

This method is defined by two separate initial points, as illustrated in FIGURE 1. Initially, the algorithm begins with the instruction to “Create initial sequence based on PR_LJP”. Secondly, the model initiation commences with the directive to “Construct method”. The end point of the method is designated “Final sequence”.

FIGURE 1.

Simulation-optimization framework.

SECTION III. Description of Recovery Time

The recovery time is the duration period necessary for a machine to reach a specified state prior to initiating the next process. The initiation of the next process depends entirely on the full completion of the recuperation period, regardless of the present process’s status, whether it is finished or ongoing.

A. Three Basic Recovery Time Modes

There are three recovery time modes depending on when the recovery time starts to elapse. The concept of three modes of recovery time can be observed in FIGURE 2. As demonstrated in FIGURE 2, there are multiple categories of time during which the machine is occupied: setup time, processing time, blocked time, and recovery time. These are represented by $t_{s}$ , $t_{p}$ , $t_{b}$ , and $t_{r}$ , respectively. Moreover, the present study delineated the temporal interval between the entry of the current component into the machine and the subsequent entry of the next component, thereby defining the total machine time, which is denoted by $t_{m}$ . Then the three recovery time modes can be described as follows.

1. Mode 1: The concept of this mode can be seen in FIGURE 2.(a). The recovery time of Mode 1 starts to elapse after the current part enters the station. This mode signifies that upon the entry of the current part into the machine, it can be prepared for the subsequent part’s entry. This mode can be found on some CNC (Computer Numerical Control) machines, which is sometimes necessary to activate the recovery mode when the part enters the CNC. In this case, the $t_{m}$ is calculated as follows.

   $$\begin{equation*} t_{m} =max(t_{r}, t_{s} +t_{p} +t_{b} ) \tag {1}\end{equation*}$$

2. Mode 2: The notion of this mode is illustrated in FIGURE 2.(b). The recovery time of Mode 2 starts to elapse after the part is processed, no matter if the part is still on the station or has left it. This mode signifies that upon the completion of the current part’s processing, it can be prepared for the subsequent part’s entry. This mode can be found in some special cases, e.g., when auxiliary materials need to be added for each part machining. Therefore, when the current part has been machined, the period is needed to reload the auxiliary material for the next part to be machined. In this mode, $t_{m}$ is calculated as follows.

   $$\begin{equation*} t_{m} =max(t_{s} +t_{p} +t_{r}, t_{s} +t_{p} +t_{b}) \tag {2}\end{equation*}$$

3. Mode 3: The concept of this mode can be seen in FIGURE 2.(c). The recovery time of Mode 3 starts to elapse after the part has left the machine. This mode is prevalent in materials handling equipment, such as robots, which necessitate a specific duration to extract components from processing stations and return to their original place. Here, $t_{m}$ is calculated as follows.

   $$\begin{equation*} t_{m} =t_{s} +t_{p} +t_{b} +t_{r} \tag {3}\end{equation*}$$

FIGURE 2.

(a) The concept of the recovery time Mode 1; (b) The concept of the recovery time Mode 2; (c) The concept of the recovery time Mode 3.

B. Four Subproblems of PFSP With SDRT

Three distinct recovery time modalities can be inferred for a certain machine, as detailed in the previous description. A plant often consists of multiple machinery, and four categories of issues can be identified for the overall factory as follows.

1. Subproblem-1. The recovery time modes of all machines in the factory are Mode 1.

2. Subproblem-2. The recovery time modes of all machines in the factory are Mode 2.

3. Subproblem-3. The recovery time modes of all machines in the factory are Mode 3.

4. Subproblem-4. The recovery time mode varies among machines inside the factory. The fourth subproblem is a hybrid kind, exemplifying the most intricate variant of PFSP with SDRT.

SECTION IV. Discrete Event Simulation-Based Optimization Procedure

With advancements in computer science, discrete event simulation technology has emerged as a crucial operational tool for addressing numerous discrete event challenges [23], [24]. The practicality of integrating simulation software with optimization theory to address production issues is effectively illustrated by literature [25]. A combination of discrete event simulation and algorithms has been reported to address specific flowshop scheduling challenges [26], [27].

This paper presents a methodology coupling discrete-event simulation and heuristic algorithm to solve the PFSP with SDRT. The methodology is outlined in FIGURE 3. The crucial difference between this methodology and the traditional method is the application of a simulation model rather than a mathematical model to assess the objective function.

FIGURE 3.

The procedure of the simulation-based optimization methodology.

The point of the method is the design of the simulation environment and the heuristic algorithms. This paper employed a simulation software to create the simulation meta-model of PFSP with SDRT, and the model can be automatically created using a given method. The fundamental contribution of this paper was to develop an integrated interface within the simulation environment, which allows the recovery time matrix, recovery time modes, the number of machines, the number of jobs, and the processing time matrix to be integrated into the simulation model.

Given the sluggish solution speed of this optimization within the simulation environment, there is an increased necessity for an efficient optimization method, with NEH being the most effective algorithm for PFSP [28]. Therefore, this paper selects the NEH_LJP algorithm [16], which is the best NEH-based algorithm currently available.

SECTION V. Computational Results

This section aims to validate the efficacy of the proposed strategy in addressing this issue and to confirm the significance of examining recovery time independently.

The NEH_LJP algorithm was coded in the simulation platform, and all the work was performed using a PC equipped with 4GB of RAM and an i5 5200U CPU operating on Microsoft Windows 10 (64-bit). Also, we designed 18 instances for the four subproblems of PFSP with SDRT, under the random number seed $m \times n$ , with processing time uniformly distributed in [1, 99], recovery time uniformly distributed in [1, 49], and for subproblem 4, the recovery time mode uniformly distributed between [1], [3].

Depending on the description of recovery time in Section III, recovery time affects both PFSPs without blocking and PFSPs with blocking. Therefore, this paper considers two scenarios: infinite buffers and 0 buffers (blocked). To ascertain the importance of evaluating recovery time independently, we subsequently examine an alternative approach in which recovery time is incorporated into the processing time according to Eq. (1), Eq. (2), and Eq. (3), respectively, and resolved as a conventional PFSP without SDRT. Then the distinctions between the two schemes (PFSP with SDRT, and PFSP without SDRT) can be discerned. The above computational results are presented in TABLE 1 and TABLE 2. It should be noted that only the two sub-columns of the same main column are comparable.

TABLE 1 The Makespan of Each Situation Under Infinite Buffer Constraint on the Instances

TABLE 2 The Makespan of Each Situation Under Blocked Constraint on the Instances

To measure the solution quality of each situation, the relative percentage deviation (RPD) is employed as the performance measure:

$$\begin{equation*} RPD=\frac {Cmax_{p} -Cmax_{\textrm {best}}}{Cmax_{\textrm {best}}}\times 100\% \tag {4}\end{equation*}$$ where Cmax_p represents the makespan obtained on problem instance p, and Cmax_best represents the minimum makespan obtained by simulation-based optimization methodology.

Under the infinite buffer constraint, the RPD curves for the two treatments under the four subproblems are presented in FIGURE 4. The average RPD values for the two treatments were 3.08 and 0 in Subproblem-1, as shown in FIGURE 4.(a). The average RPD values for the two treatments were 18.99 and 0 in Subproblem-2, as shown in FIGURE 4.(b). FIGURE 4.(c) illustrates that the average RPD values for the two treatments were 18.99 and 0 in Subproblem-3. The average RPD values for the two treatments were 15.65 and 0 in Subproblem-4, as shown in FIGURE 4.(d). Consequently, in all four subproblems, treating it as a PFSP with SDRT is superior to treating it as a conventional PFSP without SDRT, indicating that including the recovery time into the processing time is significantly biased.

FIGURE 4.

(a) PRD values of Subproblem-1 under infinite buffer constraint; (b) PRD values of Subproblem-2 under infinite buffer constraint; (c) PRD values of Subproblem-3 under infinite buffer constraint; (d) PRD values of Subproblem-mix under infinite buffer constraint.

Under the blocked constraint, the RPD curves for the two schemes under the four subproblems are presented in FIGURE 5. As shown in FIGURE 5, the treatment as PFSP with SDRT was best for each instance across all subproblems. The average RPD values for the four subproblems addressed as PFSP without SDRT were 3.30, 20.79, 17.15, and 15.00, respectively. This indicates that in the PFSP with blocking, integrating recovery time into the processing time and treating it as a standard PFSP without SDRT will significantly impair solution performance.

FIGURE 5.

(a) PRD values of Subproblem-1 under blocked constraint; (b) PRD values of Subproblem-2 under blocked constraint; (c) PRD values of Subproblem-3 under blocked constraint; (d) PRD values of Subproblem-mix under blocked constraint.

Specifically, the computational results reveal that if the recovery time is merged into the processing time and addressed as a normal PFSP without SDRT, the quality of scheduling results under the four subproblems will be reduced by 3.08%, 18.99%, 18.99%, and 15.65%, with an average of 14.18% under an infinite buffer constraint. Will be diminished by 3.30%, 20.79%, 17.15%, and 15.00%, with an average of 14.06% under blocked constraints. In contrast to the majority of literature, which reports a performance enhancement of merely 3-5% for the refined NEH algorithm, the approach utilized in this paper represents a substantial advancement in the current body of knowledge.

Regarding the notion of recovery time, the subsequent two factors may elucidate their potential influence on scheduling outcomes.

1. In PFSP with SDRT, the makespan is defined as the time interval between the release of the first part and to the departure of the last part from the last machine, excluding the elapsed recovery time of the last machine.

2. When under limited or no buffer constraints, the recovery time also affects the machine’s blocked status, which further affects the entire scheduling process.

It can be apparent from FIGURE 4 and FIGURE 5 that the RPD values for large-scale instances are slightly smaller and exhibit a reduced range of variability. It can be inferred that the recovery time has less impact on large-scale instances. The rationale for this may be that the NEH-based algorithm can continuously adjust the intermediate results with the iterative process. The larger the scale, the more iterations the NEH-based algorithm has, and thus the more it can be utilized to mitigate this effect. It is noteworthy that the impact of recovery time on scheduling outcomes is significantly associated with the distinct processes of various heuristic algorithms.

SECTION VI. Case Study

FIGURE 6 depicts the actual factory, demonstrating that a total of 12 processes were necessary to transition from gross stock to finished stock. The production process can be encapsulated as follows.

1. The overall inventory can be broken down into twelve parts that are waiting to be processed during a production run. The parts are initially moved from the gross stock to the rail shuttle by means of frame manipulators. Within the rail shuttle, they are processed by a total of twelve machines in sequential order.

2. The workpieces are automatically conveyed to the machines by short bi-directional transport lines upon their arrival at each process on the main transport line. Upon completion of the procedure, it is conveyed back to the primary transport line through a bidirectional transport line to the subsequent machine.

3. The workpiece may remain on the primary transfer line or short bi-directional transfer line until the subsequent machine becomes available, at which machine it will proceed for machining.

FIGURE 6.

Schematic representation of the actual workshop.

Prior to and subsequent to the operation, those 12 machines may require processing and post-processing operations to guarantee compliance with processing specifications for the subsequent part. This may involve the substitution of knives, the elimination of detritus, and the reinstatement of processing materials.

This paper outlines the aspects of the case study as follows:

1. Upon reaching specific processes, the part must be introduced into the machine for processing, such as during the transmission phase of the bi-directional transmission line, which allows for in-machine processing, thereby allocating setting time for the part in these processes.

2. Upon completion of the part, certain procedures are required to eliminate debris and dissipate heat, necessitating a delay before further processing may occur. The framework manipulator in a specific process can revert to the initial location prior to completing an object’s position transformation, and the part incurs a recovery time during these procedures.

3. The factory’s space is constrained, resulting in a restricted buffer capacity for the machines.

The case study under consideration constitutes a complex PFSP. This problem is characterized by the presence of PFSP with SDRT and varying finite buffer capacity. The processing time of each job on each machine is shown in TABLE 3, the SDST is shown in TABLE 4, the recovery time modes are shown in TABLE 5, the SDRT is shown in TABLE 6, and the capacity of each buffer is shown in TABLE 7. The recovery time mode ‘-’ in TABLE 5 indicates that the recovery time of the workpiece during processing is zero.

TABLE 3 The Processing Time of Each Job on Each Machine (Units: s)

TABLE 4 The Set-Up Time of Each Job on Each Machine (Units: s)

TABLE 5 The Recovery Time Mode of Each Job on Each Machine

TABLE 6 The Recovery Time of Each Job on Each Machine (Units: s)

TABLE 7 The Capacity of Each Buffer

The computational findings have underscored the importance of recovery time analyses. This section demonstrates the superiority of the simulation scheduling approach in digital twins by solving the case utilizing both the simulation scheduling method and the standard mathematical scheduling method.

FIGURE 7 delineates the procedure and distinctions between these two methodologies. The simulation scheduling process is depicted in FIGURE 7.(a) and is addressed by creating a simulation model that accurately mirrors the real situation, as seen in FIGURE 8. Thereafter, scheduling with an optimization algorithm. Nonetheless, the purely mathematical scheduling method (refer to FIGURE 7.(b)) presents difficulties in formulating an exact mathematical model owing to the significant complexity or stochastic nature of the actual situation, which encompasses multiple intricate and interrelated restrictions or parameters. The sole method to advance is to first simplify the existing problem, mathematically model the simplified version, and then resolve it by the same optimization algorithm used in the simulation scheduling process.

FIGURE 7.

The procedure and difference between simulation scheduling and purely mathematical scheduling.

FIGURE 8.

The simulation model of the actual problem.

The findings were examined for a total of three schemes, as depicted in FIGURE 9, where the horizontal axis represents the machining sequence, and the vertical axis denotes the completion time for each part. The job sequence achieved without scheduling, yet organized based on the expertise of industrial engineers, are ${J} _{1}$ -$J_{2}$ -$J_{3}$ -$J_{4}$ -$J_{5}$ -$J_{6}$ -$J_{7}$ -$J_{8}$ -$J_{9}$ -$J_{10}$ -$J_{11}$ -$J_{\mathrm {12}}$ (initial results). The processing sequence obtained by simulation scheduling proposed in this paper is ${J} _{10}$ -$J_{9}$ -$J_{11}$ -$J_{3}$ -$J_{7}$ -$J_{6}$ -$J_{8}$ -$J_{1}$ -$J_{2}$ -$J_{4}$ -$J_{5}$ -$J_{\mathrm {12}}$ (mathmatical results). There is a difference that the job sequence obtained by mathematical scheduling is ${J} _{10}$ -$J_{11}$ -$J_{3}$ -$J_{7}$ -$J_{2}$ -$J_{8}$ -$J_{5}$ -$J_{6}$ -$J_{1}$ -$J_{4}$ -$J_{9}$ -$J_{\mathrm {12}}$ (simulation results). As can be seen from FIGURE 9, the completion time without any scheduling is 4942 seconds, the completion time obtained by the traditional mathematical scheduling method is 4641 seconds, and the completion time obtained via the simulation scheduling method proposed in this paper is 4597 seconds.

FIGURE 9.

The complete time of each order.

The simulation scheduling technique exhibits the shortest maximum completion time, demonstrating a 6.98% reduction compared to empirical sequencing and a 0.95% reduction relative to the mathematical scheduling method. Moreover, the result of simulation scheduling is a more equitable distribution of completion time intervals across the manufacturing process. The findings above illustrate the effectiveness of the simulation scheduling method provided in this paper relative to the traditional mathematical scheduling methodology.

The results of a comprehensive examination are illustrated in FIGURE 10. The histograms illustrating the percentage of each status for each machine under initial scheduling, mathematical scheduling, and simulation scheduling are presented in FIGURE 10.(a), FIGURE 10.(b), and FIGURE 10.(c), respectively. The machine setup times and recovery times are considered integral to the production process and are consequently included in both the employed status and the processing time. As demonstrated in FIGURE 10.(d), the simulation scheduling has been shown to enhance the percentage of effective status of the machine and reduce the percentage of blocking time in comparison to both the initial scheme and mathematical scheduling. Furthermore, the number of machines experiencing blockages was reduced from four to three.

FIGURE 10.

Efficiency of each machine.

The simulation scheduling results are superior to those of mathematical scheduling, demonstrating a total completion time reduction of roughly 0.95% and an increase in effective machine status by approximately 0.4%. However, the increase noted in the actual case study seems to be significantly lower than the minimal benefit shown in the computational results. This is mainly because the recovery time’s order of magnitude is significantly less than the processing time in the case study, and only half of the machines possess a recovery time. Conversely, the original sequence was meticulously designed by industrial engineers with considerable competence, and the improvement resulting from optimization based on a well-conceived beginning scheme would be less pronounced.

SECTION VII. Conclusion

A discrete-event simulation-driven digital twin optimization framework is developed for finding the optimal job sequence. The concept of SDRT is introduced into PFSP for the first time. The computational simulation findings on a benchmark dataset indicate that recovery time significantly influences optimization, enhancing scheduling performance by approximately 14% relative to integrating recovery time into processing time. The empirical case study findings indicate that the suggested simulation-optimization method decreases completion time by 0.95% relative to the conventional mathematical approach in addressing the actual PFSP using SDRT. Those results validate the effectiveness of the digital twin methodology presented in this study, which combines discrete-event simulation with digital twin technology.

This study presents two primary contributions. This paper introduces a discrete event simulation-driven digital twin approach for addressing the PFSP with SDRT, highlighting the effectiveness of this method in tackling real-world challenges. This paper introduces the concept of SDRT into the PFSP for the first time, proposing three classifications of recovery time and four PFSPs with SDRT, which represent significant contributions to the field.

ACKNOWLEDGMENT

The authors would like to thank the editors and anonymous referees for their valuable suggestions and comments. They would also like to thank Mendeley Data for providing a free, open and permanent database. The benchmarks and meta-model of PFSP with SDRT proposed in this article can be accessed from Mendeley Data online by URL: https://data.mendeley.com/datasets/jxntzs86c6/1.