Scheduling additive manufacturing systems: Complexity and algorithms to minimize the number of late parts

Abstract

Additive manufacturing (AM) is a process by which three-dimensional products are made via the addition of material in a layer-by-layer fashion. This manufacturing technique is growing in commercial usage, given its advantages in creating very dense or complex geometries as well as highly customizable components. In healthcare, for example, AM can be used to improve patient outcomes by providing timely medical devices (or parts) required for treatments. Minimizing the number of late parts in this context will directly improve the patients’ welfare. This paper studies the nesting and scheduling problem within the AM context and shows that the problem of minimizing the number of late parts is strongly NP-hard even if the nesting of parts into jobs is given. We also develop efficient algorithms to minimize the number of late parts, both when nesting is fixed beforehand and when nesting is part of the algorithm. The theoretical results, including algorithm performance bounds, developed in this paper are new contributions to the literature. An extensive computational study evaluates the performance of both algorithms. The nesting and scheduling algorithm performs within 7% of the lower bound on average and shows an effective way to nest and schedule systems containing challenging problem instances. Providing efficient, high-performing algorithms such as these will allow AM managers to quickly schedule parts for AM production with a minimum number of late parts and consequently improve both customer satisfaction and the profitability of the firm.

1. Introduction

Additive manufacturing (AM) is a production technique where products are manufactured, or “printed,” by layering and fusing material in a pre-determined pattern. It derives its name from its process of “adding” material layer by layer in order to create the desired object, in contrast to the more traditional subtractive or formative manufacturing technologies. Three-dimensional (3D) printing represents a common type of AM. In fact, 3D printers today can range in materials from standard polymers to “medical-grade” plastics and a variety of metal alloys (Courses, 2023). The process of AM can vary depending on the material, but one of the most common types is Direct Metal Laser Sintering, where the material is laid out on a bed, the laser heats the material to its melting point in a predetermined pattern, and then the material is given time to cool while excess material is removed (often by physical motion of the bed or print space). This cooling period varies by machine and material, but is typically a few seconds per layer (Castells, 2023).

AM takes its origins from rapid prototyping and stereolithography, dating back to the 1940s (Gonzalez, 2020), but has seen tremendous commercial growth in the 21st century across multiple industries. A McKinsey report estimates that as of 2020, AM as an industry has grown to over $\text{€}13$ billion with an annual growth rate of 22% (Bromberger et al., 2022). According to market research, the global aerospace 3D printing market alone was worth $1.38 billion in 2020 and is expected to reach a value of $6.8 billion by 2030 (Shah, 2023). Aerospace companies leverage the ability of AM to print very complex or dense parts and objects, including components that previously would be comprised of multiple parts that would then be assembled together. AM allows for these complex assemblies to be created faster and/or at lower cost. For example, GE Aviation redesigned one of its helicopter engines to be printed via AM. They took an older engine model, which consisted of 900 separate parts, each carrying its own tolerances, costs, and schedule concerns, and produced them in 16 distinct prints. They noted that the printed parts were “40% lighter and 60% cheaper,” which represents additional operational efficiencies and cost savings (Zelinski, 2017).

The healthcare industry also leverages AM technology in different capacities. In dentistry, AM is being used to create individualized products faster and more cheaply than ever before (Dawood et al., 2015). In the United States, university hospitals have started creating tailored medications through the use of AM technologies (Reina, 2023). Hospitals also utilize AM techniques to create specialized tools, individualized medical devices, synthetic replacement organs, and even anatomical models for both teaching and practice of techniques (Hellman et al., 2023; Olsen and Tomlin, 2020; Ventola, 2014). A recent study concluded that the delay of prostheses increases the 12-month postamputation costs by over 25% (Miller et al., 2020). Given AM’s ability to meet the construction requirements for custom prosthetics for a wide variety of materials (Wang et al., 2020), ensuring AM can meet the customer’s required due date and minimize the number of late parts would help improve patient outcomes. The use of AM in the healthcare industry was valued at approximately $7.6 billion in 2022 globally and expected to grow to over $29.5 billion by 2030 (Hancock, 2023).

In the spare parts market, when parts are needed in remote locations, AM has distinct advantages over traditional manufacturing and shipping, including speed of replenishment and reduced inventory volumes (Westerweel et al., 2021). AM also allows for increased flexibility and minimizing downtime through its ability to produce specific parts on demand (Alzahmi et al., 2025). Any delay in the creation of spare parts would further delay the repairs or maintenance activities commonly served by a firm’s spare parts inventory. AM has been shown to be of great interest to the spare parts management field (Bhattacharyya et al., 2023), and being able to properly schedule their production to minimize late parts would be valuable.

AM technologies can also improve sustainability/ environmental efforts in addition to improving financial outcomes. A 2024 Institute of Supply Management study showed a particular eyewear manufacturer could reduce their carbon footprint by up to 55% simply by replacing their traditional manufacturing process with more effective 3D printing (Stern, 2024). This was primarily due to requiring less material overall. In traditional subtractive manufacturing, for example, if a process requires 4 kg of input material but generates 2 kg of wasted material, that means the firm spent money and energy to procure more material than truly needed. With AM, however, most material unused for one print run can be reused for subsequent print runs, resulting in very little waste (Baumers and Holweg, 2019).

In an operations context, AM introduces a distinctive variation on classic job scheduling problems. In traditional machine shop environments, numerous heuristics have been developed to efficiently schedule jobs to optimize specific performance measures. For example, the shortest processing time rule is used to minimize the sum of job completion times, while the earliest due date (EDD) rule aims to minimize the maximum late time of deliveries. These scheduling rules have been used historically for their simplicity and effectiveness. AM, however, introduces an added layer of complexity: nesting—the assignment of individual parts into jobs—must be determined in addition to scheduling jobs. As illustrated in Figure 1, this nesting not only dictates which parts are grouped together but also directly affects the processing time of each job. This nesting is physically limited by the print space and is studied as an expansion of the bin-packing problem, with more discussion in Section 3.1. The processing time is determined by a combination of the total volume of parts within a job and the maximum height of parts within the job. The mathematical definition of the processing time estimation is further discussed in Section 3.2.

Figure 1.

Part-to-job nesting and scheduling of resultant jobs into an ordered sequence.

Consequently, decisions about nesting and scheduling (NAS) can be intertwined, complicating the overall optimization problem. In batch processing, the job processing time is typically the longest processing time of a component within that batch (Chandru et al., 1993). In AM, however, this relationship is non-linear and significantly increases the complexity of the scheduling problem. This complexity is further compounded when the scheduling objective is to minimize the number of late parts, a measure that is less commonly addressed than traditional performance metrics such as makespan and total completion time.

This paper studies the AM scheduling problem with the objective of minimizing the number of late parts, where each part has a specified delivery due date and is considered late when completed past said date. We consider two settings: (i) fixed nesting and (ii) variable nesting. A “fixed nesting” in this context is where parts are assigned to jobs prior to considering scheduling, and this specific nesting becomes immutable. Once the nesting is “fixed,” then the scheduling step occurs, as demonstrated in Figure 1. Alternatively, “variable nesting” is where both the nesting (i.e., part-to-job assignment) and the job sequence must be decided as part of the solution procedure. For the variable nesting problem, this nesting is adjusted to shorten or lengthen job processing times, potentially altering which parts are late. These terminologies will be further defined, including mathematically, in Section 3.3.

These unique aspects of AM scheduling give rise to the following research questions:

What is the computational complexity of minimizing the number of late parts in an AM setting?

Establishing its complexity as an NP-hard problem, can we develop simple and effective algorithms for scheduling with fixed nesting to minimize the number of late parts?

Can we design effective algorithms for the joint nesting and scheduling problem, where both part-to-job assignments and job sequencing are optimized to minimize the number of late parts?

We contribute to the literature and show that the fixed nesting problem is strongly NP-hard in Section 3.3. We also develop several algorithms and their performance bounds for the fixed nesting problem. While fixed nesting is computationally solvable for challenging problem instances, variable nesting problems often become difficult to solve within a realistic time for even simple problem instances. Most existing literature treats nesting (assigning parts to jobs) and scheduling (sequencing those jobs) as two separate steps, but our approach integrates them through a feedback loop. Prior work typically nests parts using heuristic criteria—such as minimizing the spread of due dates within each job (Chergui et al., 2018)—before scheduling jobs using traditional objectives. In contrast, our newly developed feedback-based algorithm evaluates the nesting decisions based on the final performance measure—namely, the number of late parts—and iteratively adjusts nesting accordingly. Using randomly generated part datasets, we benchmark our nesting and scheduling algorithms against corresponding optimization models and find that our heuristics achieve objective values within 7% of the lower bound.

The outline of this paper is as follows. Section 2 reviews the existing literature on AM, focusing specifically on an operations management context. In Section 3, we describe attributes specific to the AM environment, as well as providing definitions and notation for our nesting and scheduling problems in AM, which is the minimization of the number of late parts in AM with a fixed nesting of jobs. For this problem, we develop fixed nesting algorithms in Section 4; likewise, the variable nesting version of this problem is detailed in Section 5. Section 6 contains the computational study for both versions, comparing solutions from mixed integer programs (MIPs) and the developed algorithms. Finally, a summary, managerial impacts, and future research opportunities are discussed in Section 7.

2. Literature review

While this research is focused on AM in the operations management domain, the existing AM literature is primarily focused on engineering and technology journals centered on process development and improvement. In the context of supply chain implications, a growing body of literature examines the potential of AM to drive substitution and structural changes in retail operations (Chen et al., 2021) as well as its associated intellectual property challenges (Zhang et al., 2022). These aspects lie outside the scope of our study, however. Existing operations management research on AM scheduling typically separates the nesting and scheduling stages of AM into two distinct procedures, as illustrated in Figure 1. In the first stage, parts are nested into jobs according to a pre-determined criterion, which may or may not align with the overall optimization objective. In the second stage, the resulting jobs are then sequenced appropriately based on the desired performance metric. While this forward-oriented approach has clear advantages—most notably its ease-of-use—this distinct two-stage procedure is less effective in addressing the number of late parts problem, which is the primary focus of our paper.

In their AM taxonomy review, Oh et al. (2020) establish that most AM research takes on a series of categorical characteristics which help to partition the wide range of different problem classes that can exist. The two main characteristics are machine class (single- vs. multiple-machine systems) and the research target (nesting- vs. scheduling-stage focused). For the latter characteristic, our research will develop a method to connect the nesting and scheduling stages in an effective manner for the number of late parts problem. As for machine class, in order to maintain the generalizability of problem instances, our research will focus on the single machine environment. Table 1 summarizes key AM research currently found in the literature, including the research objective, the solution approach, and the nesting criterion if the paper was focused on the scheduling stage.

Table 1.

Additive manufacturing related research papers.

Reference	Scheduling objective	Machine set-up	Solution approach	Nesting criterion
Kucukkoc et al. (2016)	Max. machine volume utilization	Multiple machines	Heuristic	Part value calculation based on size and current machine usage
Chergui et al. (2018)	Min. total tardiness	Multiple machines	Heuristic	Minimize due date differences within each job
Dvorak et al. (2018)	Min. maximum lateness (primary); Min. makespan (secondary)	Multiple machines	Heuristic	Maximize machine utilization while not surpassing any individual part’s due date
Fera et al. (2018)	Min. time and cost	Single machine	Genetic algorithm	Maximize 3D machine utilization
Luzon and Khmelnitsky (2018)	Min. makespan	Single machine	MIP (exact)	Job-level nesting
Kucukkoc (2019)	Min. makespan	Single and multiple machines	MIP (exact)	Nesting is primary objective
Yuanbin et al. (2019)	Max. machine volume	Multiple machines	Heuristic	Minimize height differences within each job
Fera et al. (2020)	Min. time and cost	Single machine	Tabu search	Job-level nesting
Aloui and Hadj-Hamou (2021)	Min. total lateness	Single machine	Greedy algorithm	Non-increasing delay of jobs
Altekin and Bukchin (2022)	Min. makespan	Single and multiple machines	MIP (exact)	Maximize machine utilization
Sormaz et al. (2023)	Min. tardy jobs	Single machine	MIP (exact)	Pre-determined nesting
Our paper	Min. number of late parts	Single machine	Heuristic	Part of algorithm

Note. 3D = three-dimensional; MIP = mixed integer program.

The known batch scheduling problem (Brucker et al., 1998) also has similar characteristics to problems found in AM research with parts scheduled into jobs, or batches, on the machines. The key difference between batch scheduling and AM, however, is in the determination of processing times. In batch scheduling, the processing time of a batch is typically determined by the largest processing time of the parts included in the batch. If a new part were to be added to the batch, it would likely not change the batch processing time, given there was sufficient capacity and the processing time of the current batch was longer than the new part. In contrast, the processing time of a job in AM depends on both the total volume of all parts and the maximum part height in the job. Consequently, adding a new part always increases the job’s processing time due to its contribution to total volume, even if the maximum height remains unchanged. This processing time determination for AM is discussed further in Section 3.2.

2.1. Nesting research within AM

As stated in the Introduction, most existing literature deals with the nesting and scheduling problem in a two-stage method: stage one performs nesting based on some criterion, and stage two sequences the nested jobs. Several studies have explored heuristic and metaheuristic approaches for AM scheduling, including the use of genetic algorithms and Tabu search (Fera et al., 2018, 2020; Zhang et al., 2019). Chergui et al. (2018) propose using a linear programming model which minimizes the total difference in due dates among parts assigned to the same job, thereby encouraging the nesting of parts with similar deadlines. Similarly, Yuanbin et al. (2019) introduce a “ part priority” measure—based on part area, height, and time remaining to due date—to guide the initial job generation. While the due dates influence priority in this calculation, they do not directly affect the job assignment, which still relies on the standard “first fit” (FF) rule commonly used in bin packing. The nesting problem has also been addressed by maximizing the total area used within a single machine (i.e., machine volume utilization) in several studies (Kucukkoc et al., 2016; Oh et al., 2018a; Zhang et al., 2017). While this technique minimizes the overall number of jobs and thereby decreases the set-up times required in the overall system, it does not always account for the effect each additional part in a job has on the completion time. Even as systems are expanded into the multiple machine context, such as in Oh et al. (2018b), machine utilization is still a commonly used criterion for nesting.

Each of these papers addresses the nesting stage as a wholly independent step of the procedure. This distinction simplifies the methodology, but it does not fully consider how the nesting of parts into jobs can impact the objective function. For specific objective functions, such as the sum of completion times and the makespan, maximizing the machine utilization is a generally effective method to nest parts into jobs, as seen in Zhang et al. (2017) and Kucukkoc et al. (2016). The nesting of parts into jobs can significantly impact the processing times and thus the lateness of individual parts in the system. When the objective is to minimize the number of late parts, as in our study, separating the nesting from scheduling is ineffective because these two stages are non-linearly related to the objective function.

With increased computing power, recent studies have proposed algorithms to “solve” the nesting and scheduling problems simultaneously, including the use of MIP models to obtain exact solutions for optimal makespan (Altekin and Bukchin, 2022; Luzon and Khmelnitsky, 2018). Makespan is relatively solvable in practice, even for large-scale problems. The number of late parts problem, however, is non-linear. Our paper will demonstrate that the solution time for such non-linear problems can take over 6 hours in many instances.

The final research area for the nesting stage of AM addresses the orientation selection sub-problem, where the orientation of parts is a key component of the decision variable (Che et al., 2021). While part orientation is important to the overall nesting feasibility, our paper will assume “shadow-boxes” of parts, meaning individual parts cannot overlap in any $(X,Y)$ dimension at any height $Z$ . The parts take up the full “box” created by the largest dimension in each of the cardinal directions, even if those dimensions merely “cast a shadow” onto the $(X,Y)$ plane. This is done for generalizability and is a conservative estimate representing the worst-case scenario of the parts’ individual processing times. As noted by Kucukkoc (2019: p. 61), this is also common in practice and parts are “usually designed with a pre-determined build orientation to maximise [their] quality.” This is discussed further in Section 3.1.

2.2. Lateness objective measures

When considering alternative scheduling objectives, makespan and maximum lateness are addressed by Kucukkoc (2019) and Dvorak et al. (2018), respectively, with corresponding heuristics developed for each. The former focuses on minimizing makespan, but does not account for part due dates, implicitly assuming the overall completion is the primary objective. While such an assumption may hold in specific cases—such as when multiple parts are processed for assembly into a single, long-lead item—it is not a typical scenario in most production settings. Likewise, the algorithm from Dvorak et al. (2018) seeks to minimize various measures of job tardiness, but does not evaluate the individual part measures. Our study recognizes the impact of these past methodologies, but also seeks to address part-level measures, which allow greater flexibility in the application of the algorithms developed here. Dvorak et al. (2018) include a modification for a weighting scheme based on part dimensions to utilize an EDD rule, which translates well into a part-focused measure as used in our study. This is the basis for the modified Moore–Hodgson (MMH) algorithm proposed in Section 4.2 as an adaptation of the original algorithm (Moore, 1968).

Aloui and Hadj-Hamou (2021) propose a greedy algorithm for assigning parts into jobs by selecting job placement that introduces minimal or no lateness to the overall system. This approach, however, can lead to sub-optimal part-to-job assignment when multiple options are equally acceptable. In our work, we address this limitation by introducing a secondary nesting criterion based on job/ part height to guide the assignment more effectively. Sormaz et al. (2023) employ a modified Maxwell model to minimize the number of tardy jobs, with a particular focus on print quality, which is a key concern in plastics printing. Their integer programming approach, similar to that in Pinedo (2002), uses a forward algorithm to assign jobs based on their respective due dates while rejecting jobs that cannot be completed on time—analogous to the Moore–Hodgson algorithm described in Section 4.2 (Moore, 1968). The model further accounts for job quality, where higher-quality jobs require longer processing due to slower print speeds, enabling an evaluation of how many jobs can be completed on time at optimal quality. In contrast, our approach treats print speed as a fixed machine parameter (Section 3.2), eliminating the need to consider varying part quality. Building on both Aloui and Hadj-Hamou (2021) and the modified Maxwell model of Sormaz et al. (2023), our paper focuses on determining the best bounds achievable for this NP-hard scheduling problem.

3. Problem description and computational complexity

We provide the attributes specific to the AM machine environment and the estimation of part processing times in the sections below. We then define the number of late parts problem in AM as well as establish its computational complexity.

3.1. Machine environment and part attributes

The creation of individual jobs in AM is done via the nesting of a subset of parts. In an AM environment, each job consists of a subset of parts produced simultaneously when an AM machine processes the job. When the job is completed, all parts assigned to that job are also completed at the same time. Consider an AM machine area or building platform, which is usually a rectangular shape with $M\times M\times M$ dimensions. The platform can hold a maximum volume $M^3$ of parts.

Given a nesting of jobs, we propose a method to estimate the processing times of each job consisting of a set of parts. We consider producing parts, $P_i$ , $i=1,2,\dots ,m$ , with the specification $a_i\times b_i\times c_i$ , where $a_i\le M$ , $b_i\le M$ , $c_i\le M$ denote length, width, and height of $P_i$ , respectively. The volume of part $P_i$ is $v_i=a_i\times b_i\times c_i$ if the part is a perfect rectangular shape; otherwise, $v_i<a_i\times b_i\times c_i$ . Typically, the dimensions ( $a_i$ , $b_i$ , $c_i$ ) and the volume ( $v_i$ ) are known once the design of a part $P_i$ is finalized.

The job processing time worst-case estimator detailed in Section 3.2 uses the “shadow-box” assumption and treats all parts as full rectangular-shaped boxes. We make this worst-case conservative assumption for generalization, even though it is highly unlikely that every part in a system is exactly a rectangular box. In addition, due to the potential need for support structures in parts that have sharp edges along the vertical axis (Griffiths et al., 2018), the required AM print volume can be greater than the actual volume of the part itself. This assumption is also known as a “boundary projection” limitation and is used in other AM literature, such as Zhang et al. (2016). By reducing the parts into two-dimensional rectangles, we eliminate the need for three-dimensional modeling to address any additional part orientations beyond the 90° rotations on the $(X,Y)$ -plane. This two-dimensional projection is also commonly found in practice (Kucukkoc, 2019). This assumption also eliminates any possibility of overlapping parts. While this would increase the available print space and reduce processing times (Wang et al., 2019), the shadow-box assumption is an effective generalization tool that allows for quick estimation of a job’s processing time given a nesting of parts.

3.2. Job processing time

In an AM environment, an effective method to estimate the processing time of jobs consisting of different parts is needed. In this study, we use a similar version of the volumetric print time calculations used by Chergui et al. (2018) and Aloui and Hadj-Hamou (2021). The job processing time of job $J_j$ is the sum of three components: the AM machine setup time for the job ( $t$ ), the total volumetric print time of the parts contained within the job ( $g\times V_j$ ), and the layer cooling time ( $t_c$ ) (as a function of the maximum height among parts contained within the job). The job processing time of a job is estimated as $[t+g\times V_j+t_c]$ , where $V_j$ is the total volume of parts contained within the job, $V_j=\sum _{P_i\in J_j}{v}_i$ . The AM machine setup time, $t$ , is the time required for cleaning, initializing, and calibrating the AM machine for each job. For convenience, it is standardized to 1 unit of time for each job. The volumetric print time, $g\times V_j$ , is the “active” time required to print each part and is a product of the total volume of parts contained within the job ( $V_j$ ) and the time required to print per unit volume of the part ( $g$ ). The cooling time is $t_c=e\times z_{max,j}$ , where $z_{max,j}$ is the maximum height of parts in job $J_j$ ( $z_{max,j}=max\{c_i|P_i\in J_j\}$ ) and $e$ is the per-layer “cooling” time required for material set-up and layer processing. More details can be found in E-Companion Section EC.1.

3.3. Notation definitions

We use $\alpha |\beta |\gamma$ scheduling classification by Graham et al. (1979) to denote our problem, where $\alpha$ describes the machine environment (e.g., single machine, parallel machines, etc.), $\beta$ provides the job characteristic or restrictive requirements, and $\gamma$ specifies the optimality criterion or the measure of performance. Note that the processing time of a job depends not only on the total volume of all parts within the job but also on the maximum height among those parts. Thus, the problem analyzed in this section is denoted as $1|\text{nest fixed},v_i,c_i|N_{\text{late}}$ , where $\alpha =1$ denotes the single machine environment, $\beta =\text{nest fixed}$ specifies the nesting of jobs with $v_i$ (or $c_i$ ) specifying the volume (or height) of parts in a job, and $\gamma =N_{\text{late}}$ indicates the objective function of minimizing the “Number of Late Parts.” As noted in Section 3.1, the shadow-box assumption fixes the volume of each part to be its dimensions, $v_i=a_i\times b_i\times c_i$ , to maintain generalizability. While the problem notation for this analysis should be $1|\text{nest fixed},v_i,c_i|N_{\text{late}}$ , we will drop the $v_i,c_i$ characteristic for simplicity and denote the fixed nesting problem as $1|\text{nest fixed}|N_{\text{late}}$ in the remainder of the paper. We use the notation $1|\text{nest}|N_{\text{late}}$ to denote the problem of jointly determining the assignment of parts to jobs (nesting) and the sequencing of jobs on a single machine, with the objective of minimizing the total number of late parts. Notation definitions are provided in Table 2 for the AM scheduling problem. For the following sections, we want to find a job sequence, $\sigma$ , which minimizes $N_{\text{late}}$ .

Table 2.

Notation and parameters for formulating the scheduling problem.

Parameters
$P$	Set of parts, $P=\{P_1,P_2,\dots ,P_m\}$ , where $m$ is the number of parts.
$a_i$	Length ( $X$ -dimension) of part $P_i$ , $i=1,2,\dots ,m$ .
$b_i$	Width ( $Y$ -dimension) of part $P_i$ , $i=1,2,\dots ,m$ .
$c_i$	Height ( $Z$ -dimension) of part $P_i$ , $i=1,2,\dots ,m$ .
$v_i$	Volume of part $P_i$ , where $v_i=a_i\times b_i\times c_i$ , $i=1,2,\dots ,m$ .
$w_i$	Weight assigned to part $P_i$ , $i=1,2,\dots ,m$ .
$d_i$	Due date of part $P_i$ , $i=1,2,\dots ,m$ .
$J$	Set of jobs in given nesting, $J=\{J_1,J_2,\dots ,J_n\}$ , where $n\le m$ .
$V_j$	Volume of job $J_j$ , $j=1,2,\dots ,n$ , where $V_j=\sum _{P_i\in J_j}{v}_i$ .
$z_{max,j}$	Maximum height of parts in the $j^{\text{th}}$ job and $z_{max,j}=max\{c_i|P_i\in J_j\}$ .
$p_j$	Processing time of job $J_j$ , $j=1,2,\dots ,n$ .
Variables
$C_j$	Completion time of the $j^{\text{th}}$ job in sequence $\sigma$ , where $\sigma =({\sigma }_1,{\sigma }_2,\dots ,{\sigma }_n)$ , ${\sigma }_i=J_{{\sigma }_j}$ indicates the $j^{\text{th}}$ job in sequence $\sigma$ , and $\sigma$ is an ordered sequence of jobs in given nesting $J$ .
$U_j$	Number of late parts in the $j^{\text{th}}$ job in sequence $\sigma$ , where $U_j=\sum _{P_i\in J_{{\sigma }_j}}{u}_i$ and
	$u_i=1$ if $C_j>d_i$ for part $P_i\in J_{{\sigma }_j}$ , otherwise $u_i=0$ .

3.4. Computational complexity

Within a given nesting, the number of late parts, $N_{\text{late}}(\sigma )$ in sequence $\sigma$ is defined as follows: $U_j$ denotes the number of late parts in the $j^{\text{th}}$ job in sequence $\sigma$ , where $U_j=\sum _{P_i\in J_{{\sigma }_j}}{u}_i$ ( $u_i=1$ if $C_j>d_i$ for part $P_i\in J_{{\sigma }_j}$ , otherwise $u_i=0$ ).

$$N_{\text{late}}(\sigma )=\sum _{j=1}^n{U}_j,$$

where $\sigma =\{{\sigma }_1,{\sigma }_2,\dots ,{\sigma }_{n^r}\}$ and ${\sigma }_i=J_{{\sigma }_j}$ indicates the $j^{\text{th}}$ job in $\sigma$ .

In an AM environment with fixed nesting, we need to find the job sequence $\sigma$ that minimizes the number of late parts, $N_{\text{late}}(\sigma )$ . For a given nesting, problem $1|\text{nest fixed}|N_{\text{late}}$ is shown to be strongly NP-hard.

Theorem 1

The decision version of problem $1|\text{nest}\text{fixed}|N_{\text{late}}$ is strongly NP-complete.

Proof.

The reduction is from Numerical Matching with Target Sum (Garey and Johnson, 1979). The details can be found in E-Companion Section EC.2.

Remark 1

The special case of problem $1|\text{nest fixed}|N_{\text{late}}$ , where all parts of a job share the same due date, is equivalent to the classical single machine scheduling problem $1||w_j{U}_j$ , which minimizes the weighted number of late jobs. Here, $U_j=1$ if job $j$ in sequence $\sigma$ is late; otherwise $U_j=0$ . This equivalence follows by setting in $1||w_j{U}_j$ the weight of job $j$ , $w_j$ , equal to the number of parts in job $j$ . After this conversion, the equivalence is immediate. Garey and Johnson (1979) shows that $1||w_j{U}_j$ is weakly NP-hard but solvable in pseudo-polynomial time $O(nW)$ , where $W=\sum w_j$ is the total job weight. In contrast, Theorem 1 establishes that the general problem $1|\text{nest fixed}|N_{\text{late}}$ is strongly NP-hard. Hence, neither a pseudo-polynomial nor a polynomial-time algorithm can exist for the general problem $1|\text{nest fixed}|N_{\text{late}}$ .

4. Algorithms for the problem with fixed nesting

In this section, we formulate a mixed-integer programming model to obtain the optimal solution. We then develop several heuristic algorithms that can produce comparable solutions with substantially lower computational time. Furthermore, we derive performance bounds for each heuristic in the worst-case context.

4.1. MIP formulation

We first present an MIP formulation for problem $1|\text{nest fixed}|N_{\text{late}}$ that finds the optimal sequence of jobs to minimize the total number of late parts for a given nesting. Table 3 presents the additional notation that is used in the formulation of this MIP.

$$\begin{array}{rl}\mathbf{\text{Formulation}}\mathbf{P}\mathbf{:}& \text{ Min }{N}_{\text{late}}=\sum _{i=1}^n\sum _{k=1}^m{y}_{ik}\\ \text{Subject to }\\ \sum _{j=1}^n{x}_{jk}& =1,k=1,2,\dots ,n\end{array}$$

(1)

$$\begin{array}{rl}\sum _{k=1}^n{x}_{jk}& =1,j=1,2,\dots ,n\end{array}$$

(2)

$$\begin{array}{rl}{C}_0& =0\end{array}$$

(3)

$$\begin{array}{rl}{C}_k& =C_{k-1}+\sum _{j=1}^n{p}_j{x}_{jk},k=1,2,\dots ,n\end{array}$$

(4)

$$\begin{array}{rl}{f}_{ik}& \ge x_{jk}+{\lambda }_i^j-1,k=1,2,\dots ,n;\\ & i=1,2,\dots ,m;j=1,2,\dots ,n\end{array}$$

(5)

$$\begin{array}{rl}M{y}_{ik}+M(1-f_{ik})& \ge C_k-d_i{f}_{ik},k=1,2,\dots ,n;\\ & i=1,2,\dots ,m\end{array}$$

(6)

$$\begin{array}{rl}{y}_{ik}& \le f_{ik},k=1,2,\dots ,n;i=1,2,\dots ,m\end{array}$$

(7)

$$\begin{array}{rl}{x}_{jk},f_{ik},y_{ik}& \in \{0,1\},j=1,2,\dots ,n;k=1,2,\dots ,n;\\ & i=1,2,\dots ,m\end{array}$$

(8)

$$\begin{array}{rl}{C}_k& \ge 0,k=0,1,2,\dots ,n\end{array}$$

(9)

Table 3.

Additional notation and parameters for MIP formulation.

Parameters
$m_j$	Number of parts in $J_j$ , $j=1,2,\dots ,n$ .
${\lambda }_i^j$	Prescribes the part-to-job assignment of the given fixed nesting, where ${\lambda }_i^j=1$ if part $i$ belongs to job $j$ ; otherwise ${\lambda }_i^j=0$ .
$M$	Big number. It is sufficient to set $M=\sum _{j=1}^n{p}_j+1$ .
Variables
$N_{\text{late}}$	Total number of late parts, the objective function of formulation P.
$x_{jk}$	Binary decision variable indicating whether or not job $j$ occupies the $k^{\text{th}}$ position in sequence $\sigma$ .
$C_k$	Completion time of the $k^{th}$ job in sequence $\sigma$ , where $\sigma =({\sigma }_1,{\sigma }_2,\dots ,{\sigma }_n)$ and ${\sigma }_k=J_{{\sigma }_j}$ indicates the $k^{\text{th}}$ job in sequence $\sigma$ (to be determined by $x_{jk}$ ).
$f_{ik}$	Binary decision variable indicating whether or not part $i$ is assigned to the job in position $k$ in $\sigma$ .
$y_{ik}$	Binary decision variable indicating whether or not part $i$ in position $k$ is late in sequence $\sigma$ , if the part is assigned to the job in position $k$ .

Note. MIP = mixed integer program.

Constraint (1) requires exactly one job to occupy a position $k$ in the job sequence. Constraint (2) requires a job $j$ to occupy only one position in the job sequence. Constraint (3) sets the starting time of the $1^{\text{st}}$ job in the job sequence at time $0$ . Constraint (4) determines the finish time of the $k^{\text{th}}$ job scheduled in the job sequence. Constraint (5) indicates whether or not part $i$ is assigned to the job sequenced in position $k$ , such that $f_{ik}=1$ only if job $j$ is assigned to position $k$ and part $i$ is in job $j$ . Constraints (6) and (7) determine whether each part belonging to job $j$ sequenced in the $k^{\text{th}}$ position is late. Constraints (8) and (9) define the binary and continuous variables, respectively.

The computational time for formulation P ranges from less than a second to several hours as the quantity of parts and jobs increases. During the computational study shown in Section 6, the largest problem instances (100 parts) averaged about 5 min per solution to formulation P. While this average time is not large, during the execution of our variable nesting algorithm (NAS algorithm), several hundred schedules may be evaluated for a single instance using a fixed nesting subroutine. Therefore, we develop a scheduling algorithm to address fixed nesting and provide the foundation for our variable nesting algorithm in a much shorter time-frame.

4.2. Heuristics for fixed nesting

In this section, we develop heuristic algorithms to sequence jobs under fixed nesting, where the assignment of parts to jobs is predetermined and immutable. Before addressing the specific challenges posed in this context, we first examine the problem using job-level performance measures. This foundation allows us to later extend the analysis to part-level performance measures, which are intrinsic to AM.

4.2.1. Adapted Moore–Hodgson (AMH) algorithm

In the classical single machine scheduling literature, Moore’s algorithm (Moore, 1968) minimizes the number of late jobs. Moore (1968) also presents a version of his algorithm that he attributes to T. E. Hodgson. We now adapt this algorithm (Moore, 1968) to the AM environment to address problem $1|\text{nest fixed}|N_{\text{late}}$ . This adapted algorithm is called the AMH algorithm. The complete pseudocode of the AMH algorithm is found in E-Companion Section EC.2.3, but the steps are as follows:

Let the due date of parts in $J_j$ be $\{d_1^j,d_1^j,\dots ,d_{m_j}^j\}$ such that the due dates are arranged in the non-decreasing order: $d_1^j\le d_2^j\le \cdots \le d_{m_j}^j$ , where $m_j$ denotes the number of parts in $J_j$ , $j=1,2,\dots ,n$ . Set the due date of job $J_j$ as $D_j=d_1^j$ , $j=1,2,\dots ,n$ and find the EDD sequence of jobs such that $(J_1,J_2,\dots ,J_n)$ with $D_1\le D_2\le \cdots \le D_n$ . Using these definitions, run the Moore–Hodgson algorithm as prescribed in Moore (1968). Lastly, the final step of the AMH algorithm measures the number of late parts as opposed to the number of late jobs.

Performance Bounds: We develop the worst case performance bounds of AMH and its variations below. Let $N_h(\mathcal{I})$ denote the objective value (number of late parts) given by AMH for problem instance $\mathcal{I}$ while $N^{*}(\mathcal{I})$ denotes the optimal objective function value for $\mathcal{I}$ . The proofs of these bounds are shown in E-Companion Sections EC.2.3–EC.2.5.

Theorem 2

The performance ratio $R$ of the AMH algorithm for problem $1|\text{nest fixed}|N_{\text{late}}$ is bounded by the following relation:

$$R=\frac{N_h(\mathcal{I})}{N^{*}(\mathcal{I})}\le m_o,$$

for any problem instance $\mathcal{I}$ , where $m_o=max\{m_1,m_2,\dots ,m_n\}$ . This bound is tight.

As the bound $m_o$ can be large, we enhance the AMH algorithm by adapting another version, AMH2 algorithm, which is similar to that of the AMH algorithm except Steps 1 and 2, where the due date of job $J_j$ is defined as follows. Let the due date of parts in $J_j$ be $\{d_1^j,d_1^j,\dots ,d_{m_j}^j\}$ such that the due dates are arranged in the non-decreasing order: $d_1^j\le d_2^j\le \cdots \le d_{m_j}^j$ . Let $o_j=\lceil m_j/2\rceil$ and set the due date of job $J_j$ as $D_j=d_{o_j}^j$ , $j=1,2,\dots ,n$ (Step 1 of the AMH2 algorithm). Step 2 of the AMH2 algorithm finds the EDD sequence of jobs: $(J_1,J_2,\dots ,J_n)$ with $D_1\le D_2\le \cdots \le D_n$ . The pseudocode of the AMH2 algorithm can be found in E-Companion Section EC.2.4.

Let $m_{\ell }=min\{m_1,m_2,\dots ,m_n\}$ . Note that $m_o=max\{m_1,m_2,\dots ,m_n\}$ . $N_h(\mathcal{I})$ denotes the objective value (number of late parts) given by the heuristic algorithm, the AMH2 algorithm, for problem instance $\mathcal{I}$ while $N^{*}(\mathcal{I})$ denotes the optimal objective function value for $\mathcal{I}$ . Let $n_r$ be the number of jobs rejected by the AMH2 algorithm.

Theorem 3

The performance ratio $R$ of the AMH2 algorithm for problem $1|\text{nest fixed}|N_{\text{late}}$ is bounded by the following relation:

$$R=\frac{N_h(\mathcal{I})}{N^{*}(\mathcal{I})}\le [\frac{n}{n_r}-1]\frac{\lfloor m_o/2\rfloor }{\lceil m_{\ell }/2\rceil }+\frac{m_o}{\lceil m_{\ell }/2\rceil },$$

for any problem instance $\mathcal{I}$ . This bound is tight.

Corollary 1

For problem instance $\mathcal{I}$ with $m_o=m_{\ell }$ , then the performance ratio $R$ of the AMH2 algorithm for problem $1|\text{nest fixed}|N_{\text{late}}$ is bounded by the following relation:

$$R=\frac{N_h(\mathcal{I})}{N^{*}(\mathcal{I})}\le \frac{n}{n_r}+1.$$

The above result suggests that the AMH2 algorithm performs well for problem instances where a large number of jobs $n_r$ are rejected (i.e., labeled as late jobs) by the algorithm, and the number of parts in all jobs is nearly equal.

To further improve the performance, we now propose the AMH^* algorithm that executes both AMH and AMH2 algorithms, and selects the sequence corresponding to the best objective function value among the two sequences obtained by AMH and AMH2 algorithms. The AMH^* algorithm is used as a benchmark to measure the performance of a more complex MMH algorithm presented in the next section. The detailed steps of the AMH^* algorithm can be found in E-Companion Section EC.2.5. The following result follows from Theorems 2 and 3.

Theorem 4

The performance ratio $R$ of the AMH^* algorithm for problem $1|\text{nest fixed}|N_{\text{late}}$ is bounded by the following relation:

$$R=min\{m_o,[\frac{n}{n_r}-1]\frac{\lfloor m_o/2\rfloor }{\lceil m_{\ell }/2\rceil }+\frac{m_o}{\lceil m_{\ell }/2\rceil }\},$$

for any problem instance $\mathcal{I}$ . This bound is tight.

The computational study in Section 6.2 shows that, on average, the AMH^* algorithm performs best when a strict EDD nesting rule is applied, among the four nesting rules proposed in Section 6. We now introduce the MMH algorithm, which achieves superior performance under the remaining nesting rules.

4.2.2. The MMH algorithm

Building on the previous literature, we modify the Moore–Hodgson algorithm to include the features of AM scheduling, $1|\text{nest fixed}|N_{\text{late}}$ , and develop the MMH algorithm. In an AM environment, for a fixed job nesting, we need to find the job sequence $\sigma$ that minimizes the number of late parts, $N_{\text{late}}(\sigma )$ . Recall that $m_j$ and $p_j$ are the number of parts and the processing time of job $J_j$ , respectively, for a given nesting. The step-by-step description of this algorithm can be found in Algorithm 1. The pseudocode for Algorithm 1 can be found in E-Companion Section EC.3.

Similar to the AMH algorithm, we first arrange the due dates of parts in job $J_j$ as $d_1^j,d_2^j,\dots ,d_{m_j}^j$ in non-decreasing order: $d_1^j\le d_2^j\le \cdots \le d_{m_j}^j$ , for $j=1,2,\dots ,n$ . The due date of job $J_j$ is then set to $D_j=d_1^j$ , and the jobs are sequenced in EDD order, yielding $(J_1,J_2,\dots ,J_n)$ with $D_1\le D_2\le \cdots \le D_n$ . Based on this initial sequence, we compute job completion times and determine the number of late parts.

Using the ratio of late parts within each job as the weight, we iteratively reject jobs to a reject sequence according to the longest weighted processing time. In the event of a tie, the job with the smallest index is rejected. The reject sequence is always maintained in EDD order. After each rejection, we update the completion times and recalculate the number of late parts for the entire system (with the reject sequence appended at the end of the main sequence). The weights are then updated to reflect the new number of late parts, and the process repeats as long as the total number of late parts does not increase.

The algorithm terminates once the total number of late parts reaches its minimum or when all jobs in the main sequence have been evaluated. The final output is the complete sequence—including both main and reject sequences—together with the corresponding total number of late parts.

Performance of the MMH algorithm: The MMH algorithm for the problem $1|\text{nest fixed}|N_{\text{late}}$ is complex due to its iterative nature. Nevertheless, we investigate the performance bound for the general case of the problem. The proofs of these bounds are shown in E-Companion Section EC.2.6.

Theorem 5

The performance ratio $R$ of the MMH algorithm is bounded by the following relation:

$$R=\frac{N_h(\mathcal{I})}{N^{*}(\mathcal{I})}\le m,$$

for any problem instance $\mathcal{I}$ , where $m$ is the total number of parts. This bound is tight.

Remark 2

The performance bound derived in Theorem 5 for the MMH algorithm is not stronger than those obtained for the AMH algorithm. However, our computational study in Section 6 shows that the MMH algorithm outperforms the AMH algorithm for most practically relevant problem instances, in contrast to the limitations implied by the worst-case bounds. This discrepancy arises because the worst-case instances are constructed based on extreme scenarios that rarely occur in practice.

5. Algorithms for the problem with variable nesting

In variable nesting, a batch of parts with known dimensions and due dates must be nested into jobs and then appropriately sequenced. This additional nesting flexibility introduces greater complexity but also provides more opportunities to reduce the overall number of late parts in the system. Similar to the fixed nesting case, we first present an MIP formulation to minimize the number of late parts. We then extend the MMH algorithm to the NAS algorithm, incorporating a feedback loop to jointly address both nesting and scheduling decisions. The NAS algorithm can generate solutions of comparable quality to those obtained by the MIP model, but with substantially lower computational time. Moreover, we establish a worst-case performance bound for this algorithm. As before, the part-to-job nesting procedure described in Section 3.1 and the job processing time estimation outlined in Section 3.2 remain applicable under variable nesting.

5.1. MIP formulation

We present an MIP, formulation Q, for problem $1|\text{nest}|N_{\text{late}}$ that determines the assignment of parts to jobs and the sequence of jobs to minimize the total number of late parts. Table 4 presents the additional notation used in the formulation of this MIP. We assume that the problem instance consists of $m$ parts. In the worst case, $m$ jobs may be formed where each job is assigned only one part. Thus, in this MIP, we allow the formation of at most $m$ jobs.

Table 4.

Additional notation and parameters for variable nesting MIP formulation.

Parameters
$m$	Total number of parts to be produced.
$s_i$	Surface area of part $P_i$ , where $s_i=a_i\times b_i+\delta$ and $\delta$ is a small surface area added to facilitate the arrangement of parts with some space between them in the surface area $S$ of the AM machine, $i=1,2,\dots ,m$ .
$S$	Printable surface area of the AM machine.
$g$	Per volume print time, as defined by the AM machine.
$e$	Per-layer cooling time, as defined by the AM machine.
$t$	Setup time of a job in the AM machine.
$M$	Large number. It is sufficient to set $M=m(t+(e\times z_o)+(g\times S\times z_o))$ , where $z_o=max\{c_1,c_2,\dots ,c_m\}$ .
Variables
$N_{\text{late}}$	Total number of late parts, the objective function of formulation Q (dependent on $\sigma$ ).
$x_{ij}$	Binary decision variable indicating whether or not part $i$ is assigned to the $j^{\text{th}}$ job in sequence $\sigma$ .
$y_i$	Binary indicator of the lateness of part $i$ in $\sigma$ , 1 being late and 0 otherwise.
$z_{max,j}$	Maximum height of parts in the $j^{\text{th}}$ job in sequence $\sigma$ .
$p_j$	Processing time of the $j^{\text{th}}$ job in sequence $\sigma$ .
$C_j$	Completion time of the $j^{\text{th}}$ job in sequence $\sigma$ .
$F_i$	Dummy variable to obtain the completion time of part $P_i$ job in sequence $\sigma$ when positive.
${\mu }_j$	Binary decision variable indicating whether or not job $J_j$ contains any parts.

Note. MIP = mixed integer program; AM = additive manufacturing.

Note that in formulation Q, the assignment of parts to jobs and the sequencing of jobs are determined simultaneously. The characteristics of each job on a single machine are known at the time the job is formed—specifically, its print volume and maximum print height—so its processing time is known when it is formed. In addition, setup times and print speeds are identical for all jobs. These features allow formulation Q to place job $J_j$ in position $j$ , and then determine the optimal assignment of parts to job $J_j$ at that position.

$$\begin{array}{rl}\mathbf{\text{Formulation}}\mathbf{Q}\mathbf{:}& \text{ Min }{N}_{\text{late}}=\sum _{i=1}^m{y}_i\\ \text{Subject to }\\ \sum _{j=1}^m{x}_{ij}& =1,i=1,2,\dots ,m\end{array}$$

(10)

$$\begin{array}{rl}\sum _{i=1}^m{x}_{ij}& \le m\cdot {\mu }_j,j=1,2,\dots ,m\end{array}$$

(11)

$$\begin{array}{rl}{\mu }_j& \le \sum _{i=1}^m{x}_{ij},j=1,2,\dots ,m\end{array}$$

(12)

$$\begin{array}{rl}{\mu }_j& \le {\mu }_{j-1},j=1,2,\dots ,m\end{array}$$

(13)

$$\begin{array}{rl}{z}_{max,j}& \ge c_i{x}_{ij},j=1,2,\dots ,m;i=1,2,\dots ,m\end{array}$$

(14)

$$\begin{array}{rl}{z}_{max,j}& \le \sum _{i=1}^m{c}_i{x}_{ij},j=1,2,\dots ,m\end{array}$$

(15)

$$\begin{array}{rl}\sum _{i=1}^m{s}_i{x}_{ij}& \le S,j=1,2,\dots ,m\end{array}$$

(16)

$$\begin{array}{rl}{p}_j& =t\cdot {\mu }_j+g\sum _{i=1}^m{v}_i{x}_{ij}+e\cdot z_{max,j},\\ & j=1,2,\dots ,m\end{array}$$

(17)

$$\begin{array}{rl}{C}_0& =0\end{array}$$

(18)

$$\begin{array}{rl}{C}_j& =C_{j-1}+p_j,j=1,2,\dots ,m\end{array}$$

(19)

$$\begin{array}{rl}{F}_i& \ge C_j-(1-x_{ij})M,i=1,2,\dots ,m;\\ & j=1,2,\dots ,m\end{array}$$

(20)

$$\begin{array}{rl}M{y}_i& \ge F_i-d_i,i=1,2,\dots ,m\end{array}$$

(21)

$$\begin{array}{rl}{x}_{ij},y_i,{\mu }_j& \in \{0,1\},i=1,2,\dots ,m;j=1,2,\dots ,m\end{array}$$

(22)

$$\begin{array}{rl}{p}_j,C_j,F_j,z_{max,j}& \ge 0,j=1,2,\dots ,m\end{array}$$

(23)

Constraint (10) requires each part to be placed in exactly one job $j$ . Constraint (11) bounds the number of parts in a job. Constraint (12) ensures that jobs are only counted as open when they contain parts, and Constraint (13) ensures earlier jobs are opened before later jobs in the sequence. Constraint (14) specifies the maximum height of the parts assigned to each job $j$ , while Constraint (15) ensures that this maximum height does not exceed the height of any part within the job. Constraint (16) limits the total surface area of the parts assigned in each job $j$ to be less than or equal to the available printable surface area $S$ of the AM machine. Constraint (17) determines the processing time of each job $j$ . Constraint (18) sets the starting time of the $1^{\text{st}}$ job in the job sequence at time $0$ . Constraint (19) determines the finish time of the $j^{\text{th}}$ job in the job sequence. Constraints (20) and (21) determine the lateness of part $i$ as a function of the completion time of the associated job $j$ . Constraint (22) defines the binary variables. Constraint (23) defines the non-negative variables.

Constraint (16) limits the total surface area of the parts assigned to a job to be less than or equal to the available printable surface of the AM machine. While this constraint restricts the total surface area of parts that can be nested together, it does not account for their fixed geometries, which may lead to nesting configurations that are infeasible to physically fit within the machine’s build area. Consequently, the objective function value of formulation Q represents a lower bound on the optimal number of late parts for each problem instance, even though the corresponding nesting may be infeasible. In contrast, the NAS algorithm, described in Section 5.2, only generates feasible solutions and therefore yields a number of late parts that is always greater than or equal to this lower bound. In our computational study, we observe that the NAS algorithm achieves results close to the lower bound, indicating its strong performance. This also suggests that the objective values of formulation Q are close to the true optimal values.

5.2. Heuristic for nesting and scheduling

In this section, we develop a heuristic algorithm for AM problems in which nesting is not predetermined before scheduling. In other words, nesting and scheduling decisions are made in an iterative manner, with parts being assigned to jobs simultaneously as the scheduling is carried out. The NAS algorithm is comprised of an outer loop, which determines a “similarity coefficient” between pairs of jobs (refer to Section 5.2.1 for further details) to assess desirable combinations for nesting, and an inner loop which contains the MMH algorithm (refer to Section 4.2 for details) to detect overall performance improvement in scheduling jobs. The step-by-step description can be found in Algorithm 2, while the pseudocode can be found in E-Companion Section EC.3.

This algorithm begins by initializing a set of jobs, $J$ , with each part, $P_i$ , assigned to its own job, $J_j$ , $j=1,2,\dots ,m$ . Every resulting job is then assigned a due date and a maximum height, both of which are taken from its respective parts. In all steps of this algorithm, a job’s due date will always be the minimum due date of the parts within that job $(d_j=\underset{P_i\in J_j}{min}\{d_i\})$ and a job’s height will always be the maximum height of the parts within that job $(z_{max,j}=\underset{P_i\in J_j}{max}\{c_i\})$ . This initial job set now represents a nesting of parts-to-jobs, which can be used in the scheduling-only MMH algorithm (see Section 4.2), to determine the initial number of late parts, $N_{\text{late}}$ .

For each pair of jobs, $J_a$ and $J_b$ in set $J$ , a similarity coefficient, ${\delta }_{ab}$ , is calculated. The details on the calculation and reasoning behind this similarity coefficient are found in Section 5.2.1. The set of similarity coefficients for all pair of jobs $J_a$ and $J_b$ in $J$ is denoted as $S_c$ , where $S_c=\{{\delta }_{ab}\}$ .

The inner loop of the NAS algorithm then runs in the following manner. First, the most similar pair of jobs (minimum ${\delta }_{ab}$ ) is selected, and ${\delta }_{ab}$ is removed from the similarity coefficient set, $S_c$ . In the case of a tie, the similarity coefficient associated with the lowest index job $a$ is selected, followed by the lowest index $b$ . These two jobs are then temporarily merged together, which combines any parts contained within them into a single job, $J_o$ . The first check is job feasibility: by utilizing a two-dimensional bin packer, we check if the parts associated with the merged job fit inside a single print surface. The two-dimensional bin packer in this study is a typical Python package, $rectpack$ , which attempts to fit the parts, “squares,” onto the print surface, “bins,” while allowing for rotation on the $(X,Y)$ -plane in alignment with our shadow-box assumption, detailed in Section 3.1. If this bin packer results in a single bin containing all parts, the temporary job is considered feasible. If the job is not feasible, the pair is rejected, and the inner loop begins again. If the job is feasible, then a temporary job set, $J_{\text{temp}}$ , is created that contains all current jobs and this merged job in place of its two parent jobs. This nesting is then put into the MMH algorithm to determine the number of late parts, $N_{\text{temp}}$ . If the number of late parts in this temporary job set is increased, the pair is rejected, and the inner loop begins again. If the objective function value is the same or improved $(N_{\text{temp}}\le N_{\text{late}})$ , the merged job is accepted. The job set and current number of late parts are then updated $(J_{\text{temp}}\to J,N_{\text{temp}}\to N_{\text{late}})$ . The similarity coefficient set, $S_c$ , is recalculated using the new job set, and the inner loop begins again.

The NAS algorithm terminates when the similarity coefficient set $S_c$ becomes empty, indicating that all remaining job pairings would either result in infeasible jobs or lead to a deterioration in performance. At this point, the current job set and the corresponding number of late parts are reported as the output of the NAS algorithm.

5.2.1. Similarity coefficient

For the NAS algorithm, a “similarity coefficient” is used to identify which job pairs are better candidates for merging. This measure, ${\delta }_{ab}$ , represents the difference between each pair of jobs, calculated based on the normalized difference in their job heights $(x)$ and due dates $(y)$ as a Cartesian distance, that is, ${\delta }_{ab}=\sqrt{(\mathrm{\Delta }x{)}^2+(\mathrm{\Delta }y{)}^2}$ . Each of these individual differences is normalized to their respective ranges, due date  $\sim U(8,72)$ and height  $\sim U(5,50)$ , to maintain balance between the two measures. In general, the closer this measure is to zero, the “more similar” the two associated jobs are in terms of height and due date. Recall that the height of any job, $J_j$ , is the maximum height of all parts currently assigned to the job, $x_j=\underset{P_i\in J_j}{max}\{z_i\}$ , and the due date is the minimum due date of all parts assigned to the job, $y_j=\underset{P_i\in J_j}{min}\{d_i\}$ .

Maximum height is utilized as the first component of job similarity to avoid “waste time” in job processing. During the creation of a single job, no parts may be removed from the build platform until all parts in that job are completed. Consequently, if a specific part is shorter in height than the other parts in that job, it remains idle while the taller parts finish printing. To reduce this idle or “waste” time, we incorporate the height of the job as a similarity measure. This leads to less waiting time for shorter parts. Since the algorithm begins with one part per job assignment, including this height-based similarity measure ensures that height differences are taken into account throughout the algorithm’s execution.

Second, incorporating the due date parameter for each job increases the likelihood that jobs with similar due dates will be merged. This approach aligns with existing heuristics, such as Chergui et al. (2018), where the initial nesting step seeks to minimize the total spread of due dates among parts within jobs. By merging jobs based on due dates, jobs with more parts are formed with synchronized completion times, thereby reducing the likelihood that parts due later in the planning horizon delay parts due earlier based solely on their heights. Unlike Chergui et al. (2018), however, we do not impose a hard restriction that prevents any part from becoming late due to job mergers. While this restriction is logical in early iterations of the algorithm, later iterations often present opportunities where merging two jobs could cause a few early-due parts to become late, and also allow multiple later parts to now be completed on time. In these cases, the overall system would improve despite a few early parts becoming tardy. Because the NAS algorithm measures the overall objective, it allows for these strategic tradeoffs, thereby enhancing the overall effectiveness of the scheduling process.

5.3. Performance of the NAS algorithm

The NAS algorithm for the problem $1|\text{nest}|N_{\text{late}}$ is inherently complex. However, we are able to analyze its performance in the general setting. We begin by deriving the bound for a special case. The insights obtained from the proof of this special case serve as the foundation for extending the result to the general case. Complete proofs of these bounds are presented in Section EC.2.7 of the E-Companion. Although this special case is formulated under additional restrictions, Theorem 6 demonstrates that, even with these constraints, the worst-case bound matches the result established in Theorem 7 for the general case.

Special Case: Here, $m=k+1$ , where $k$ denotes the maximum number of parts that can fit on the AM machine surface area. All parts have identical shapes in the sense that they have identical surface area ( $a\times b$ ) and the same height ( $z_o$ ), thus all parts have identical volumetric print time as defined in Section 3.2. Additionally, due to the same height across all parts, all jobs will have the same maximum height, $z_{max,j}$ , irrespective of part assignment. Here, a job can comprise at most $k$ parts. The following theorem shows that the worst-case bound is $k$ when $m=k+1$ . The performance bound derived for this special case matches that of the general case.

Theorem 6

The performance ratio $R$ of the NAS algorithm for the special case satisfies the following bound when $m=k+1$ :

$$R=\frac{N_h(I)}{N^{*}(I)}\le k,$$

for any problem instance $I$ , where $k$ denotes the maximum number of parts that can fit on the AM machine surface area, and $m$ is the total number of parts. Moreover, this bound is tight.

Remark 3

The intuition behind the proof of Theorem 7 is as follows. The NAS algorithm repeatedly employs the MMH algorithm to evaluate multiple candidate nestings and their corresponding sequences, selecting the one that minimizes the number of late parts. In doing so, the NAS algorithm yields $m$ late parts across all candidate nesting–sequence solutions in the worst case. Consequently, Theorem 7 establishes the same performance bound as Theorem 5 for the MMH algorithm.

Theorem 7

The performance ratio $R$ of the NAS algorithm satisfies the following bound:

$$R=\frac{N_h(I)}{N^{*}(I)}\le m,$$

for any problem instance $I$ , where $m$ is the total number of parts. Moreover, this bound is tight.

Remark 4

It should be noted that the NAS algorithm repeatedly employs the MMH algorithm to evaluate multiple candidate nestings and their sequences, and thereby identify the best nesting and its sequence among them. The bounds established in Theorems 6 and 7, for the special case and the general case, respectively, remain comparable to those obtained in Theorem 5 for the MMH algorithm under fixed nesting. However, our computational study in Section 6 demonstrates that the NAS algorithm significantly outperforms the values suggested by these worst-case bounds for most practically relevant problem instances.

6. Computational analysis

In this section, we first computationally evaluate the performance of the MMH algorithm (described in Section 4.2) when the nesting is fixed. Second, we computationally evaluate the NAS algorithm (described in Section 5.2) for variable nesting. Many problem instances with varying numbers of parts were randomly generated to simulate realistic problem instances in these computational analyses.

6.1. Instance generation

To create each problem instance, we generate a preset number of parts which have known ( $X,Y,Z,d_i$ ) dimensions taken from the following distributions: $(X,Y)\sim \text{Uniform}(5,150)$ , $Z\sim \text{Uniform}(5,50)$ , and due dates, $d_i\sim \text{Uniform}(8,72)$ , where $(X,Y,Z)$ are measured in millimeters and $d_i$ is in hours. These dimension bounds were chosen similarly to past research to allow the parts to potentially take up a significant portion of the print space but still have a 72-hour (3-day) bounded time for due dates, as in Chergui et al. (2018). Additionally, in order to see the impact of nesting, the dimensions of each generated part were restricted to a maximum of 60% of the machine size in any dimension, which is 250 mm as defined in Table EC.1 in the E-Companion Section EC.1. This increased the likelihood that each part would be able to nest with another in a single job.

In order to create a fixed nesting for evaluating the MMH algorithm, the generated parts were nested into jobs using several different rules. The “Earliest Due Date” (EDD) rule sorts all parts via EDD into the minimum number of jobs. For example, 10 parts would have been first ordered by due date, and then assigned in order to Job #1, then Job #2, and so on. Utilizing a two-dimensional binpacker allows us to determine if a part fits within a job based on all parts already assigned to that job. If the binpacker returns a single “bin” after including a new part, that part is assumed to “fit” within the job. If the part is unable to fit in the current job, we consider the job “full” and it is closed. The part then rolls forward to the next job with all remaining unassigned parts. There is no returning to closed jobs, that is, we maintain an EDD order among the part-to-job assignment.

Second, a “First Fit” (FF) rule was implemented where the parts were assigned to the first job in which they fit in the sequence in which they were received from the customers. The idea is to simulate part orders being placed in their natural sequence during the planning horizon, and each part is assigned to the first job in which the part would fit, or a new job would be opened to accommodate the part. This does not take into account the due date of the part and is based solely on the part’s dimensions and available job space in the current jobs. This space utilization-focused method is commonly used in practice, where machine utilization is often a primary focus, and is also found extensively in the literature, such as in Fera et al. (2018) or Altekin and Bukchin (2022).

A third rule was implemented, which combined the features of the EDD rule and FF rule, known here as the “EDD-FF” rule. In this setup, parts were ordered by due date, similar to the EDD rule, and then nested in the first available job, as in the FF rule. This rule allows returning to jobs previously closed if a part did not fit, contrary to the original EDD rule. The key difference from the FF rule is that parts are now nested in a particular order, with earlier due dates having the nesting priority.

Lastly, the “Chergui Rule” is a part-to-job assignment made in a similar fashion to Chergui et al. (2018). An MIP solver was used to assign parts to jobs with the objective of minimizing the sum of the due date ranges of all jobs. In this rule, each job could contain as few as one part or could be completely full. This rule focuses entirely on the due date range and does not take into account similarities in part height or the level of machine utilization in any job.

Our analysis was run over 100 instances, with each instance being a group of new parts with generated dimensions and due dates; these parts were then nested into four distinct job sets using each of the rules described above. In each individual instance, the parts are the same and only the nesting changes. This allows a cross-wise comparison of the performance of each nesting type as well. The number of late parts for each instance-rule combination was then averaged across all instances to compare to the average value of the objective function result from Formulation P. In a fixed nesting setting, the solution to Formulation P is the optimal solution.

6.2. Fixed nesting results

The MMH algorithm (developed in Section 4.2) was tested on a varying number of parts to assess its performance, which is shown in Figure 2. These results include the average of Formulation P’s objective value ( $N_{\text{opt}}$ ), the average number of late parts of MMH algorithm ( $N_{\text{MMH}}$ ), and the average number of late parts of the AMH^* algorithm ( $N_{\text{AMH}}$ ). The results of all four nesting rules are shown. Additionally, the average overall completion time for each of the different nesting rules is shown in Figure 3. While overall completion time is not the primary focus of this paper, it is commonly a large factor in managerial decision-making and is included to see how it is impacted by the nesting rules.

Figure 2.

Fixed nesting results showing the average objective function value to Formulation P (left/blue bar), the average number of late parts for the MMH algorithm (center/yellow bar), and the average number of late parts for the AMH^* algorithm (right/red-striped bar) for each of the four different nesting rules used. In each of these graphs, the number of parts generated in each instance is across the bottom axis. Note. MMH = modified Moore–Hodgson; AMH^* = adapted Moore–Hodgson ${}^{*}$ .

Figure 3.

Average overall completion time for problem instances using the four nesting rules across 100 instances. FF and EDD-FF rules overlap, though they are technically different values. In half of these instances (20, 30, 40, 70, and 100 parts), FF is lower, but the values are always within 12 min of each other. Note. FF = first-fit; EDD = earliest due date.

From these results, we identify several key findings. First, as expected, the objective function value for Formulation P, which is the optimal solution in a fixed nesting problem, increases as the number of parts increases in all the different nesting rules. The rule used also has an impact. We see the lowest average number of late parts for the largest part set (100 parts) in the EDD-FF rule, while the FF rule is 18% higher. The EDD and Chergui rules fall in between at 3% and 10% higher than EDD-FF, respectively. This suggests that a focus on “due date” in the nesting rule can have an impact on the overall number of late parts.

Another driver for the number of late parts is the number of jobs themselves, since more jobs lead to more setup times and thus higher completion times. In the EDD, FF, and EDD-FF rules, the number of jobs is relatively smaller, ranging up to 13 jobs on average, even in the largest of part instances. The Chergui rule is the only rule presented here, which has a forced higher number of jobs, in this case, getting to as many as 21 jobs in the 100- part instances. Due to its nesting based on due date range minimization, the MIP formulation used in the Chergui rule wants to fill as many jobs as possible, leading to jobs with as few as one part in them. The impact of fewer jobs on the number of late parts is not absolute, however, as seen in the difference between the EDD-FF rule and the FF rule. The EDD-FF and FF rules average 40 and 48 late parts, respectively, in their solutions to Formulation P for the 100- part instances, while both averaging 11 jobs. At the same time, the Chergui rule averages over 20 jobs and results in 45 late parts. While both the number of jobs created and the due date focus are important, neither is dominating in all cases. From these results, we confirm that the nesting used to create jobs matters to the overall number of late parts.

The nesting rules play a critical role in shaping the performance of our algorithms, with marked variation observed in the average number of late parts. The EDD nesting rule is the only setup where the AMH^* algorithm outperforms the MMH algorithm. We see the MMH algorithm resulting in up to 25% more late parts than optimal, while the AMH^* algorithm remains within 10% of the optimal. This suggests two advantages to the AMH^* algorithm for the EDD nesting rule. First, since it is an extension of the original Moore–Hodgson algorithm, it performs best when the due date order is maintained in the nesting. Second, because the EDD rule does not allow for returning to “closed jobs,” the MMH algorithm can vary on the quantity of parts “rejected” or moved to the end of the sequence. Jobs with many parts can carry a lower weighted processing time even though they can have more late parts in them because of the weight ratio, which leads to jobs with fewer parts being rejected to the end of the sequence, despite the minimal impact these rejections have on the completion times of the other jobs. This, in turn, leads to poor performance of the MMH algorithm for an EDD nesting.

Given their ability to better fill jobs with parts, the remaining three nesting rules allow the MMH algorithm to outperform the AMH^* algorithm across the part sets. In the case of the Chergui nesting rule, which has a lower average number of late parts in the corresponding optimal solutions than the FF rule, the MMH algorithm produces nearly 10 fewer late parts on average than the AMH^* algorithm in the 100- part instances. In the EDD-FF nesting rule, the MMH algorithm performs close to the optimal objective value and has the lowest overall number of late parts on average for any nesting rule–algorithm combination. This suggests, in a fixed nesting scenario, the EDD-FF nesting rule allows for a lower number of late parts based on its ability to balance the due date arrangement of the parts while also accounting for a better fill of the jobs. Across both algorithms and Formulation P, Figure 2 illustrates that the nesting matters to the number of late parts in the system.

In addition to the number of late parts, which is our primary objective, managers are also commonly concerned with the overall completion time of all parts. While we operate within a 72 hour planning window for this study, an examination of the average overall completion times of our four nesting rules shows there are other tradeoffs to consider. We see in Figure 3, the average overall completion time for the EDD nesting rule is always higher than in the EDD-FF or FF nesting rules. This difference is nearer 5 hours in the 100- part instances, but is still approximately 16 hours faster than the associated Chergui nesting. This reduction in the number of jobs in the EDD, FF, and EDD-FF rules can lead to a reduction in overall completion time, which can reduce overtime for an AM firm and improve part flow.

A key managerial benefit of the MMH algorithm over its MIP counter part is operational speed and ease of use. From a real-world perspective, the MMH algorithm could be used by commercial manufacturers without requiring any optimization packages if the nesting is fixed beforehand, which can save up to $13,500 in starter licensing fees (FrontlineSolvers, 2025). Fixed nesting is more common if certain parts are always printed together, which could occur if there is a post-processing driver, such as the decomposed subcomponent assembly problem found in Oh et al. (2018a), or if complex support structures need to be used during printing. The MMH algorithm demonstrated here also runs in $<2\text{s}$ , even in instances containing 100 parts. If a sales rep is on the phone with a customer and needs a quote quickly, the MMH algorithm can be run within seconds every time.

While this is incredibly fast, the associated MIP model, Formulation P, also runs quickly, taking $<1\text{min}$ on average in instances containing 80 parts or less. In the 90 or 100- part instances, the average computation time of the MIP model increases to nearly 5 min, while the actual computation times ranged from 15 seconds to over 6 hours. For longer-term production planning, either the algorithm or an optimization model, such as Formulation P, could be run effectively.

Recall that the variable nesting algorithm (the NAS algorithm) has the potential to evaluate several hundred schedules for any single instance, as discussed in Section 4.1. Because of this, the potential for Formulation P to take hours to address a single schedule instance is problematic, and the MMH algorithm is necessary to facilitate the NAS algorithm’s speed and efficacy.

6.3. Variable nesting results

The NAS algorithm (described in Section 5.2) was tested on a varying number of parts to assess its performance against the variable nesting MIP model, formulation Q, as summarized in Figure 4. Since nesting is included in this algorithm, only the parts generation step, detailed at the beginning of Section 6.1, is used. As a result, an individual instance could result in any number of jobs up to the number of parts. In Figure 4, we report the average number of late parts from both the objective function value of formulation Q and the NAS algorithm.

Figure 4.

Variable nesting results showing the average number of late parts for the objective function value of formulation Q and the NAS algorithm. Each part set size was run to 100 instances. For the 60 problem instances, the average objective function value of formulation Q is greater because we are using a time-restricted model. Note. NAS = nesting and scheduling.

The NAS algorithm presented in this paper runs in $<5\text{s}$ for any instance across all part quantities tested. In comparison, the average computation time for formulation Q could range from $<1\text{min}$ up to several hours for large problem instances when it is able to reach a solution. In order to avoid extensive computation time, a 1 hour time limit was placed on formulation Q for every instance in this analysis. When this time limit is relaxed to 6 hours, the average objective function value for formulation Q drops by $<1$ late part per instance, but nearly every instance runs the full 6 hours in instances containing 60 parts or more.

Figure 4 illustrates that the NAS algorithm averages $<3$ late parts across all instances up to 40 parts, while the objective function value of formulation Q is $<1$ late part on average. As the total number of parts in the instances increases, both the formulation Q and NAS averages increase in a similar fashion up to 32.3 and 35.1 parts in the 100 part instances, respectively, and the difference between these averages is $<7\mathrm{\%}$ of the total number of parts at most. Given that the solution of formulation Q is not always guaranteed to be feasible, as noted in Section 5.2, and can take quite a bit more computation time, this suggests that the NAS algorithm is an effective tool for nesting and scheduling parts-into-jobs within an AM environment.

Figure 5 shows the overall completion times for the Variable Nesting problem instances. In this analysis, the average overall completion time of the NAS algorithm is always lower than the relative output of formulation Q. In the variable nesting environment, the operational time savings between formulation Q’s output and the NAS algorithm can be large, greater than a full day, starting as early as 50 part instances and reaching three full days in the 100 part instances. With an original planning period of only 72 hours in this analysis, the potential for saving a full day or more of operational time is an important managerial benefit of the NAS algorithm.

Figure 5.

Average overall completion time for various problem instances using both formulation Q and the NAS algorithm. Note. NAS = nesting and scheduling.

When comparing the NAS algorithm and formulation Q results, it is apparent that formulation Q utilizes a much larger operational window in minimizing the number of late parts. In order to test how formulation Q would handle a reduced window, further analyses were done on the same part sets to see if formulation Q could generate solutions within the same operational window as the NAS algorithm. This resulted in a new version of the MIP, known as Formulation $Q^{*}$ , with additional completion time constraints based on the completion time of the NAS algorithm. Formulation $Q^{*}$ was able to generate solutions that keep a similar number of late parts as the NAS algorithm, but suffered from far more infeasible solutions and lengthy computation times. These results are discussed in detail in E-companion Section EC.4.

As a reminder, because the nesting is now variable in the system, formulation Q’s solution may not always be feasible due to incompatible fixed geometries of the parts. However, the NAS algorithm can only produce feasible solutions. Therefore, the binpacker procedure utilized in the NAS algorithm was run on each formulation Q output in order to determine how many jobs in each instance were feasible based on their assigned part nesting. In all instances of 90 parts or lower, at least 60% of the instances were feasible, with an average “job feasibility” of at least 90% in each instance except for the 20 part instances, which drop to about 79% job feasibility. For example, the 90 part instances have 39 jobs, on average, in their formulation Q solution, which means with an average job feasibility of 92%, approximately 3 of the 39 jobs are infeasible. In the 100 part instances, the number of feasible instances drops to 44%, and yet the average job feasibility across all instances increases to 98%. Even if it is not feasible, the solution to formulation Q is still the lower bound and represents an effective benchmark to compare the output of the NAS algorithm. This is discussed further in Section 5.1.

We also determined additional managerial insights into how parts can be added to an existing production schedule. From the NAS algorithm, we find that the overall impact of adding parts is minimized by finding a job that both (a) has the two-dimensional space for the part, and (b) has a job height greater than the height of the new part. By following these two guidelines, the impact of adding the part is a simple, direct addition of the part’s volumetric print time (typically, relatively small) to the processing time of that job. As long as the job height limitation is not violated, there is no need to calculate any change to the cooling time or setup times of any job, as they are not impacted. Thus, as long as that job and subsequent jobs have due dates with slack time of more than the small additional volumetric print time, no additional parts will be late. If a suitable space in a job cannot be found, then these new parts would need to be considered a “rush part,” which would typically be run on a dedicated machine for a price premium.

7. Conclusions

This paper tackles the fundamental and practically relevant problem of jointly nesting and scheduling parts in a single-machine AM environment. We rigorously prove that minimizing the number of late parts in this setting is strongly NP-hard, even when the nesting of parts into jobs is fixed. To the best of our knowledge, this is the first formal complexity result for this class of problems, underscoring the inherent computational challenges of integrated nesting and scheduling in AM systems.

Building on this theoretical foundation, we introduce a hierarchy of efficient heuristic algorithms for fixed nesting. We first propose two simple yet effective algorithms, AMH and AMH2, and establish performance bounds for both. We then develop the AMH^* algorithm, which executes both AMH and AMH2 algorithms, and selects the sequence corresponding to the best objective function value between the two sequences. The general case performance bound of the AMH^* algorithm is also derived. Leveraging these insights, we design a more complex MMH algorithm, which yields improved schedules for minimizing late parts when compared with optimal MIP solutions and the AMH^* algorithm for fixed nestings obtained by various nesting rules. We also derive the performance bound for the MMH algorithm for the general case.

To address scenarios where nesting is variable (i.e., not fixed), we propose the NAS algorithm, which simultaneously determines both part-to-job nestings and their corresponding schedules. This represents a key advancement over prior research that treats nesting as a static, independent step. By integrating these two critical decisions, the NAS algorithm enables faster, more adaptive, and more efficient scheduling.

Our results show that if the nesting is fixed, the EDD-FF rule carries a lower overall completion time while having a low number of late parts on average for all algorithms developed. If an EDD order needs to be maintained in the fixed nesting, however, the AMH^* algorithm also carries a low completion time and number of late parts. For variable nesting, the NAS algorithm developed in this paper is able to obtain a feasible combined nesting and scheduling solution and averages <7% more late parts than the respective MIP solution across challenging problem instances. Moreover, the NAS algorithm outperforms all fixed nesting rules and algorithm combination scenarios. Additionally, when evaluating against the overall completion time, the NAS algorithm results in part-into-job nestings with significant operational time savings. These algorithms will serve as the foundation for the growing field of AM research focused on increasing operational efficiency and enhancing commercial applicability.

Future research can build on these contributions in two main directions. First, validating the proposed algorithms on real-world part data will allow for more accurate processing time estimation and capture machine-specific dynamics such as print speed and cooling time. Second, since parallel machine operations are common in AM environments (Chergui et al., 2018), extending the NAS algorithm to parallel machine settings represents a natural next step toward greater scalability and generalizability.

In summary, this paper makes three major contributions: it establishes the computational complexity of a core AM scheduling problem, develops a suite of efficient implementable algorithms, including the NAS algorithm, and introduces a powerful nesting–scheduling integration framework offering a foundation for more responsive, scalable, and production-ready AM systems. These contributions lay the groundwork for advancing both the theory and practice of scheduling in AM and support the broader goal of achieving higher operational efficiency and commercial viability.

Supplemental Material

sj-pdf-1-pao-10.1177_10591478261442695 - Supplemental material for Scheduling additive manufacturing systems: Complexity and algorithms to minimize the number of late parts

Supplemental material, sj-pdf-1-pao-10.1177_10591478261442695 for Scheduling additive manufacturing systems: Complexity and algorithms to minimize the number of late parts by Michael D Stott, Chelliah Sriskandarajah and Jon M Stauffer in Production and Operations Management