Open AccessArticle

An Adaptive Search Algorithm for Multiplicity Dynamic Flexible Job Shop Scheduling with New Order Arrivals

Linshan Ding

Zailin Guan

¹,

Dan Luo

^1,*

Mudassar Rauf

^2,*

and

Weikang Fang

School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China

College of Mechanical and Electrical Engineering, Wenzhou University, Wenzhou 325060, China

Authors to whom correspondence should be addressed.

Symmetry 2024, 16(6), 641; https://doi.org/10.3390/sym16060641

Submission received: 9 April 2024 / Revised: 14 May 2024 / Accepted: 17 May 2024 / Published: 22 May 2024

(This article belongs to the Special Issue Symmetry in Computing Algorithms and Applications)

Download

Browse Figures

Figure 1
An example of the MDFJSP with new order arrivals. "> Figure 2
(a) A flow diagram of the dynamic scheduling system. (b) A basic flow of the FRAS algorithm. "> Figure 3
An example of public critical operations. "> Figure 4
The trend of the factor level. "> Figure 5
(a) The average makespan of different cases. (b) The interval plot for <math display="inline"><semantics> <mrow> <mi>R</mi> <mi>P</mi> <mi>D</mi> </mrow> </semantics></math> of the five algorithms. (c) The total computation time. (d) The total response time. "> Figure 6
The mean response time of the four algorithms at each rescheduling point on four represent instances. "> Figure 7
The production process of the motorcycle parts manufacturing factory. "> Figure 8
The initial scheduling scheme and rescheduling scheme of Data01 obtained by the FRAS algorithm. "> Figure A1
The average makespan of different static cases and interval plot for <math display="inline"><semantics> <mrow> <mi>R</mi> <mi>P</mi> <mi>D</mi> </mrow> </semantics></math> of the five algorithms. "> Figure A2
The mean convergence curve of LSM-Mk01-LSM-Mk10. "> Figure A3
The impact of the time interval between new orders’ arrival on the objective and the mean total response time (TR). ">

Versions Notes

Abstract

In today’s customer-centric economy, the demand for personalized products has compelled corporations to develop manufacturing processes that are more flexible, efficient, and cost-effective. Flexible job shops offer organizations the agility and cost-efficiency that traditional manufacturing processes lack. However, the dynamics of modern manufacturing, including machine breakdown and new order arrivals, introduce unpredictability and complexity. This study investigates the multiplicity dynamic flexible job shop scheduling problem (MDFJSP) with new order arrivals. To address this problem, we incorporate the fluid model to propose a fluid randomized adaptive search (FRAS) algorithm, comprising a construction phase and a local search phase. Firstly, in the construction phase, a fluid construction heuristic with an online fluid dynamic tracking policy generates high-quality initial solutions. Secondly, in the local search phase, we employ an improved tabu search procedure to enhance search efficiency in the solution space, incorporating symmetry considerations. The results of the numerical experiments demonstrate the superior effectiveness of the FRAS algorithm in solving the MDFJSP when compared to other algorithms. Specifically, the proposed algorithm demonstrates a superior quality of solution relative to existing algorithms, with an average improvement of 29.90%; and exhibits an acceleration in solution speed, with an average increase of 1.95%.

Keywords:

multiplicity dynamic flexible job shop scheduling; dynamic fluid model; online fluid dynamic tracking policy; fluid randomized adaptive search algorithm

1. Introduction

The individualized requirements in the market are increasing, which is placing higher demands on manufacturing systems [1,2]. To remain competitive, companies are increasing the flexibility of their manufacturing systems [3,4]. However, flexibility in the manufacturing environment can lead to increased complexity, posing challenges for production managers when making decisions [5,6]. Industry 4.0 has led to the emergence and evolution of various technologies that support decision-making in manufacturing systems [7,8]. This enables continuous iteration and upgrading of both hardware and software in manufacturing systems. Benefiting from the support and maturity of these technologies, dynamic scheduling has become a trend of general interest for enterprises and researchers. Compared to traditional scheduling, dynamic scheduling is more adaptable [9,10,11]. Specifically, the dynamic flexible job shop scheduling problem (DFJSP) is considered more valuable than the traditional job shop scheduling problem (JSP) [12,13]. This is because it encapsulates most of the scheduling challenges of high-mix, low-volume production in modern discrete manufacturing systems. Moreover, it deals with uncertainties inherent in the production environment, such as fluctuating demand, machine downtime, and unpredictable lead times [14].

Among the various iterations of the standard DFJSP, the multiplicity dynamic flexible job shop scheduling problem (MDFJSP) stands out as particularly applicable to manufacturing systems characterized by a significant volume of identical or similar jobs that can be grouped in the production process. Industries such as semiconductor manufacturing and motorcycle component production serve as prime examples of such systems [15,16,17]. Addressing the MDFJSP can assist production managers in increasing throughput, decreasing lead times, minimizing machine downtime, and maximizing resource utilization. Enterprises can enhance their market competitiveness by effectively managing the scheduling of multiple job instances, which can increase productivity and enable prompt response to customer requirements. The literature contains extensive research on the DFJSP, but few studies have addressed the MDFJSP [18,19,20]. Ding et al. (2022) [21] proposed a fluid master-apprentice evolutionary method to address the multiplicity flexible job shop scheduling problem, and Ding et al. (2024) [22] presented a multi-policy deep reinforcement learning method for multi-objective multiplicity flexible job shop scheduling problem. But these two papers are only applicable to static scheduling problems, and are not suitable for addressing dynamic scheduling challenges.

To fill this research gap, we investigate the MDFJSP with new order arrivals. The inclusion of numerous new jobs in new orders is more indicative of actual production scenarios [23]. However, new order arrivals frequently generate numerous new positions, leading to an extensive solution space that challenges achieving high-quality solutions. The current methods, such as meta-heuristics and dispatching rules for the DFJSP, have been observed to have shortcomings in terms of time efficiency and long-term solution quality [24,25,26]. The current literature indicates that fluid models can rapidly identify near-optimal solutions in the context of multiplicity job shop scheduling. Therefore, we propose a new algorithm called the fluid randomized adaptive search (FRAS) algorithm for the MDFJSP, by incorporating a fluid model. The FRAS algorithm integrates a fluid model-based approach named the fluid construction heuristic (FCH) with the GRAS framework. The main function of the FCH in this algorithm is to optimize the initial solution. By incorporating the FCH, which captures the system’s continuous dynamics, the FRAS algorithm offers a more robust and adaptive solution approach for the MDFJSP. The results of numerical experiments prove this novel algorithm can efficiently generate high-quality scheduling schemes for the MDFJSP with varying problem scales in a reasonable computation time. This study makes the following key contributions.

(1): We propose a fluid randomized adaptive search algorithm for addressing the MDFJSP, effectively bridging the existing research gap in this area.
(2): A dynamic fluid model is developed for the first time to address the MDFJSP with new order arrivals.
(3): The proposed FRAS algorithm surpasses existing algorithms due to two design features. Firstly, we developed a fluid construction heuristic that incorporates an online fluid dynamic tracking policy to optimize the initial solution. Secondly, we propose a tabu search procedure based on the public critical operation to enhance the efficiency of the solution space search.

The following sections of this article are structured as follows: Section 2 reviews the related papers. Section 3 describes the MDFJSP and introduces a mathematical model along with an illustrative example. Section 3 delineates the FRAS algorithm. Section 4 provides the results and analyses. Finally, we summarize this article in Section 5, and outline future directions and recommendations.

2. Literature Review

This section provides a review of the relevant work, which consists of two main parts. Due to the scarcity of research on the MDFJSP, the first part focuses on methodologies used to solve the FJSP. The second part reviews the current state of research on fluid modeling in scheduling.

2.1. Methodologies for the FJSP

To solve FJSPs, researchers have proposed various optimization strategies, including dispatching rule-based, and meta-heuristic. Even though exact solution methods can produce the optimal solution to a problem, their complexity makes it difficult to obtain viable solutions in a reasonable timeframe [27]. Dispatching rules are widely used to address FJSPs in practical production systems [28]. However, choosing a specific dispatching rule for a particular problem is complex. Therefore, numerous methods to extract and select dispatching rules for FJSPs have been presented by researchers [29]. Furthermore, many researchers have extracted dispatching rules using the genetic programming-based method to solve the DFJSP with particular constraints [30,31]. Although dispatching rules are easy to implement, they often exhibit myopic behavior, which means they may not guarantee to reach a local optimum in the long run [32].

In addition to dispatching rule-based methods, many meta-heuristics have been proposed to generate feasible and promising schedule schemes [33,34]. Meta-heuristics can achieve new near-optimal solutions by utilizing global information at each rescheduling point [35,36]. However, these methods often encounter challenges in terms of time efficiency, primarily attributed to their intricate evolutionary processes and search methods in an expansive search space [37,38,39]. This limitation hinders their application in manufacturing systems, where new disturbances may happen unexpectedly, even before a new rescheduling scheme has been established. For more information about meta-heuristic-based methods, refer to the overview literature by Xie et al. (2019) [40].

2.2. Fluid Model

The fluid model was first proposed by Chen (1993) [41] to address the dynamic scheduling challenges associated with multiple classes of fluid traffic. The fluid model method offers a robust mathematical framework for analyzing and solving job shop scheduling problems with multiplicity characteristics [42,43,44,45]. By representing the discrete scheduling problem as a continuous fluid model, researchers can gain valuable insights into system behavior by analyzing the performance measures and developing optimization techniques. Fluid models are deterministic, continuous approximations of stochastic. Several researchers have effectively employed fluid models in both static and dynamic JSP [45,46]. However, most of the existing literature works have primarily focused on addressing the JSP. When it comes to the FJSP, applying the fluid model approach becomes more challenging due to the additional complexities involved in decision-making and representation.

Because of the limited literature on the fluid model in FJSPs, we just can conduct a comprehensive analysis of the existing literature on fluid modeling in JSPs. Table 1 analyzes the application of fluid models in JSP from three key perspectives: problem type, problem scale, and objective function. Our findings indicate that fluid models are primarily used in JSP research to obtain approximate solutions in a relatively short time frame. Consequently, they are often combined with other heuristic algorithms to enhance the efficiency of the algorithmic solution. The existing research primarily concerns deterministic problems [42,44,47,48,49], with only very few papers addressing stochastic problems [45,50]. Fluid modeling can rapidly resolve large-scale problems in certain specific contexts. However, its application is contingent on certain parameters, which means that it is applicable to a limited number of practical scenarios and some scenarios are not applicable.Furthermore, a review of the existing literature reveals that most studies on fluid models are conducted in the context of JSPs with high multiplicity [43,44]. The application of the fluid model in these papers remains constrained, and the scenarios in which the fluid model is applicable are not sufficiently discussed. This represents an avenue for further exploration.

Despite the extensive research on DFJSPs, there is a lack of studies specifically addressing the multiplicity of characteristics of DFJSPs. This research gap highlights the need to develop an optimization model and propose an efficient solution approach for addressing the complexities introduced by multiplicity in DFJSPs. By considering the unique challenges posed by multiplicity, future research efforts can contribute to the advancement of scheduling methodologies and provide valuable insights for optimizing the performance of DFJSPs in practical manufacturing environments.

3. Problem Description

This article studies a special variant of the DFJSP called the multiplicity dynamic flexible job shop scheduling problem (MDFJSP). In MDFJSPs, multiple jobs are permitted for any job type. It consists of M machines, S orders with random arrival times, and R job types. Each job type r comprises

J_{r}

several operations. All jobs are classified into a total of R unique types. The orders s arrive randomly, containing

N_{s r}

jobs for job type r. The job quantity belonging to a specific job type r in order s is called its multiplicity (

N_{s r} \geq 1

). In the actual manufacturing environment, the arrival of new orders containing multiple jobs for each job type follows the Poisson distribution [51], which means the time interval between new orders’ arrival obeys an exponential distribution [52]. Rescheduling occurs when a new order s arrives at

A_{s}

, serving as the rescheduling point. All operations are divided into four sets: completed, being processed, unprocessed, and new arrived operations. To handle complexity, some assumptions were made:

(1): Machines are assumed to be ready for operation at the beginning of the time horizon.
(2): The same type of jobs can be processed on a specified series of machines. However, it is not permitted for any given machine to perform more than one operation simultaneously.
(3): Operations must be completed without interruption.
(4): Operations must be conducted in a specified order, with no operation starting before the previous one has finished.
(5): Setup times between operations are not considered.

The mathematical model uses the following notations:

Notation	Description
Indexes:
s	Orders, $s = 1, 2, \dots, S$ .
m	Machines, $m = 1, 2, \dots, M$ .
$r, r^{'}$	Job types, $r, r^{'} = 1, 2, \dots, R$ .
$n, n^{'}$	Jobs belonging to job types r and $r^{'}$ , $n = 1, 2, \dots, N_{r}$ , $n^{'} = 1, 2, \dots, N_{r^{'}}^{'}$ .
$j, j^{'}$	Operations of job types r and $r^{'}$ , $j = 1, 2, \dots, J_{r}$ , $j^{'} = 1, 2, \dots, J_{r^{'}}^{'}$ .
Parameters:
R	The number of job types.
M	The number of machines.
$J_{r}$	The operation quantity of job type r.
$J_{r n}$	Job $n t h$ of type r.
$o_{r n j}$	Operation $j t h$ of the job $n t h$ pertaining to job type r.
$o_{r j}$	Operation $j t h$ of type r.
$t_{r j m}$	The processing time for operation $o_{r j}$ on machine m.

Notation	Description
Sets:
$M_{m}$	The complete set of machines, $M_{m} = {1, 2, \dots, M}$ .
$M_{r j}$	The specific set of machines that are eligible to perform the operation $o_{r j}$ .
$R_{r}$	The set of all job types, $R_{r} = {1, 2, \dots, R}$ .
$I_{r}$	The set of all jobs belonging to type r, $I_{r} = {1, 2, \dots, N_{r}}$ .
$O_{r}$	The set of all operations belonging to job type r, $O_{r} = {1, 2, \dots, J_{r}}$ .
$O_{R J}$	The complete set of operations belonging to all job types, $O_{R J} = {o_{r j} ∣ r \in R_{r}, j \in O_{r}}$ .
$O_{m}^{R J}$	The set of operations that machine m can perform, $O_{m}^{R J} = {o_{r j} ∣ r \in R_{r}, j \in O_{r}, m \in M_{r j}}$ .
Variables:
S	The quantity of new orders.
$A_{s}$	The arrival time of order s; order $s = 1$ is the first order, and $A_{1} = 0$ .
$D_{s}$	The due date of order s.
$d_{r n}$	The due date of job $J_{r n}$ ; $d_{r n} = D_{s}$ if $z_{r n s} = 1$ .
$N_{s r}$	The total job quantity of job type r in order s.
$N_{s}$	The total job quantity in order s, $N_{s} = \sum_{r = 1}^{R} N_{s r}$ .
$N_{r}$	The total job quantity of job type r in all orders, $N_{r} = \sum_{s = 1}^{S} N_{s r}$ .
N	The number of jobs in all orders, $N = \sum_{s = 1}^{S} N_{s}$ .
$c t_{r n j}$	The completion time of operation $o_{r n j}$ .
Decision variables:
$x_{r n j m}$	$x_{r n j m} = \{\begin{matrix} 1, & if o_{r n j} is assigned on machine m . \\ 0, & otherwise . \end{matrix}$
$y_{r n j r^{'} n^{'} j^{'}}$	$y_{r n j r^{'} n^{'} j^{'}} = \{\begin{matrix} 1, & if o_{r n j} is a predecessor of o_{r^{'} n^{'} j^{'}} . \\ - 1, & if o_{r n j} is a successor of o_{r^{'} n^{'} j^{'}} . \end{matrix}$
$z_{r n s}$	$z_{r n s} = \{\begin{matrix} 1, & if job J_{r n} belongs to order s . \\ 0, & otherwise . \end{matrix}$

We describe the mathematical model as follows:

min C_{\max} = \min (\max {c t_{r n j} ∣ r \in R_{r}, n \in I_{r}, j \in O_{r}})

(1)

Subject to:

\begin{matrix} c t_{r n 0} = 0, c t_{r n j} > 0, \forall r, n, j \end{matrix}

(2)

\sum_{m \in M_{r j}} x_{r n j m} = 1, \forall r, n, j

(3)

\sum_{s = 1}^{S} z_{r n s} = 1, \forall r, n

(4)

(c t_{r n j} - t_{r j m} - c t_{r, n, j - 1}) x_{r n j m} \geq 0, \forall r, n, j, m

(5)

(c t_{r n j} - t_{r j m} - A_{s}) z_{r n s} x_{r n j m} \geq 0, \forall r, n, j, m, s

(6)

\begin{matrix} (c t_{r^{'} n^{'} j^{'}} - t_{r^{'} n^{'} m} - c t_{r n j}) x_{r n j m} x_{r^{'} n^{'} j^{'} m} (y_{r n j r^{'} n^{'} j^{'}} + 1) + \\ (c t_{r n j} - t_{r n m} - c t_{r^{'} n^{'} j^{'}}) x_{r n j m} x_{r^{'} n^{'} j^{'} m} (1 - y_{r n j r^{'} n^{'} j^{'}}) \geq 0, \forall r, r^{'}, n, n^{'}, j, j^{'}, m \end{matrix}

(7)

Equation (1) represents the objective of minimizing the maximum completion time in the mathematical model, where

C_{max}

means the maximum completion time, i.e., the makespan. Equation (2) implies that the completion time of each operation is non-negative. Equation (3) indicates that each operation can be assigned to only one available machine. Equation (4) indicates that each job belongs to only one order. Equation (5) states the precedence constraint of operations for each job, while Equation (6) ensures jobs are processed only upon arrival. Equation (7) ensures that the scheduling schemes are feasible for the capacity of machines.

To facilitate comprehension for the reader, Table 2 provides an illustrative example of MDFJSP with two new orders and three machines. Initially (in order 1), each job type is allocated a specific number of available positions. The dynamic scheduling system then implements the schedule until the next order arrives. The process of dynamic scheduling is repeated until all jobs have been completed.

Figure 1 presents the details of the example of the MDFJSP. Figure 1a illustrates that two task types, r = 1, 2, are processed on three machines, m = 1, 2, 3. In addition, six jobs, 11, 12, 13, 21, 22, and 23, in order one must be planned, and order two includes four new jobs, 14, 15, 24, and 25, which come at time 50. First, we establish the scheduling scheme based on the first order, as depicted in Figure 1a. At time 50, the ongoing activities 222, 122, and 113 are not halted, but rather the rescheduling procedure is initiated when order number two arrives. All non-processed operations are rescheduled following the proposed DA3C once a rescheduling process commences. Consequently, 19 operations must be scheduled for time 50 (Reschedule point). Figure 1b depicts the new schedule scheme acquired following the arrival of the second order.

4. Fluid Randomized Adaptive Search Algorithm

In the construction phase of the fluid randomized adaptive search (FRAS) algorithm, the fluid construction heuristic (FCH) method is used to construct a solution step by step, considering symmetry. For each decision time, one operation and one corresponding available machine are selected according to the online fluid dynamic tracking policy. D solutions are constructed with the FCH. Then, the proposed tabu search procedure improves the best solution of the D solutions. Figure 2 presents the flow diagram of dynamic scheduling systems and the basic flow of the FRAS algorithm.

4.1. Construction Phase

4.1.1. Dynamic Fluid Model and Control Problem

The proposed dynamic fluid model has the advantage of being a linear programming model that can be easily solved using CPLEX. We define the solution of the fluid model as a fluid solution. The solution of the fluid model is called the fluid solution. In the dynamic fluid model, the operation

o_{r j}

is represented as fluids

k_{r j}

. Then, the set of all operations of all job types can be represented as fluid set

F = {k_{r j} ∣ r \in R_{r}, j \in O_{r}}

. The dynamic fluid model provides a fluid solution, which is a time proportion

{u_{m k_{r j}} \in R ∣ 0 \leq u_{m k_{r j}} \leq 1, m \in M_{m}, k_{r j} \in F}

that each machine devotes to each fluid. Here, we illustrate with a simple example. If machine m is equipped to perform the set of operations

{o_{11}, o_{12}, o_{21}}

. After solving the fluid model, the deduced optimal time fractions that machine m spends on each operation are

{u_{m k_{11}} = 0.3, u_{m k_{12}} = 0.4, u_{m k_{21}} = 0.2}

. The interpretation of these fractions is such that for each unit of time,

30 %

40 %

, and

20 %

of that duration is allocated by machine m for performing operations

o_{11}

o_{12}

, and

o_{21}

, respectively. The details of the dynamic fluid model are as follows:

Notations	Description
Indexes:
$k_{r j}$	The fluid which represents the operation $o_{r j}$ in the dynamic fluid model.
Parameters:
$e_{m k_{r j}}$	The processing rate of fluid $k_{r j}$ on machine m.
$e_{k_{r j}}$	The total processing rate of fluid $k_{r j}$ , $e_{k_{r j}} = \sum_{m = 1}^{M} e_{m k_{r j}} u_{m k_{r j}}$ .
Sets:
F	The set of fluids, $F = {k_{r j} ∣ r \in R_{r}, j \in O_{r}}$ .
$F_{m}$	The subset of fluids that machine m can process, $F_{m} = {k_{r j} ∣ r \in R_{r}, j \in O_{r}, o_{r j} \in O_{m}^{R J}}$ .
$M_{k_{r j}}$	The subset of machines that can process fluid $k_{r j}$ , $M_{k_{r j}} = {m ∣ m \in M, m \in M_{r j}}$ .
Variables:
$u_{m k_{r j}}$	The proportion of processing time that machine m devotes to fluid $k_{r j}$ .
$c_{k_{r j}}$	The completion time of fluid $k_{r j}$ .
$q_{k_{r j}} (t)$	The amount of fluid $k_{r j}$ at time t.
$Q_{r j} (t)$	The job quantity in operation stage $o_{r j}$ at time t.
$q_{k_{r j}}^{+} (t)$	The total amount of fluid $k_{r j}$ not processed at time t.
$Q_{r j}^{+} (t)$	The total job quantity in operation $o_{r j}$ not processed at time t.
$q_{m k_{r j}}^{+} (t)$	The total amount of fluid $k_{r j}$ not processed by machine m at time t.
$Q_{m r j}^{+} (t)$	The total job quantity in operation $o_{r j}$ not processed by machine m at time t.

After the arrival of order s and before the arrival of order

s + 1

, the dynamic fluid model satisfies the following Equations (8)–(16). Obviously, the time

t \in [A_{s}, A_{s + 1})

. Equation (8) means the number of fluid

k_{r j}

at time t. The number of fluid

k_{r j}

that has not yet been processed can be calculated as Equation (9). The number of the fluid

k_{r j}

that has not yet been processed by machine m can be calculated as Equations (10) and (11). The computation time of each fluid k is shown in Equation (12). Equation (13) indicates that the utilization rate must be less than 100% for each machine. Equation (14) demonstrates that if

q_{k_{r j}} (A_{s}) = 0

, then the total processing rate of fluid

k_{r j}

is no more than its arrival rate. This makes

q_{k_{r j}} (t) \geq 0

, which ensures that the fluid solution is feasible. Equation (15) denotes the range of decision variables.

q_{k_{r j}} (t) = \{\begin{matrix} q_{k_{r j}} (A_{s}) + (t - A_{s}) (e_{k_{r, j - 1}} - e_{k_{r j}}), & \forall k_{r j} \in F, j \geq 2 \\ q_{k_{r j}} (A_{s}) - (t - A_{s}) e_{k_{r j}}, & \forall k_{r j} \in F, j = 1 \end{matrix}

(8)

q_{k_{r j}}^{+} (t) = q_{k_{r j}}^{+} (A_{s}) - (t - A_{s}) e_{k_{r j}}, \forall k_{r j} \in F

(9)

q_{m k_{r j}}^{+} (A_{s}) = q_{k_{r j}}^{+} (A_{s}) \frac{e_{m k_{r j}} u_{m k_{r j}}}{e_{k_{r j}}}, \forall k_{r j} \in F, m \in M_{k_{r j}}

(10)

q_{m k_{r j}}^{+} (t) = q_{m k_{r j}}^{+} (A_{s}) - (t - A_{s}) e_{m k_{r j}} u_{m k_{r j}}, \forall k_{r j} \in F, m \in M_{k_{r j}}

(11)

c_{k_{r j}} = \frac{q_{k_{r j}}^{+} (A_{s})}{e_{k_{r j}}}, \forall k_{r j} \in F

(12)

\sum_{k_{r j} \in F} u_{m k_{r j}} \leq 1, \forall m \in M_{m}

(13)

e_{k_{r j}} \leq e_{k_{r, j - 1}}, \forall k_{r j} \in F, j \geq 2, q_{k_{r j}} (A_{s}) = 0

(14)

u_{m k_{r j}} \in [0, 1], \forall k_{r j} \in F, m \in M_{k_{r j}}

(15)

The dynamic fluid model aims to minimize the maximum completion time at each rescheduled point

A_{s}

, which is shown in Equation (16).

C_{f}^{s} = min \{max \{c_{k_{r j}} | k_{r j} \in F\}\}

(16)

Note that we must solve the dynamic fluid model based on both the unprocessed operations and the new operations when order s arrives at the time

A_{s}

. Therefore, the fluid solution changes dynamically with the arrival of new orders.

4.1.2. Online Fluid Dynamic Tracking Policy

The dynamic fluid model above offers a fluid solution for each rearrangement point

A_{s}

. The fluid solution only specifies the fraction of time devoted to a particular operation

o_{r j}

on machine m, but does not specify the job sequence for each machine. However, the dynamic flexible job shop scheduling is a process in a discrete manufacturing environment, and job sequencing must be considered along with machine assignment. Consequently, to construct high-quality discrete solutions, the fluid solution needs to transform into a policy that can guide us to finish selecting an operation and assigning it to an available machine. To generate the policy, two metrics are defined to measure the similarity between the constructed discrete and fluid solutions.

Fluid-Gap: At time t, the gap between the total job quantity that operation $o_{r j}$ has not been processed and the amount of fluid $k_{r j}$ , which has not been processed, is calculated as follows:

{gap}_{r j} (t) = \frac{Q_{r j}^{+} (t) - q_{k_{r j}}^{+} (t)}{q_{k_{r j}}^{+} (A_{s})}, \forall k_{r j} \in F

(17)

Fluid–Machine-Gap: At time t, the gap between the total job quantity with operation $o_{r j}$ not processed by machine m and the number of fluid $k_{r j}$ not processed by machine m is calculated as follows:

{gap}_{m r j} (t) = \frac{Q_{m r j}^{+} (t) - q_{m k_{r j}}^{+} (t)}{q_{m k_{r j}}^{+} (A_{s})}, \forall k_{r j} \in F, m \in M_{k_{r j}}

(18)

In Equation (17),

Q_{r j}^{+} (t)

is related to the construction state of the discrete solution at time t. The

{gap}_{r j} (t)

indicates a gap between the constructed discrete solution and the fluid solution. In Equation (18),

Q_{m r j}^{+} (t) = q_{m k_{r j}}^{+} (A_{s}) - Q_{m r j}^{-} (t)

, the parameter

Q_{m r j}^{-} (t)

is the number of the operation

o_{r j}

that has been processed by machine m at time t. Therefore,

Q_{m r j}^{-} (t)

is related to the construction state of the discrete solution at time t. The

{gap}_{m r j} (t)

indicates a gap between the processing state of the operation

o_{r j}

on machine m in the constructed discrete solution and that in the fluid solution. Based on the two defined metrics, an online fluid dynamic tracking policy is designed, consisting of two steps: operation selection and machine selection.

Operation selection step: At decision point t, one operation $o_{r^{'} n^{'} j^{'}}$ is selected according to Equations (19) and (20).

o_{r^{'} j^{'}} \leftarrow {o_{r j} ∣ o_{r j} \in O_{R J} (t), {gap}_{r j} (t) \geq {gap}^{*} (t)}_{random}

(19)

o_{r^{'} n^{'} j^{'}} \leftarrow {o_{r^{'} n^{'} j^{'}} ∣ n \in I_{r^{'} j^{'}} (t)}_{min_{ct}_{r^{'}, n^{'}, j^{'} - 1}}

(20)

In Equation (19),

O_{R J} (t)

is the operation set that is available processed by idle machines.

O_{R J} (t) = {o_{r j} ∣ m \in M_{idle} (t), o_{r j} \in O_{m}^{R J}, Q_{r j} (t) > 0}

M_{idle} (t)

is the set of idle machines,

Q_{r j} (t) > 0

means there are jobs in the operation stage

o_{r j}

, so operation

o_{r j}

is selectable. In this step, the operation

o_{r^{'} j^{'}}

is selected randomly based on Equation (19), in which a threshold value

{gap}^{*} (t) = {gap}^{-} (t) + b ({gap}^{+} (t) - {gap}^{-} (t))

. The parameters

{gap}^{-}

and

{gap}^{+}

are the minimum and maximum

{gap}_{r j} (t)

value of all operations belongs to

O_{R J} (t)

, b is applied to balance the stochasticity and covetousness. However, due to the multiplicity of our research problem, there may be multiple jobs in the operation stage

o_{r^{'} j^{'}}

. In Equation (20),

I_{r^{'} j^{'}} (t)

is the set of jobs in the operation stage

o_{r^{'} j^{'}}

. Therefore, the operation

o_{r^{'} n^{'} j^{'}}

, which has the minimum

{ct}_{r^{'}, n, j^{'} - 1}

value, is selected according to Equation (20). The job

n^{'}

which is the first arrival operation stage

o_{r^{'} j^{'}}

is selected.

Machine selection step: The machine $m^{'}$ is selected to process the selected operation $o_{r^{'} n^{'} j^{'}}$ at the operation selection step.

m^{'} \leftarrow {{m ∣ m \in M_{r^{'} j^{'}} \cap M_{idle} (t)}_{max_{gap}_{m r^{'} j^{'}} (t)}}

(21)

Based on Equation (21), where

m^{'}

with the maximum value of

{gap}_{m r^{'} j^{'}} (t)

is chosen to perform operation

o_{r^{'} n^{'} j^{'}}

4.1.3. The Fluid Construction Heuristic Method

Once new order s arrives at the time

A_{s}

, the dynamic fluid model is resolved to obtain the fluid solution. Then, the FCH is used to construct D high-quality initial solutions at the rescheduling point

A_{s}

. Pseudo-code Algorithm 1 illustrates the detailed steps of the FCH.

O_{s}^{R N J}

is the set of operations that contain the unprocessed operations and the new operations at the rescheduling point

A_{s}

O_{R N J} (t)

is the set of unprocessed operations for all jobs at time t.

D_{F C H} = {d_{1}, \dots, d_{D}}

is the set of initial solutions constructed by the FCH, in which

d_{i}

is the ith solution.

4.2. Local Search

Tabu search has been used effectively in diverse scheduling problems since it was proposed by Glover (1990) [53]. In the local search phase of the FRAS algorithm, an improved tabu search (ITS) procedure is presented to improve the feasible solutions obtained with the FCH. In the ITS, neighborhood solutions are formed by relocating a public critical operation to a different machine and repositioning a public critical operation on the same machine. In the disjunctive graph representation of the current solution, the longest path is the critical path and each operation on the critical path is a critical operation. However, the current solution may have more than one critical path. Then, the operation is a public critical operation if it belongs to all the critical paths [54]. For example, in Figure 3, three public critical operations belong to two critical paths 111, 112, 211.

Algorithm 1 The fluid construction heuristic method.

Require:: $D_{F C H}$
Ensure:: $D_{F C H}$
1:: Initialization:
2:: Solve the dynamic fluid model and obtain the fluid model.
3:: The set of initial solutions: $D_{F C H} \leftarrow \emptyset$ .
4:: for $i = 1$ to D do
5:: The current time: $t \leftarrow A_{s}$ .
6:: Next idle time of all machines: ${{time}_{idle}^{m} | m \in M_{m}}$ .
7:: $O_{R N J} (t) \leftarrow O_{s}^{R N J}$ . // Construct a solution $d_{i}$ with the online fluid dynamic tracking policy.
8:: while $O_{R N J} (t) \neq \emptyset$ // If there are operations that have not been assigned. do
9:: if $O_{R J} (t) = \emptyset$ // If no operations can be selected at the current decision point t.
then
10:: // Move the time to the next decision point.
11:: $t \leftarrow min {{time}_{idle}^{m} | m \in M_{m}}$ .
12:: else
13:: //Select the operation $o_{r^{'} n^{'} j^{'}}$ according to the operation selection step.
14:: $o_{r^{'} j^{'}} \leftarrow {o_{r j} | o_{r j} \in O_{R J} (t), {gap}_{r j} (t) \geq {gap}^{*} (t)}_{random}$ .
15:: $o_{r^{'} n^{'} j^{'}} \leftarrow {o_{(r^{'} n j^{'})} | n \in I_{(r^{'} j^{'})} (t)}_{min_{ct}_{r^{'}, n, j^{'} - 1}}$ .
16:: //Select machine $m^{'}$ to perform operation $o_{r^{'} n^{'} j^{'}}$ .
17:: $m^{'} \leftarrow {m | m \in M_{r^{'} j^{'}} \cap M_{idle} (t)}_{max {gap}_{m r^{'} j^{'}} (t)}$ .
18:: // Update the unprocessed operations set $O_{R N J} (t)$ .
19:: Remove the operation $o_{r^{'} n^{'} j^{'}}$ from $O_{R N J} (t)$ .
20:: // Update the next idle time of machine $m^{'}$ .
21:: ${time}_{idle}^{m^{'}} \leftarrow {time}_{idle}^{m^{'}} + t_{r^{'} j^{'} m^{'}}$ .
22:: end if
23:: end while
24:: Add the constructed solution $d_{i}$ to $D_{F C H}$ .
25:: end for
26:: return $D_{F C H} = {d_{1}, \dots, d_{D}}$ .

In the ITS, a public critical operation is reallocated on the same machine based on the neighborhood structure

N^{π}

[55] and move a critical operation to another machine and insert it into a feasible position according to the neighborhood structure

N_{1}^{(α - ρ)}

[56]. Moreover, the makespan estimate approach [56] is adopted to estimate the neighborhood quality for accelerating the local search. The procedure of the ITS is outlined in Algorithm 2.

Algorithm 2 The improved tabu search algorithm.

Require:: The best solution $d^{*}$ in the set $D_{F C H}$ .
Ensure:: The best solution $d_{b e s t}$ .
1:: Initialize the maximum iteration number ${i t e r}_{s t o p}$ .
2:: Initialize the count of iterations without improvement in the optimal solution: ${i t e r}_{n u m b e r} \leftarrow 0$ .
3:: while ${i t e r}_{n u m b e r} < {i t e r}_{s t o p}$ do
4:: The neighborhood structures $N^{π}$ and $N_{1}^{(α - ρ)}$ are selected with the same probability to generate neighborhood solutions.
5:: Estimate the makespan of all neighborhood solutions.
6:: if the criteria for aspiration is fulfilled then
7:: ${i t e r}_{n u m b e r} \leftarrow 0$ .
8:: Update both the current solution $d^{*}$ and the best solution $d_{b e s t}$ .
9:: else
10:: ${i t e r}_{n u m b e r} \leftarrow {i t e r}_{n u m b e r} + 1$ .
11:: Choose the best no-tabu solution from all neighborhood solutions as the current solution.
12:: end if
13:: Update the tabu list.
14:: end while
15:: return the best solution $d_{b e s t}$ .

4.3. Implementation

Pseudo-code Algorithm 3 details the procedure of the proposed FRAS algorithm. The FRAS algorithm obtains the best solution

d_{g l o b a l}^{s}

at the rescheduling point

A_{s}

Algorithm 3 The FRAS algorithm.

1:: for $s = 1$ to S do
2:: New orders arrival.
3:: New order s arrive at the time $A_{s}$ and trigger the rescheduling.
4:: Update the set $O_{s}^{R N J}$ .
5:: while the termination condition is not fulfilled do
6:: Generate D initial feasible solution of order s with Algorithm 2.
7:: ${d_{1}, d_{2}, \dots, d_{D}} \leftarrow FCH ()$ .
8:: Select the best solution from $D_{F C H}$ .
9:: $d^{*} \leftarrow {d_{1}, \dots, d_{D}}_{min makespan}$ .
10:: Improve the solution ${solution}_{s}$ with Algorithm 3.
11:: $d_{b e s t} \leftarrow ITS (d^{*})$ .
12:: Update the best solution $d_{global}^{s}$ .
13:: $d_{global}^{s} \leftarrow {d_{global}^{s}, d_{b e s t}}_{min makespan}$ .
14:: end while
15:: Execute the solution $d_{global}^{s}$ in the dynamic scheduling system.
16:: end for

5. Experiments and Results

In this section, various experiments are performed to compare the efficiency and effectiveness of the FRAS algorithm. First, dynamic cases are designed to verify the performance of the FRAS algorithm. Second, the FRAS algorithm is applied to the real-world manufacturing plant case study. In practical dynamic environments, achieving satisfactory solutions quickly is crucial. Therefore, the termination condition is established as a CPU time limit of

n_{s} \times M \times t

milliseconds. Here,

n_{s}

represents the total quantity of jobs pending rescheduling at point s, M represents the count of machines, and t stands for a pre-defined constant (assigned the value of 200 in the experimental setups). All algorithms undergo 30 independent executions on each case, using a PC equipped with an Intel(R) Core(TM) i5-9300 CPU @ 2.40 GHz and 8 GB RAM, and implemented in Python 3.6. Furthermore, the MDFJSP instances (

M D 01 - M D 12

) were generated based on real-world problem scenarios. Table 3 presents the generation parameters for instances. In Table 3, ‘randi’ denotes the uniform distribution of integer numbers.

5.1. Parameter Settings

Parameter selection plays a crucial role in algorithm performance. Three parameters affect the efficiency of the proposed FRAS algorithm. In this section, we calibrate the algorithm parameters with the Taguchi method for the design of experiments (DOE) [57]. The DOE is an effective and efficient investigative method widely used to evaluate the effect of multiple factors on different algorithms. The three parameters {D,

{i t e r}_{s t o p}

, b} define the FRAS. D is the number of generated initial feasible solutions with the FCH method for each iteration of the FRAS algorithm,

{i t e r}_{s t o p}

is the permitted maximum iteration number with no improvement of ITS, and b is the

α

parameter, which used to balance the stochasticity and covetousness of the proposed algorithm. Ten randomly generated instances are selected to identify the effect of the three parameters. The parameter D has four possible values: {10,20,40,80}, the parameter

{i t e r}_{s t o p}

can be {10,20,30,40}, and the parameter b can be {0.1,0.2,0.3,0.4}. As shown in Table 4, the parameter combinations are represented with the orthogonal array

L_{16}

. The average makespans

C_{a v g}

of 10 instances, obtained through 30 independent runs of the FRAS, are used as the response values in our analysis. Figure 4 illustrates the trend in factor levels. Figure 4 shows that the FRAS algorithm with control parameters of

{i t e r}_{s t o p} = 40

D = 40

, and

b = 0.3

, performs better.

5.2. Validation of Proposed Methods

We conduct a set of experiments to assess the effectiveness of the proposed FCH and ITS methods in the FRAS framework for solving instances of the MDFJSP. Table 5 summarizes the experimental results. Two variants of the FRAS algorithm are considered:

F R A S_R A N D O M

, which is a variant obtained by replacing the FCH with a random initialization method in the FRAS framework, and

F R A S_T S

, which is a variant obtained by replacing the ITS with a classical tabu search (TS) procedure in the FRAS algorithm. The performance of these variants is compared and analyzed to assess the impact of the FCH and ITS methods in the FRAS framework.

Table 5 presents data on the best and average makespan for each algorithm in the “

B e s t

” and “

A v g

” columns, respectively. The rows labeled “#best”, “#even”, and “#worse” indicate the number of cases where the FRAS algorithm outperforms, equals, or lags behind the reference methods. The “

R P D

” column indicates the average relative percentage deviation, calculated using Equation (22). Smaller

R P D

values signify superior algorithm performance.

R P D = \frac{C_{a v g} - C_{b e s t}}{C_{b e s t}} \times 100 %

(22)

Table 5 demonstrates that the FRAS algorithm achieves the best and average makespan among all 12 instances. It outperforms FRAS_TS in 11 out of 12 instances, with FRAS_TS only achieving the best makespan for MD07. Additionally, the FRAS algorithm outperforms FRAS_RANDOM in all 12 instances. These results prove the effectiveness of the proposed FCH and ITS methods. Comparing FRAS_TS and FRAS_RANDOM, it is observed that FRAS_TS generally outperforms FRAS_RANDOM in most instances. This suggests that the FCH method has a more significant impact on improving the FRAS’s performance compared to the ITS method. Moreover, the FRAS algorithm exhibits a smaller

R P D

value and displays less fluctuation in the results, indicating that the proposed methods enhance the stability and robustness of the FRAS algorithm.

5.3. Comparison with Existing Algorithms

In this section, the FRAS algorithm is compared with the self-learning genetic algorithm (SLGA) [58], two-stage genetic algorithm (2SGA) [59], and greedy randomized adaptive search (GRAS) algorithm [38,60]. These three algorithms are utilized for solving combinatorial optimization problems. The SLGA combines Q-learning reinforcement learning methods, leading to improved performance compared to the classical genetic algorithm. The GRAS includes a successful greedy initialization method and effectively addresses FJSPs in both static and dynamic environments. The 2SGA combines fast neighborhood estimation, tabu search, and path relinking operators to successfully address FJSPs. These algorithmic approaches have demonstrated their effectiveness and efficiency in tackling complex optimization challenges in various domains. These algorithms are activated to generate a new schedule when rescheduling is triggered. The parameter settings for all comparative algorithms are selected from their corresponding literature. The respective literature has established these parameters’ values through experimental determination. Table 6 lists the result.

Furthermore, the total computation time (TCPU) of each algorithm in every run is monitored. The TCPU represents the cumulative time expended by the algorithms across all rescheduling points. It encompasses the time taken to produce the optimal new scheduling scheme at each rescheduling point, known as the response time. Additionally, the total response time (TR) for all orders in each run is documented. Table 7 summarizes the mean TCPU and the mean TR times.

Table 7 demonstrates that the FRAS algorithm consistently achieves the optimal solution in all 12 instances with minimal time consumption. In Figure 5b, the FRAS algorithm demonstrates the smallest

R P D

value and fluctuations, indicating enhanced stability and robustness. The mean TCPU of all algorithms is depicted in Figure 5c, revealing that the four algorithms incur comparable TCPU times. Nevertheless, as shown in Figure 5d, the mean TR of the FRAS algorithm significantly outperforms the reference algorithms, making the FRAS algorithm more suitable for practical production applications, particularly in scenarios with frequent dynamic events. Moreover, the computational efficiency of the FRAS algorithm is pivotal, particularly when scaling to larger, more complex problem instances involving an increase in machines (M), job types (R), and orders (S). This growth is accompanied by an escalation in computational demand, as measured by TCPU and TR, due to the expanding and increasingly intricate solution space. The algorithm’s solution through this space necessitates more computational resources and time to secure optimal or near-optimal solutions. The influx of new orders intensifies the scheduling complexity, prompting more frequent rescheduling and a higher number of jobs to be reallocated at each rescheduling juncture. This dynamic facet of the problem amplifies the computational burden, necessitating continuous adaptation and reevaluation by the algorithm in response to evolving conditions.

It is important to note that response time is essential when dealing with scheduling problems in actual manufacturing, especially when dynamic events are involved. Figure 6 presents a mean reaction time comparison for the four algorithms across all rescheduled points in four representative cases. It illustrates that the FRAS algorithm consistently exhibits shorter response times than the reference algorithms for the majority of rescheduled issues. In addition, the mean response time of the FRAS algorithm has more minor fluctuations throughout all the orders. This is owing to the addition of the FCH methods to the FRAS algorithm. The FCH constructs D solutions, and chooses the best solution as the initial solution in each iteration of the FRAS algorithm. This ensures both high quality and diversity in initial solutions. Furthermore, the FRAS algorithm maintains a well-balanced approach between exploitation and exploration capabilities through the selection of appropriate parameters

{iter}_{stop}

and b. To statistically assess FRAS’s performance against the reference algorithms, the Wilcoxon test [61] is employed. Furthermore, we perform a sensitivity analysis to assess the impact of the time interval for new order arrivals on the algorithm’s performance. Due to space limitations, a more detailed description is provided in the Appendix D.

5.4. Industrial Application

To further validate the effectiveness of the FRAS algorithm, we conducted a series of practical case studies from a real-world motorcycle part manufacturing factory. The study utilizes process information obtained from a motorcycle part manufacturing factory (details in Appendix E). The manufacturing system comprises 20 machine tools, including various CNC machines, used to process 3 different types of motorcycle parts with flexible process routes as shown in Figure 7. The factory’s production data revealed the processing of hundreds of jobs daily, with orders containing multiple jobs of each part type arriving randomly. This scenario exhibits large-scale, multiplicity, and dynamic production characteristics. Five manufacturing cases (Data01–Data05) are selected based on enterprise orders, with additional information provided in Appendix E.

For instance, Data01’s initial schedule is created for orders 1-1, consisting of 51 new parts across three types, arriving at time 0 (stage 1). Subsequently, order 1-2, comprising 65 new parts and arriving at time 537, triggers the transition to the next stage (stage 2). The FRAS algorithm then generates a new schedule after orders 1-2 arrive. Figure 8 illustrates both the initial and rescheduled schemes for Data01.

Table 8 demonstrates that the FRAS algorithm consistently achieves optimal and average makespan results across all cases. More importantly, the FRAS algorithm exhibits significantly reduced mean total response times (TR) compared to the GRAS by from

40 %

90 %

, surpassing the other three reference algorithms by more than

70 %

. These results emphasize the strong suitability of the FRAS algorithm for tackling the MDFJSP. Additionally, the FRAS algorithm consistently outperforms the reference algorithms regarding mean TR time and completion time. This indicates that the FRAS algorithm processes all parts more efficiently and can swiftly generate new rescheduling schemes in response to dynamic events. The FRAS algorithm shows significant promise for effectively addressing practical production challenges characterized by multiplicity and dynamic flexibility in shop scheduling.

Furthermore, the FRAS algorithm’s practical utility shines through its capacity to deliver significant advantages across a spectrum of manufacturing contexts. In high-mix, low-volume sectors, such as aerospace and automotive parts production, where customization and product diversity are paramount, the algorithm’s proficiency in orchestrating various job types enhances the scheduling efficiency, shortens lead times, and elevates customer satisfaction. In just-in-time production environments, like electronics and consumer goods, marked by elevated inventory costs and variable market needs, the FRAS algorithm’s dynamic rescheduling capabilities ensure the seamless synchronization with real-time orders, minimizing stockpiles and waste. Its rescheduling agility is equally crucial in emergency response scenarios, where it facilitates rapid realignment in the face of unexpected disruptions, such as production disturbances, aiding in the swift restoration of operations and the mitigation of losses. Furthermore, for contract manufacturing enterprises where agility and rapid response are vital, the FRAS algorithm offers a competitive edge by enabling nimble scheduling adjustments to accommodate fluctuating client requirements. In each of these settings, the FRAS algorithm’s ability to navigate complexity and adapt to changing conditions not only substantiates its theoretical underpinnings but also yields tangible benefits, making it a compelling tool for elevating operational efficiency and resilience in the manufacturing landscape.

6. Conclusions and Perspective

This article investigates the multiplicity dynamic flexible job shop scheduling problem (MDFJSP) with new order arrivals. A novel fluid randomized adaptive search (FRAS) algorithm is proposed to minimize makespan. The proposed FRAS algorithm comprises two phases. In the first phase, a fluid construction heuristic (FCH) incorporating an online fluid dynamic tracking policy is presented to generate high-quality initial solutions. In the second phase, we employ an improved tabu search to enhance the search efficiency in the solution space. The efficiency of the FRAS algorithm is validated by a comparison with its variants

F R A S_T S

and

F R A S_R A N D O M

. Further, the performance of the FRAS algorithm is compared with the self-learning genetic algorithm, two-stage genetic algorithm, and greedy randomized adaptive search algorithm. The results indicate that the FRAS algorithm outperformed the other algorithms in terms of effectiveness and superiority for solving the MDFJSP. Statistical analysis using the Wilcoxon test further validates FRAS’s outperformance over the reference algorithms. However, the FRAS algorithm exhibits a prolonged computational time when addressing large-scale problems, rendering it unsuitable for the efficient response requirements in large-scale optimization problems.

In the future, researchers could explore multi-objective approaches for MDFJSPs. Furthermore, expanding the problem scope to incorporate machine breakdowns and changes in due dates would provide valuable insights for addressing real-world complexities.

Author Contributions

Conceptualization, L.D.; methodology, L.D., D.L. and W.F.; software, L.D.; validation, L.D. and W.F.; formal analysis, L.D., D.L. and M.R.; investigation, D.L.; writing—original draft, D.L.; writing—review and editing, Z.G., D.L., M.R. and W.F.; supervision, Z.G.; project administration, Z.G.; funding acquisition, M.R. All authors have read and agreed to the published version of the manuscript.

Funding

This work was supported by the National Natural Science Foundation of China (Grant No. 52275489), and the National Program on Key Basic Research Project (Grant No. 2021YFB3301902).

Data Availability Statement

The data that support the findings of this study are openly available at https://doi.org/10.5281/zenodo.8369652 (accessed on 18 May 2024).

Conflicts of Interest

The authors declare no conflicts of interest.

List of Abbreviations

Abbreviation	Definition
JSP	Job shop scheduling problem
FJSP	Flexible job shop scheduling problem
DFJSP	Dynamic flexible job shop scheduling problem
MDFJSP	Multiplicity dynamic flexible job shop scheduling problem
FRAS	Fluid randomized adaptive search
FCH	Fluid construction heuristic
ITS	Improved tabu search
$R P D$	Average relative percentage deviation
2SGA	Two-stage genetic algorithm
GRAS	Greedy randomized adaptive search
SLGA	Self-learning genetic algorithm
TCPU	Total computation time
TR	Total response time
TS	Tabu search

Appendix A. Comparison with Optimal Value

This section tests the FRAS algorithm on multiplicity instances (

d a t a 01 \sim d a t a 08

) to be compared with optimal value. The optimal values are obtained with the KNITRO 9.0.1 solver. Table A1 shows the optimal value obtained with respect to time. The KNITRO 9.0.1 solver can only optimally solve the instance with equal or less than

N = 9, M = 10

within the limit of two hours of computation time. The best-obtained solution by the FRAS algorithm in

d a t a 6 \sim d a t a 7

outperforms the KNITRO with a high gap. However, the exact method is not effective for solving problems with a larger number of jobs and machines.

Table A1. Computation results on generated instances.

Instance	N × M	KNITRO 9.0.1		FRAS
Instance	N × M	$C_{\max}$	$t (s)$	Optimality Gap (%)	$B e s t (A v g)$	$t (s)$
data01	3 × 3	303	0.34	0	303 (303)	0.70
data02	6 × 3	551	0.48	0	551 (553)	1.05
data03	6 × 5	370	0.59	0	370 (371)	0.85
data04	9 × 5	555	0.72	0	555 (557)	1.19
data05	9 × 10	272	46.76	0	272 (272.8)	20.06
data06	15 × 10	583	7200	19.68	394 (396.2)	12.26
data07	20 × 10	1574	7200	99.23	770 (772.5)	22.88
data08	40 × 10				1457 (1462.7)	40.10

Appendix B. Experiments on Static Datasets

In this section, experiments on multiplicity static FJSP instances are conducted to have an idea about the general attitude of the proposed FRAS algorithm. Because there is no benchmark instance for multiplicity static or dynamic FJSP so far, then this article designed 10 multiplicity static FJSP instances (LSM-Mk01-LSM-Mk10) based on the static FJSP benchmark datasets (

M k 01 \sim M k 10

) [62]. The standard benchmarks consist of a single job per job type. Therefore, each job is duplicated several times

(N_{r})

to create large-scale multiplicity instances

(M \times N \geq 1000)

. To further verify the efficiency of the proposed FRAS algorithm, we compared it with the tabu search algorithm (TS) [63], genetic algorithm (GA) [12], and two state-of-the-art algorithms (two-stage genetic algorithm (2SGA) [59] and greedy randomized adaptive search algorithm (GRSA) [38]). All the algorithms run 20 times independently. The results are shown in Table A2.

In Table A1, the

B e s t

and

A v g

columns represent each algorithm’s best and average makespan. The best solutions obtained by each algorithm are shown in bold. The rows of

# b e s t

# e v e n

, and

# w o r s e

denote that the number of cases obtained by the FRAS algorithm is better, equal, and worse than the reference algorithms. The column

R P D

is the average relative percentage deviation of the objective over 20 runs. Equation (A1) defines the calculation of

R P D

. The

C_{a v g}

and

C_{b e s t}

are the average and minimum makespan, respectively. The algorithm has a better performance when a smaller

R P D

is obtained.

R P D = \frac{C_{a v g} - C_{b e s t}}{C_{b e s t}} \times 100 %

(A1)

The results in Table A1 show that the FRAS algorithm obtains the best solutions in 9 out of the 10 instances. 2SGA obtains the best solution for LSM-Mk03 and LSM-Mk04. Therefore, the FRAS algorithm has a better performance than the reference algorithms on the best solution.

Table A2. Comparison of the FRAS and reference algorithms on generated static instances.

Instance	R	$N_{r}$	$N \times M$	TS		GA		2SGA		GRAS		FRAS
Instance	R	$N_{r}$	$N \times M$	$B e s t (A v g)$	$R P D$	$B e s t (A v g)$	$R P D$	$B e s t (A v g)$	$R P D$	$B e s t (A v g)$	$R P D$	$B e s t (A v g)$	$R P D$
LSM-Mk01	10	20	200 × 6	1212 (1241)	69.54	1024 (1025)	40.03	782 (784)	7.10	941 (942)	28.69	732 (732)	0.00
LSM-Mk02	10	20	200 × 6	973 (999)	95.12	840 (851)	66.21	567 (570)	11.33	836 (847)	65.43	512 (512)	0.00
LSM-Mk03	15	10	150 × 8	2780 (2984)	46.27	2555 (2595)	27.21	2040 (2040)	0.00	2545 (2625)	28.68	2040 (2047)	0.34
LSM-Mk04	15	10	150 × 8	889 (929)	52.80	780 (781)	28.45	608 (608)	0.00	687 (692)	13.82	617 (622)	2.30
LSM-Mk05	15	20	300 × 4	4687 (4782)	39.21	4371 (4395)	27.95	3602 (3607)	5.01	3628 (3655)	6.40	3435 (3435)	0.00
LSM-Mk06	10	10	100 × 15	1221 (1262)	139.02	1139 (1140)	115.91	584 (585)	10.80	617 (623)	17.99	528 (529)	0.19
LSM-Mk07	20	10	200 × 5	2483 (2578)	85.33	2170 (2192)	57.58	1559 (1565)	12.51	1898 (1911)	37.38	1391 (1391)	0.00
LSM-Mk08	20	10	200 × 10	6226 (6263)	19.75	6056 (6075)	16.16	5430 (5442)	4.05	5489 (5505)	5.26	5230 (5230)	0.00
LSM-Mk09	20	10	200 × 10	5274 (5294)	74.66	4723 (4755)	56.88	3337 (3344)	10.33	3495 (3545)	16.96	3031 (3036)	0.16
LSM-Mk10	20	10	200 × 15	4102 (4364)	127.53	3649 (3671)	91.40	2212 (2217)	15.59	3217 (3228)	68.30	1918 (1921)	0.16
#better				10		10		8		10
#even				0		0		1		0
#worse				0		0		1		0

Figure A1a shows that among the compared algorithms, 2SGA is the closest to the FRAS algorithm, but the FRAS algorithm is superior to 2SGA in 8 out of the 10 instances except for instance LSM-Mk03 and LSM-Mk04. Figure A1b shows the interval plot for the

R P D

of the FRAS algorithm and reference algorithms (

C I

: 95%), which are used for checking whether the FRAS algorithm outperforms reference algorithms statistically. The FRAS algorithm obtains a better

R P D

value and has smaller fluctuations in the results, which means it has better stability and robustness.

Figure A1. The average makespan of different static cases and interval plot for

R P D

of the five algorithms.

Figure A1. The average makespan of different static cases and interval plot for

R P D

of the five algorithms.

In Figure A2, it is not difficult to find that the convergence curve of the FRAS algorithm stays below the convergence curve of other algorithms in all instances except LSM-Mk03 and LSM-Mk04. The FRAS algorithm holds the lower iteration initial point in 9 out of the 10 instances, and the final solutions of all reference algorithms are not even better than the initial solution of the FRAS algorithm in 8 instances. This is due to the proposed FCH significantly improving the performance of the FRAS algorithm, and the FRAS algorithm occupies a competitive achievement for reaching the optima at the beginning. Moreover, the FRAS algorithm converges to the best solution faster than the reference algorithms. In general, we can conclude that the FRAS algorithm is significantly more excellent than other algorithms while solving the large-scale multiplicity static FJSPs.

Figure A2. The mean convergence curve of LSM-Mk01-LSM-Mk10.

Appendix C. Statistical Analysis

In this section, the Wilcoxon test is used to compare the FRAS algorithm with the reference algorithms to check whether the proposed algorithm outperforms all reference algorithms statistically. The Wilcoxon is a non-parametric test method that is suitable for continuous optimization problems in multiple-problem analysis [61]. Table A3 summarizes the results of applying the Wilcoxon test on the average makespan. They display the sum of rankings obtained in each comparison and the p-value associated. The FRAS algorithm outperforms these reference algorithms considering independent pairwise comparisons due to the p-value are below

α = 0.05

. However, Wilcoxon’s test performs individual comparisons between two algorithms. If we include them within the multiple comparisons, the p-value obtained is

p = 0.0155

. Then it can be deduced that HFMAE outperforms the three reference algorithms in terms of solution quality with a level of significance

α = 0.05

Table A3. Wilcoxon test considering average makespan.

FRAS vs.	$R^{+}$	p-Value
SLGA	36	0.00390625
2SGA	36	0.00390625
GRAS	36	0.00390625

Appendix D. Sensitivity Analysis

To further assess the extent of our proposed algorithm, an instance with

M = 10

S = 5

R = 20

is used to perform a sensitivity analysis to analyze the impact of the time interval between new orders’ arrival on the objective and the mean total response time (TR). Figure A3 shows the results of the sensitivity analysis.

Figure A3. The impact of the time interval between new orders’ arrival on the objective and the mean total response time (TR).

From Figure A3, it can be observed that increasing the time interval between new orders’ arrival leads to an increase in makespan and a decrease in the mean total response time. This can be explained by the fact that fewer jobs need to be rescheduled at each rescheduling point, reducing the complexity of the scheduling problem. As a result, the FRAS algorithm can converge to a final solution more quickly. Additionally, a more significant time interval between new orders’ arrival makes the scheduling system more myopic, limiting the potential for finding better overall schedules. These findings indicate that the FRAS algorithm effectively captures the impact of the time interval between new orders’ arrival on system performance. Furthermore, the proposed algorithm demonstrates a good stability and robustness across various levels of new orders’ arrival time intervals.

Appendix E. Process Information Furthermore, Production Data

Table A4. The processing information of the three types of parts.

Part Types	Operation	Processing Time
r	j	$(r, j, m, t_{r j m})$
1	1	(1, 1, 1, 18)
	2	(1, 2, 3, 10)
	3	(1, 3, 1, 21)
	4	(1, 4, 6, 19)
	5	(1, 5, 7, 28) (1, 5, 8, 28) (1, 5, 9, 28)
	6	(1, 6, 11, 10)
	7	(1, 7, 13, 20) (1, 7, 14, 20)
	8	(1, 8, 15, 32) (1, 8, 16, 32) (1, 8, 17, 32)
	9	(1, 9, 18, 19) (1, 9, 19, 19) (1, 9, 20, 19)
	10	(1, 10, 10, 8)
2	1	(2, 1, 2, 18)
	2	(2, 2, 3, 10)
	3	(2, 3, 4, 21)
	4	(2, 4, 5, 19)
	5	(2, 5, 7, 28) (2, 5, 8, 28) (2, 5, 9, 28)
	6	(2, 6, 11, 10)
	7	(2, 7, 13, 20) (2, 7, 14, 20)
	8	(2, 8, 15, 32) (2, 8, 16, 32) (2, 8, 17, 32)
	9	(2, 9, 18, 19) (2, 9, 19, 19) (2, 9, 20, 19)
	10	(2, 10, 10, 8)
3	1	(3, 1, 2, 23)
	2	(3, 2, 3, 14)
	3	(3, 3, 4, 25)
	4	(3, 4, 5, 26) (3, 4, 6, 26)
	5	(3, 5, 7, 42) (3, 5, 8, 42) (3, 5, 9, 42) (3, 5, 10, 42)
	6	(3, 6, 11, 15)
	7	(3, 7, 12, 25)
	8	(3, 8, 13, 31) (3, 8, 14, 31)
	9	(3, 9, 15, 48) (3, 9, 16, 48) (3, 9, 17, 48)
	10	(3, 10, 18, 28) (3, 10, 19, 28)
	11	(3, 11, 7, 10) (3, 11, 8, 10) (3, 11, 9, 10) (3, 11, 10, 10)

Table A5. The detailed information of the five cases.

Cases	Orders (s)	Arrival Time ( $A_{s}$ )	Number of Parts for Different Types
Cases	Orders (s)	Arrival Time ( $A_{s}$ )	$r_{1}$	$r_{2}$	$r_{3}$
Data01	1-1	0	22	13	16
Data01	1-2	537	19	17	29
Data02	2-1	0	11	14	15
	2-2	641	22	20	29
	2-3	2537	12	16	11
Data03	3-1	0	11	15	26
	3-2	1075	19	18	15
	3-3	1652	15	21	18
	3-4	4247	24	12	25
Data04	4-1	0	18	16	28
	4-2	2253	29	16	15
	4-3	2885	19	19	28
	4-4	4726	25	24	20
	4-5	4937	11	12	11
Data05	5-1	0	24	13	12
	5-2	1161	29	24	11
	5-3	3214	22	13	24
	5-4	3327	20	26	23
	5-5	3437	29	20	28

References

Gu, X.; Koren, Y. Mass-Individualisation–the twenty first century manufacturing paradigm. Int. J. Prod. Res. 2022, 60, 7572–7587. [Google Scholar] [CrossRef]
Leng, J.; Zhu, X.; Huang, Z.; Li, X.; Zheng, P.; Zhou, X.; Mourtzis, D.; Wang, B.; Qi, Q.; Shao, H.; et al. Unlocking the power of industrial artificial intelligence towards Industry 5.0: Insights, pathways, and challenges. J. Manuf. Syst. 2024, 73, 349–363. [Google Scholar] [CrossRef]
Basantes Montero, D.T.; Rea Minango, S.N.; Barzallo Núñez, D.I.; Eibar Bejarano, C.G.; Proaño López, P.D. Flexible Manufacturing System Oriented to Industry 4.0. In Proceedings of the Innovation and Research: A Driving Force for Socio-Econo-Technological Development 1st, Sangolquí, Ecuador, 1–3 September 2021; Springer: Berlin/Heidelberg, Germany, 2021; pp. 234–245. [Google Scholar]
Margherita, E.G.; Braccini, A.M. Industry 4.0 technologies in flexible manufacturing for sustainable organizational value: Reflections from a multiple case study of Italian manufacturers. Inf. Syst. Front. 2023, 25, 995–1016. [Google Scholar] [CrossRef]
Leng, J.; Chen, Z.; Sha, W.; Lin, Z.; Lin, J.; Liu, Q. Digital twins-based flexible operating of open architecture production line for individualized manufacturing. Adv. Eng. Inform. 2022, 53, 101676. [Google Scholar] [CrossRef]
Zhang, W.; Xiao, J.; Liu, W.; Sui, Y.; Li, Y.; Zhang, S. Individualized requirement-driven multi-task scheduling in cloud manufacturing using an extended multifactorial evolutionary algorithm. Comput. Ind. Eng. 2023, 179, 109178. [Google Scholar] [CrossRef]
Ghaleb, M.; Zolfagharinia, H.; Taghipour, S. Real-time production scheduling in the Industry-4.0 context: Addressing uncertainties in job arrivals and machine breakdowns. Comput. Oper. Res. 2020, 123, 105031. [Google Scholar] [CrossRef]
Luo, D.; Thevenin, S.; Dolgui, A. A state-of-the-art on production planning in Industry 4.0. Int. J. Prod. Res. 2023, 61, 6602–6632. [Google Scholar] [CrossRef]
Sangaiah, A.K.; Suraki, M.Y.; Sadeghilalimi, M.; Bozorgi, S.M.; Hosseinabadi, A.A.R.; Wang, J. A new meta-heuristic algorithm for solving the flexible dynamic job-shop problem with parallel machines. Symmetry 2019, 11, 165. [Google Scholar] [CrossRef]
Zhou, J.; Zheng, L.; Fan, W. Multirobot collaborative task dynamic scheduling based on multiagent reinforcement learning with heuristic graph convolution considering robot service performance. J. Manuf. Syst. 2024, 72, 122–141. [Google Scholar] [CrossRef]
Han, X.; Cheng, W.; Meng, L.; Zhang, B.; Gao, K.; Zhang, C.; Duan, P. A dual population collaborative genetic algorithm for solving flexible job shop scheduling problem with AGV. Swarm. Evol. Comput. 2024, 86, 101538. [Google Scholar] [CrossRef]
Pezzella, F.; Morganti, G.; Ciaschetti, G. A genetic algorithm for the Flexible Job-shop Scheduling Problem. Comput. Oper. Res. 2008, 35, 3202–3212. [Google Scholar] [CrossRef]
Gui, Y.; Tang, D.; Zhu, H.; Zhang, Y.; Zhang, Z. Dynamic scheduling for flexible job shop using a deep reinforcement learning approach. Comput. Ind. Eng. 2023, 180, 109255. [Google Scholar] [CrossRef]
Tang, D.B.; Dai, M.; Salido, M.A.; Giret, A. Energy-efficient dynamic scheduling for a flexible flow shop using an improved particle swarm optimization. Comput. Ind. 2016, 81, 82–95. [Google Scholar] [CrossRef]
Monch, L.; Fowler, J.W.; Dauzere-Peres, S.; Mason, S.J.; Rose, O. A survey of problems, solution techniques, and future challenges in scheduling semiconductor manufacturing operations. J. Sched. 2011, 14, 583–599. [Google Scholar] [CrossRef]
Purba, H.H.; Aisyah, S.; Dewarani, R. Production capacity planning in motorcycle assembly line using CRP method at PT XYZ. In Proceedings of the IOP Conference Series: Materials Science and Engineering, Chennai, India, 16–17 September 2020; IOP Publishing: Bristol, UK, 2020; Volume 885, p. 012029. [Google Scholar]
Han, J.H.; Lee, J.Y. Scheduling for a flow shop with waiting time constraints and missing operations in semiconductor manufacturing. Eng. Optim. 2023, 55, 1742–1759. [Google Scholar] [CrossRef]
Zhang, F.; Mei, Y.; Nguyen, S.; Zhang, M. Evolving scheduling heuristics via genetic programming with feature selection in dynamic flexible job-shop scheduling. IEEE Trans. Cybern. 2020, 51, 1797–1811. [Google Scholar] [CrossRef] [PubMed]
Tang, H.; Xiao, Y.; Zhang, W.; Lei, D.; Wang, J.; Xu, T. A DQL-NSGA-III algorithm for solving the flexible job shop dynamic scheduling problem. Expert Syst. Appl. 2024, 237, 121723. [Google Scholar] [CrossRef]
Jing, X.; Yao, X.; Liu, M.; Zhou, J. Multi-agent reinforcement learning based on graph convolutional network for flexible job shop scheduling. J. Intell. Manuf. 2024, 35, 75–93. [Google Scholar] [CrossRef]
Ding, L.; Guan, Z.; Zhang, Z.; Fang, W.; Chen, Z.; Yue, L. A hybrid fluid master–apprentice evolutionary algorithm for large-scale multiplicity flexible job-shop scheduling with sequence-dependent set-up time. Eng. Optim. 2024, 56, 54–75. [Google Scholar] [CrossRef]
Ding, L.; Guan, Z.; Rauf, M.; Yue, L. Multi-policy deep reinforcement learning for multi-objective multiplicity flexible job shop scheduling. Swarm. Evol. Comput. 2024, 87, 101550. [Google Scholar] [CrossRef]
Guo, C.T.; Jiang, Z.B.; Zhang, H.; Li, N. Decomposition-based classified ant colony optimization algorithm for scheduling semiconductor wafer fabrication system. Comput. Ind. Eng. 2012, 62, 141–151. [Google Scholar] [CrossRef]
Kundakci, N.; Kulak, O. Hybrid genetic algorithms for minimizing makespan in dynamic job shop scheduling problem. Comput. Ind. Eng. 2016, 96, 31–51. [Google Scholar] [CrossRef]
Lei, D.; Zhang, J.; Liu, H. An Adaptive Two-Class Teaching-Learning-Based Optimization for Energy-Efficient Hybrid Flow Shop Scheduling Problems with Additional Resources. Symmetry 2024, 16, 203. [Google Scholar] [CrossRef]
Liu, J.; Sun, B.; Li, G.; Chen, Y. Multi-objective adaptive large neighbourhood search algorithm for dynamic flexible job shop schedule problem with transportation resource. Eng. Appl. Artif. Intell. 2024, 132, 107917. [Google Scholar] [CrossRef]
Pei, Z.; Zhang, X.F.; Zheng, L.; Wan, M.Z. A column generation-based approach for proportionate flexible two-stage no-wait job shop scheduling. Int. J. Prod. Res. 2020, 58, 487–508. [Google Scholar] [CrossRef]
Subramaniam, V.; Ramesh, T.; Lee, G.K.; Wong, Y.S.; Hong, G.S. Job shop scheduling with dynamic fuzzy selection of dispatching rules. Int. J. Adv. Manuf. Technol. 2000, 16, 759–764. [Google Scholar] [CrossRef]
Zhang, H.; Roy, U. A semantics-based dispatching rule selection approach for job shop scheduling. J. Intell. Manuf. 2019, 30, 2759–2779. [Google Scholar] [CrossRef]
Zhang, F.F.; Mei, Y.; Nguyen, S.; Zhang, M.J. Correlation Coefficient-Based Recombinative Guidance for Genetic Programming Hyperheuristics in Dynamic Flexible Job Shop Scheduling. IEEE Trans. Evol. Comput. 2021, 25, 552–566. [Google Scholar] [CrossRef]
Đurasević, M.; Jakobović, D. Selection of dispatching rules evolved by genetic programming in dynamic unrelated machines scheduling based on problem characteristics. J. Comput. Sci. 2022, 61, 101649. [Google Scholar] [CrossRef]
Holthaus, O.; Rajendran, C. Efficient jobshop dispatching rules: Further developments. Prod. Plan. Control 2010, 11, 171–178. [Google Scholar] [CrossRef]
Ren, W.; Yan, Y.; Hu, Y.; Guan, Y. Joint optimisation for dynamic flexible job-shop scheduling problem with transportation time and resource constraints. Int. J. Prod. Res. 2021, 60, 5675–5696. [Google Scholar] [CrossRef]
Fuladi, S.K.; Kim, C.S. Dynamic Events in the Flexible Job-Shop Scheduling Problem: Rescheduling with a Hybrid Metaheuristic Algorithm. Algorithms 2024, 17, 142. [Google Scholar] [CrossRef]
Thi, L.M.; Mai Anh, T.T.; Van Hop, N. An improved hybrid metaheuristics and rule-based approach for flexible job-shop scheduling subject to machine breakdowns. Eng. Optim. 2023, 55, 1535–1555. [Google Scholar] [CrossRef]
Guo, H.; Liu, J.; Wang, Y.; Zhuang, C. An improved genetic programming hyper-heuristic for the dynamic flexible job shop scheduling problem with reconfigurable manufacturing cells. J. Manuf. Syst. 2024, 74, 252–263. [Google Scholar] [CrossRef]
Mohan, J.; Lanka, K.; Rao, A.N. A Review of Dynamic Job Shop Scheduling Techniques. Procedia Manuf. 2019, 30, 34–39. [Google Scholar] [CrossRef]
Baykasoğlu, A.; Madenoğlu, F.S.; Hamzadayı, A. Greedy randomized adaptive search for dynamic flexible job-shop scheduling. J. Manuf. Syst. 2020, 56, 425–451. [Google Scholar] [CrossRef]
Zhang, H.; Buchmeister, B.; Li, X.; Ojstersek, R. An Efficient Metaheuristic Algorithm for Job Shop Scheduling in a Dynamic Environment. Mathematics 2023, 11, 2336. [Google Scholar] [CrossRef]
Xie, J.; Gao, L.; Peng, K.; Li, X.; Li, H. Review on flexible job shop scheduling. IET Collab. Intell. Manuf. 2019, 1, 67–77. [Google Scholar] [CrossRef]
Chen, D.D.Y.H. Dynamic Scheduling of a Multiclass Fluid Network. Oper. Res. Lett. 1993, 41, 1104–1115. [Google Scholar] [CrossRef]
Dai, J.G.; Weiss, G. A fluid heuristic for minimizing makespan in job shops. Oper. Res. 2002, 50, 692–707. [Google Scholar] [CrossRef]
Bertsimas, D.; Gamarnik, D.; Sethuraman, J. From fluid relaxations to practical algorithms for high-multiplicity job-shop scheduling: The holding cost objective. Oper. Res. 2003, 51, 798–813. [Google Scholar] [CrossRef]
Masin, M.; Raviv, T. Linear programming-based algorithms for the minimum makespan high multiplicity jobshop problem. J. Sched. 2014, 17, 321–338. [Google Scholar] [CrossRef]
Gu, J.W.; Gu, M.Z.; Lu, X.W.; Zhang, Y. Asymptotically optimal policy for stochastic job shop scheduling problem to minimize makespan. J. Comb. Optim. 2018, 36, 142–161. [Google Scholar] [CrossRef]
Bertsimas, D.; Nasrabadi, E.; Paschalidis, I.C. Robust Fluid Processing Networks. IEEE Trans. Autom. Control 2015, 60, 715–728. [Google Scholar] [CrossRef]
Bertsimas, D.; Gamarnik, D. Asymptotically optimal algorithms for job shop scheduling and packet routing. J. Algorithms 1999, 33, 296–318. [Google Scholar] [CrossRef]
Bertsimas, D.; Sethuraman, J. From fluid relaxations to practical algorithms for job shop scheduling: The makespan objective. Math. Program. 2002, 92, 61–102. [Google Scholar] [CrossRef]
Nazarathy, Y.; Weiss, G. A fluid approach to large volume job shop scheduling. J. Sched. 2010, 13, 509–529. [Google Scholar] [CrossRef]
Boudoukh, T.; Penn, M.; Weiss, G. Scheduling jobshops with some identical or similar jobs. J. Sched. 2001, 4, 177–199. [Google Scholar] [CrossRef]
Shen, X.N.; Yao, X. Mathematical modeling and multi-objective evolutionary algorithms applied to dynamic flexible job shop scheduling problems. Inf. Sci. 2015, 298, 198–224. [Google Scholar] [CrossRef]
Vinod, V.; Sridharan, R. Dynamic job-shop scheduling with sequence-dependent setup times: Simulation modeling and analysis. Int. J. Adv. Manuf. Technol. 2008, 36, 355–372. [Google Scholar] [CrossRef]
Glover, F. Tabu search-part II. ORSA J. Comput. 1990, 2, 4–32. [Google Scholar] [CrossRef]
Li, J.Q.; Pan, Q.K.; Liang, Y.C. An effective hybrid tabu search algorithm for multi-objective flexible job-shop scheduling problems. Comput. Ind. Eng. 2010, 59, 647–662. [Google Scholar] [CrossRef]
González, M.A.; Vela, C.R.; Varela, R. Scatter search with path relinking for the flexible job shop scheduling problem. Eur. J. Oper. Res. 2015, 245, 35–45. [Google Scholar] [CrossRef]
Kemmoé-Tchomté, S.; Lamy, D.; Tchernev, N. An effective multi-start multi-level evolutionary local search for the flexible job-shop problem. Eng. Appl. Artif. Intell. 2017, 62, 80–95. [Google Scholar] [CrossRef]
Mandavi, S.; Shiri, M.E.; Rahnamayan, S. Metaheuristics in large-scale global continues optimization: A survey. Inf. Sci. 2015, 295, 407–428. [Google Scholar] [CrossRef]
Chen, R.H.; Yang, B.; Li, S.; Wang, S.L. A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem. Comput. Ind. Eng. 2020, 149. [Google Scholar] [CrossRef]
Defersha, F.M.; Rooyani, D. An efficient two-stage genetic algorithm for a flexible job-shop scheduling problem with sequence dependent attached/detached setup, machine release date and lag-time. Comput. Ind. Eng. 2020, 147. [Google Scholar] [CrossRef]
Resende, T.A.F.M.G.C. Greedy randomized adaptive search procedures. J. Glob. Optim. 1995, 6, 109–133. [Google Scholar]
García, S.; Molina, D.; Lozano, M.; Herrera, F. A study on the use of non-parametric tests for analyzing the evolutionary algorithms’ behaviour: A case study on the CEC’2005 special session on real parameter optimization. J. Heuristics 2009, 15, 617–644. [Google Scholar] [CrossRef]
Brandimarte, P. Routing and scheduling in a flexible job shop by tabu search. Ann. Oper. Res. 1993, 41, 157–183. [Google Scholar] [CrossRef]
Mastrolilli, M.; Gambardella, L.M. Effective neighbourhood functions for the flexible job shop problem. J. Sched. 2000, 3, 3–20. [Google Scholar] [CrossRef]

Figure 1. An example of the MDFJSP with new order arrivals.

Figure 2. (a) A flow diagram of the dynamic scheduling system. (b) A basic flow of the FRAS algorithm.

Figure 3. An example of public critical operations.

Figure 4. The trend of the factor level.

Figure 5. (a) The average makespan of different cases. (b) The interval plot for

R P D

of the five algorithms. (c) The total computation time. (d) The total response time.

Figure 5. (a) The average makespan of different cases. (b) The interval plot for

R P D

of the five algorithms. (c) The total computation time. (d) The total response time.

Figure 6. The mean response time of the four algorithms at each rescheduling point on four represent instances.

Figure 7. The production process of the motorcycle parts manufacturing factory.

Figure 8. The initial scheduling scheme and rescheduling scheme of Data01 obtained by the FRAS algorithm.

Table 1. Literature review of fluid models in JSPs.

Paper	Type of JSPs			Problem Scale		Objective
Paper	Number of Multiplicity	Deterministic	Stochastic	Small	Large	Makespan	Holding Cost
Bertsimas and Gamarnik (1999) [47]	Up to 2500	✔		✔		✔
Boudoukh et al. (2001) [50]	Up to 1000		✔		✔	✔
Dai and Weiss (2002) [42]	Up to 100,000	✔		✔		✔
Bertsimas and Sethuraman (2002) [48]	Up to 1000	✔				✔
Bertsimas et al. (2003) [43]	Up to 10,000	✔		✔			✔
Nazarathy and Weiss (2010) [49]	Up to $2^{14}$	✔			✔	✔
Masin and Raviv (2014) [44]	Up to 10	✔		✔		✔
Gu et al. (2018) [45]	Up to 100		✔	✔		✔

Table 2. An example for the MDFJSP with 2 new orders and 3 machines.

$N_{1 r}$	$N_{2 r}$	r	j	$M 1$	$M 2$	$M 3$
			1	29	11	28
3	2	1	2	14	15	24
			3	18	25	25
			1	12	16	25
3	2	2	2	22	15	14
			3	26	26	20

Table 3. Parameter settings for instances.

Parameter	Value
Total number of machines (M)	randi [10, 20]
Total number of job types (R)	randi [5, 10]
Total number of operations of job type r ( $J_{r}$ )	randi [5, 10]
Number of available machines per operation	randi [1, M]
Processing time of an operation ( $t_{r j m}$ )	randi [1, 20]
Total number of new orders (S)	randi [1, 5]
Total number of job type r in new order s ( $N_{s r}$ )	randi [10, 20]
Mean interarrival time of new jobs ( $λ$ )	randi [200, 800]

Table 4. Orthogonal array and average response values.

Combination	Parameters			$C_{avg}$
Combination	${iter}_{stop}$	$D$	$b$	$C_{avg}$
1	10	10	0.1	2010
2	10	20	0.2	2030.7
3	10	40	0.3	2017.7
4	10	80	0.4	2014
5	20	10	0.2	2025
6	20	20	0.1	2034
7	20	40	0.4	2016.7
8	20	80	0.3	2025.3
9	30	10	0.3	2032.3
10	30	20	0.4	2035.3
11	30	40	0.1	2021
12	30	80	0.2	2017.3
13	40	10	0.4	2024.7
14	40	20	0.3	2000.7
15	40	40	0.2	2006.3
16	40	80	0.1	2024.3

Table 5. Comparison of the FRAS algorithm and its variant algorithms on generated instances.

Instance	M	R	S	FRAS_RANDOM			FRAS_TS			FRAS
Instance	M	R	S	$Best$	$Avg$	$RPD$	$Best$	$Avg$	$RPD$	$Best$	$Avg$	$RPD$
MD01	10	5	1	639	732.6	0.86	398	403.6	0.02	394	400.4	0.02
MD02	10	5	3	2814	2951.6	1.05	1457	1468.4	0.02	1440	1457.2	0.01
MD03	10	5	5	3489	3683.8	0.76	2101	2113.6	0.01	2089	2092.8	0.00
MD04	10	10	1	1180	1277	1.30	570	575	0.04	555	556.4	0.00
MD05	10	10	3	4721	5103	1.87	1789	1806	0.02	1778	1791.8	0.01
MD06	10	10	5	9370	9569.6	2.07	3127	3137.2	0.00	3122	3148.2	0.01
MD07	20	5	1	452	492.8	0.30	380	380	0.00	380	380	0.00
MD08	20	5	3	3794	3841.2	0.09	3545	3548.4	0.00	3540	3541.6	0.00
MD09	20	5	5	2347	2419.2	0.17	2078	2078	0.00	2075	2075	0.00
MD10	20	10	1	775	929.4	1.53	395	401.4	0.09	367	373.6	0.02
MD11	20	10	3	2577	2727.8	0.37	1992	1993.6	0.00	1986	1988.8	0.00
MD12	20	10	5	3539	3667.6	0.34	2768	2773.2	0.01	2737	2737	0.00
#better				12			11
#even				0			1
#worse				0			0

Table 6. Comparison of the FRAS and reference algorithms.

Instance	SLGA			2SGA			GRAS			FRAS
Instance	$B e s t$	$A v g$	$R P D$	$B e s t$	$A v g$	$R P D$	$B e s t$	$A v g$	$R P D$	$B e s t$	$A v g$	$R P D$
MD01	648	660.4	0.68	414	419.2	0.06	479	482.4	0.22	394	400.4	0.02
MD02	2230	2282.8	0.59	1503	1511.4	0.05	1739	1754.2	0.22	1440	1457.2	0.01
MD03	2928	2989.8	0.43	2131	2147.2	0.03	2255	2281	0.09	2089	2092.8	0.00
MD04	1051	1086	0.96	619	625.4	0.13	674	684.6	0.23	555	556.4	0.00
MD05	4461	4517.2	1.54	2151	2163.8	0.22	2328	2344.2	0.32	1778	1791.8	0.01
MD06	9189	9333.2	1.99	3916	3935.4	0.26	4360	4392.2	0.41	3122	3148.2	0.01
MD07	420	436	0.15	380	380	0.00	393	396.2	0.04	380	380	0.00
MD08	3795	3815	0.08	3543	3543.8	0.00	3560	3565.8	0.01	3540	3541.6	0.00
MD09	2155	2168.2	0.04	2075	2075.6	0.00	2231	2255	0.09	2075	2075	0.00
MD10	756	792.4	1.16	383	387	0.05	531	541.4	0.48	367	373.6	0.02
MD11	2405	2419	0.22	2002	2011.2	0.01	2098	2106.4	0.06	1986	1988.8	0.00
MD12	3135	3219.4	0.18	2754	2758	0.01	2929	2936.2	0.07	2737	2737	0.00
#better	12			10			12
#even	0			2			0
#worse	0			0			0

Table 7. Comparison of the mean TCPU time and the mean TR time for the FRAS and reference algorithms.

Instance	SLGA		2SGA		GRAS		FRAS
Instance	TCPU (s)	TR (s)	TCPU (s)	TR (s)	TCPU (s)	TR (s)	CPU (s)	TR (s)
MD01	810.91	158.34	817.53	128.01	801.36	104.01	811.41	77.13
MD02	2692.95	515.80	2627.61	405.75	2522.59	336.10	2593.53	204.81
MD03	4617.25	873.66	4210.52	638.91	4048.66	516.81	4175.16	332.65
MD04	1486.13	286.94	1479.06	246.47	1462.64	128.97	1472.91	218.72
MD05	7037.06	1312.37	6870.16	1208.66	6454.06	589.96	6615.44	584.89
MD06	17,062.52	2928.87	15,696.34	2623.23	13,776.69	2038.57	14,340.09	898.58
MD07	1690.17	280.26	1688.42	10.19	1680.81	224.95	1685.28	3.22
MD08	4471.08	843.80	4469.41	554.09	4425.31	374.18	4436.13	260.98
MD09	8368.03	1497.52	8192.67	65.39	8194.89	1016.40	8128.34	21.76
MD10	3156.47	614.29	3154.64	291.18	3121.53	400.18	3132.09	344.46
MD11	10,460.31	2011.12	9734.64	1338.01	9601.25	1256.72	9600.47	852.91
MD12	15,184.58	2880.93	14,310.42	905.46	14,043.11	1906.02	14,065.84	1379.80

Table 8. Comparison of the FRAS algorithm and reference algorithms on manufacturing cases.

Example	SLGA		2SGA		GRAS		FRAS
	$B e s t (A v g)$	TR (s)	$B e s t (A v g)$	TR (s)	$B e s t (A v g)$	TR (s)	$B e s t (A v g)$	TR (s)
Data01	3501 (3529)	558.6	2851 (2960)	548.5	2108 (2124)	250.7	1933 (1959)	39.5
Data02	3828 (3856)	718.6	3483 (3524)	598.6	3416 (3422)	412.2	3327 (3328)	136.9
Data03	6107 (6168)	1072.8	5785 (5839)	1002.5	5493 (5499)	570.7	5376 (5378)	199.4
Data04	8358 (8443)	1651.5	7566 (7572)	1533.6	6632 (6641)	736.5	6431 (6433)	428.7
Data05	10,698 (10,785)	1803.5	9369 (9532)	1748.2	6801 (6806)	647.4	6502 (6504)	273.2

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

© 2024 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Ding, L.; Guan, Z.; Luo, D.; Rauf, M.; Fang, W. An Adaptive Search Algorithm for Multiplicity Dynamic Flexible Job Shop Scheduling with New Order Arrivals. Symmetry 2024, 16, 641. https://doi.org/10.3390/sym16060641

AMA Style

Ding L, Guan Z, Luo D, Rauf M, Fang W. An Adaptive Search Algorithm for Multiplicity Dynamic Flexible Job Shop Scheduling with New Order Arrivals. Symmetry. 2024; 16(6):641. https://doi.org/10.3390/sym16060641

Chicago/Turabian Style

Ding, Linshan, Zailin Guan, Dan Luo, Mudassar Rauf, and Weikang Fang. 2024. "An Adaptive Search Algorithm for Multiplicity Dynamic Flexible Job Shop Scheduling with New Order Arrivals" Symmetry 16, no. 6: 641. https://doi.org/10.3390/sym16060641

APA Style

Ding, L., Guan, Z., Luo, D., Rauf, M., & Fang, W. (2024). An Adaptive Search Algorithm for Multiplicity Dynamic Flexible Job Shop Scheduling with New Order Arrivals. Symmetry, 16(6), 641. https://doi.org/10.3390/sym16060641

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

An Adaptive Search Algorithm for Multiplicity Dynamic Flexible Job Shop Scheduling with New Order Arrivals

Abstract

1. Introduction

2. Literature Review

2.1. Methodologies for the FJSP

2.2. Fluid Model

3. Problem Description

4. Fluid Randomized Adaptive Search Algorithm

4.1. Construction Phase

4.1.1. Dynamic Fluid Model and Control Problem

4.1.2. Online Fluid Dynamic Tracking Policy

4.1.3. The Fluid Construction Heuristic Method

4.2. Local Search

4.3. Implementation

5. Experiments and Results

5.1. Parameter Settings

5.2. Validation of Proposed Methods

5.3. Comparison with Existing Algorithms

5.4. Industrial Application

6. Conclusions and Perspective

Author Contributions

Funding

Data Availability Statement

Conflicts of Interest

List of Abbreviations

Appendix A. Comparison with Optimal Value

Appendix B. Experiments on Static Datasets

Appendix C. Statistical Analysis

Appendix D. Sensitivity Analysis

Appendix E. Process Information Furthermore, Production Data

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI