Introduction

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,6,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,17,18,19,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.
Full size table

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, \(A{1/}M{1/15}\) signifies that process \(A{1}\) will be processed on equipment \(M{1}\) 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
figure 1

Product processing process tree.

Full size image

Furthermore, the integrated scheduling problem is constrained by the following conditions:

  1. (1)

    Each process must strictly adhere to the defined partial order relationship within the processing tree.

  2. (2)

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

  3. (3)

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

  4. (4)

    The execution of a process must be continuous without interruption.

  5. (5)

    Each device is characterized by distinct functionalities.

  6. (6)

    The presence of idle time for devices is permissible.

  7. (7)

    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:

$$ T{ = }max_{p \in P} {(}end{(}p{)) - }min{}_{p \in P}{(}start{(}p{))} $$
(1)

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, \( max_{p \in P} {(}end{(}p{))}\) represents the latest completion time among all processes. \( min{}_{p \in P}{(}start{(}p{))}\) denotes the earliest start time among all processes.

The constraint model is as follows:

$$ start{(}p{)}max_{{q \in pre{(}p{)}}} {(}end{(}q{))} $$
(2)
$$ \sum {_{p \in P} } \, processing{(}p{,}d{,}t{)}{\text{1}} $$
(3)
$$ end{(}p{) - }start{(}p{) = }duration{(}p{)} $$
(4)

Formula (2) indicates that for each process \(p \in 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 \, \in \, 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:

figure a

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
figure 2

Schematic diagram of adjacent process interchange strategy.

Full size image

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
figure 3

Schematic diagram of three situations of interchange between process P1 and process P2.

Full size image

When exchanging the two interchangeable processes, there are three cases:

  1. (1)

    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.

  2. (2)

    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.

  3. (3)

    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:

  1. a.

    Identify the immediate successor process P' in the process queue.

  2. b.

    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.

  1. a.

    If they employ identical equipment, move to Step 4.

  2. b.

    If they employ different equipment, transition to Step 9.

Step 4: Assess whether processes P and P' maintain a sequential processing relationship.

  1. a.

    If such a relationship is observed, transition to Step 9.

  2. b.

    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:

figure b

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:

figure c

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{)/(2}p{)),(}qq{)/(16}p)]\} \).

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{)/(2}p{)),(}qq{)/(16}p)]\} \). 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
figure 4

Results of quasi-critical path strategy scheduling.

Full size image
Fig. 5
figure 5

Final product scheduling scheme.

Full size image

The specific scheduling process can be referred to in Table 2.

Table 2 The process of scheduling product A with the proposed algorithm.
Full size table

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
figure 6

Comparison chart of experiment 1 results.

Full size image

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
figure 7

Comparison chart of experiment 2 results.

Full size image

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
figure 8

Comparison chart of experiment 3 results.

Full size image

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
figure 9

Comparison chart of experiment 4 results.

Full size image

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

Table 3 Comparative experimental results.
Full size table

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.