
==== Front
Sci Rep
Sci Rep
Scientific Reports
2045-2322
Nature Publishing Group UK London

71963
10.1038/s41598-024-71963-6
Article
An improved intelligent optimization algorithm for small-batch order production scheduling
Zhang Xiaohuan
Wang Zhen wzhen_hz@163.com

Zhang Dan
Xu Tao
Jiang Hui
https://ror.org/03q3s7962 grid.411411.0 0000 0004 0644 5457 School of Computer Science and Engineering, Huizhou University, Huizhou, 516007 China
13 9 2024
13 9 2024
2024
14 2139427 3 2024
2 9 2024
© The Author(s) 2024
2024
https://creativecommons.org/licenses/by-nc-nd/4.0/ Open Access This article is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License, which permits any non-commercial use, sharing, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if you modified the licensed material. You do not have permission under this licence to share adapted material derived from this article or parts of it. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by-nc-nd/4.0/.
Although the critical path method (CPM) is effective for the integrated scheduling of small-batch orders, its overemphasis on vertical process relationships and neglect of horizontal parallel relationships have imposed limitations on scheduling, often leading to suboptimal outcomes in terms of the total product completion time. This study introduces an innovative algorithm designed to overcome these limitations and further optimize the total processing time of products. We propose a strategy of "exchanging adjacent processes on the same device", which operates based on the scheduling results of the CPM. By swapping adjacent and interchangeable processes within the constraints of the problem, this algorithm generates multiple new scheduling schemes, effectively expanding the solution space. This expansion enables the discovery of optimized solutions that leverage "horizontal parallel relationships", which is crucial for reducing the "total processing time of products". Finally, the effectiveness of the proposed algorithm is verified through experiments.

Keywords

Quasi-critical path
Integrated scheduling
Small-batch
Product scheduling schemes
Subject terms

Applied mathematics
Computer science
Mechanical engineering
The fund which aims to improve scientific research capability of key construction disciplines in Guangdong province “Light-weight federal learning paradigm and its application”No:2022ZDJSO58 Wang Zhen The Professorial and Doctoral Scientific Research Foundation of Huizhou UniversityNo. 2019JB014 No. 2018JB007 Wang Zhen Guangdong Overseas Famous Teacher Project: Research on artificial intelligence and new generation intelligent manufacturing technology2021 practice teaching base project of integration of science, industry and education in Guangdong Undergraduate Universities: Huizhou information technology science, industry and education integration practice teaching baseissue-copyright-statement© Springer Nature Limited 2024
==== Body
pmcIntroduction

Scheduling profoundly influences the productivity of enterprises. Efficient scheduling optimization algorithms have the potential to maximize production efficiency, thereby aiding businesses in achieving enhanced profitability. Currently, within the field of production scheduling, two primary research directions have emerged: single processing (assembly) scheduling and integrated scheduling. Single processing (assembly) scheduling includes job-shop and flow-shop scheduling. This methodology has been extensively applied in large-scale production scenarios. Specifically, when faced with the necessity to process a substantial volume of products, segmenting them into distinct workpieces for individual production can inadvertently generate considerable inventory. Subsequently, the accumulated inventory is assembled, facilitating the synchronized processing of subsequent workpieces and consequently reducing the overall production cycle. In this domain, numerous sophisticated algorithms have been devised, including genetic algorithms1, tabu search methodologies2, neural network approaches3, heuristic algorithms4, and a range of hybrid algorithms5–7. Simultaneously, these methodologies have been effectively applied across a variety of fields, offering viable solutions to unique challenges within each. For instance, in the field of workshop scheduling, Yan Jie et al.8 delved into the details of flexible scheduling for digital twin workshops under constrained transportation scenarios. Concurrently within this domain, Leng Jie et al.9 scrutinized the rapid reconfiguration challenges inherent to digital twin-driven automated manufacturing systems. Additionally, Zhou Wei et al.10 introduced an innovative heuristic integrated scheduling algorithm for dual workshops, based on process tree cyclic decomposition. Transitioning to the aerospace sector, Zhang Yong et al.11 outlined a foundational reactive scheduling approach tailored for aircraft maintenance tasks aboard carriers. Within the realm of energy and power systems, Qin Jie et al.12 meticulously examined the implications of a two-stage robust optimization scheduling framework for integrated energy systems, further considering the impact of joint trading involving carbon-green certificates. Concurrently, Su Zhong et al.13 embarked on an optimization endeavor focused on virtual power plants, encompassing considerations of tiered carbon trading and comprehensive demand response strategies. Finally, in the field of hydroelectric power generation, Huang Liang et al.14 conducted a comprehensive optimization study concerning pump-gate scheduling for the Taopu River system. Collectively, these scholarly contributions provide invaluable theoretical insights and practical experiences, thereby laying solid foundations for the advancement of their respective disciplines.

However, despite the extensive research in the field of scheduling, there remains a gap in the literature regarding scheduling strategies for small-batch and single-piece orders. Particularly today, as the demand for personalized and customized products grows, integrating production and assembly processes to shorten the production cycle has become an urgent issue to address. Small-batch orders rarely generate inventory during the production process, and in some cases, may result in no inventory at all. In this context, employing production models described by job-shop and flow-shop scheduling fails to reduce the production duration of products. On the contrary, it disrupts the intrinsic connection between production and assembly, extending the production cycle. To tackle this challenge, Xie et al.15 introduced an integrated scheduling methodology that accounts for both production processing activities and assembly operations, particularly suitable for small-batch or single-piece orders. Notably, the quasi-critical path approach has emerged as a prominent technique for addressing the integrated scheduling dilemma. This algorithm posits that the product process should be defined as a hierarchical tree structure, with the scheduling of nodes along the extended paths within this process tree having a significant impact on the final scheduling outcomes. Since its inception, many scholars have endeavored to refine this algorithm, introducing enhancements such as layer prioritization strategies, dynamic critical path methods, and others16–20. However, these refinements often introduce increased computational complexity. The summary of the literature is presented in Table 1, as shown below.Table 1 Summary of research background and literature review.

No	Author(s)	Year	Contribution/findings	Relevance to current research	
1	Hou Y S, et al	2022	Modeled and optimized integrated distributed flow shop scheduling with time windows, highlighting the complexity and potential solutions in distribution problems	Provides insights into integrated scheduling models and distribution	
2	Lei D, et al	2017	Novel teaching–learning-based optimization algorithm for energy efficiency in hybrid flow shops, emphasizing the importance of energy conservation in scheduling	Offers an energy-efficient perspective to scheduling problems	
3	Mastrolilli M, Svensson O	2011	Analyzed the computational complexity of flow and job shop scheduling problems, contributing to the understanding of the challenges in approximating solutions	Highlights the computational complexity in scheduling	
4	Chen R H, et al	2020	Self-learning genetic algorithm using reinforcement learning for solving flexible job-shop scheduling problems, demonstrating the potential of machine learning in optimization	Introduces machine learning in genetic algorithms for scheduling	
5	Mathlouthi I, et al	2021	Metaheuristic based on Tabu search for technician routing and scheduling problems, showcasing the effectiveness of Tabu search in complex routing scenarios	Presents a metaheuristic approach to routing and scheduling	
6	Naik A, et al	2020	Modified social group optimization for short-term hydrothermal scheduling, addressing the specific challenges in energy sector scheduling	Applies meta-heuristic algorithms to energy sector scheduling	
7	Bewoor L A, et al	2017	Evolutionary hybrid particle swarm optimization for no-wait flow shop problems, providing a novel approach to tackle NP-hard problems	Introduces a hybrid approach to no-wait flow shop scheduling	
8	Yan J, et al	2021	Flexible job shop scheduling under finite transportation conditions for digital twin workshops, integrating digital twin technology with scheduling	Explores the application of digital twin in workshop scheduling	
9	Leng J, et al	2020	Digital twin-driven rapid reconfiguration of automated manufacturing systems, emphasizing the role of digital twins in system flexibility	Discusses system reconfiguration using digital twin technology	
10	Zhou W, et al	2023	Symmetric two-workshop heuristic integrated scheduling algorithm based on process tree cyclic decomposition, contributing to dual-environment scheduling strategies	Presents an algorithm for dual workshop scheduling scenarios	
11	Zhang Y, et al	2023	Reactive scheduling method for aircraft maintenance tasks on carriers, tailored for the specific needs of aerospace maintenance	Provides a baseline for reactive maintenance scheduling	
12	Qin J, et al	2024	Two-stage robust optimization scheduling of integrated energy systems with consideration of carbon-green certificate trading, addressing energy trading impacts	Examines robust optimization in energy system scheduling	
13	Su Z, et al	2023	Optimal dispatch of virtual power plants considering stepped carbon trading and comprehensive demand response, integrating energy trading with power dispatch	Explores dispatch strategies in virtual power plants	
14	Huang L	2023	Optimization research of pump gate scheduling for the Taopu River system, focusing on water management and scheduling	Offers insights into water management scheduling	
15	Xie Z Q, et al	2003	Dynamic job-shop scheduling algorithm based on ACPM and BFSM, introducing dynamic approaches to traditional job-shop problems	Provides a foundation for dynamic scheduling methodologies	
16	Xie Z Q, et al	2008	Optimization control with dynamic generated collection of operation having priority, focusing on multi-product manufacturing processes	Introduces priority in multi-product manufacturing processes	
17	Xie Z Q, et al	2008	Dynamic job-shop scheduling with a dynamic set of operations having priority, advancing dynamic scheduling strategies	Enhances understanding of dynamic priority in job-shop scheduling	
18	Xie Z Q, et al	2018	Time-selective integrated scheduling algorithm considering the compactness of serial processes, optimizing scheduling for serial process compactness	Presents a time-selective approach to integrated scheduling	
19	Wang Z, et al	2021	Improved integrated scheduling algorithm with a process sequence time-selective strategy, refining existing time-selective methods	Offers improvements to time-selective scheduling strategies	
20	Zhang X, et al	2022	Scheduling algorithm for two-workshop production with time-selective and backtracking strategies, addressing complex product		

In this paper, we propose a novel integrated scheduling method capable of handling both production processing activities and assembly operations, especially suitable for small-batch or single-piece orders. Based on the quasi-critical path method, we introduce a new strategy that optimizes scheduling outcomes by exchanging adjacent parallel processes on the same equipment while reducing algorithmic complexity. The proposed algorithm has been empirically validated, demonstrating its effectiveness and superiority across various test sets. This study provides new theoretical insights and practical guidance for the field of production scheduling, particularly in addressing the scheduling issues of small-batch and single-piece production. The second section of this paper presents the algorithm description and analysis, outlining the constraints of the research problem and the mathematical programming model. The third section focuses on strategy design, detailing the overall algorithm framework design, the analysis and design of the strategy for exchanging adjacent processes on the same device, the analysis and design of the optimal product scheduling scheme selection strategy, and the specific implementation steps of the algorithm. Additionally, a detailed algorithm application example is provided. Furthermore, performance comparisons between the proposed algorithm and the prospective critical path algorithm are conducted using different test sets. The fourth section concludes the work of this paper and provides prospects for future research endeavors.

Problem description and analysis

The research problem of this paper focuses on the integrated scheduling issue in the workshop for single-piece and small-batch production. We take the "quasi-critical path" algorithm as the foundation and incorporate a strategy of swapping adjacent processes on the same equipment to construct a new algorithm, thereby optimizing the total processing time of the product. In the production process of such products, both the processing and assembly steps are considered simultaneously, which is more likely to reduce the total processing time of the product. The process flowchart of the product is presented in a tree-like structure. The tree-like structure depicted in Fig. 1 delineates the process flow diagram of the integrated scheduling production mode, illustrating the concurrent processing and assembly characteristics of the product. Each node within the diagram symbolizes an individual processing operation of the product. Nodes with an in-degree exceeding one denote assembly operations, whereas those with an in-degree of one signify processing operations. The integrated scheduling methodology adeptly manages both categories of operations, collectively termed as processes. Within the diagram, the initial segment of each node denotes the process identifier, the subsequent segment designates the processing equipment identifier, and the concluding segment specifies the processing duration. For example, A1/M1/15 signifies that process A1 will be processed on equipment M1 for a duration of 15 time units. The directed edges symbolize the partial order relationship of the processing sequence, with the root node of the process tree denoting the final assembly operation within the product. The investigation into integrated scheduling problems necessitates adherence to the following constraints.Fig. 1 Product processing process tree.

Furthermore, the integrated scheduling problem is constrained by the following conditions:Each process must strictly adhere to the defined partial order relationship within the processing tree.

A process can commence only when all preceding processes have been completed (or if there are no preceding processes).

At any given instance, each device is capable of handling only one process.

The execution of a process must be continuous without interruption.

Each device is characterized by distinct functionalities.

The presence of idle time for devices is permissible.

The difference between the termination time of the final processing step and the initiation time of the initial processing step equates to the overall processing duration of the product.

Typically, the scheduling objective of integrated scheduling problems is to optimize the total processing time of the product. The total processing time for a product is computed as the difference between the completion time of the latest concluding process and the initiation time of the earliest commencing process within the product. Integrated scheduling problems are conventionally characterized as follows:

Throughout the production process, each device within the workshop possesses the capability to concurrently handle multiple processes. Each device is presumed to be operational at time zero, accounting for potential idle intervals. The requisite duration for processing a product is determined by the device endowed with the lengthiest processing time.

The objective function T can be defined as:1 T=maxp∈P(end(p))-minp∈P(start(p))

Let end(p) denote the completion time of process p. We aim to maximize the maximum value among these completion times, as it will give the total processing time for the entire product. Here, maxp∈P(end(p)) represents the latest completion time among all processes. minp∈P(start(p)) denotes the earliest start time among all processes.

The constraint model is as follows:2 start(p)maxq∈pre(p)(end(q))

3 ∑p∈Pprocessing(p,d,t)1

4 end(p)-start(p)=duration(p)

Formula (2) indicates that for each process p∈P, its start time start(p) must be after the completion of all its preceding processes pre(p). Here, end(q) denotes the end time of the process.

Formula (3) indicates that for each device d∈D, only one process can be processed at any given time. Here, processing(p,d,t) represents the processing status of process p on device d at time t (1 indicates processing, otherwise 0).

Formula (4) indicates that the processing of a process cannot be interrupted. Here, duration(p) represents the duration of process p.

Strategy design

The objective of the algorithm design proposed in this paper is to optimize the total processing time of products without increasing the computational complexity of the algorithm. The methodology employed is as follows: Based on the scheduling outcomes derived from the quasi-critical path scheduling algorithm15, for each processing device, adjacent processes are systematically identified, followed by an evaluation of their interchangeability. Should interchangeability be feasible, these adjacent processes are then swapped, and any resultant implications on subsequent processes are managed by modifying the scheduling sequence. This iterative procedure yields novel scheduling schemes, which are subsequently incorporated into a collection of candidate scheduling solutions. Ultimately, the most optimal solution is selected from this ensemble of candidate schedules.

The algorithm framework is as follows:

Step 1: Assume the total number of devices is N, and the total number of processes on each machine is Nd[i], where i=1,2,...,N.

Step 2: Compute the path length for each leaf node within the product process tree. Herein, the path length is defined as the cumulative sum of the processing durations of all nodes traversed from the root node to the respective leaf node.

Step 3: Employ the quasi-critical path strategy15 to formulate a product scheduling scheme denoted as D, subsequently incorporating it into the collection of candidate scheduling schemes.

Step 4: For i = 1 to N.

Step 5: For j = 1 to Nd[i-1].

Step 6: Based on the product scheduling scheme D, use the adjacent process exchange strategy for the same device to select process j and process j+1 for interchange, and evaluate whether they can be interchanged. If they can be interchanged, perform the exchange; if not, proceed to step 9.

Step 7: Employ the adjacent process exchange adjustment strategy for identical devices to modify the processes influenced by the interchange executed in step 6, thereby producing a revised product scheduling scheme.

Step 8: Incorporate the newly formulated scheduling scheme into the collection of candidate scheduling schemes.

Step 9: j = j + 1, Jump to Step 5.

Step 10: i = i + 1, Jump to Step 4.

Step 11: Utilize the criteria-based approach for determining the optimal product scheduling scheme, selecting the most suitable scheduling scheme from the compilation of candidate scheduling schemes.

Step 12: End.

The pseudocode for this part is as follows:

Analysis and design of the strategy for exchanging adjacent processes on the same device

Suppose there is a process tree consisting of 20 processes denoted as A1, A2, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19, and A20. The processes have been scheduled on the processing devices as follows:

Device M1: A1, A2, A3, A4, A5, A6, and A7.

Device M2: A8, A9, A10, A11, and A12.

Device M3: A13, A14, A15, A16, A17, A18, A19, and A20.

As shown in Fig. 2, the processes on each device are arranged in a queue. The final scheduling order is A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19, and A20.Fig. 2 Schematic diagram of adjacent process interchange strategy.

Starting with the first process, A1, we examine its neighboring processes on the same device. In this case, process A7 belongs to device M1, while process A8 belongs to device M2, so they cannot be exchanged. Similarly, process A12 and process A13 cannot be exchanged because they belong to different devices.

For the subsequent adjacent processes, an assessment will be conducted to determine if a sequential relationship exists between each consecutive pair within their individual processing sequences. Should such a relationship be identified, signifying that one process necessitates completion prior to the commencement of the subsequent one, then the interchangeability of these processes will be precluded.

As shown in Fig. 3, processes P1 and P2 are processed on the same device, M3. Process P3 has already been processed on device M3 before these two processes. Additionally, process P1 has a predecessor process P1' processed on device M2, and process P2 has a predecessor process P2' processed on device M1 in the process tree.Fig. 3 Schematic diagram of three situations of interchange between process P1 and process P2.

When exchanging the two interchangeable processes, there are three cases:If the completion time of both process P1' and process P2' is earlier than the completion time of process P3, the start time of process P1 is set as the completion time of process P3, and the start time of process P2 is set as the completion time of process P1. This exchange only involves adjusting the start time of process P1 to match the start time of process P2 and adjusting the end time of process P2 to match the start time of process P1.

If the completion time of process P2' is later than the completion time of process P3, the start time of process P1 is set as the completion time of process P3, and the start time of process P2 is set as the completion time of process P1. This exchange involves adjusting the start time of process P2' to match the start time of process P2 and adjusting the end time of process P2 to match the start time of process P1.

If the completion time of process P1' is later than the completion time of process P3, the start time of process P1' is set as the completion time of process P1', and the start time of process P2 is set as the completion time of process P1. This exchange involves adjusting the start time of process P2' to match the start time of process P2 and adjusting the end time of process P2 to match the start time of process P1.

In summary, to facilitate the exchange between process P1 and process P2, the starting time of process P2 is determined first, followed by the determination of the starting time of process P1.

Based on the previously described algorithm, the following is a summarized procedure for applying the adjacent process interchange strategy based on the generated initial scheduling scheme:

Step 1: Initialize the process queue with the initial scheduling scheme.

Step 2: For each process P in the process queue:Identify the immediate successor process P' in the process queue.

If P' exists, proceed to Step 3. If P' does not exist, proceed to Step 10.

Step 3: Examine if processes P and P' utilize the same processing equipment.If they employ identical equipment, move to Step 4.

If they employ different equipment, transition to Step 9.

Step 4: Assess whether processes P and P' maintain a sequential processing relationship.If such a relationship is observed, transition to Step 9.

If no sequential relationship exists, advance to Step 5.

Step 5: Contrast the processing completion time of the immediate predecessor process of P on the equipment with that of the immediate predecessor process of P' within the process tree. Select the greater value and designate it as T.

Step 6: Establish the processing initiation time of process P' as T.

Step 7: Contrast the processing completion time of the immediate predecessor process of P' on the equipment with that of the immediate predecessor process of P' within the process tree. Choose the greater value and designate it as T'.

Step 8: Set the processing initiation time of process P as T'.

Step 9: Update P to P' and revert to Step 2.

Step 10: Conclude the algorithm.

The pseudocode for this part is as follows:

These steps delineate the approach for employing the adjacent process interchange strategy during the generation of the initial scheduling scheme. By adhering to this methodology, one can assess the interrelations among processes, equipment prerequisites, and processing durations, thereby refining the initial scheduling arrangement.

Analysis and design of optimal product scheduling scheme selection strategy

The provided algorithmic procedures are as follows:

Algorithm Steps:

Step 1: Verify whether the current collection of product scheduling schemes is devoid of content. If affirmative, advance to Step 4. If negative, transition to Step 2.

Step 2: Extract the scheme denoted as D from the collection of schemes characterized by the minimum aggregate processing duration.

Step 3: Transmit scheme D.

Step 4: Conclude the algorithm.

Algorithmic implementation steps as detailed in the manuscript

The steps delineated in the manuscript are:

Step 1: Postulate the existence of m processing apparatus within the manufacturing workshop.

Step 2: Employ the pseudo-critical path algorithm15 to systematically allocate each procedure within the process tree, culminating in an inaugural scheduling blueprint denoted as d.

Step 3: Initialize i to 1.

Step 4: Ascertain the veracity of i ≤ m. If confirmed, transition to Step 5. If refuted, move to Step 7.

Step 5: Queue every procedure located on the i-th apparatus in the foundational scheduling blueprint d, aligning them based on their designated processing sequence into the queue q.

Step 6: Increment i and revert to Step 4.

Step 7: Ascertain the non-emptiness of queue q. If substantiated, advance to Step 8. If negated, navigate to Step 12.

Step 8: Extract a procedure from the queue q, designating it as process w.

Step 9: Initiate the strategy for adjacent process interchange, discerning the feasibility of process w's exchange with its proximate succeeding procedure in the queue. Should interchangeability be established, transition to Step 10. Else, revert to Step 7.

Step 10: Implement the adjustment strategy subsequent to the process interchange as executed in Step 9 and proceed to Step 11.

Step 11: Incorporate the freshly derived product scheduling blueprint into d and revert to Step 7.

Step 12: Compute the cumulative processing duration for every product scheduling scheme embedded within d.

Step 13: Utilize a strategy dedicated to optimal scheduling scheme selection to pinpoint the ultimate scheduling arrangement for the product.

Step 14: Conclude the algorithmic process.

Complexity analysis of the proposed algorithm

The pseudocode for this part is as follows:

Let n denote the number of cross-points in the product processing tree with an in-degree greater than 1, p represent the total number of devices, and q indicate the total number of processes. According to literature15, the complexity of the pseudo-critical path algorithm is O{max[(q(q-p)/(2p)),(qq)/(16p)]}.

In this manuscript, an adjacent process interchange strategy algorithm is proposed. On average, this algorithm involves q/2 processes, and the complexity of the process interchange operation is O(1). Therefore, the time complexity of this strategy algorithm is O(q/2).

A neighboring process interchange adjustment strategy algorithm is also designed in this paper. This algorithm involves at most q-1 processes, and the complexity of adjusting the processing time of the processes is O(1). Hence, the time complexity of this strategy algorithm is O(q-1).

Based on the above analysis, the complexity of the proposed algorithm is determined by taking the maximum value among the series of sequential operations mentioned above. Thus, the complexity is O{max[(q(q-p)/(2p)),(qq)/(16p)]}. It can be seen that the complexity of the proposed algorithm is no higher than that of the pseudo-critical path algorithm.

The example analysis

To facilitate the readers' comprehension of the algorithm, the product process tree depicted in Fig. 1 of this article is utilized as an illustrative example to elucidate the scheduling process of the proposed algorithm.

Adhering to the algorithm delineated in literature15, an initial scheduling scheme for Product A was formulated, resulting in a cumulative processing time of 265, as depicted in Fig. 4. Subsequently, leveraging this initial scheduling scheme, the algorithm posited in this article was implemented, culminating in a diminished total processing time of 255 for Product A. The ultimate Gantt chart illustrating the scheduling of Product A is delineated in Fig. 5.Fig. 4 Results of quasi-critical path strategy scheduling.

Fig. 5 Final product scheduling scheme.

The specific scheduling process can be referred to in Table 2.Table 2 The process of scheduling product A with the proposed algorithm.

ID	Replaced process	Adjusted scheme: process (start time)	Total processing time	
1	A1, A22	M1: A22 (0), A1 (15), A19 (30), A7 (70), A23 (140), A20 (180), A28 (240)

M2: A10 (0), A6 (30), A3 (50), A9 (70), A15 (95), A27 (225)

M3: A5 (0), A16 (25), A8 (50), A24 (80), A18 (115), A21 (140), A14 (155)

M4: A2 (0), A4 (30), A12 (50), A11 (65), A13 (85), A17 (115), A26 (170), A25 (205)

	260	
2	A22, A19	M1: A1 (0), A19 (15), A22 (30), A7 (70), A23 (140), A20 (180), A28 (240)

M2: A10 (0), A6 (30), A3 (50), A9 (70), A15 (95), A27 (225)

M3: A5 (0), A16 (25), A8 (50), A24 (80), A18 (115), A21 (140), A14 (155)

M4: A2 (0), A4 (30), A12 (50), A11 (65), A13 (85), A17 (115), A26 (170), A25 (205)

	260	
3	A19, A7	M1: A1 (0), A22 (15), A7 (70), A19 (85), A23 (140), A20 (180), A28 (240)

M2: A10 (0), A6 (30), A3 (50), A9 (70), A15 (95), A27 (225)

M3: A5 (0), A16 (25), A8 (50), A24 (80), A18 (115), A21 (140), A14 (155)

M4: A2 (0), A4 (30), A12 (50), A11 (65), A13 (85), A17 (115), A26 (170), A25 (205)

	260	
4	A7, A23	M1: A1 (0), A22 (15), A19 (30), A23 (140), A7 (170), A20 (185), A28 (245)

M2: A10 (0), A6 (30), A3 (50), A9 (70), A15 (95), A27 (230)

M3: A5 (0), A16 (25), A8 (50), A24 (80), A18 (115), A21 (140), A14 (155)

M4: A2 (0), A4 (30), A12 (50), A11 (65), A13 (85), A17 (115), A26 (170), A25 (210)

	265	
5	A23, A20	M1: A1 (0), A22 (15), A19 (30), A7 (70), A20 (180), A23 (205), A28 (245)

M2: A10 (0), A6 (30), A3 (50), A9 (70), A15 (95), A27 (255)

M3: A5 (0), A16 (25), A8 (50), A24 (80), A18 (115), A21 (140), A14 (155)

M4: A2 (0), A4 (30), A12 (50), A11 (65), A13 (85), A17 (115), A25 (235), A26 (235)

	275	
6	A20, A28	M1: A1 (0), A22 (15), A19 (30), A7 (70), A23 (140), A20 (180), A28 (240)

M2: A10 (0), A6 (30), A3 (50), A9 (70), A15 (95), A27 (225)

M3: A5 (0), A16 (25), A8 (50), A24 (80), A18 (115), A21 (140), A14 (155)

M4: A2 (0), A4 (30), A12 (50), A11 (65), A13 (85), A17 (115), A25 (205), A26 (170)

	265	
7	A10, A6	M1: A1 (0), A22 (15), A19 (30), A7 (95), A23 (175), A20 (215), A28 (275)

M2: A6 (30), A10 (50), A3 (75), A9 (95), A15 (120), A27 (260)

M3: A5 (0), A16 (75), A8 (95), A24 (125), A18 (155), A21 (175), A14 (190)

M4: A2 (0), A4 (30), A12 (50), A11 (65), A13 (125), A17 (155), A26 (205), A25 (240)

	295	
8	A6, A3	M1: A1 (0), A22 (15), A19 (30), A7 (50), A23 (150), A20 (190), A28 (250)

M2: A10 (0), A3 (25), A6 (45), A9 (65), A15 (90), A27 (235)

M3: A5 (0), A16 (25), A8 (65), A24 (95), A18 (125), A21 (150), A14 (165)

M4: A2 (0), A4 (30), A12 (50), A11 (65), A13 (95), A17 (125), A25 (215), A26 (180)

	270	
9	A3, A9	M1: A1 (0), A22 (15), A19 (30), A7 (95), A23 (160), A20 (205), A28 (260)

M2: A10 (0), A6 (30), A9 (50), A3 (75), A15 (95), A27 (245)

M3: A5 (0), A16 (25), A8 (50), A24 (80), A18 (140), A21 (165), A14 (180)

M4: A2 (0), A4 (30), A12 (50), A11 (65), A13 (110), A17 (140), A26 (190), A25 (230)

	280	
10	A9, A15	M1: A1 (0), A22 (15), A19 (30), A7 (70), A20 (180), A23 (140), A28 (240)

M2: A10 (0), A6 (30), A3 (50), A15 (70), A9 (90), A27 (225)

M3: A5 (0), A16 (25), A8 (50), A24 (80), A18 (115), A21 (140), A14 (155)

M4: A2 (0), A4 (30), A12 (50), A11 (65), A13 (85), A17 (115), A25 (205), A26 (170)

	260	
11	A15, A27	M1: A1 (0), A22 (15), A19 (30), A7 (70), A20 (180), A23 (140), A28 (240)

M2: A10 (0), A6 (30), A3 (50), A9 (70), A15 (95), A27 (225)

M3: A5 (0), A16 (25), A8 (50), A24 (80), A18 (115), A21 (140), A14 (155)

M4: A2 (0), A4 (30), A12 (50), A11 (65), A13 (85), A17 (115), A25 (205), A26 (170)

	260	
12	A5, A16	M1: A1 (0), A22 (15), A19 (30), A7 (70), A20 (190), A23 (150), A28 (250)

M2: A10 (0), A6 (30), A3 (50), A9 (70), A15 (95), A27 (235)

M3: A16 (25), A5 (45), A8 (65), A24 (95), A18 (125), A21 (150), A14 (165)

M4: A2 (0), A4 (30), A12 (50), A11 (65), A13 (95), A17 (125), A25 (215), A26 (180)

	270	
13	A16, A8	M1: A1 (0), A22 (15), A19 (30), A7 (70), A20 (185), A23 (145), A28 (245)

M2: A10 (0), A6 (30), A3 (50), A9 (70), A15 (95), A27 (230)

M3: A5 (0), A8 (50), A16 (80), A24 (100), A18 (120), A21 (145), A14 (160)

M4: A2 (0), A4 (30), A12 (50), A11 (65), A13 (85), A17 (115), A25 (210), A26 (175)

	265	
14	A8, A24	M1: A1 (0), A22 (15), A19 (30), A7 (70), A20 (190), A23 (150), A28 (240)

M2: A10 (0), A6 (30), A3 (50), A9 (70), A15 (95), A27 (235)

M3: A5 (0), A16 (25), A24 (45), A8 (65), A18 (125), A21 (150), A14 (165)

M4: A2 (0), A4 (30), A12 (50), A11 (65), A13 (95), A17 (125), A26 (180), A25 (215)

	260	
15	A24, A18	M1: A1 (0), A22 (15), A19 (30), A7 (70), A23 (140), A20 (200), A28 (255)

M2: A10 (0), A6 (30), A3 (50), A9 (70), A15 (95), A27 (240)

M3: A5 (0), A16 (25), A8 (50), A18 (115), A24 (140), A21 (160), A14 (175)

M4: A2 (0), A4 (30), A12 (50), A11 (65), A13 (85), A17 (115), A26 (175), A25 (225)

	265	
16	A18, A21	M1: A1 (0), A22 (15), A19 (30), A7 (70), A23 (175), A20 (205), A28 (265)

M2: A10 (0), A6 (30), A3 (50), A9 (70), A15 (95), A27 (250)

M3: A5 (0), A16 (25), A8 (50), A24 (80), A21 (135), A18 (150), A14 (175)

M4: A2 (0), A4 (30), A12 (50), A11 (65), A13 (85), A17 (115), A26 (200), A25 (230)

	285	
17	A21, A14	M1: A1 (0), A22 (15), A19 (30), A7 (70), A23 (140), A20 (170), A28 (235)

M2: A10 (0), A6 (30), A3 (50), A9 (70), A15 (95), A27 (220)

M3: A5 (0), A16 (25), A8 (50), A24 (80), A18 (115), A14 (140), A21 (165)

M4: A2 (0), A4 (30), A12 (50), A11 (65), A13 (85), A17 (115), A26 (180), A25 (200)

	255	
18	A2, A4	M1: A1 (0), A22 (15), A19 (30), A7 (90), A23 (160), A20 (200), A28 (260)

M2: A10 (0), A6 (50), A3 (70), A9 (90), A15 (115), A27 (245)

M3: A5 (0), A16 (25), A8 (70), A24 (90), A18 (135), A21 (160), A14 (175)

M4: A4 (0), A2 (20), A12 (50), A11 (65), A13 (105), A17 (135), A26 (190), A25 (225)

	280	
19	A4, A12	M1: A1 (0), A22 (15), A19 (30), A7 (70), A23 (140), A20 (180), A28 (240)

M2: A10 (0), A6 (30), A3 (50), A9 (70), A15 (95), A27 (225)

M3: A5 (0), A16 (25), A8 (50), A24 (80), A18 (115), A21 (140), A14 (155)

M4: A2 (0), A12 (30), A4 (45), A11 (65), A13 (85), A17 (115), A26 (170), A25 (205)

	260	
20	A12, A11	M1: A1 (0), A22 (15), A19 (30), A7 (70), A23 (140), A20 (180), A28 (240)

M2: A10 (0), A6 (30), A3 (50), A9 (70), A15 (95), A27 (225)

M3: A5 (0), A16 (25), A8 (50), A24 (80), A18 (115), A21 (140), A14 (155)

M4: A2 (0), A4 (30), A11 (50), A12 (70), A13 (85), A17 (115), A26 (170), A25 (205)

	260	
21	A11, A13	M1: A1 (0), A22 (15), A19 (30), A7 (70), A23 (140), A20 (180), A28 (240)

M2: A10 (0), A6 (30), A3 (50), A9 (70), A15 (95), A27 (225)

M3: A5 (0), A16 (25), A8 (50), A24 (80), A18 (115), A21 (140), A14 (155)

M4: A2 (0), A4 (30), A12 (50), A13 (85), A11 (115), A17 (135), A26 (170), A25 (205)

	260	
22	A13, A17	M1: A1 (0), A22 (15), A19 (30), A7 (70), A23 (140), A20 (180), A28 (260)

M2: A10 (0), A6 (30), A3 (50), A9 (70), A15 (95), A27 (245)

M3: A5 (0), A16 (25), A8 (50), A24 (80), A18 (135), A21 (160), A14 (175)

M4: A2 (0), A4 (30), A12 (50), A11 (65), A17 (85), A13 (105), A26 (170), A25 (225)

	280	
23	A17, A26	M1: A1 (0), A22 (15), A19 (30), A7 (70), A23 (140), A20 (180), A28 (260)

M2: A10 (0), A6 (30), A3 (50), A9 (70), A15 (95), A27 (245)

M3: A5 (0), A16 (25), A8 (50), A24 (80), A18 (135), A21 (160), A14 (175)

M4: A2 (0), A4 (30), A12 (50), A11 (65), A13 (85), A17 (115), A26 (170), A25 (205)

	260	
24	A26, A25	M1: A1 (0), A22 (15), A19 (30), A7 (70), A23 (140), A20 (180), A28 (245)

M2: A10 (0), A6 (30), A3 (50), A9 (70), A15 (95), A27 (245)

M3: A5 (0), A16 (25), A8 (50), A24 (80), A18 (135), A21 (160), A14 (175)

M4: A2 (0), A4 (30), A12 (50), A11 (65), A13 (85), A17 (115), A25 (205), A26 (225)

	265	

Based on the provided example analysis, it is evident that the scheduling results obtained from the pseudo-critical path algorithm are encompassed within the scheduling results generated by the algorithm proposed in this paper. The algorithm proposed in this paper selects the optimal scheme from a set of schemes, which includes the scheduling results derived from the pseudo-critical path algorithm. Consequently, the scheduling outcome produced by this algorithm is guaranteed to be at least as good as that of the pseudo-critical path algorithm.

Experimental comparison and analysis

The experimental platform utilized in this study operates on a 64-bit Windows 10 system and executes the Python 3.9 interpreter. The hardware specifications of the experimental setup comprise an Intel Core i7-860 processor coupled with 32 GB of RAM. The implementation of the algorithm is realized using the Python programming language.

To validate the efficacy of the proposed algorithm, four distinct datasets, each comprising 100 products, were randomly generated. The product parameters, encompassing attributes such as the quantity of processes, individual processing durations, and the requisite equipment count, were randomly generated across varied scale intervals.

The subsequent sections delineate the four experimental configurations detailed in this paper:

In Experiment 1, the randomly generated process count fluctuates within the interval10,20, with each process having a preceding process count between1,5. The equipment count for processing ranges between3,4, and the individual process durations are situated within the range10,20. The outcomes of this experiment are depicted in Fig. 6.Fig. 6 Comparison chart of experiment 1 results.

In Experiment 2, the process count varies within the range [20, 30], with analogous constraints on the preceding process count and equipment count as in Experiment 1. However, the individual process durations are now confined to the interval [30, 40]. The corresponding results are illustrated in Fig. 7.Fig. 7 Comparison chart of experiment 2 results.

Experiment 3 encompasses a process count that spans the range [30, 40], with consistent constraints on the preceding process count and equipment count. The individual process durations for this configuration are situated within the range [40, 50]. The experimental findings are displayed in Fig. 8.Fig. 8 Comparison chart of experiment 3 results.

Lastly, in Experiment 4, the process count extends from [40, 50], while retaining similar constraints on the preceding process count and equipment count as in the prior experiments. The individual process durations for this scenario are constrained to the range [50, 60]. The experimental outcomes for this configuration are presented in Fig. 9.Fig. 9 Comparison chart of experiment 4 results.

The comparison of the mean values for the four sets of experimental results is shown in Table 3.Table 3 Comparative experimental results.

	Experiment 1	Experiment 2	Experiment 3	Experiment 4	
Mean of the current article's algorithm	198.53	609.74	1004.64	1480.64	
Mean of the literature15 algorithm	213.84	741.5	1278.56	1823.4	

Within the four distinct experimental datasets, the red bars delineate the scheduling outcomes derived from the algorithm presented in this study, whereas bars of alternative hues signify results obtained through the quasi-critical path approach. Upon examination of the graphical representations, a consistent observation emerges: the stature of the red bars consistently resides below that of the bars of alternative colors across all experiments. This disparity implies that the scheduling solutions procured by the proposed algorithm yield diminished values in comparison to those derived from the quasi-critical path methodology. Consequently, it is deduced that the algorithm posited in this study excels in enhancing scheduling outcomes relative to the quasi-critical path technique, thereby affirming the robustness and efficacy of the proposed approach.

Conclusion

To overcome the limitations of the quasi-critical path algorithm in scheduling small-batch production, we have introduced a new method that involves the exchange of adjacent parallel processes on the same device. Our proposed method not only surpasses the critical path algorithm15 in terms of scheduling outcomes without increasing time complexity but also lays a theoretical foundation for future algorithmic research.

However, there are still deficiencies: although the algorithm is based on the "quasi-critical path" strategy that expands the solution space, it only adjusts adjacent processes on the same device and does not consider the mutual influence between non-adjacent processes. Therefore, it has not completely overcome the "vertical precedence" constraints of the tree-like structure.

In the future, our plans include:

Further considering the mutual influence between non-adjacent processes and extending the application of the improved algorithm to more integrated scheduling fields. This method can be applied to address various integrated scheduling challenges, such as multi-device processes, batch scheduling, and distributed scheduling.

By exploring these applications, we aim to further enhance the effectiveness and versatility of the proposed approach.

Proposing to break away from the "quasi-critical path" strategy and to explore newer and more optimal strategies to solve integrated scheduling problems.

Through these efforts, we expect to improve the efficiency and applicability of the scheduling method, providing more robust solutions for complex production scheduling scenarios.

Acknowledgements

Thank the editors and reviewers of the journal for their strong support to this manuscript.

Author contributions

Xiaohuan Zhang: Writing the main manuscript text, Methodology; Zhen Wang: Formal analysis, Writing—Review & Editing, Funding acquisition; Dan Zhang: Investigation, Data Curation; Tao Xu:Investigation, Data Curation; Hui Jiang: Data Curation, Formal analysis. All authors contributed to the article and approved the submitted version.

Funding

This research was funded by the fund which aims to improve scientific research capability of key construction disciplines in Guangdong province “Light-weight federal learning paradigm and its application”(No:2022ZDJSO58), The Professorial and Doctoral Scientific Research Foundation of Huizhou University(No. 2019JB014, No. 2018JB007), Guangdong Overseas Famous Teacher Project: Research on artificial intelligence and new generation intelligent manufacturing technology, 2021 practice teaching base project of integration of science, industry and education in Guangdong Undergraduate Universities: Huizhou information technology science, industry and education integration practice teaching base the 2024 Guangdong Province's key field special project for natural science projects in ordinary colleges and universities, titled "Research on Intelligent Quality Control and Supply Chain Optimization Strategy of Litchi Based on Deep Learning",the 2024 Guangdong Province's characteristic innovation project in ordinary colleges and universities, titled "Research on Accurate Segmentation Model of Multimodal Lung Cancer Lesion Area in PETCT Based on Feature Adaptive U-Net",Guangdong Provincial University-Enterprise Joint Laboratory "OpenHarmony Innovation Laboratory".

Data availability

All data generated or analysed during this study are included in this published article.

Competing interests

The authors declare no competing interests.

Publisher's note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
==== Refs
References

1. Hou YS Fu YP Gao KZ Zhang H Modelling and optimization of integrated distributed flow shop scheduling and distribution problems with time windows Expert Syst. Appl. 2022 187 115827 10.1016/j.eswa.2021.115827
Hou, Y. S., Fu, Y. P., Gao, K. Z. & Zhang, H. Modelling and optimization of integrated distributed flow shop scheduling and distribution problems with time windows. Expert Syst. Appl. 187, 115827 (2022).10.1016/j.eswa.2021.115827
2. Lei D Gao L Zheng Y A novel teaching-learning-based optimization algorithm for energy-efficient scheduling in hybrid flow shop IEEE Trans. Eng. Manage. 2017 65 2 330 340 10.1109/TEM.2017.2774281
Lei, D., Gao, L. & Zheng, Y. A novel teaching-learning-based optimization algorithm for energy-efficient scheduling in hybrid flow shop. IEEE Trans. Eng. Manage. 65(2), 330–340 (2017).10.1109/TEM.2017.2774281
3. Mastrolilli M Svensson O Hardness of approximating flow and job shop scheduling problems J. ACM (JACM) 2011 58 5 1 32 10.1145/2027216.2027218
Mastrolilli, M. & Svensson, O. Hardness of approximating flow and job shop scheduling problems. J. ACM (JACM) 58(5), 1–32 (2011).10.1145/2027216.2027218
4. Chen RH Yang B Li S Wang SL A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem Comput. Ind. Eng. 2020 149 106778 10.1016/j.cie.2020.106778
Chen, R. H., Yang, B., Li, S. & Wang, S. L. A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem. Comput. Ind. Eng. 149, 106778 (2020).10.1016/j.cie.2020.106778
5. Mathlouthi I Gendreau M Potvin JY A metaheuristic based on Tabu search for solving a technician routing and scheduling problem Comput. Oper. Res. 2021 125 105079 10.1016/j.cor.2020.105079
Mathlouthi, I., Gendreau, M. & Potvin, J. Y. A metaheuristic based on Tabu search for solving a technician routing and scheduling problem. Comput. Oper. Res. 125, 105079 (2021).10.1016/j.cor.2020.105079
6. Naik A Satapathy SC Abraham A Modified social group optimization—A meta-heuristic algorithm to solve short-term hydrothermal scheduling Appl. Soft Comput. 2020 95 106524 10.1016/j.asoc.2020.106524
Naik, A., Satapathy, S. C. & Abraham, A. Modified social group optimization—A meta-heuristic algorithm to solve short-term hydrothermal scheduling. Appl. Soft Comput. 95, 106524 (2020).10.1016/j.asoc.2020.106524
7. Bewoor LA Chandra Prakash V Sapkal SU Evolutionary hybrid particle swarm optimization algorithm for solving np-hard no-wait flow shop scheduling problems Algorithms 2017 10 4 121 10.3390/a10040121
Bewoor, L. A., Chandra Prakash, V. & Sapkal, S. U. Evolutionary hybrid particle swarm optimization algorithm for solving np-hard no-wait flow shop scheduling problems. Algorithms 10(4), 121 (2017).10.3390/a10040121
8. Yan, J., Liu, Z., Zhang, C., Zhang, T., Zhang, Y. & Yang, C. Research on flexible job shop scheduling under finite transportation conditions for digital twin workshop. Robot. Comput.-Integr. Manuf. 72, 122 (2021).
9. Leng, J., Liu, Q., Ye, S., Jing, J., Wang, Y., Zhang, C., Zhang, D. & Chen, X. Digital twin-driven rapid reconfiguration of the automated manufacturing system via an open architecture model. Robot. Comput.-Integr. Manuf. 63 (2020)..
10. Zhou, W., Zhou, P., Yang, D., Cao, W., Tan, Z. & Xie, Z. Symmetric two-workshop heuristic integrated scheduling algorithm based on process tree cyclic decomposition. Electronics 12(7) (2023).
11. Zhang Y Li C Su X Cui R Wan B A baseline-reactive scheduling method for carrier-based aircraft maintenance tasks Complex Intell. Syst. 2023 9 367 397 10.1007/s40747-022-00784-9
Zhang, Y., Li, C., Su, X., Cui, R. & Wan, B. A baseline-reactive scheduling method for carrier-based aircraft maintenance tasks. Complex Intell. Syst. 9, 367–397 (2023).10.1007/s40747-022-00784-9
12. Qin, J., Pan, X., Sun, X., Guo, J. & Shi, W. Two-stage robust optimization scheduling of integrated energy system and influence of repeated benefit under carbon-green certificate joint trading. Electr. Power Autom. Equip. 1–14 (2024)..
13. Su Z Wang L Liang X Chen T Zeng S Yu Z Optimal dispatch of virtual power plant considering stepped carbon trading and comprehensive demand response Electr. Power 2023 56 12 174 182
Su, Z. et al. Optimal dispatch of virtual power plant considering stepped carbon trading and comprehensive demand response. Electr. Power 56(12), 174–182 (2023).
14. Huang L Optimization research of pump gate scheduling for comprehensive management of Taopu river system China Municipal Eng. 2023 06 36 3998
Huang, L. Optimization research of pump gate scheduling for comprehensive management of Taopu river system. China Municipal Eng. 06, 36–3998 (2023).
15. Xie ZQ Liu SH Qiao P Dynamic job-shop scheduling algorithm based on ACPM and BFSM J. Comput. Res. Dev. 2003 40 7 977 983
Xie, Z. Q., Liu, S. H. & Qiao, P. Dynamic job-shop scheduling algorithm based on ACPM and BFSM. J. Comput. Res. Dev. 40(7), 977–983 (2003).
16. Xie ZQ Zhou Y Yang G Tan GY Multi-product manufacturing process optimization control with dynamic generated collection of operation having priority Electr. Mach. Control 2008 12 6 734 738
Xie, Z. Q., Zhou, Y., Yang, G. & Tan, G. Y. Multi-product manufacturing process optimization control with dynamic generated collection of operation having priority. Electr. Mach. Control 12(6), 734–738 (2008).
17. Xie ZQ Yang J Yang G Tan GY Dynamic job-shop scheduling algorithm with dynamic set of operation having priority Chinese J. Comput.-Chinese Ed. 2008 31 3 502 508 10.3724/SP.J.1016.2008.00502
Xie, Z. Q., Yang, J., Yang, G. & Tan, G. Y. Dynamic job-shop scheduling algorithm with dynamic set of operation having priority. Chinese J. Comput.-Chinese Ed. 31(3), 502–508 (2008).10.3724/SP.J.1016.2008.00502
18. Xie ZQ Zhang XH Gao YL Xin Y Time-selective integrated scheduling algorithm considering the compactness of serial processes J. Mech. Eng. 2018 54 6 191 202 10.3901/JME.2018.06.191
Xie, Z. Q., Zhang, X. H., Gao, Y. L. & Xin, Y. Time-selective integrated scheduling algorithm considering the compactness of serial processes. J. Mech. Eng. 54(6), 191–202 (2018).10.3901/JME.2018.06.191
19. Wang, Z., Zhang, X. & Peng, G. An improved integrated scheduling algorithm with process sequence time-selective strategy. Complexity (2021).
20. Zhang, X., Wang, Z., Zhang, D. & Xu, T. Scheduling algorithm for two-workshop production with the time-selective strategy and backtracking strategy. Electronic 11(23) (2022).
