Distributed shop scheduling: A comprehensive review on classifications, models and algorithms

1.   Introduction

Manufacturing is the foundation of the real economy, which is the cornerstone of China's development and an important support for building future development strategic advantages ^[1]. According to statistics, up to 90% of the time in the manufacturing process is spent on non-processing stages. Therefore, the reasonable use of existing resources for production scheduling is the key to improving the economic efficiency and competitiveness of enterprises ^[2]. Efficient production scheduling can reduce the production management costs, improve production efficiency, comprehensively improve the production organization and management of enterprises and realize the optimal performance of the production system.

Over the past few decades, scheduling problems in manufacturing and service systems have been extensively investigated, which can be classified into single machine scheduling, parallel machine scheduling, flow shop scheduling ^[3], job shop scheduling and their variants. Research on workshop scheduling ^[4] has mainly focused on traditional manufacturing modes of single-factory production, with less research on scheduling in multiple workshops distributed in different regions. With the tremendous impact of economic globalization on traditional manufacturing industries, the centralized production mode has made enterprises face problems, such as low product quality, high logistics costs, over-concentration of resources, low production efficiency, poor performance and long delivery times. More and more manufacturers are aware of the need to achieve sustainable economic development and gain a foothold in the increasingly competitive global market, the traditional manufacturing mode must be improved or broken ^[5], so they turn to a multiple factory processing mode: assigning a batch of workpieces to multiple workshops or factories for processing. This can reduce production costs and management risks by assigning tasks to multiple factories, while increasing output of finished products within a certain period of time. The scale of intelligent manufacturing industry is continuously expanding, and the overall decision optimization technology for distributed workshops has an extremely important impact on the operational efficiency of the entire manufacturing system ^[6]. Holistic optimization approaches typically use artificial intelligence algorithms and data analysis to form optimal decisions from a global and integrated approach ^[7]. How to make use of production data, mechanism models and efficient artificial intelligence algorithms for accurate reconfiguration and flexible operations, to respond to market demands and meet production quality requirements, has become a critical issue to be addressed ^[8].

In recent years, researchers have proposed a new scheduling method, namely distributed scheduling, with the aim of scheduling distributed manufacturing systems. The distributed shop scheduling problem (DSSP) ^[9] studies the allocation of workpieces between factories and the processing order within each factory in the context of cooperative or collaborative production between different factories in distributed manufacturing, in order to achieve the optimization of scheduling metrics. Unlike traditional centralized manufacturing methods, distributed shop scheduling responds quickly to changes in market demand by coordinating resource allocation between enterprises or factories in different locations, adjusting production plans and shortening the production cycle time from raw materials, parts, to finished products delivered to customers, thus completing customer production orders more efficiently within the scheduled time. Distributed scheduling also improves the quality of the production process ^[10] and disperses the management risks of single factories to multiple factories, greatly reducing production costs and improving production efficiency.

Compared with the single-shop scheduling problem, the distributed shop scheduling problem is more complex ^[11]. In distributed production scheduling, each factory is considered as a production line workshop, and the scheduling plan of a single workshop often conflicts with the scheduling production objectives of the entire system. The scheduling goal of a single production workshop is to minimize the maximum completion time of the factory, while the optimization indicator of distributed production scheduling is to coordinate the task assignments of each factory ^[12], achieving the minimization of the maximum completion time of the factory with the longest completion time. The key to solving the conflict between single-shop scheduling and distributed shop scheduling is how to allocate workpieces to each workshop reasonably, achieving a balanced workload for each workshop and ensuring the balance of processing time for each workpiece in each workshop. However, traditional workshop scheduling mechanisms, research methods and optimization strategies for single shops are difficult to achieve ideal results in distributed manufacturing problem research. Therefore, scholars have gradually explored the distributed scheduling problem in order to improve the scheduling ability and workshop efficiency of actual production, and have developed scheduling models and optimization algorithms for multiple factories, workshops and manufacturing processes. The large number of tasks, strong production continuity and large number of processes in distributed shop scheduling led to huge scheduling scheme scale, which is one of the main factors that make it difficult to achieve efficient and global optimization ^[13]. Blockchain can potentially meet the need for decentralized collaboration, that is, ensuring trust on a technical level ^[14]. Blockchain has the advantages of distributed consensus and tamper-resistance, enabling decentralized and autonomous manufacturing collaboration ^[15]. The integration of industrial Internet and blockchain ^[16] can create a digital twin of physical space and establish an online decentralized social manufacturing network, which can realize the overall collaborative optimization of distributed manufacturing and improve the operational efficiency of distributed manufacturing systems ^[17]. At present, there is still a lack of edge cloud ^[18] collaborative scheduling framework and mechanism that can effectively support distributed intelligent manufacturing systems, and rapidly respond to dynamic anomalies and interference events ^[19].

Multi-factory production planning and scheduling have been applied in various industries, and many industries have benefited from geographically dispersed factories, such as semiconductor manufacturing, concrete industry, automotive industry, pharmaceutical industry and textile industry. Reality has shown that efficient distributed workshop scheduling methods can achieve the optimization of production and manufacturing processes, energy savings, consumption reduction, emission reduction and cost reduction for enterprises ^[20]. Looking at the research status of distributed workshop scheduling in recent years, the research status of distributed workshop scheduling has become a hot topic in the field of manufacturing systems. This article briefly discusses the necessity of multi-factory production planning and scheduling, first clarifies the research method of the specific review in this article, and then reviews the literature on scheduling problems from the perspectives of workshop types, workshop configurations, constraint types and objective functions. According to the classification of workshop types, it reviews the scheduling problems of distributed parallel machine scheduling, distributed flow shop scheduling, distributed job shop scheduling and distributed assembly shop scheduling, and finally summarizes and gives research prospects.

The organization of the paper is as follows. In the first section, we describe the methods used in retrieving, classifying and reviewing relevant literature. Sections two through five classify distributed scheduling by workshop type, analyze literature related to multi-factory production planning and distributed scheduling and identify specific features, typical constraints and assumptions of the multi-factory production planning and scheduling models. Literature is classified based on the objective function considered and the configuration environment, and structured reviews of current literature on distributed scheduling are provided based on the solution methods and case studies of the key literature in each section. Finally, in section six, we summarize the results of the review and provide possible directions for future research and management insights.

2.   Scope and methodology

The methodology used in this paper consists of seven steps (see Figure 1). First, we start the research by identifying the research topic and defining the boundaries of the review. We declare our research intentions intention and objective of this study in the introduction and describe the scope of our review in this chapter. In a second step, before tackling the distributed scheduling literature, we needed to identify distributed metrics that were applicable to the manufacturing environment. To do this, we first searched for a number of recent papers that discussed the use of distributed metrics. We then searched the literature by querying journal search engines using specific keywords (e.g., "distributed shop floor" or "distributed manufacturing"). We then identify all the metrics, classify them into four shop types: distributed parallel machine, distributed flow shop, distributed job shop and distributed assembly shop, and collect them into a library of metrics. We then use this library as a reference to generate classification attributes when reviewing the distributed shop floor scheduling paper.

The four semantic fields on which the literature search was based were: (i) field 1: "distributed"; (ii) field 2: "Shop scheduling"; (iii) field 3: "multi-factory"; (iv) field 4: "Factory distribution". Each semantic field is made up of the keywords selected after checking their relevance through individual searches. In the exploration phase, all papers published after 2010 were considered, with a focus on the period from 2011 to 2023. Given the complexity and size of the queries to be completed, in order to simplify them, we decided to divide them up and formulate them separately for all four studied semantic domains (distributed, shop scheduling, multi-factory, factory assignment), and then combine their results. In this way, information can be obtained not only from the overall combination of "fields 1–4", but also from the local combination of semantic domain.

Second, the obtained documents as a whole were subjected to a first manual filtering consisting of: (i) deleting duplicate literature; (ii) Deletion of abstracts of meeting minutes; (iii) Delete literature with keywords different from the meaning of the said framework, such as "server environment" or "centralized scheduling"; (iv) Deletion is different from the subject of this study. This gave 154 documents. Subsequently, a filtering process was carried out by reading the content and performing a first analysis of the 154 preselected documents, which consisted of discarding: (i) those that represented academic contributions with no correspondence to the research framework; (ii) those documents that did not combine at least two of the semantic fields defined in the present research. After this filtering process, 117 literatures are finally screened out. Figure 2 illustrates the research framework proposed by us for classifying distributed shop scheduling references.

The statistics of the trend in the number of publications in the literature are seen in Figure 3, where papers are grouped by eleven years of publication for the sake of clarity. Given the clear trend of increasing publication numbers, although still low compared to other publications on common shop floor scheduling issues, we can infer that distributed shop floor scheduling is an area that holds promise for further development. Research in distributed shop floor scheduling has grown rapidly over the past few years, with the top three literature types distributed as Operations Research Management Science, Computer Science Artificial Intelligence and Engineering Industry, as shown in Figure 4.

Although there is a significant increase in interest in distributed scheduling problems, to our knowledge there are not many reviews of distributed scheduling in the literature. Therefore, the objectives of this paper are: (i) to classify the literature in the "Classification" section; (ii) to review the literature in the "Literature review" section and summarize the research results on distributed scheduling; (iii) to comb and summarize the literature in the "Literature analysis"; (iv) Based on the survey and analysis, the "Conclusion and future research directions" section provides possible references for future research. The problem of production scheduling has been the focus of many papers over the past decades, but most of the research has focused on non-distributed environments. With distributed players, however, we can have a flexible, demand-driven and reconfigurable production system that can adapt to increasing competition. In this environment, the management of production resources is influenced by rapid changes in market demand and shortened product lifecycles. Before concentrating on the literature on distributed scheduling, we first classify distributed scheduling problems and then survey the literature for each class separately. This paper classifies scheduling problems into five categories: single machine, parallel machine, flow shop, job shop and assembly shop, based on the nature of the shop configuration. This paper specifically describes parallel machine scheduling, flow shop scheduling, job shop scheduling and assembly shop scheduling in a distributed shop, with a focus on the distributed flow shop scheduling problem. Figure 5 shows the classification of shop types and Table 1 presents a comparison of scheduling types in a production environment. Figure 6 shows the percentage of distributed shop scheduling shop type classifications. This review analyzed 116 papers and the most common configurations in terms of manufacturing shop types were flow shop (58 papers, 50% of the total) and parallel machine (25 papers, 22%).

3.   Distributed parallel machine scheduling

Parallel machine scheduling, as an extension of the single machine scheduling problem, is a class of distributed shop scheduling problems consisting of a combination of multiple parallel machine scheduling problems (PMSP) across regions, where the workpiece processes of the workpieces to be processed within each parallel machine shop are the same and only one. Distributed parallel machine scheduling (DPMSP) combines distributed manufacturing characteristics and is more in line with the needs of actual production ^[21]. Distributed parallel machine scheduling includes subproblems such as plant allocation, subproblems such as machine allocation and scheduling within a plant, which are widely found in manufacturing industries such as automotive and chemical industries, are a common class of problems in actual manufacturing enterprises. In addition to considering the characteristics of single machine scheduling, equipment performance and environmental factors need to be taken into account.

The early research on distributed parallel machine scheduling began in 1980s, and some progress has been made in recent years. DPMSP can be divided into distributed homogeneous parallel machine scheduling problem and distributed heterogeneous parallel machine scheduling problem. Because distributed heterogeneous parallel machine scheduling problem is more suitable to the actual production situation and more difficult to solve. Therefore, it has attracted more attention from experts and scholars ^[22].

Parallel machine can be divided into identical parallel machine and unrelated parallel machine ^[23] according to the similarities and differences of equipment quantity and processing capacity in each factory. Distributed parallel machine scheduling is shown in Figure 7.

3.1.   Distributed identical parallel machine

Where identical parallel machine scheduling means that all machines can process the workpiece and each machine can process the same workpiece for the same amount of time.

Farmand et al. ^[24] solved a bi-objective integrated scheduling problem for production and distribution in a production environment with identical parallel machines by designing a multi-objective particle swarm optimization and a non-dominated ranking genetic algorithm (NSGA-II) with a single-point crossover operator and a heuristic mutation operator using mutation functions.

Abedi et al. ^[25] proposed a new BPM dual-objective mixed integer linear programming model for scheduling the same parallel batch machines with arbitrary job size, unequal job release time and capacity constraints. Two multi-objective optimization methods, Fast non-dominated sorting Genetic algorithm (NSGA-II) and multi-objective Imperialist Competition Algorithm (MOICA), are used to find the Pareto optimal frontier for big problems.

3.2.   Distributed unrelated parallel machine scheduling

Unrelated parallel machine, that is, the same kind of workpiece can be processed on any machine, but the processing time of the workpiece on different machines is different.

3.2.1.   Single objective unrelated parallel machine

Zheng et al. ^[26] studied the distributed unrelated parallel machine scheduling problem (DUPMSP) and proposed a hybrid imperialist competition algorithm (HICA) to minimize the total delay. Logendrana et al. ^[27] proposed six different search algorithms based on tabu search to minimize job-weighted delay in unrelated parallel processing scheduling with sequentially dependent Settings, taking into account dynamic job release and machine dynamic availability.

Behnamian et al. ^[28] studied plants processing work with identical parallel machines of different speeds, with the optimization objective of minimizing the maximum completion time between plants. After proposing a mixed-integer linear programming model for this problem, a polynomial-time heuristic algorithm was proposed, which consists of a hierarchical algorithm and a maximum processing time rule. In practice, the hierarchical algorithm and the LPT rule are used to handle the assignment of jobs to plants and the scheduling decisions for each plant respectively. For large scale problems, genetic algorithms are very effective, so for future scheduling of large-scale instances, a second algorithm, a new genetic algorithm, is introduced, a new encoding scheme is proposed and it is improved using local search.

Distributed scheduling cases with little consideration of practical processing constraints such as preventive maintenance (PM), sequence-related and machine-related setup times. Lei et al. ^[29] studied the distributed unrelated parallel machine scheduling problem with PM (DUPMSP) and proposed an artificial bee colony (DABC) to minimize the time and demonstrated the advantages of DABC by optimizing the data update colony; Gulcin et al. ^[30] studied the generalized problem of using public server scheduling, which is an unrelated parallel machine scheduling problem with series-dependent setup time and machine qualification restrictions. They considered sequence-dependent setup times and proposed taboo search (TS) and simulated annealing (SA) algorithms to minimize the total weighted tardiness; Hamza et al. ^[31] proposed a simulated annealing algorithm and a hybrid method of the sine cosine algorithm (SCA) to solve the uncorrelated parallel machine scheduling problem with sequence-related and machine-related setup times; Lei et al. ^[32] considered the distributed uncorrelated parallel machine scheduling problem with makespan minimization in heterogeneous production networks and reduced it directly to extended machine allocation by proposing a new imperialist memory competition algorithm (MICA), which uses machine assignment strings and introduces four neighborhood structures and a global search operator; Li et al. ^[33] studied the parallel machine scheduling problem with different color series, sequential correlation setup times and machine qualification restrictions, formulated an integer programming model to minimize the total delay, proposed a hybrid differential evolution (HDE) algorithm incorporating chaos theory and two local search algorithms to solve real instances of textile mills.

A literature review using maximum completion time as the sole objective is presented in Table 2. In addition, specific characteristics of applicable solving algorithms and models are reported in Table 2.

3.2.2.   Multi-objective unrelated parallel machine

Lei et al. ^[34] considered multi-objective DUPMSP, then for the distributed uncorrelated parallel machine scheduling problem, they proposed an improved artificial bee colony (IABC) to minimize both manufacturing and total tardiness. To minimize manufacturing time, late/early penalties and machine purchase costs, Shahidi-Zadeh et al. ^[35] consider a new bi-objective model for batch processor scheduling problems with uncorrelated parallel machines, while proposing a multi-objective harmony search (MOHS) algorithm for large problems to calculate better machine types and number of machines per machine. He et al. ^[36] developed a novel mixed integer linear programming (MILP) model for the decentralized plant scheduling problem, proposing a new solution algorithm based on the interoperability of metaheuristics and mathematical planning techniques, where a set of transport vehicles is used to transport goods between parallel plants to minimize the production cost of all plants. Pan et al. ^[37] considered the distributed heterogeneous parallel machine scheduling problem. With the objective of minimizing the maximum completion time, the DEPMSP is solved by integrating plant allocation and machine allocation into extended machine allocation to deal with the coupling of subproblems, proposing a knowledge-based double cluster optimization (KTPO) algorithm that reduces both total energy consumption and total tardiness. Zhang et al. ^[38] proposed a memetic algorithm based on the NSGA-II architecture by focusing on the new objective of total operational utility of all distributed equipment from the demand side, where total energy consumption, including processing energy and transportation energy on the manufacturing side, is another objective, and integrating it into an energy-efficient production scheduling model based on a distributed parallel machine environment. Wu et al. ^[39] consider an energy efficient bi-objective unrelated parallel machine scheduling problem and, to solve the parallel machine is speed-scaling problem, propose a Modal Differential Evolution (MDE) algorithm with speed tuning and work swap heuristics aimed at minimizing manufacturing time and total energy consumption. Behnamian ^[40] considered a novel multi-plant production network scheduling problem and proposed a multi-objective hybrid forbidden search-VNS algorithm, but their model and algorithm had some serious drawbacks that led to the complete ineffectiveness of the model and algorithm. Therefore, Yazdani et al. ^[41] considered an improved model and solution algorithm based on the Behnamian. The problem of a multi-plant parallel machine problem was considered, three mathematical models were proposed for the makespan and total completion time objectives, and an effective meta-heuristic based on the artificial bee colony algorithm was proposed.

In current industrial production engineering, plant allocation schemes can be given in advance, but allowing a heavily loaded plant to transfer orders to other plants for production requires consideration not only of the distribution of workpieces between plants and the order in which they are processed on machines, but also of the different processing capacities of multiple plants. The study of the multi-plant problem is slightly flawed because when considering multi-plant scheduling of parallel machines, most scholars have studied the homogeneous plant problem for which scheduling is designed as the distributed multi-parallel machine scheduling problem (DMPMSP), where several plants are geographically scattered in different locations, each plant may have a different objective function as a production agent, all use parallel machines, and jobs can be transported from an overloaded plant to a plant with a lower workload. For example, in the multi-factory model early considered by Behnamian and Fatemi Ghomi ^[42], there are multiple parallel machines in each factory, and the machines in each factory may have different processing speeds, ignoring the time required to transport work between them. In order to minimize the total time of all operations, they proposed a MILP model. Based on the maximum processing time heuristic and genetic algorithm (GA), the proposed GA is improved by using the local search algorithm; a distributed production network with parallel plants considered by Behnamian ^[43] subsequently set up a mixed integer planning model where jobs could be transported from overloaded plants to plants with lower workloads; in the same year, Behnamian ^[44] also proposed a MIP model for the problem of distributed production networks with heterogeneous parallel plants distributed in different geographical locations. In this study, we proposed anarchic particle swarm optimization (APSO) based on the anarchic behavior of society to minimize the maximum completion time. Behnamian and Fatemi Ghomi ^[45] addressed the multi-plant scheduling problem for heterogeneous plants and parallel machines, modelling the scheduling problem as mixed-integer linear programming in order to simultaneously minimize the sum of the lead and delay of jobs and the total completion time. Behnamian ^[46] considered the transport time of jobs between multiple plants, uncorrelated processing times of jobs in parallel machines depend on the machine and setup times. To minimize the time, a mixed integer linear model is first proposed, which combines both types of modelling. Then, a super heuristic algorithm (HHA) is designed.

3.2.3.   Distributed heterogeneous parallel machine with assembly lines

The distributed heterogeneous parallel machine scheduling problem with assembly lines (DHPMSPAS) refers to the existence of a distributed set of identical factories, each with a set of unrelated parallel machines in the production phase and one assembly machine in the assembly phase. Jobs must be assigned to one of the distributed plants and processed by one of the unrelated parallel machines. There is an assembly phase with one assembly machine and the jobs that have been processed are assembled into the final product by means of a defined assembly procedure. It is to further consider the workpiece assembly problem on the DHPMSP problem model, that is, to further improve the model of the factory in the actual production process. The study of the DHPMSPAS problem is of industrial importance, but there is less research on DHPMSPAS and therefore it is of great academic value.

Hatami et al. ^[47] studied the production scheduling problem in the production and assembly phases of distributed heterogeneous parallel machines and proposed a mixed integer linear programming (MILP) model with the objective of minimizing the manufacturing time in the assembly phase. Sara et al. ^[48] studied the distributed uncorrelated parallel machine problem and proposed a mathematical model and two high-performance heuristics.

In summary, most of the existing studies are on homogeneous plants or same-speed machines, but actual multi-plants are often heterogeneous plants, where the processing capacity and processing environment of each plant differ greatly, and there are mostly unrelated parallel machines in the plants, so the scheduling coordination between plants is more difficult, closer to actual production and has higher application value. Therefore, future research on the scheduling of distributed parallel machine shops in heterogeneous environments is expected to increase.

The current research on scheduling problems considering maximum completion time and total delay time in a distributed environment is of practical importance, but rarely takes into account the various optimization objectives, constraints and various uncertainties required in a real production shop, such as energy consumption, cost, emergency order insertion during production, machine failure and machine maintenance, etc. The industrial value is insufficient. Therefore, it is necessary to further investigate the distributed unrelated parallel machine scheduling problem (DUPMSP) with more objectives including energy consumption objectives and more practical constraints. In the future, for parallel machine heterogeneous workshops, the problem can be extended for different plants with heterogeneous constraints on materials, personnel and other resources by considering in the proposed model the set-up time, the transport phases between production and assembly, the heterogeneous production plants, complex assembly stages with parallel assembly machines or assembly shops in order to make it more compatible with the actual production situation.

4.   Distributed flow shop scheduling

The flow shop scheduling problem, also known as the parallel flow line problem, has become a challenging frontier topic in the field of intelligent manufacturing due to its characteristics of multiple resources, multiple objectives and multiple constraints ^[49]. As a core aspect of distributed manufacturing, the distributed flow shop scheduling problem has become the focus of research in both academia and industry, and initial progress has been made.

Currently, there is a wealth of research on the distributed flow shop scheduling problem, mainly focusing on the study of distributed replacement flow shop scheduling and distributed hybrid flow shop scheduling. The distributed permutation flow-shop scheduling problem based on this context has been widely focused and studied by many scholars ^[50], which is both an extension of the traditional flow shop scheduling problem and a sub-problem of the distributed flow shop scheduling problem, which has been proved to be an NP-hard problem.

4.1.   Distributed permutation flow-shop scheduling

The permutation flow shop (1954) has been one of the most interesting problems for researchers since the classical scheduling problem. Flow shop configurations are common in manufacturing environments, which are characterized by $n$ tasks being processed on $m$ machines. Each job passes through the machines in the same process order, that is, starting with machine 1, then going to machine 2, . up to machine $\mathcal{M}$. The decision to be made is to choose the order in which the different jobs pass through the machines, and the intermediate storage capacity between machines is considered to be infinite, with machines always available for processing jobs.

If all machines have the same sequence of jobs, the scheduling is called permutation and the problem of choosing the optimal scheduling is called the permutation flow shop problem (PFSP).

The distributed permutation flow shop scheduling problem is a distributed job shop scheduling problem composed of multiple permutation flow shop scheduling problems, in which all machines in each permutation flow shop have the same processing sequence of jobs to be processed. DPFSP is a f-shop distributed in different regions, which jointly processes $n$ jobs with the same processing path on $m$ machines. Through reasonable allocation and sorting, the maximum completion time of f-shop is minimized ^[51]. The maximum completion time of DPFSP is the time required for all processing of $n$ workpieces in the $f$ workshop ^[52], which is determined by the workshop with the longest processing time in the $f$ workshop. The distributed permutation flow shop scheduling is shown in Figure 8.

Distributed permutation flow shop scheduling problem is a new scheduling problem, which is a generalization of classical permutation flow shop scheduling problem (PFSP). A common assumption in most PFSP studies is that there is only one production center or factory, which means that all jobs are assumed to be handled in the same factory. However, in order to move closer to the trend of globalization, more and more enterprise managers have transformed traditional single factories into distributed factories to meet the market's requirements for high quality, low risk and fast response. In a distributed environment, Naderi and Ruiz ^[53] named the distributed permutation flow shop scheduling problem (DPFSP, denoted as DF / prmu / ${C}_{\mathrm{m}\mathrm{a}\mathrm{x}}$). The two introduced a generalization of the classical permutation flow shop scheduling problem, called the distributed permutation flow shop scheduling problem, in which a group of factories are combined with the classical problem, and each job is allowed to be processed in a factory. Aiming at the optimization criterion of minimizing the maximum completion time in all factories, the two proposed 14 mixed integer linear programming models and developed 420 factory allocation rules. Taillard ^[54] developed 720 heuristic methods based on scheduling rules, effective construction heuristics and variable neighborhood descent methods on the basis of the flow shop scheduling problem designed in a single factory mode, which is suitable for the verification of DPFSP algorithm.

Based on these examples of Taillard, Gao et al. ^[55] proposed a tabu search algorithm to solve DPFSP, a method of exchanging job sequences to generate neighborhoods, and tested the performance of the algorithm. The proposed tabu algorithm outperforms all existing algorithms, including heuristic algorithms (i.e., NEH1, NEH2, VND (a) and VND (b)) and hybrid genetic algorithms. In addition, an improved local search method is proposed and combined with tabu algorithm. However, the research of Gao et al. only focused on some examples, and did not list the results of direct comparison. In response to this shortcoming, Wang et al. ^[56] first used EDA to solve DPFSP-related problems. First, the earliest completion factory rules are used for permutation-based coding to generate feasible scheduling and calculate scheduling target values; On this basis, the probability model of generating new individuals is designed, and the corresponding probability update mechanism is given. By sampling the probability model, new individuals can be generated in the promising search area. In addition, according to the characteristics of the problem, some local search operators are designed to enhance the development ability and utilize the potential individuals.

4.1.1.   Single objective distributed permutation flow shop

In the actual production process of an enterprise, the optimization goal of the scheduling problem is usually the focus of its attention. In the optimization research of DPFSP, the most common optimization goal is to minimize the maximum completion time. Other optimization goals usually include minimizing total flow time, average flow time, total tardiness time and energy consumption. The change of production from single factory to multiple factories is to reduce processing time and improve processing efficiency. Therefore, Makespan is the most commonly considered objective function. In fact, about 66 % of the reviewed papers regard Makespan as a single goal. Therefore, we separate this goal from other completion time goals.

Optimizing the maximum completion time can not only improve the productivity of enterprises but also reduce the production cost. Ferone et al. ^[57] proposed an efficient and parameter-free algorithm for solving this problem, which combines an improved iterative local search algorithm and evaluates its effectiveness. Huang et al. ^[58] designed an iterative greedy algorithm, which contains the restart strategy of six different operators, and proposed two local search methods to get rid of local optimization and solve the DPFSP considering the preparation time constraints related to the workpiece sequence. Xu et al. ^[59] proposed a hybrid immune algorithm (HIA), proposed a local search containing four search operators, and designed a special crossover operator to effectively solve the DPFSP. Arshad et al. ^[60] considered this goal and proposed a meta-heuristic tabu search (TS) to develop MILP formulations to find the best solution. Alper ^[61] developed a new mixed integer linear programming model for distributed permutation flow shop and developed a bending decomposition algorithm.

A literature review using maximum completion time as the sole objective is presented in Table 3. In addition, specific characteristics of applicable solving algorithms and models are reported in Table 3.

The optimization algorithms in the above literature are used to solve the problem with the goal of minimizing Makespan, and for specific problems, different goals need to be set or solved by other optimization methods. Review the related literature on the distributed permutation shop problem and other completion time-based goals. In particular, we will focus on the following objective functions: Total flow time, total flow time and total weighted flow time.

When a batch of jobs needs to be completed as soon as possible, total flow time (TFT) has been identified as a more relevant and meaningful goal in today's dynamic manufacturing environment. Minimizing total flow time helps to reduce work flow and optimize inventory savings. In order to minimize the total flow time, Mao et al. ^[62] studied the distributed flow shop with preventive maintenance to minimize the total flow time, and improved the meme algorithm based on the population of hash graph. Yu et al. ^[63] studied the DPFSP of SDST under total flow time minimization, proposed three constructive heuristic frameworks, proposed four different neighborhood structures and proposed a discrete artificial bee colony (DABC) method based on variable neighborhood structure (DABCvns). Victor et al. ^[64] proposed eighteen constructive heuristic methods, provided several attributes and allocation rules, and effectively solved the distributed permutation flow shop with minimum total flow time.

In the classical distributed permutation flow shop scheduling problem (DPFSP), there are many studies on the minimization of completion time, total flow time and total delay. Most of the above literature focuses on minimizing the maximum completion time, total flow time or total delay ^[65], which are very commonly used classical indicators. Some scholars have also studied different indicators, such as Li et al. ^[66] to solve DPFSP with delivery date and cumulative revenue. An algorithm called Insert-Pruning is proposed to improve the search efficiency, and some modifications and improvements are made to the IG algorithm, including destruction method, local search method and acceptance criteria. Villarinho et al. ^[67] studied the distributed flow shop scheduling problem with delivery date and cumulative revenue, and proposed a partial stochastic heuristic method for the deterministic version of the problem. Then, by encapsulating it into the variable neighborhood descent framework, this heuristic method is extended to meta-heuristic. Li et al. ^[68] studied the distributed flow shop scheduling problem with batch delivery constraints, while minimizing manufacturing time and energy consumption. A hybrid algorithm combining WALE optimization algorithm (WOA) and local search heuristic is proposed.

4.1.2.   Multi-objective distributed permutation flow shop

A single optimization criterion is not enough to meet the conditions of actual processing, and there may be multiple mutually restrictive objectives. Multi-objectives often considered in actual production include Makespan, total flow time, total cost, total tardiness and maximum tardiness time.

Rifai et al. ^[69] proposed a newly developed multi-objective adaptive large neighborhood search (MOALNS) to generate near-optimal solutions with the goal of simultaneously minimizing Makespan, average delay time and total production cost. Different construction operators are used to balance and strengthen the search process of the algorithm in order to better search for the optimal solution. Deng et al. ^[70] proposed a competitive meme algorithm to minimize Makespan and total tardiness. The two populations are optimized using a variety of search methods and knowledge-based local search, and the target balance between the populations is improved by exchanging the two populations to achieve multi-objective optimization.

Under the pressure of climate change and global warming, green manufacturing, which aims to reduce environmental pollution and energy waste, has attracted more and more global attention ^[71]. Greenhouse gases constitute the majority of environmental pollution, especially carbon dioxide, which is mainly produced in the combustion of fossil fuels. Since most of the electricity comes from fossil fuels, rational use of energy will effectively reduce carbon emissions. In most countries, carbon emissions from manufacturing are restricted. Many governments have launched low-carbon projects to advocate for the reduction of carbon emissions. At the same time, with the increasing energy costs, manufacturing enterprises pay more and more attention to reducing energy consumption. Therefore, it is of great significance to develop effective energy-saving measures and technologies, especially considering energy efficiency in conjunction with traditional economic standards such as makespan ^[72]. Wu et al. ^[73] proposed an adaptive multi-objective variable neighborhood search (AM-VNS) algorithm to minimize makespan and total energy consumption for an energy-efficient permutation-free flow shop scheduling problem. Chen et al. ^[74] studied the energy-efficient distributed no-idle permutation flow shop scheduling problem that simultaneously minimizes the maximum completion time and total energy consumption. Using the properties of the collaborative optimization algorithm and some collaborative mechanisms, a collaborative optimization algorithm (COA) was proposed to increase energy consumption through speed control strategies.

In the classical distributed permutation flow shop scheduling problem (DPFSP), jobs are regarded as independent entities and processed independently. However, in many practical cases, many jobs actually come from the same customer order. In this case, processing work from the same customer order in a single factory can reduce transportation costs and management burdens. In the distributed permutation flow shop scheduling problem with customer order constraints, Meng et al. ^[75] introduced customer order constraints into DPFSP with the goal of minimizing the maximum completion time or the maximum completion time between factories. Inspired by the NEH2 method, three heuristic methods are proposed, namely variable neighborhood descent (ORVND), artificial bee colony (ORABC) and iterative greedy (ORIG).

4.1.3.   Distributed permutation flow shop with constraints

In order to refine management and scheduling, in the process of organization and production, in addition to considering the basic production process factors, some special production constraints caused by product uniqueness and processing environment constraints should also be fully considered. These constraints mainly include: blocking, batch processing, no-idle, machine failure, preventive maintenance, sequence dependent set time (SDST) constraints, etc., It is a realistic constraint condition for the processing and manufacturing links in the current intelligent factory, which meets some demand scenarios that may occur in the actual production process, and also expands and improves the distributed scheduling problem, which has certain research value.

Wang et al. ^[76] proposed a hybrid distribution estimation algorithm based on fuzzy logic (FL-HEDA) to solve DPFSP under machine failure. Mao et al. ^[77] studied the distributed permutation flow shop scheduling problem with preventive maintenance operations (PM / DPFSP). In this paper, a multi-start iterative greedy (MSIG) algorithm using improved NEH2 heuristic algorithm and dropout operation to initialize the solution is proposed.

In the literature, the special case of no intermediate buffer or the machine environment with zero capacity of all buffers is called blocking or no waiting flow shop. The blocking flow shop will keep the completed job on the current computer until the next machine is available, while in the no-wait flow shop, the processing of each job must be an uninterrupted process on or between machines before it can be completed. Shao et al. ^[78] used the proposed iterative greedy (IG) algorithm and the makespan criterion to solve the distributed no-wait flow shop scheduling problem (DNWFSP). In order to solve the distributed no-wait flow shop scheduling problem, Lin et al. ^[79] established a mixed integer programming (MIP) mathematical model and an enhanced version of the iterative cocktail greedy (ICG) algorithm. Zhang et al. ^[80] proposed a differential evolution algorithm running in a continuous search space and a discrete differential evolution algorithm directly implemented in a combined search space under distributed and limited buffer constraints. Zhao et al. ^[81] proposed an integrated discrete differential evolution (EDE) algorithm to deal with the blocking DPFSP with makespan criterion.

In practice, there is always a time interval between two consecutive jobs that are processed on the same machine, because the machine usually undergoes some additional operations between processing two consecutive jobs, such as machine cleaning, tool change, job transportation, etc. Usually, we call the time interval sequence dependent setup time (SDST), because the duration of such operations depends not only on the current job being processed, but also on the last job being processed. In 2021, Han et al. ^[82] studied DPFSP by minimizing the span criterion under the constraint of sequence correlation setting time (SDST), and proposed a NIG algorithm based on two-stage local search strategy. In 2022, Han et al. ^[83] added blocking constraints and sequence-dependent setup times (SDST), and proposed an effective iterative greedy algorithm based on learning-based variable neighborhood search algorithm (VNIG) to deal with the distributed blocking flow shop scheduling problem with sequence-dependent setup times (DBFSP_SDST). Shao et al. ^[84] considered a multi-objective distributed no-wait flow shop scheduling problem with sequence-dependent setup times. The constraint is no-wait and preparation time. A Pareto-based estimation of distribution algorithm (PEDA) was proposed. In 2020 ^[85] and 2021 ^[86], Huang et al. considered two sequence-dependent setup times in DPFSP, and proposed an iterative greedy algorithm with restart scheme (IGR), three effective constructive heuristic methods and discrete bee colony optimization.

Meng et al. ^[87] introduced customer order constraints into DPFSP and developed three meta-heuristic methods, namely variable neighborhood descent (ORVND), artificial bee colony (ORABC) and iterative greedy (ORIG). Cai et al. ^[88] studied the distributed flow shop scheduling problem (DPFSSP) with transportation and eligibility constrains. They proposed a mathematical model aiming at minimizing completion time, maximum delay, transportation cost and installation cost, and then developed several heuristic algorithms for solving single-objective problems and genetic algorithms for solving multi-objective problems.

4.1.4.   Distributed assembly permutation flow-shop scheduling problem

The distributed assembly permutation flow shop scheduling problem (DAPFSSP) is a two-stage scheduling problem. The workpiece processing stage consists of F permutation flow shops, which is a distributed permutation flow shop scheduling. The product assembly stage is composed of an assembly mechanism, which belongs to a single machine assembly scheduling. The workpiece goes through two processes: processing and assembly.

Hatami et al. ^[89] first proposed the mixed integer programming model of DAPFSSP in 2013, and proposed two simple and practical algorithms to solve DAPFSSP.

In order to optimize the maximum completion time, Quan-Ke et al. ^[90] considered multiple identical factories, each factory consists of a parts processing flow shop and a product processing assembly line. In order to meet the needs of different CPU time and solution quality, three constructive heuristics, two variable neighborhood search methods and an iterative greedy algorithm are proposed. Li et al. ^[91] used a genetic algorithm with enhanced crossover strategy and three different local search methods to solve DAPFSP. Daniele et al. ^[92] used a biased-randomized iterated local search metaheuristic; Lin et al. ^[93] proposed a backtracking search hyper-heuristic (BS-HH) algorithm composed of ten heuristic structures to solve DAPFSP. Zhang et al. ^[94] established a computational model, and then proposed a construction heuristic (TPHS) and two hybrid meta-heuristic (HVNS and HPSO); Deng et al. ^[95] proposed a mixed integer linear programming model and a competitive memetic algorithm (CMA). Hong-Yan et al. ^[96] proposed three DIWO-based algorithms by combining the knowledge of specific problems and the idea of invasive weed optimization: two-stage discrete invasive weed optimization (TDIWO), discrete invasive weed optimization with hybrid search operator (HDIWO) and discrete invasive weed optimization with selection probability (HDIWO). Zhao et al. ^[97] proposed a memetic discrete differential evolution (MDDE) algorithm to solve the distributed permutation flow shop scheduling problem (DPFSP) to minimize the manufacturing time. In addition, they proposed an enhanced NEH method to generate potential candidate solutions, and used Taillard's acceleration method to improve the efficiency of MDDE.

Xiong et al. ^[98] established a mathematical model for the distributed two-stage assembly flow shop scheduling problem, and proposed a variable neighborhood search (VNS) algorithm and a hybrid genetic algorithm combined with reduced variable neighborhood search (GA-RVNS). The DAFJSP problem can be decomposed into multiple flexible job shop scheduling problems and multiple single-machine factory scheduling problems. Wu et al. ^[99] proposed an improved differential evolution simulated annealing algorithm (IDESAA) to minimize lead / tardiness and total cost simultaneously. Minimizing the total flow time helps to evenly distribute production resources and optimize inventory savings. In order to minimize makespan and total flow time (TF) simultaneously, Huang et al. ^[100] collected group thinking on the basis of traditional IGA, and proposed an improved iterative greedy algorithm based on group thinking to deal with distributed assembly flow shop scheduling problem (DAPFSP) with total flow time (TF) criterion.

With the introduction of the concept of green manufacturing, energy conservation has become a priority issue for the manufacturing industry in recent years. As an important process in many manufacturing processes, welding production is a typical high energy consumption process in the manufacturing industry, the improvement of its efficiency is of great significance to the whole manufacturing process. Distributed welding permutation flow shop scheduling problem is an extension of distributed permutation flow shop scheduling problem. Distributed welding flow shop manufacturing is a new manufacturing mode, which consists of a set of identical welding flow shop factories. In addition, the welding workshop allows multiple machines to process a workpiece at the same time. Increasing the number of machines can shorten the processing time of the operation, but it also wastes more energy. Therefore, it is of great significance to consider the total energy consumption in this scheduling. In order to save energy DHWFSP, WANG et al. ^[101] established a mathematical model to optimize production efficiency and energy cost under constraints. In order to obtain the Pareto solution set, an improved MOEA / D algorithm based on genetic operator is proposed, and the update operator is constructed, and the local search strategy in different directions is adopted. In order to verify the effectiveness of this method and other MOEA / D methods, numerical comparison experiments are carried out. However, the welding workshop is very different from the mechanical workshop. During welding, multiple welding machines will weld the same workpiece at the same time. Therefore, the traditional mechanical workshop scheduling models (including energy consumption models) and methods cannot be directly applied to the welding workshop scheduling problem (WSSP). In the last year, his team ^[102] proposed a multi-objective mixed integer programming model for energy-saving scheduling of distributed welding flow shop, and proposed a multi-objective whale swarm algorithm to optimize total energy consumption and manufacturing span. However, they do not take into account the transport between processes.

4.2.   Distributed hybrid flow shop scheduling

The mixed flowshop scheduling problem has been widely applied in a single factory, however, according to the development trend, it should be fully studied in combination with distributed manufacturing. In current research, scholars continue to focus on the distributed mixed flowshop scheduling problem (DHFSP), and consider the real production situation. Cai et al. ^[103] considered DHFSP with sequence-related setup times where the factory assignment and the first stage machine allocation are integrated together to propose a new randomly weighted frog-leaping algorithm with quality by modularity (MQSFLA) to minimize total delay and manufacturing time at the same time. Later the same year, Cai et al. ^[104] further studied DHFSP with multiprocessor tasks, and proposed a dynamic shuffle frog-leaping algorithm (DSFLA) to minimize the maximum completion time, and designed a disruption construction process in the meme to obtain lower bounds. Lu et al. ^[105] proposed a Pareto-based hybrid iterative greedy algorithm (MOHIG) to solve energy-efficient DHFSP, reducing manufacturing time and total energy consumption (TEC). Hu et al. ^[106] proposed three fast heuristics (based on CR, SLACK and EDD) and an adaptive human learning genetic algorithm (AHLBGA) to minimize the sum of earliness, tardiness and delivery cost for integrated production and distribution scheduling problem (IPDSP) with factory qualification and third-party logistics (3PL) to improve supply chain efficiency and competitiveness. Lu et al. ^[107] studied energy-efficient scheduling for distributed flowshops with heterogeneous factories containing permutation and mixed flowshops: they first established a new mathematical model to minimize manufacturing and total energy consumption, then designed a hybrid multi-objective optimization algorithm combining iterative greedy (IG) and efficient local search to provide a set of balanced solutions. Jiang et al. ^[108] solved the energy-aware distributed mixed flowshop scheduling problem with multiprocessor tasks by simultaneously considering two objectives (completion time and total energy consumption) and proposed a mixed linear programming model and a novel multi-objective evolutionary algorithm based on decomposition (NMOEA/D).

The concepts of fuzziness and flexibility are prevalent in actual manufacturing systems, because machines often have multiple functions and cannot know exactly in advance the processing time. If there is inadequate DHFSP research with uncertainty, meaning that the constraints considered in the problem model are few, there may be a certain gap between research results and the actual production process. Most existing scheduling optimization methods are limited to deterministic environments and do not consider uncertain factors that may cause processing time to change during product production.

Research on the distributed hybrid flow shop scheduling problem with fuzzy processing time is crucial for practical applications. In order to make the scheduling plan more in line with the actual production situation of the workshop, reduce the chaos caused by unexpected situations and improve the production efficiency, Cai et al. ^[109] considered the distributed energy-saving hybrid flow shop scheduling problem (DEHFSP) with fuzzy processing time. They proposed a cooperative mixed frog-leaping algorithm (CSFLA) to optimize the fuzzy makespan, the total protocol index and the fuzzy total energy consumption, and utilized iterative greedy, variable neighborhood search and global search algorithms, as well as adaptive population mixture methods to improve the search efficiency. Zheng et al. ^[110] considered the uncertainty of distributed manufacturing systems and solved a multi-objective fuzzy distributed hybrid flow shop scheduling problem with fuzzy processing time and fuzzy due dates. In order to simultaneously optimize the fuzzy total delay and robustness, they proposed a collaborative evolution algorithm with problem-specific strategies by reasonably combining the Estimation of Distribution Algorithm (EDA) and Iterative Greedy (IG) search algorithms.

Due to limited space and storage capacity, limited buffers are usually present in some distributed manufacturing systems. Therefore, Distributed Permutation Flow Shop Scheduling Problem with Limited Buffer (DPFSP-LB) is closer to actual production environments. Wang et al. ^[111] proposed a knowledge-based collaborative algorithm (KCA) for solving the EEDPFSP based on the complexity of distributed and multi-objective optimization, with the goal of minimizing manufacturing and total energy consumption, but they did not consider the limited buffer in this problem. Zhang et al. ^[112] first attempted to explore DPFSP-LB by minimizing manufacturing span. However, DPFSP-LB only considers economic standards (such as makespan) and ignores environmental standards (such as energy consumption or carbon emissions). Therefore, Lu et al. ^[113] developed a new Pareto-based Collaborative Multi-Objective Optimization Algorithm (CMOA) to minimize manufacturing span and total energy consumption.

Since the beginning of the 21^st century, a new type of manufacturing workshop – the reentrant hybrid flow shop – has attracted the attention of scholars at home and abroad due to the inherent need of manufacturing companies to improve production efficiency and increase production flexibility. Reentrant hybrid flow shop scheduling (RHFS) means that jobs may need to enter certain stations multiple times and be processed multiple times on the same machine. The distributed RHFS problem is more complex than the traditional hybrid flow shop (HFS), and research on its modeling, optimization theory and methods is a challenging issue. Geng et al. ^[114] established a mathematical model aimed at minimizing the maximum completion time and total energy cost under the constraint of customer orders in a high-efficiency distributed reentrant hybrid flow shop scheduling problem considering time-of-use electricity pricing. In the study, some customer orders need to be produced in multiple factories, and jobs belonging to the same customer order must be processed in one factory. First, a memetic algorithm (MA) was proposed to solve the problem. Then, coding and decoding methods, energy-saving steps, three heuristic rules for population initialization and some neighborhood search methods were designed. Dong et al. ^[115] established a distributed two-stage reentrant hybrid flow shop double-layer scheduling model to pursue a green manufacturing pattern and achieve energy conservation and emission reduction. They proposed an improved hybrid salp swarm (SSA) and NSGA-III algorithm to minimize the total carbon emissions and total energy cost.

The distributed hybrid flow shop scheduling problem (DHFSP) is an extension of the hybrid flow shop scheduling problem in a distributed manufacturing environment, which has received widespread attention in recent years. However, research on DHFSP has not yet considered constraints commonly found in actual production processes, such as transportation and assembly.

4.3.   Summary of distributed flow shop scheduling

Nowadays, the impact of industrial processes, energy consumption and carbon emissions on the earth has made environmental sustainability and protection of the Earth's health one of the most interesting challenges faced with population growth and the depletion of natural resources. In a report by Alaouchiche et al. ^[116], it was stated that industrial sector energy consumption accounted for 31.7% of the world's energy consumption (see Figure 9). The industry consumes one-third of the world's energy, so energy efficiency in manufacturing can help reduce pollution emissions and improve resource utilization. For many years, companies have been almost exclusively focused on economic aspects, but this viewpoint, which ignores sustainable development, must change. Additionally, the resources used in industry are not always renewable, and as resources become scarcer, the prices of these resources continue to rise.

Therefore, improving energy efficiency in manufacturing is becoming an inevitable requirement for energy conservation, emission reduction and sustainable development. As mentioned above, due to the large proportion of energy consumption in welding activities, the energy efficiency of welding workshops is receiving increasing attention. Therefore, proposing effective scheduling methods to improve the efficiency of welding workshops and reduce energy consumption is very necessary. In addition, although some scholars combine the welding shop scheduling problem with the distributed permutation flow shop scheduling problem, there are still few researches on the welding shop scheduling problem at present. In-depth research on the distributed flow shop scheduling problem of welding production has certain reference significance for the development of scheduling theory and solving practical production problems.

To summarize this section on the overview of distributed flow shop scheduling, we analyzed and classified the 58 key research works on distributed flow shop scheduling reviewed in the literature based on the number and type of optimization objectives. Figure 10 shows the proportion of published research literature classified according to the number of objective functions. Among the 58 published literature, the contribution rate of single-objective models was 62%, while the contribution rates of two-objective models and multiple-objective models were 26 and 12%, respectively.

In this section, we analyzed in more detail the objective functions and solution methods used in the literature. Similar to the literature on traditional production scheduling, minimizing the maximum completion time is the most commonly used objective in distributed problems. The methods for solving the problem are quite diversified and depend on the configuration of the workshop, The overall trend of using metaheuristics in all fields is evident.

5.   Distributed job shop scheduling problem

In recent years, manufacturing organizations have faced a series of market changes, such as shortened product life cycles, technological advancements, enormous pressure from competitors and growing customer expectations. Market conditions are becoming more dynamic and customer-driven, and manufacturing performance is no longer driven solely by product prices. Instead, other competitive factors, such as flexibility, quality and delivery, have become equally important. In today's fiercely competitive global market, to survive and compete, manufacturing companies need to be flexible, adaptable, responsive to changes and able to produce a variety of products at lower costs in a short period to meet different customer groups' needs. Flexible companies are those that can quickly enter the market, operate at the lowest total cost, and are most capable of pleasing their customers. Therefore, manufacturing flexibility is the most needed attribute of modern production systems, and the development of distributed job shop scheduling problems follows actual market changes.

5.1.   Distributed job shop

Distributed job shop scheduling problem (DJSP) deals with assigning jobs to factories and determining the operation sequence on each machine in a distributed manufacturing environment ^[117], with the ultimate goal of minimizing the total manufacturing time of all factories. In DJSP, each factory is a job shop, and the process paths of different workpieces may differ ^[118].

In the early 2000s, scholars started researching DJSP, but compared with classical job shop scheduling, literature on DJSP is relatively limited. Jia et al. studied the DJSP under different criteria in 2002 ^[119] and 2003 ^[120], and used a standard genetic algorithm (GA) to solve the problem. In 2007, Jia et al. ^[121] improved the GA for solving small and medium-sized distributed scheduling problems. Chan et al. ^[122] proposed an adaptive GA to solve distributed machining workshops and used the makespan criteria for solving larger problems. Jeong et al. ^[123] proposed a distributed collaboration method to minimize the total completion time, in which each sub-production system is responsible for assigning a set of workpieces, and the subsystems collaborate with each other and interact with shared machines to solve the DJSP. De Giovanni and Pezzella ^[124] proposed an improved GA to solve the distributed and flexible job shop scheduling problem.

Currently, research on distributed job shop scheduling has made significant progress ^[125]. Naderi et al. ^[126] established a mixed integer linear programming model, aiming to minimize the maximum completion time, and developed a new simulated annealing algorithm and greedy algorithm further to enhance the algorithm's optimization ability through local search strategies. Liu et al. ^[127] proposed a refined coding operator, which integrated the concept of probability into the parameter encoding method of real parameters to improve the genetic algorithm's performance. Their proposed algorithm can significantly shorten the chromosome's length to save computing space. Chaouch et al. ^[128] proposed a hybrid ant colony algorithm combined with local search to solve the distributed job shop scheduling problem. They also proposed a new dynamic allocation rule for factory jobs and used the Taguchi robust design method to find the optimal combination of parameters based on their ant-based algorithm.

For multi-objective distributed job shop scheduling, Luo et al. ^[129] studied the distributed flexible job shop scheduling problem and adopted an efficient memetic algorithm (EMA) to minimize factory manufacturing time, maximum workload and total energy consumption. Li et al. ^[130] used a Pareto-based hybrid taboo search algorithm (HPTSA) and various methods considering problem and objective features for initialization, applied five neighborhood structures and a reverse optimization criterion to enhance search ability while simultaneously minimizing four objectives, including completion time, maximum workload, total workload and early/late delivery (E/T) standards.

5.2.   Distributed flexible workshop

Distributed flexible job shop scheduling problem is an extension of the distributed job shop scheduling problem. Chan et al. ^[131] and Giovanni et al. studied the distributed flexible job shop scheduling problem using genetic algorithms, which drew researchers' attention to the problem of distributed job shop scheduling. The main optimization objectives in the research are manufacturing cost and manufacturing time. Figure 11 illustrates a schematic diagram of distributed flexible job shop scheduling.

To solve the distributed flexible job shop scheduling problem (DFJSP) by minimizing the maximum completion time (makespan), Meng et al. ^[132] proposed four different MILP models. As these models were not effective in solving relatively larger problems, they proposed a Constraint Programming (CP) formula to effectively solve DFJSP and demonstrated good performance in scheduling problems with makespan objectives. Marzouki et al. ^[133] proposed a novel Chemical Reaction Optimization metaheuristic algorithm for solving DFJSP. Zandieh et al. ^[134] proposed a hybrid algorithm based on the Improved Cultural Algorithm (ICA) and simulated annealing algorithm to solve the flexible job-shop scheduling problem. Lu et al. ^[135] applied an improved GA and designed and demonstrated a coding method that solves the three-dimensional solution space search problem by optimizing one-dimensional solution space. Wu et al. ^[136] proposed a new genetic algorithm (GA-OP) with a novel chromosome representation to solve the DFJSP. Compared with previous research on Hybrid Genetic Algorithm (HGA), Chang et al. ^[137] proposed a HGA method that uses the Taguchi method to optimize the GA's parameters and achieves better results.

In terms of multi-objective research on distributed flexible job shop scheduling problems, Xu et al. ^[138] studied the distributed flexible job shop scheduling problem considering outsourcing operations, established a mathematical model including four optimization objectives (completion time, cost, quality and carbon emissions) and used fuzzy analytic hierarchy process to convert the multi-objective problem into a single-objective problem. They proposed a hybrid algorithm to solve it. Meng et al. ^[139] proposed an effective hybrid frog leaping algorithm to solve large-scale energy-saving scheduling problems and minimize energy consumption.

With the development of the manufacturing industry in China, the distributed flexible job shop scheduling problem will become a more practical problem in production. Although some progress has been made in its research, existing research still needs to be further developed. For example, modeling of the distributed flexible job shop scheduling problem is studied to better guide actual production. However, in actual production processes, the scale of distributed flexible manufacturing is often very large, and there are more factors to consider, making it more prone to uncertain events such as machine failures or the insertion of rush orders, which can affect scheduling arrangements. Therefore, it is necessary to study a more realistic distributed flexible job shop scheduling model and to solve it, so that theoretical research can better guide practice and optimize the production processes of enterprises.

Currently, to minimize the construction of distributed job shop scheduling problem DFJSP, research mainly focuses on metaheuristic and heuristic algorithms, especially GA. Many scholars have applied improved genetic algorithms to the distributed flexible job shop scheduling problem, such as GA_JS with concise chromosome representation, HGA and SOP with chromosome representation. In particular, immune genetic algorithm is a multi-disciplinary optimization algorithm that combines the advantages of immune theory and basic genetic algorithms. However, they are approximation methods and cannot guarantee the optimal solution even for small problems. In addition, the performance of metaheuristic algorithms largely depends on coding and decoding rules. Different coding and decoding rules can significantly affect the performance of metaheuristic algorithms. Poorly designed metaheuristic algorithms may have poor performance. Therefore, exact algorithms and other easier-to-implement algorithms are worth researching.

In scheduling problems with makespan objectives, MILP models can effectively solve small-scale problems to optimality. However, the MILP models commonly used cannot effectively solve relatively large problems. A CP formula has been proposed by scholars for effectively solving DFJSP, as CP has shown good performance in exploring feasible solutions in a short computation time and can find high-quality solutions. The effectiveness of the CP method has been demonstrated in many combinatorial problems and can be utilized in the future.

6.   Distributed assembly workshop scheduling

As an important branch of workshop scheduling, the assembly shop scheduling problem mainly focuses on the assembly manufacturing industry. With the development of integrated and systematic manufacturing, distributed assembly shop scheduling (DASP) combining assembly shop scheduling and distributed manufacturing is gradually replacing traditional assembly shop scheduling. The distributed assembly shop scheduling problem can better adapt to complex assembly manufacturing systems ^[140], improve the coordination and agility of assembly manufacturing systems. Compared with traditional assembly shop scheduling, distributed assembly shop scheduling can better adapt to the production of small batches of multiple varieties, promote the integration and coordination of assembly manufacturing systems and therefore studying the DASP has high application research value ^[141]. The distributed assembly scheduling is shown in Figure 12.

Research on distributed assembly shop scheduling can be divided into two categories: single-objective optimization and multi-objective optimization. Single-objective optimization generally aims to minimize the maximum completion time, while multi-objective optimization also considers other factors during production. Yang et al. ^[142] proposed a new type of distributed assembly line scheduling problem (DAPFSP-FABD) with flexible assembly and batch delivery, with the objective of minimizing the total cost of delivery and delay. They proposed several batch allocation strategies for production and distribution and designed four neighborhood structures to search for the optimal batch sequence, batch allocation, product sequence and job sequence, proposing a total of 7 algorithms, including 4 heuristic algorithms, 1 variable neighborhood descent algorithm and 2 iterative greedy algorithms. Although the classical constraint holds that the capacity of the buffer is infinite, in practice, some flow shops configure to process or not to process a limited buffer, leading to job processing blocking. Shao et al. ^[143] studied the distributed assembly blocking flow line shop scheduling problem (DABFSP), which consists of two stages of production and assembly. They proposed an iterative local search (ILS) algorithm, with the goal of minimizing the longest completion time of all products.

For the dual-objective distributed assembly line scheduling problem, Niu et al. ^[144] considered the distributed assembly line scheduling problem with time constraints related to blocking and continuation sequences in prefabricated systems, proposing a two-stage collaborative evolution algorithm (TS-CCEA) to minimize completion time and total energy consumption (TEC). Jolai et al. ^[145] solved the dual-objective problem of flexible flow shop scheduling with two stages without waiting, considering the minimum manufacturing time, and developed three simulated annealing-based dual-objective optimization methods, called CWSA (classical weighted simulated annealing), NWSA (normalized weighted simulated annealing) and FSA (fuzzy simulated annealing).

For the distributed two-stage assembly line scheduling problem, where each factory has an assembly machine and the parts of each product can be processed in parallel, Deng et al. ^[146] solved the competitive multi-factor algorithm of the distributed two-stage assembly line scheduling problem with the criterion of minimizing the completion time by proposing a mixed-integer linear programming model and a competitive multi-factor algorithm (CMA); Nikzad et al. ^[147] discussed the scheduling and sorting problems of two-stage assembly flexible flow shops with dedicated assembly lines, proposing a method combining simulated annealing (SA) and imperialist competitive algorithm (ICA); Azadeh et al. ^[148] proposed an integrated computer simulation and artificial neural network (ANN) algorithm for random two-stage assembly line scheduling problems. To minimize the total delay of the distributed assembly line blocking flow shop, Zhao et al. ^[149] proposed an effective water wave optimization algorithm with specific problem knowledge; Zhang et al. ^[150] proposed a meme algorithm (MA) based on social spider optimization (SSO) to study the distributed two-stage assembly line scheduling problem with separate time settings, integrating problem-specific local search and adaptive restart strategies with the SSO framework in the MA. Additionally, Lei and Li ^[151] proposed a cooperative teaching-learning optimization (CTLBO) to solve this problem.

Assembly scheduling problems and distributed assembly scheduling problems have received some attention. However, existing work mainly focuses on two-stage assembly scheduling problems with processing and assembly as the research object. There is relatively little research on three-stage assembly scheduling problems that simultaneously consider processing, transportation and assembly, let alone distributed assembly scheduling problems. In practice, most complex assembly system scheduling models have three or more stages. Therefore, the multi-stage distributed assembly shop scheduling problem with three or more stages is one of the important research directions for future distributed assembly shop scheduling problems. In the actual assembly production process, there are often three stages: processing, transportation and assembly. For the three-stage assembly line scheduling problem with machine availability constraints, Shoaardebili et al. ^[152] considered both the objective of minimizing the total weighted completion time (flow time) and the objective of minimizing the weighted total sum of lateness and earliness.

In the distributed flexible job shop, the first stage is to process the workpieces by the distributed flexible job shops, and the second stage is to assemble the workpieces in the assembly shop to form the final product. Du et al. ^[153] proposed a mixed estimation of distribution algorithm (EDA) and variable neighborhood search (VNS) algorithm for the distributed flexible job shop scheduling problem with the objectives of minimizing the completion time and the total energy consumption. Wu et al. ^[154] proposed an improved differential evolution simulated annealing algorithm (IDESAA) for balance scheduling that aims to minimize both the earliness/tardiness and the total cost. Recently, Zhang et al. ^[155] replaced the single machine assembly in DAPFSP with flexible assembly layout, constructed a MILP model and then proposed a meme algorithm (MAGL) to solve the distributed flexible assembly line scheduling problem.

To sum up, there has been some progress in the research of distributed assembly shop scheduling problems. Existing research mainly focuses on distributed assembly line scheduling problems, but the research directions and models are relatively concentrated, and there is still great room for improvement in the algorithms. For the distributed two-stage assembly line scheduling problem with distributed parallel machine scheduling in the processing stage, there is relatively little research, especially for the case where the processing stage includes machine availability constraints. However, such problems are common in practical production, so it is necessary to study DASP with distributed parallel machine scheduling with machine availability constraints in the processing stage. Future research can increase the study of distributed assembly shop scheduling problems under different machine environments according to the actual needs of distributed assembly shop problems, integrate the characteristics of distributed assembly shop problems and optimize both local and global objectives, including logistics transportation time.

Currently, existing research on the assembly stage of distributed assembly shop scheduling problems only considers a single assembly machine, and there are few related research papers on distributed assembly shop scheduling problems with parallel assembly machines. However, there are a large number of parallel assembly machines in practical production systems, and studying DASP with parallel assembly machines can better meet actual production needs. In addition, compared with general DASP, the DASP model with parallel assembly machines is more complex and more difficult to solve. Therefore, research on DASP with parallel assembly machines has higher theoretical and practical research value. This inspires us to apply it to more complex scenarios, such as constrained buffering, batch processing, multi-objectives, heterogeneous factories, etc.

7.   Conclusions and prospects

7.1.   Conclusions

In this brief review article, we reviewed 116 papers on distributed shop scheduling problems published between 2007 and 2023, as depicted in Figure 13. Specifically, we analyzed the characteristics considered in the review articles, including workshop configuration, factory type, number and type of objective functions and solution methods.

Due to the ongoing digital transformation, Industry 4.0, and the increasing focus on optimizing costs and efficiency, there is a growing interest in distributed multi-factory production planning and scheduling. Therefore, our research findings may provide some useful assistance for further research. Table 4 provides a description of the objectives of the literature problems. The standard based on job completion time is the maximum completion time (makespan) and total flow time (TFT). The former minimizes the completion time of the last job in the schedule and maximizes the machine utilization efficiency. The latter minimizes the sum of completion times of all jobs, reducing work-in-progress and average production lead time in the schedule. Total energy consumption, such as carbon emissions/energy consumption indicators, also appear in the construction objectives. We found that 19 papers incorporated environmental indicators into the constraint set of their models.

In summary, the literature on modeling distributed scheduling problems predominantly focuses on minimizing the maximum completion time as the objective function, while other objectives, such as deadline correlation (earliness and tardiness), receive less consideration. Performance standards related to due dates are commonly used to measure lateness and tardiness. However, due to the complexities and uncertainties present in actual production workshops, including factors like production costs, energy consumption, order changes, random machine failures and machine maintenance, there is a need for further research on distributed shop scheduling with additional objectives such as energy consumption and stochastic effects like maintenance measures or uncertain demands.

In modeling distributed scheduling problems, heuristic methods are the most commonly used solution algorithms, followed by analysis and simulation. The in-depth consideration of objectives and solution methods indicates that the improvement of traditional scheduling algorithms and heuristic algorithms also performs well in distributed scheduling. In this review, genetic algorithms and iterative greedy algorithms, which are flexible, efficient and widely utilized for addressing large-scale instances of these NP-hard problems, are discussed as met-heuristic algorithms.

For different multi-factory problems, the trend from genetic algorithms to iterative greedy algorithms, knowledge-based systems and learning algorithms is significant. Many scholars have proposed further research directions, including comprehensive problem-solving that can utilize complex meta-heuristics to cope with globalization and digital transformation, which is crucial for industries to move towards multi-factory networks and cross-organizational collaboration. With the development of deep learning, scheduling problems based on deep learning are also an important research direction, but currently lack sufficient research.

It is important to acknowledge the limitations of this literature review. The final selection of papers was generated by searching academic databases using the mentioned keywords and employing descriptive exclusion criteria. Although efforts were made to conduct a comprehensive search, it is possible that some necessary keywords were missed, resulting in the exclusion of relevant publications. The selection process of the literature set may also be biased, although we have made every effort to minimize this potential bias.

7.2.   Prospects

Regarding the current research status mentioned above, future research work can be conducted in the following areas:

1) Exploring the complex multi-objective distributed shop scheduling: If actual production is considered, distributed shop scheduling problems related to production indicators, such as total lateness, total earliness and delivery time, in addition to the maximum completion time and total flow time, are also worth studying. Current distributed research often focuses on objectives, such as the maximum completion time, while delay-related objectives, such as the total delay time, are rarely discussed. The ability to deliver on time directly affects a company's profits and market reputation, Failure to meet customer needs or time principles in the supply chain can lead to customer loss, and the loss due to delayed delivery will be greater in a multi-factory environment. Therefore, future research should focus on strengthening optimization of delay-related objectives. Under the condition of multi-objective optimization, the current research rarely considers the problem of machine life loss, but this is an important factor affecting the efficiency of enterprises in the actual long-term production; the energy consumption or cost caused by raw material transportation, finished product transportation and workpiece transportation in the workshop due to distributed production in different places of the factory are also less considered; large workpiece manufacturing enterprises are generally highly polluting enterprises, and the cost of environmental protection is high in the current market environment, so it is also necessary to re-establish a suitable multi-objective optimization model considering transport and environmental protection. In addition, the green multi-objective scheduling problem of energy consumption needs to be considered, which is more in line with the current concept of carbon peak and carbon neutralization, it has practical value and is conducive to promoting the overall green transformation of enterprises.

Shop scheduling problems are NP-hard problems, and many current studies only consider one objective (i.e., optimal). In the future, multiple optimization objectives can be considered to obtain the final optimization result and improve the accuracy of the final scheduling result. Most shop scheduling problems in practice are multi-objective optimization problems, and their solutions exist as a set of Pareto optimal solutions, which have very important scientific research value and practical significance.

2) Considering actual constraints and uncertainties: The problem model for distributed shop scheduling should be continuously improved to align with the real needs of enterprises and production networks. In practical distributed production scheduling, there are many constraint conditions to be considered, such as delivery time, machine load, machine processing speed, cost, energy consumption, etc., which will all affect the final result. Moreover, uncertainties, such as resources and machine failures, are widely existent in actual production environments. Further research on distributed shop scheduling problems with machine failures or limited resources, and designing effective response strategies for different types of uncertainties, are necessary to ensure the normal and orderly operation of existing production activities, and to develop effective scheduling strategies for the good and orderly operation of distributed manufacturing activities.

In the future, distributed shop scheduling can consider introducing some uncertain factors in actual production to make the scheduling more reasonable. This mostly includes the following aspects: First, traditional shop scheduling only considers static information in the production process, while there are many dynamic factors in actual production, such as product demand, machine equipment failure, resource allocation, etc. Therefore, in the future, static and dynamic information can be combined to model actual production; second, in actual production, each part is a separate production unit, so each part has its own independent processing time. When each part is individually scheduled, redundant information is generated, which can be utilized in the future. By incorporating these uncertain factors into the scheduling field, it can more accurately describe the dynamic characteristics of shop production.

3) Exploring alternative optimization algorithms and solution methods: Distributed shop scheduling problems are mainly solved using heuristic algorithms and various intelligent algorithms, However, traditional heuristic algorithms are generally complex and slow to converge, so it is necessary to continuously improve existing heuristic methods to improve efficiency. Shop scheduling problems belong to discrete combinatorial optimization problems. When intelligent optimization algorithms are used to solve such problems, their mathematical analysis is subject to the constraint of non-continuity of the solution space. Therefore, how to understand the optimization mechanism of intelligent optimization algorithms and improve their solving performance for specific problems is the focus of future research. As different swarm intelligence algorithms have advantages in different aspects, exploring different algorithms applied to solve distributed shop scheduling has great academic significance, and future research can not only be limited to using swarm intelligence algorithms for solving problems, but also exploring other AI-based algorithms, such as machine learning. In recent years, many formulas have appeared in the literature on distributed shop scheduling, of which mixed integer programming (54.2%) accounts for 68.13% of the literature. Among them, 57.8% of the models have been solved by commercial solvers. Therefore, efficient development remains challenging.

From the perspective of solving methods, metaheuristic algorithms and exact solution algorithms are the most commonly used methods for solving distributed scheduling problems. From a critical perspective, the overall trend of these reviews is that researchers focus more on proposing new solving methods rather than improving existing ones. Therefore, future research can focus on metaheuristic algorithms and explore efficient hybrid metaheuristic algorithms. Metaheuristic algorithms have low problem dependency, but single metaheuristic algorithms are difficult to balance local and global searches. Combining optimization algorithms with different advantages can complement each other's shortcomings in the algorithm and improve the efficiency of the search. Combining clustering algorithms with heuristic algorithms or intelligent optimization algorithms to solve distributed shop scheduling problems can make the solution more tending towards the optimal solution, whether in solving large-scale instances or small-scale instances. However, the key lies in the mixing strategy between algorithms, and an appropriate mixing strategy can better balance the local and global searches of the algorithm. In the future, further studies can be conducted on the characteristics of metaheuristic algorithms and hybrid strategies.

4) Leveraging intelligent computing methods like deep learning: With the development of artificial intelligence technology, various algorithms represented by machine learning have achieved significant accomplishments in fields like image recognition, natural language processing and combinatorial optimization. Due to the reusability of reinforcement learning models after training, they possess characteristics of short response time and strong generalization when addressing shop scheduling problems. In traditional distributed shop scheduling, machines are mainly controlled by experience. In the field of distributed shop scheduling using deep reinforcement learning, the strategies and experience adopted in deep reinforcement learning need to be combined to obtain better results. Deep reinforcement learning can control the behavior of machines during scheduling, making the scheduling results more reasonable. However, the current application of deep reinforcement learning has its limitations, especially when dealing with large-scale shop scheduling problems. In the context of shop scheduling, the definition of system states is highly flexible, and inappropriate representation methods can make the algorithms challenging to train and utilize. Therefore, in the future, combining deep reinforcement learning with other methods, such as machine learning, holds great potential for overcoming these limitations and improving the solutions for shop scheduling problems.

5) Exploring distributed shop scheduling problems in heterogeneous environments: Currently, most of the research on distributed shop scheduling problems is conducted in homogenous shop environments. However, in actual production, the processing capacities, process flows, number of machines and factory environments of various processing plants in enterprises may differ. Therefore, studying distributed shop scheduling problems in heterogeneous environments has practical significance. Through continuous real-time data and new analysis tools, production can be better integrated with the logistics processes upstream and downstream. The convergence of industrial internet and blockchain can create a digital twin of the physical space and establish an online, decentralized social manufacturing network. Integrating production and distribution scheduling is also an important area for further research, especially when multiple distribution modes are available.

6) Increase other sustainable development indicators: Our country is facing strong pressure from the international community to reduce emissions, and the energy consumption gap continues to exist. Nowadays, experts and scholars are paying more and more attention to energy conservation, energy efficiency, sustainability and environmental issues when considering distributed shop scheduling problems, making existing problems more realistic. However, most of them only focus on environmental issues such as power consumption or carbon emissions. More and more companies are applying environmentally friendly technological solutions, not only by implementing environmentally oriented but also socially responsible and economically sound management solutions. Therefore, in the future, research can expand the sustainable scheduling progress by considering more sustainable indicators, helping many companies achieve sustainable improvement, especially in distributed scheduling problems. Based on this, we can obtain a broader framework and discover more potential issues for future distributed shop scheduling research.

7) Continuing in-depth research on distributed shop scheduling: Future research should delve deeper into distributed parallel machine shop scheduling, distributed flow shop scheduling, distributed job shop scheduling, distributed assembly shop scheduling and other related issues. Considering distributed non-identical factories, mixed flow shop, job shop and dynamic shop scheduling problems, or exploring distributed cooperative scheduling for different shop types are also important future research directions.

We believe that this review may contribute to new research efforts in distributed shop scheduling, which is a field that still requires further development.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Conflict of interest

The authors declare there is no conflict of interest.