Optimization of Production Scheduling for the Additive Manufacturing of Ship Models Using a Hybrid Method

Abstract

This paper introduces a hybrid optimization method that leverages either linear programming (LP) or a genetic algorithm (GA) based on the problem size to enhance the parallel additive manufacturing (AM) process for ship models. The LP ensures optimality but can experience exponential increases in the computation time as the problem size grows. To address this limitation, the GA is employed for larger problems, providing optimal solutions within reasonable quality and time constraints. The method optimizes the module allocation to AM machines and determines the build processing sequence for each machine, while also considering the availability of workers preparing for consecutive module production. Applied to a case study, the proposed method achieves a 14% reduction in the completion time compared to a heuristic method from a previous study. Furthermore, the method is validated by benchmarking against the heuristic method across various problem sizes, consistently demonstrating superior performance.

1. Introduction

Although computational fluid dynamics (CFD) has demonstrated high accuracy in evaluating the hydrodynamic performance of ships, ship model testing remains essential due to physical environmental challenges that are difficult to address with CFD, such as turbulence modeling, grid resolution, and numerical approximation. With the recent emergence of low-emission ships, hull shapes are becoming more diverse to accommodate additional elements for different power systems, such as increased battery sizes. This diversification leads to an increased demand for model tests. However, research on the optimization and efficiency of manufacturing costs related to ship models is insufficient.

Conventional ship model manufacturing methods include the use of fiber-reinforced plastics (FRPs) and wood. FRP, a glass fiber-reinforced plastic, is favored for its high corrosion resistance, lightweight properties, and durability, making it well suited for model construction [1]. However, FRP has significant drawbacks: it is flammable and releases toxic gases upon disposal. Moreover, its production and disposal processes contribute to environmental pollution. The quality of the final product is highly dependent on the skill level of the worker, as the hand layup technique is commonly employed [2].

The technique of using computer numerical control (CNC) machines to cut wood for model fabrication has been a reliable and precise method in the industry for a long time. CNC machines are also sometimes used in the production of FRP models, offering faster production times and reduced labor compared to manual methods since the machine can execute tasks based on the provided input model. However, the high initial costs and space requirements for large cutting equipment can be a barrier for small businesses or individuals [3].

The recent accessibility of additive manufacturing or 3D printing technologies has significantly accelerated its growth [4]. This technique fabricates 3D models by layering and bonding materials such as metals, plastics, powders, and liquids. Unlike traditional casting or machining, which require skilled labor, 3D printing allows anyone to manufacture products. Its widespread use in various industries [5,6,7,8,9,10] is due to its capacity for freeform design and quick adaptation to design changes, which shortens production times. Choi et al. [3] introduced a modular AM approach for producing ship models. They chose a modular method due to the high initial costs and size limitations of 3D printers, which can hinder the production of certain models. While integrated methods can simplify the process by printing models as a single piece, modularity provides a more practical solution under these constraints.

The modular nature allows ship models to be produced in parallel across multiple machines, significantly reducing the production time through simultaneous manufacturing. However, this approach increases the importance of production scheduling, as scheduling decisions can greatly impact the overall production time. By strategically allocating resources such as 3D printers, materials, and manpower, production supervisors can maximize productivity and throughput while minimizing costs and idle time.

There has been research on scheduling optimization in AM. For example, Chergui et al. [11] addressed the parallel production scheduling problem in AM, and Choi et al. [3] employed a heuristic for scheduling the production of modular ship models, determining the module allocation and making sequencing decisions simultaneously. However, previous studies did not consider the availability of the workers needed to prepare for the next production task upon completion of a module. This factor adds complexity to the optimization of production scheduling for modular ship models.

In this study, we propose an optimization method for the efficient production scheduling of ship models in AM. Our method aims to minimize the production time of the final module by optimizing the module allocation and sequencing while considering worker availability. To achieve this, we employ a hybrid approach that combines linear programming (LP) and a genetic algorithm (GA), selectively using either LP or GA based on the number of modules being produced to leverage the strengths of both techniques. To validate the efficacy of our approach, we compare the proposed method with a heuristic approach through case studies.

2. Scheduling Challenges in Additive Manufacturing with Consideration of Workers’ Availability

Traditionally, scheduling was not a primary concern in the monolithic AM process, where entire objects were typically produced as single prints. However, efforts to enhance the efficiency of AM have spurred exploration of various strategies. This includes dividing oversized products exceeding the capacity of AM, or employing multiple machines to increase the production volume [12], leading to the emergence of configurations like 3D printing farms. With the advent of modular AM, where small modules are produced using multiple AM machines and assembled to create larger products, scheduling has become a crucial consideration for optimizing the production process. Scheduling, a significant aspect of traditional manufacturing processes, is increasingly gaining importance in AM as it evolves toward formats resembling 3D printing farms. With the emergence of modular AM production, where small modules are produced using multiple AM machines and then assembled to create larger products, scheduling has become an important consideration for optimizing the production process. Li et al. [13] addressed the production planning problem in AM using a parallel production approach that assigns multiple parts to groups and allocates them to machines. Ransikarbum et al. [14] used a mixed integer linear programming method to optimize the allocation of modules to machines for multipurpose optimization. Dvorak et al. [15] explained and modeled the key optimization problem of minimizing the production time using layered manufacturing, operational research, and artificial intelligence. A mathematical approach was proposed for scheduling the build and post-processing processes for decomposed parts in layered manufacturing [16].

In addition to these AM-specific studies, broader operational research (OR) techniques offer valuable insights for scheduling in modular AM processes. Our work is similar to the blocking job shop scheduling problem (BJSSP), which addresses scheduling delays caused by resource constraints, particularly when tasks are blocked from proceeding to the next stage due to limited machine capacity. Relevant studies include [17,18,19]. These studies explore the complexities of blocking effects, which are also present in modular AM when machines become bottlenecks.

Furthermore, recent advancements in hybrid algorithms, such as the hybrid differential evolution (HDE) algorithm [20], have been proposed to handle resource-constrained project scheduling with flexible project structures. The combination of differential evolution and forward–backward improvement demonstrates strong potential for managing complex scheduling problems in resource-limited environments. Similarly, the adaptive large neighborhood search with constraint programming (ALNS-CP) algorithm was proposed for flexible job shop scheduling [21], which provides an efficient approach to address multiple resource constraints in production planning. An improved evolutionary algorithm for parallel batch processing machine scheduling was introduced [22], which combines GAs with heuristic placement strategies to optimize both part allocation and placement in AM systems. Rohaninejad et al. [23] also developed a hybrid learning-based meta-heuristic algorithm for the scheduling of an AM system consisting of parallel SLM machines, combining NSGA-II with k-means clustering and a regression neural network to enhance the scheduling efficiency. These methods can be particularly useful in modular AM, where tasks must be efficiently scheduled across multiple machines with varying capabilities.

Lastly, as the importance of production planning for AM has grown, it has become important to accurately predict the production time for 3D printing. To address this problem, machine learning-based predictions have been developed to facilitate efficient production planning [24,25].

In this paper, the objective of scheduling optimization is to minimize the total production time, known as the makespan, by simultaneously making module assignment and sequencing decisions. Figure 1 illustrates the optimization problem.

In defining the mathematical model, we make the following assumptions: (1) the required production time for each module is known, (2) multiple identical machines are used, (3) the production setup time is uniform, and (4) each machine can produce only one module at a time. Based on these assumptions, the model is constructed, incorporating flexible production start times and task time limits.

Let us consider an example problem involving two AM machines and four modules, each with different production times, as shown in

Table 1. Required build time of modules.

Module Index	1	2	3	4
Time (minute)	500	700	800	900

. When these modules are assigned to the two machines, various schedules can be created depending on the allocation and sequencing of these modules, as illustrated in Figure 2. The numbers on the bar graph represent each module number and the red dotted line represents the production completion time. As shown in Figure 2a, the Gantt chart illustrates an example where modules 1 and 3 are produced sequentially on printer 1, while modules 2 and 4 are produced sequentially on printer 2. Similarly, Figure 2b–d depict Gantt charts representing different cases of module assignments and production sequences on the printers. These examples demonstrate how the total production time varies depending on the assignment and production sequence of the modules.

However, the previous examples did not consider workers’ available time. Figure 3 shows workers’ available time, divided into start and finish times. The production start time for each module must fit within these divisions. Figure 4a–d show the revised schedules adjusted for workers’ availability based on the initial schedules shown in Figure 2a–d.

The adjusted completion times in Figure 4 reveal an interesting result. Despite identical module assignments and sequencing decisions, the completion times differ significantly. While Figure 2d initially shows the shortest production time without considering workers’ availability, Figure 4a becomes the shortest when accounting for workers’ available time. This demonstrates that the makespan can vary significantly when solutions derived without considering workers’ availability are implemented in real-world scenarios.

3. Hybrid Method for Parallel Production Scheduling for Additive Manufacturing

3.1. Mathematic Definition Using Linear Programming

To solve the module assignment and sequencing problem, we propose a network-based model commonly used in scheduling problems, as seen in works like Choi [26]. This model comprises nodes and arcs, as illustrated in Figure 5. In this context, each network corresponds to a machine, with nodes representing modules and arcs indicating the production sequence. The source node signifies the starting point of production, and the sink node represents the endpoint. Other nodes represent modules. Each module must be processed exactly once and cannot revisit the same node. An arc originating from the source node and connecting to a module node indicates the commencement of production for that module. Conversely, an arc leading from a module node to the sink node signifies the completion of production of the machine. Additionally, the sets ${\mathit{A}}_{\mathit{p}\mathit{o}}$, ${\mathit{A}}_{\mathit{p}\mathit{i}}$, ${\mathit{A}}_{\mathit{d}\mathit{h}}$ are all subsets of set $\mathit{A}$, in which ${\mathit{A}}_{\mathit{p}\mathit{o}}$ represents the arcs going out from the source node to module nodes, ${\mathit{A}}_{\mathit{p}\mathit{i}}$ represents the arcs going into the sink node from the module nodes, and ${\mathit{A}}_{\mathit{d}\mathit{h}}$ represents the arcs between the modules.

We mathematically describe the optimization problem using the following sets, parameters, and variables.

Sets:

N	Nodes, indexed by $i \mathrm{or} j$
J	Nodes associated with modules, indexed by $i or j$
R	AM machines, indexed by $k$
A	Arcs, indexed by $\left(i,j\right)$
${\mathit{A}}_{\mathit{p}\mathit{o}}$	Pull-out arcs, indexed by $\left(i,j\right)$
${\mathit{A}}_{\mathit{p}\mathit{i}}$	Pull-in arcs, indexed by $\left(i,j\right)$
${\mathit{A}}_{\mathit{d}\mathit{h}}$	Deadhead arcs, indexed by $\left(i,j\right)$
$\mathit{D}$	Divisions, indexed by $d$

Parameters:

$T_i^{BUILD}$	The production time of module $i$
$T_d^{ST}$	Start time of division $d$
$T_d^{FN}$	Finish time of division $d$
$M$	The big number

Variables:

$x_{ijk}$	1 if arc $\left(i,j\right)$ of AM machine $k$ is selected, 0 otherwise
$y_{id}$	1 if division $d$ selected by module $i$, 0 otherwise
$u_i$	Production start time of module $i$
$z$	The latest completion time among the AM machines

Model:

$$\mathrm{Minimize}z$$

(1)

$$\mathrm{s}.\mathrm{t}.{\displaystyle \sum }_{k\in \mathit{R}}{\displaystyle \sum }_{\left(i,j\right)\in {\mathit{A}}_{\mathit{p}\mathit{o}}{\displaystyle \cup }{\mathit{A}}_{\mathit{d}\mathit{h}}}{x}_{ijk}=1\mathit{j}\in \mathit{J}$$

(2)

$${\displaystyle \sum }_{\left(i,j\right)\in {\mathit{A}}_{\mathit{p}\mathit{o}}}{x}_{ijk}={\displaystyle \sum }_{\left(i,j\right)\in {\mathit{A}}_{\mathit{p}\mathit{i}}}{x}_{ijk}k\in \mathit{R}$$

(3)

$${\displaystyle \sum }_{\left(i,j\right)\in {\mathit{A}}_{\mathit{p}\mathit{o}}}{x}_{ijk}\le 1k\in \mathit{R}$$

(4)

$${\displaystyle \sum }_{\left(i,j\right)\in {\mathit{A}}_{\mathit{p}\mathit{o}}{\displaystyle \cup }{\mathit{A}}_{\mathit{d}\mathit{h}}}{x}_{ijk}={\displaystyle \sum }_{\left(i,j\right)\in {\mathit{A}}_{\mathit{p}\mathit{i}}{\displaystyle \cup }{\mathit{A}}_{\mathit{d}\mathit{h}}}{x}_{jik}j\in \mathit{J},k\in \mathit{R}$$

(5)

$${\displaystyle \sum }_{\left(i,j\right)\in {\mathit{A}}_{\mathit{d}\mathit{h}}}{x}_{ijk}\le M{\displaystyle \sum }_{\left(i,j\right)\in {\mathit{A}}_{\mathit{p}\mathit{o}}}{x}_{ijk}k\in \mathit{R}$$

(6)

$$u_i+T_i^{BUILD}\le zi \in \mathit{J}$$

(7)

$$u_i+T_i^{BUILD}\le u_j+M\left(1-x_{ijk}\right)\left(i,j\right)\in \mathit{A}, k\in \mathit{R}$$

(8)

$${\displaystyle \sum }_{d\in \mathit{D}}{y}_{id}=1i\in \mathit{J}$$

(9)

$${\displaystyle \sum }_{d\in \mathit{D}}{T}_d^{ST}{y}_{id}\le u_i\le {\displaystyle \sum }_{d\in \mathit{D}}{T}_d^{FN}{y}_{id}i\in \mathit{J}$$

(10)

$$x_{ijk}\in \left\{0,1\right\}\left(i,j\right)\in \mathit{A}, k\in \mathit{R}$$

(11)

$$0\le u_{i}i \in \mathit{N}$$

(12)

Equation (1) is the objective function of this model, which aims to minimize the module $z$ that is produced the latest. Equations (2)–(12) represent the production constraints of multiple AM machines using a network model. Equation (2) indicates that each module must be produced once, ensuring that all the modules are produced. Equations (3)–(6) represent network flow conservation constraints. Equation (3) states that the number of arcs entering the sink node should be equal to the number of arcs leaving the source node. Equation (4) represents a constraint in which each machine should have only one arc from the source node to a different node. Equation (5) indicates that the number of arcs assigned to the source and module nodes is equal to the number of arcs assigned to the sink module node. Equation (6) is a constraint that mandates the existence of an arc leading to the sink node if there is an arc between the modules in each machine. Equation (7) sets the start time of each module as $u_i$ and defines z as the sum of the production time and the module that takes the latest time to produce. Equation (8) is a constraint that requires the production start time of module $j$ to be after the production start time of the previous module $i$. Constraints (9) and (10) are defined to limit the working times. In this model, the concept of segments has been introduced. The available and unavailable working times are also segmented, and the production start time of each module must be within the feasible time division. Equation (9) is a constraint that requires each module to belong to one of the divisions, and Equation (10) is a constraint that requires the production start time of each module to be within the specified division range. Equations (11) and (12) represent constraints on the range of variables.

3.2. Hybrid Method to Overcome the Size Limitations of Linear Programming

LP offers the advantage of mathematically proving the optimality of solutions and providing quick results, making it a powerful tool for optimization problems. However, the optimization time for LP increases exponentially as the problem size grows. To address this limitation, we adopted a GA as an alternative method for scenarios where the number of modules exceeds what LP can handle in a reasonable time. GAs are well known for their effectiveness in finding solutions for complex problems with various constraints due to their adaptability. However, despite their global search capabilities, GAs often require relatively long processing times for simpler problems and can become stuck in local optima.

To leverage the strengths of both LP and GAs, we employ a hybrid method. The LP is used for problems when the problem size is below a certain threshold, and the GA is used when the problem size exceeds this threshold. We conducted experiments to determine the appropriate threshold number, investigating the computation times as the problem size increased. As shown in Figure 6a, the experimental results indicate that when the number of modules is 14, the computation is completed in approximately 1 s. However, when the number of modules increases to 15, the computation time sharply rises to around 1500 s. This significant increase is due to the rapid growth in computational complexity as the number of modules increases. Therefore, we set 15 modules as the threshold value. Based on this threshold, LP is applied to problems with fewer than 15 modules, while the GA optimization method, as illustrated in Figure 6b, is employed for problems with 15 or more modules.

It is crucial to represent the solutions effectively, which is determined by the chromosome structure in the GA. Figure 7 illustrates the chromosome structure used in the GA. Each gene represents a module, containing information about the machine assigned to build the module and its production priority on that machine. The priority is a value between 0 and 1.

The chromosome representation scheme shown in Figure 7 illustrates how each gene corresponds to a specific module. Each gene contains information about the machine to which the module is assigned and the production priority of that module on the machine. After grouping the modules by their assigned machine, the priority values of the modules are compared within each group. Modules with lower priority values are produced first. This process is repeated across all the machines to determine the final allocation and production order. During the initial population generation, gene values are assigned randomly, which may result in imbalances, such as some machines being overloaded with modules while others have none. These initial schedules are then adjusted to consider workers’ available time for starting production tasks. Figure 7 and Figure 8 illustrate this schedule conversion. Figure 8a shows the allocation of modules to machines and their arrangement by priority without considering worker’s available time. Figure 8b illustrates the adjusted schedule that accounts for worker’s available time.

The GA employs a one-point crossover strategy, where the cutting point can occur anywhere along the chromosome. Figure 9 illustrates an example of one-point crossover, with the cutting point located in the middle of the parent chromosomes.

During mutation, the GA randomly determines the number of genes to be altered and selects those genes accordingly. The selected genes are then replaced with randomly generated genes. This process helps in achieving global optimization. The overall flow of the GA is depicted in Figure 10.

4. Case Study

In the case study, we selected the ship model from the previous study by Choi et al. [3] and applied our proposed method to its production. The ship’s dimensions, including the length overall (L.O.A), length between perpendiculars (L.B.P), breadth (B), depth (D), and draft (T), are provided in

Table 2. Detailed specifications of the ship model [3].

Subject	Ship	Model (Scale Ratio, λ = 10)
L.O.A [m]	17.6	1.760
L.B.P [m]	12.32	1.232
B [m]	3.98	0.398
D [m]	0.95	0.095
T [m]	0.66	0.066

.

The authors removed the ship’s interior and divided the ship into 32 modules to fit six identical AM machines with a maximum size of 300 × 250 × 250 mm, as shown in Figure 11.

The production time for each module is specified in

Table 3. Production time required for each module.

Module Index	Time (min)	Module Index	Time (min)
1, 17	1483	9, 25	1534
2, 18	1711	10, 26	1179
3, 19	1038	11, 27	1408
4, 20	1064	12, 28	1922
5, 21	1510	13, 29	2209
6, 22	873	14, 30	2613
7, 23	1575	15, 31	756
8, 24	745	16, 32	756

. To account for potential uncertainties in production, such as variations in the operating conditions and machine performance, an additional 5% buffer time allowance has been included for each module. Each module must be assigned to one of the six AM machines for production, and each module is produced once. [3] used a heuristic method for the production scheduling problem of the modular ship model. The heuristic method assigned the modules using the module index to the available machines in order. Using this heuristic approach, the makespan was 9813 min.

To validate the performance of the proposed method, we applied it to the same scheduling problem. Given that the ship model comprises 32 modules, exceeding the threshold of 15, the hybrid method utilized the GA. The optimization algorithms were executed on a CPU with an Intel(R) Core(TM) i7-13700HX processor operating at 3.70 GHz and 16.0 GB of memory. The GA hyperparameters were configured as follows: the population size was 50, with 7 elite individuals retained from the top-performing solutions of the previous generation, 27 individuals generated through crossover, and 16 individuals generated through mutation. The termination criterion for the GA was set to halt reproduction after generating 3000 solutions. The convergence curve for each generation is shown in Figure 12.

Due to the stochastic nature of the GA, the results can vary with each run. Empirically, repeating the GA 10 times yielded the best solution. Each iteration took an average of 27 s, depending on the number of modules. This demonstrated that the scheduling results could be obtained in a sufficiently short time. Additionally, by running the GA multiple times, the best, worst, and average results were recorded. The makespan through the GA was 8481 min for the best result, 9396 min for the worst result, and 8974.1 min on average. Compared to the heuristic approach, this shows a maximum difference of 1332 min, or approximately 13.58%. The comparison of the scheduling results is described alongside a Gantt chart in Figure 13.

We also applied the proposed method to a different problem, where the same ship model was divided into larger modules, assuming different numbers of machines and build capabilities. Under these new assumptions, the ship model was divided into 12 modules to be assigned to three machines.

Table 4. Module production times.

Module Index	1	2	3	4	5	6	7	8	9	10	11	12
Time (minutes)	1483	1711	1711	1038	1064	1064	1510	1510	873	1575	1575	745

presents the production times for each module.

For this problem, the hybrid method used LP instead of the GA because the number of modules was below the threshold. The optimal schedule derived by the hybrid method is presented in Figure 14. Using LP ensured the optimality of the solution, and the optimization process took only 0.2 s, highlighting the efficiency of LP for problem sizes under the threshold for AM processes.

In comparison, the makespan derived by the heuristic method was 5965 min, whereas the proposed method yielded a makespan of 5358 min. This reduction of 607 min (approximately 10.02%) demonstrates the effectiveness of the proposed method in optimizing the production schedule, both in terms of the computation time and the solution quality.

5. Conclusions

This paper presented a hybrid method that employs either linear programming (LP) or a genetic algorithm (GA) to tackle the parallel production scheduling problem in additive manufacturing (AM) for modularized ship models, taking into account workers’ available time. While some may view the scheduling of ship model production as non-critical, ineffective scheduling can lead to significant wasted time. For manufacturers operating 3D printing farms and producing multiple ship models for various customers, the proposed method is particularly powerful because it can determine the optimal schedule under conditions involving numerous printers and modules. This research provides a solid foundation for further exploration and development.

The case study demonstrated the proposed method’s effectiveness by applying it to a ship model from earlier research [3]. The new method significantly reduced the makespan when compared to the heuristic approach. In a scenario involving 32 modules, the GA-derived schedule achieved the best makespan of 8481 min, a substantial improvement over the heuristic method’s 9813 min. Furthermore, when the ship model was divided into 12 larger modules and assigned to three machines, the hybrid method using LP resulted in a makespan of 5358 min, compared to 5965 min with the heuristic method. This reduction of 607 min (approximately 10.02%) underscores the method’s ability to optimize production schedules effectively, both in terms of the computation time and the solution quality.

However, there is room for improvement. In this paper, we assumed fixed production times and no failures. In practice, the estimated production time of modules can be uncertain, and this uncertainty can vary depending on the operating software for the 3D printers. To determine more robust solutions, the model needs to account for uncertainties caused by estimation errors and potential production failures. In particular, addressing the variability in production times is a crucial area for future research, as real-world manufacturing conditions often involve fluctuations due to machine performance and operational factors. Incorporating this variability would significantly enhance the applicability and robustness of the proposed scheduling method.

Moreover, this study did not consider potential scheduling conflicts due to pre-existing tasks or maintenance schedules. In industrial settings, machines are often shared between multiple tasks or undergo maintenance, leading to scheduling challenges. Future research should incorporate these factors to further improve the real-world relevance and applicability of the proposed method.

Additionally, we assumed the homogeneous build capabilities of 3D printers and no production failures or pre-existing tasks. However, in real-world scenarios, companies often operate a variety of 3D printers with different capacities and may encounter unexpected failures or have ongoing commitments that need to be managed. This diversity in machine capabilities, along with the possibility of failures and varying availability, must be considered to create a truly effective scheduling method. Future research will address these factors to improve the robustness and real-world applicability of the proposed model. While the proposed method has shown potential in controlled experimental settings, further validation in real-world manufacturing environments is necessary. Testing the model in diverse industrial settings will help assess its robustness and applicability under practical conditions, where machine variability, production failures, and operational constraints are prevalent. Such testing will ensure that the model can deliver optimized scheduling solutions in real-world scenarios.

Lastly, an optimized solution can be achieved when the scheduling problem is handled together with the module division problem. The scheduling results are highly dependent on the module division decisions. Therefore, future research should integrate these two consecutive problems into a single, unified problem to improve the overall efficiency and effectiveness.