# Scheduling of Parallel 3D-Printing Machines with Incompatible Job Families: A Matheuristic Algorithm

Mohammad Rohaninejad, Zdeněk Hanzálek, Reza Tavakkoli-Moghaddam

► To cite this version:

Mohammad Rohaninejad, Zdeněk Hanzálek, Reza Tavakkoli-Moghaddam. Scheduling of Parallel 3D-Printing Machines with Incompatible Job Families: A Matheuristic Algorithm. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2021, Nantes, France. pp.51-61, 10.1007/978-3-030-85874-2_6. hal-04030388

HAL Id: hal-04030388

https://inria.hal.science/hal-04030388

Submitted on 15 Mar 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
# Scheduling of parallel 3D-printing machines with incompatible job families: A Matheuristic algorithm

Mohammad Rohaninejad¹[0000-0002-0623-4890],
Zdeněk Hanzálek¹[0000-0002-8135-1296], and
Reza Tavakkoli-Moghaddam²[0000-0002-6757-926X]

¹ Industrial Informatics Department, Czech Institute of Informatics Robotics and Cybernetics, Czech Technical University in Prague, Prague, Czech Republic
Mohammad.Rohani.Nezhad@cvut.cz

² School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran

**Abstract.** Additive manufacturing (AM) is a promising technology for the rapid prototyping and production of highly customized products. The scheduling of AM machines has an essential role in increasing profitability and has recently received a great deal of attention. This paper investigates the scheduling of batch processing of parallel 3d-printing machines to minimize the total weighted tardiness. Accordingly, a mathematical model is proposed to formulate the problem considering the sequence-dependent setup time and incompatible job families, where jobs of different families are processed with different materials and desired quality. Due to the high complexity of the problem, an efficient matheuristic algorithm is presented based on the hybridization of a genetic algorithm and a local search method based on mixed integer programming (MIP). Computational results show that the proposed approach is efficient and promising to solve the problem.

**Keywords:** Additive manufacturing · Batch processing · Scheduling · Matheuristic.

## 1 Introduction and Literature Review

Additive manufacturing (AM) that also called 3D-printing is a remarkable technology in the context of industry 4.0, which is rapidly developing smart manufacturing systems. various 3D-printing machine types are developed and applied in prototyping, production, and biomedicine [1]. In terms of industrial production, manufacturing companies are employing 3D-printing technology for facilitating the fabrication of highly customized, and lighter weight products. Powder-based, liquid-based, and solid or wire extrusion techniques are the main processing technologies applied in 3D-printing machines [2] that produce parts by depositing material layer upon layer according to a predesigned computer pattern.
This research focuses on the scheduling of a special kind of powder-based 3D-
printing machine known as Selective Laser Melting (SLM) machine. We consider
several independent machines working in parallel. In the SLM machine, the laser
beam hits the metal powder and welds its particles together. Then, a new layer
of metal powder is added and this process continues until the final product is
reached. In the current study, the scheduling of parallel SLM machines consists of
batching a variety of parts with incompatible job families and then determining
the allocation and sequencing of the formed batches in such a way that the total
cost of tardiness is minimized ($\mathbf{P}_m|batch, incompatible|\sum w_j T_j$).

According to the shift of AM from making the prototype to real parts pro-
duction, the production planning and scheduling in AM systems has changed
to a crucial problem. Special characteristics of AM environments, such as the
wide variety of orders, high production cost, high purchasing cost of AM ma-
chines in industrial dimension, and dependence on the orientation of parts in
machines, etc. have made the scheduling of AM more complex than the other
scheduling problems. Li et al. [3] proposed a mathematical model and two differ-
ent heuristics to solve the problem. Dvorak et al. [4] presented the scheduling of
3D-printing machines in a job shop while minimizing makespan and satisfying
deadlines. Li et al. [5] proposed an approach to make decisions simultaneously on
the acceptance and scheduling in AM production. Zhou et al. [6] and Maiet et al. [7]
studied the scheduling of distributed AM in cloud manufacturing [8]. Regarding
to SLM machines, Li et al. [3] proposed two heuristic procedures named ‘best-fit’
and ‘adapted best-fit’ to minimize the production cost per volume of material
on nonidentical SLM machines. Griffiths et al. [9] studied part orientation and
2D bin packing in the SLM machine to minimize the production cost.

There are few studies on parallel batch processing machine scheduling in
AM. Zhang et al. [10] have developed an improved evolutionary algorithm for
$(\mathbf{P}_m|batch|C_{max})$ in SLA (Stereo Lithography Appearance) 3D printing ma-
chines. They have combined a genetic algorithm with a heuristic placement
strategy to take into account the allocation and placement of parts integrally.
Kucukkoc [11] has addressed scheduling problem of Single, parallel identical and
parallel non-identical AM machines to minimize the makespan. He developed
an MILP model that can easily be adopted by AM firms. Our study extended
Kucukkoc [11] research. In his research, there was only one type of material
and desired quality, and the objective function was the makespan. In contrast,
we considered parts with different material types and desired quality, sequence-
dependent setup times, and total weighted tardiness as the objective function.
Hence, a new mathematical model is presented and due to the high complex-
ity of the problem, a novel matheuristic algorithm based on the combination of
Genetic algorithm and an efficient MIP-based local search is developed. Regard-
ing to the computational results, it is clear that the proposed algorithm is an
effective step forward to solve the proposed problem.

The rest of this paper proceeds as follows. Section 2 illustrates the problem description and presents the corresponding mixed integer linear programming (MILP) model. In Section 3, the proposed matheuristic algorithm is described.
Section 4 presents the computational results and evaluation of the proposed method. Finally, Section 5 concludes the paper and presents some directions for future research.

## 2 Problem Description

This section describes the investigated 3D-printing scheduling problem, its assumptions, and the mathematical model. There is a set of parts ($i \in I$) with specific properties that must be produced on a set of parallel SLM machines ($m \in M$), while machines have different area of build platform ($CA_m$) and height of build platform ($CH_m$). The characteristics of the parts include material type ($Mt_i \in K$), area ($ap_i$), height ($hp_i$), volume ($vp_i$), desired quality ($Qu_i \in Q$), as well as the due date ($dd_i$) and tardiness penalty per time unit ($tc_i$). There is a set of batches ($b \in B$), and the parts with different families (different material types or different desired quality) cannot be assigned to the same batch. The processing speed of the machine depends on the material type and the desired quality of its allocated batch, and the processing time of each batch depends on the total volume and the maximum height of its assigned parts. In other words, the total volume of parts affects the total time required to melt the metal powder and the maximum height of assigned parts affects the number of times to add a new layer of metal powder. After processing each batch, the cleaning and setting of machines should be performed for starting the next batch, while the time required for the new setup depends on the material type of the previous batch. Other parameters and variables and the corresponding mathematical model (Model 1) are as follows.

### Parameters

$vt_m^{kq}$ Time for melting material $k$ with quality $q$ on machine $m$ per volume unit

$ht_m^k$ Time required for powder layering of material type $k$ on machine $m$

$\sigma_m^{0k}$ Setup time to start the first batch with material type $k$ on machine $m$

$\sigma_m^{kk'}$ Setup time required to start the batch with material type $k$ on machine $m$ when the material type of the previous batch on the machine was $k'$

$G$ Big positive number

### Variables

$x_{ibm}$ 1 if part $i$ is processed in batch $b$ by machine $m$; 0, otherwise

$y_{mb}^{kq}$ 1 if material $k$ is employed for batch $b$ on machine $m$ to produce the parts with quality $q$; 0, otherwise

$p_{mb}$ Processing time of batch $b$ on machine $m$

$tr_i$ Tardiness of part $i$
$C_{mb}$ Completion time of batch b on machine m

$c_i$ Completion time of part i

$$ \text{Min} \sum_{i \in I} tc_i \cdot tr_i \quad \forall i \quad (1) $$

$$ \text{s.t.} \quad \sum_{m \in M} \sum_{b \in B} x_{ibm} = 1 \quad \forall i \quad (2) $$

$$ \sum_{i \in I} ap_i \cdot x_{ibm} \leq CA_m \quad \forall m, \forall b \quad (3) $$

$$ hp_i \cdot x_{ibm} \leq CH_m \quad \forall i, \forall m, \forall b \quad (4) $$

$$ y_{mb}^{kq} \cdot G \geq \sum_{\substack{i \in I \\ |Mt_i=k \\ \& Qu_i=q}} x_{ibm} \quad \forall m, \forall k, \forall q, \forall b \quad (5) $$

$$ \sum_{k \in K} \sum_{q \in Q} y_{mb}^{kq} \leq 1 \quad \forall m, \forall b \quad (6) $$

$$ y_{mb}^{kq} \leq \sum_{\substack{i \in I \\ |Mt_i=k \\ \& Qu_i=q}} x_{ibm} \quad \forall m, \forall k, \forall q, \forall b \quad (7) $$

$$ \sum_{\substack{i' \in I \\ |Mt_{i'}=k \\ \& Qu_{i'}=q}} x_{i'bm} \leq G \cdot (1 - x_{ibm}) \quad \forall i, \forall m, \forall k, \forall q, \forall b \quad (8) $$

$$ p_{mb} \geq vt_m^{kq} \sum_{i \in I} vp_i \cdot x_{ibm} + ht_m^k \max_{i \in I} \{hp_i \cdot x_{ibm}\} - G \cdot (1 - y_{mb}^{kq}) \quad \forall m, \forall k, \forall q, \forall b \quad (9) $$

$$ \sum_{i \in I} x_{ib+1m} \leq G \cdot \sum_{i \in I} x_{ibm} \quad \forall m, \forall b \leq B - 1 \quad (10) $$

$$ C_{m1} \geq p_{m1} + \sigma_m^{0k} - G \cdot (1 - \sum_{q \in Q} y_{m1}^{kq}) \quad \forall m, \forall k, b = 1 \quad (11) $$

$$ C_{mb} \geq C_{mb-1} + p_{mb} + \sigma_m^{k'k} + G \cdot (\sum_{q \in Q} y_{mb-1}^{k'q} + \sum_{q \in Q} y_{mb}^{kq} - 2) \quad \forall m, \forall k, k', b \neq 1 \quad (12) $$

$$ c_i \geq C_{mb} - G \cdot (1 - x_{ibm}) \quad \forall i, \forall m, \forall b \quad (13) $$

$$ tr_i \geq c_i - dd_i \quad \forall i \quad (14) $$

$$ x_{ibm}, y_{mb}^{kq} \in \{0, 1\}; C_{mb}, c_i, tr_i, p_{mb} \geq 0 \quad \forall i, \forall m, \forall k, \forall q, \forall b \quad (15) $$

The relation (1) indicates the objective function of the problem, which is the minimization of the total tardiness cost. Constraint (2) ensures that each part is assigned to one batch. The capacities of SLM machines in terms of area and
height of building platform is observed by constraints (3) and (4). Constraints (5)-(7) determine the material type and quality of each formed batch. Constraint (8) prevents the assignment of parts with different material and desired quality to the same batch. The production time of each batch based on the total material volume and the maximum height of its assigned parts is determined by constraint (9). This constraint can be linearized by using variable $\gamma_{m,b}$ instead of $\max_{i \in I}\{hp_i \cdot x_{ibm}\}$ while $\gamma_{m,b} \ge (hp_i \cdot x_{ibm})$ for all $i, m$ and $b$. Constraint (10) ensures that the parts cannot be assigned to a specific batch while its previous batch is not formed. This constraint, along with constraints (11) and (12) are necessary to determine the completion time of the batches. The tardiness of each part is computed by constraints (13) and (14). Finally, Constraint (15) specifies the ranges for the variables of Model 1.

## 3 Solution procedure

In this section, a hybrid algorithm called GA-MLS-$\alpha$% is proposed based on a hybridization of the genetic algorithm (GA) and a local search based on mixed-integer programming (MIP-based local search). In this hybrid algorithm, the GA is used to optimize the sub-problems related to determining the sequence of parts, and allocation of parts to the machine. Then the assignment of parts to the batches is performed by an effective heuristic named batching heuristic. Finally, the MIP-based local search is implemented on the $\alpha$% of the best solutions in the current population to exchange the batch of parts respecting their sequence. This process continues until the termination condition is met. This procedure is terminated by reaching one of the cases i) a given number of iterations or ii) a computational time limit. Fig. 1 illustrates the procedure of the proposed algorithm.

<figure><img src="image_3.png" /><figcaption>Fig. 1. Schematic pattern of proposed Matheuristic algorithm</figcaption></figure>

### 3.1 Solution representation and initial population

The utilized solution representation consists of a matrix $S$ with two rows and $|I|$ columns. In the $S$ matrix, the elements of the first row indicate the set of parts ($i \in I$) while their arrangement delineates the relative execution sequence of parts. The components in the second row determine the assigned machines to
their corresponding part in the first row. Fig. 2 shows a solution for a problem with 10 parts and 2 machines. In this figure, the columns with the same color show parts that have the same material type and desired quality (same family). For generating the initial population different rules are applied. Sequence of parts is obtained by three rules using: i) random generation ii) shortest processing time (SPT) first and iii) earliest due date (EDD) first. Moreover, the assignment of machines to parts is obtained i) randomly and by ii) earliest time of machine availability (ETA) rule [12].

<table><caption>Fig. 2. Solution representation for a problem with 10 parts and 2 machines</caption><thead><tr><th>Parts</th><th>8</th><th>6</th><th>5</th><th>2</th><th>10</th><th>1</th><th>3</th><th>7</th><th>9</th><th>4</th></tr></thead><tbody><tr><th>Machines</th><td>2</td><td>1</td><td>1</td><td>2</td><td>1</td><td>2</td><td>1</td><td>2</td><td>1</td><td>1</td></tr></tbody></table>

## 3.2 Crossover and mutation operators

The crossover and mutation operators are performed in the same way that proposed by Rohaninejad et al. [13] In the crossover operator, first, $\rho$ ($1 \le \rho < I$) parts are randomly selected. Then, all selected parts are transferred to the first offspring in the same sequence and position related to the first parent. The assigned machines for these parts are selected from the second parent. Next, the remaining parts are transferred to the offspring respecting their sequence in the second parent, and their assigned machines are determined according to the first parent. A reverse procedure of the first offspring is used for the second offspring. In the mutation operator, first, 50% of the parts are selected randomly, and their sequence and assigned machines are determined randomly as well. The remained parts are copied to the mutated individual according to their order of placement and machine assignment in the previous individual.

## 3.3 Batching heuristic method

This section presents an effective heuristic for the assignment of parts to batches. As shown in Fig. 2, the proposed solution representation lacks any information regarding this decision variable. This pattern of solution representation contributes to a faster search in the solution space and provides feasible solutions in any condition in combination with the proposed batching heuristic. In this method, the parts are assigned to an opened batch as much as possible with maximum observance of their sequence. Algorithm 1 shows the pseudo code of the proposed batching heuristic method.

## 3.4 MIP-based local search

In each iteration of the solution algorithm, an MIP-based local search is performed on the $\alpha$% of the best solutions in the current population. The MIP-based
<caption>**Algorithm 1:** *Batching (assignment of parts to the batches) heuristic*</caption>

**Result:** The corresponding schedule of solution representation
**input:** The solution representation matrix (S); nb = 0; MC=[ ]; MK=[ ]; RC=[ ]
**for** ρ = 1 to |I| **do**
> *i* = S[1, ρ] and *m* = S[2, ρ] and *k* = *Mt*<sub>*i*</sub>
> **if** ∃ *batch* *b* ≤ *nb* while *MC*[*b*] = *m* and *MK*[*b*] = *k* and *RC*[*b*] ≥ *ap*<sub>*i*</sub> **then**
> > Open new batch (*b* = *nb* + 1) and *b* ← *i*
> > *MC*[*b*] = *m*; *MK*[*b*] = *k*; *RC*[*b*] = *CA*<sub>*m*</sub> − *ap*<sub>*i*</sub>
> > *nb* = *nb* + 1
> **else**
> > Find the smallest *b* which *MC*[*b*] = *m* and *MK*[*b*] = *k* and *RC*[*b*] ≥ *ap*<sub>*i*</sub> **then**
> > *b* ← *i* and *RC*[*b*] = *RC*[*b*] − *ap*<sub>*i*</sub>

local search explores the neighborhood of the original solution. According to this
local search, the batching decision variables will be optimized again by a new
MIP model (Model 2) with respect to the sequence of parts and their assigned
machines corresponding to the original solution. The proposed local search steps
in each iteration of the GA are as follows respectively.

- Create set E including α% of the best solutions in the current population.

- Set the model 2 for each solution in E.

- Solve model 2 for each solution in E and determine the batching variables again.

In Model 2, the objective function (1) and constraints (4), (6), (11), (12), (14), and (15) are repeated without any change. Constraints (3), (5), (7), (8), (9), (10) and (13) just needs to be written for every combination of *m* and *i* that *ω[m, i]* > 0. The constraint (2) is replaced by constraint (16) and the constraints (17) and (18) must be added in Model 2. Constraint (17) ensures that the order of the parts with the same material and quality is according to their order on the original solution. Constraint (18) guarantees that the parts can be processed before a part with a lower sequence number just to fill the remaining capacity of the previous batches.

$\varphi[m]$ Number of parts that assigned to the machine $m$

$\omega[m, i]$ Sequence number of part $i$ in solution representation if $m$ is assigned to $i$; 0, otherwise

$$
\sum_{b \in B \mid b \le \varphi[m]} x_{ibm} = 1 \quad \forall i, \forall m \mid \omega[m, i] > 0 \quad (16)
$$

$$
\sum_{b'=1 | b' \le \varphi[m] \ \& \ b' > b} x_{ib'm} \le G.(1 - x_{i'bm}) \quad (17)
$$

$$
\begin{array}{l}
\forall i, \forall i', \forall m, \forall b \mid \omega[m, i] > 0 \ \& \ \omega[m, i'] > 0 \ \& \ \omega[m, i] < \omega[m, i'] \\
\phantom{\forall i, \forall i', \forall m, \forall b \mid \omega[m, i]} \& \ Mt_i = Mt_{i'} \ \& \ Qu_i = Qu_{i'}
\end{array}
$$
$$ \sum_{\substack{i' \in I \\ |\omega[m, i']| > 0 \\ \omega[m, i'] > \omega[m, i] \\ \& M_{t_{i'}} \neq M_{t_i} \\ \& Q_{u_{i'}} \neq Q_{u_i}}} x_{i'bm} \leq G.(1 - x_{ib'm}) + G. \sum_{\substack{i' \in I \\ |\omega[m, i']| > 0 \\ \omega[m, i'] < \omega[m, i]}} x_{i'bm} \quad (18) $$

$$ \forall i, \forall m, \forall b \leq \varphi[m], \forall b' \leq \varphi[m] \mid b < b' \& \omega[m, i] > 0 $$

# 4 Computational results

In this section, 10 random instances are solved to evaluate the validation of Model 1 and efficiency of the proposed algorithm. The instances are labeled with $(I - M - F)$, which represent the number of parts, machines, and job families, respectively. The proposed algorithm with different $\alpha\%$ (GA_MLS_\alpha%) is compared with two different metaheuristic algorithms that named GA_BH and GA_ATC and the mathematical formulation (Model 1). The GA_BH algorithm is developed based on combination of proposed genetic algorithm and batching heuristic. The GA_ATC is a custom version of the genetic algorithm that presented by Balasubramanian et al. [14]. They proposed a GA-based algorithm for $(\mathbf{P}_m|\text{batch, incompatible}|\sum w_j T_j)$ while first assigns jobs to machines using a GA, then forms batches on each machine and sequences them by a dispatching rule called Apparent Tardiness Cost (ATC). In this study the GA algorithms and mathematical models (Models 1 and 2) are coded by Python. Also, we have used the CPLEX solver for solving the mathematical models. For each algorithm, we have set the run-time limit to 1800 seconds. In Table 1, a detailed results of proposed algorithms are given. In order to analyze the results of the table, first the RPD% criteria is calculated for each algorithm. The RPD% specifies the Relative Percentage Deviation from mean of the objective functions that obtained by each algorithm. Accordingly, an efficient algorithm has a lower value of RPD%. Based on this criteria, it can be found that the GA_MLS_10% is the best algorithm with the average of RPD% equal to -6.6%. The average of RPD% for all instances are equal to -3.3%, -2.9%, 3.6%, 2.9% and 6.4% for GA_MLS_5%, GA_MLS_15%, GA_BH, GA_ATC and CPLEX, respectively.

Fig. 3 shows the computational time of different proposed algorithms. According to this figure, the GA_MLS_\alpha% algorithms are defensibly able to solve medium-size problems in a reasonable time.

The box plot in Fig. 4 is employed and depicted based on RPD% criteria of GA_BH, GA_ATC and GA_MLS_10% as the best of GA_MLS_\alpha% algorithms. According to Fig. 4 the GA_MLS_10% has significantly better performance so that 3/4 of its RPD values are at least smaller than 3/4 of the RPD values related to other methods.

# 5 Conclusion

This research addresses a scheduling problem in an AM environment with unrelated SLM machines and incompatible job families. A new mathematical model is
<table><caption>**Table 1.** Compare performance of the proposed algorithms</caption><thead><tr><th rowspan="3">Instances</th><th colspan="2">CPLEX</th><th colspan="2">GA-BH</th><th colspan="2">GA-ATC</th><th colspan="2">GA-MLS-5%</th><th colspan="2">GA-MLS-10%</th><th colspan="2">GA-MLS-15%</th></tr><tr><th>Best</th><th>Time</th><th>Best</th><th>Time</th><th>Best</th><th>Time</th><th>Best</th><th>Time</th><th>Best</th><th>Time</th><th>Best</th><th>Time</th></tr><tr><th>Obj</th><th>Obj</th><th>Obj</th><th>Obj</th><th>Obj</th><th>Obj</th><th>Obj</th><th>Obj</th><th>Obj</th><th>Obj</th><th>Obj</th><th>Obj</th></tr></thead><tbody><tr><td>8-2-2</td><td>839</td><td>50</td><td>839</td><td>6</td><td>885</td><td>8</td><td>839</td><td>11</td><td>839</td><td>18</td><td>839</td><td>26</td></tr><tr><td>10-2-2</td><td>504</td><td>127</td><td>732</td><td>9</td><td>732</td><td>11</td><td>732</td><td>17</td><td>504</td><td>32</td><td>504</td><td>44</td></tr><tr><td>12-2-4</td><td>1805</td><td>&gt;1800</td><td>1688</td><td>12</td><td>1956</td><td>15</td><td>1688</td><td>35</td><td>1688</td><td>72</td><td>1688</td><td>106</td></tr><tr><td>15-3-4</td><td>2994</td><td>&gt;1800</td><td>2712</td><td>16.6</td><td>2740</td><td>22</td><td>2728</td><td>57</td><td>2642</td><td>102</td><td>2606</td><td>152</td></tr><tr><td>20-2-6</td><td>4779</td><td>&gt;1800</td><td>4627</td><td>18</td><td>5074</td><td>34</td><td>4472</td><td>149</td><td>4472</td><td>330</td><td>4413</td><td>492</td></tr><tr><td>25-3-6</td><td>10683</td><td>&gt;1800</td><td>10472</td><td>23</td><td>11027</td><td>55</td><td>10521</td><td>285</td><td>9860</td><td>498</td><td>10412</td><td>729</td></tr><tr><td>30-3-6</td><td>8840</td><td>&gt;1800</td><td>8316</td><td>26</td><td>8532</td><td>86</td><td>8467</td><td>401</td><td>8320</td><td>784</td><td>8145</td><td>1144</td></tr><tr><td>35-3-6</td><td>7768</td><td>&gt;1800</td><td>7477</td><td>28</td><td>6430</td><td>164</td><td>5925</td><td>722</td><td>5860</td><td>1365</td><td>5925</td><td>&gt;1800</td></tr><tr><td>40-3-6</td><td>15318</td><td>&gt;1800</td><td>10548</td><td>36</td><td>12919</td><td>123</td><td>9155</td><td>1640</td><td>10441</td><td>&gt;1800</td><td>12370</td><td>&gt;1800</td></tr><tr><td>45-4-6</td><td>13664</td><td>&gt;1800</td><td>11203</td><td>56</td><td>10036</td><td>238</td><td>9712</td><td>&gt;1800</td><td>10285</td><td>&gt;1800</td><td>12421</td><td>&gt;1800</td></tr></tbody><tfoot><tr><td>Average</td><td>6689</td><td>&gt;1457</td><td>6098</td><td>23</td><td>5795</td><td>76</td><td>5423</td><td>&gt;512</td><td>5491</td><td>&gt;680</td><td>5932</td><td>&gt;810</td></tr></tfoot></table>

<figure><img src="image_4.png" /><figcaption>**Fig. 3.** Comparing computational time</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>**Fig. 4.** Comparing the RPD% (Box plot)</figcaption></figure>

presented and due to the high complexity of the problem, an efficient matheuris- tic method based on the combination of genetic algorithm and a MIP-based local search was developed. Computational results showed the efficiency of the proposed matheuristic method especially for medium-sized problems.

Combination of scheduling and bin packing of parts in 3D-printing machines can be an interesting topic for further research. Besides, studying the given problem with stochastic parameters (e.g, setup time, demand, and available time of machines) brings the problem closer to more realistic conditions.
Acknowledgement

The research has been supported by the Ministry of Education, Youth and Sports
within the dedicated program ERC CZ under the project POSTMAN with ref-
erence LL1902.

References

1. Berman, B.: 3D printing: the new industrial revolution. Business Horizons 55(2):155–162 (2012)

2. Rajaguru, K., Karthikeyan, T., Vijayan, V.: Additive manufacturing-State of art. Materials Today: Proceedings **21**: 628–633 (2020)

3. Li, Q., Kucukkoc, I., Zhang, D. Z.: Production planning in additive manufacturing and 3D printing. Computers & Operations Research **83**: 157–172 (2017)

4. Dvorak, F., Micali, M., Mathieug, M.: Planning and scheduling in additive manu-facturing. Inteligencia Artificial, **21**(62), 40–52 (2018)

5. Li, Q., Zhang, D., Wang, S., Kucukkoc, I.: A dynamic order acceptance and schedul-ing approach for additive manufacturing on-demand production. The International Journal of Advanced Manufacturing Technology, **105**(9), 3711–3729 (2019)

6. Zhou, L., Zhang, L., Laili, Y., Zhao, C., Xiao, Y.: Multi-task scheduling of dis-tributed 3D printing services in cloud manufacturing. The International Journal of Advanced Manufacturing Technology, **96**(9), 3003–3017 (2018)

7. Mai, J., Zhang, L., Tao, F., Ren, L.: Customized production based on distributed 3D printing services in cloud manufacturing. The International Journal of Advanced Manufacturing Technology, **84**(1-4), 71–83 (2016)

8. Vahedi-Nouri, B., Tavakkoli-Moghaddam, R., Rohaninejad, M.: A multi-objective scheduling model for a cloud manufacturing system with pricing, equity, and order rejection. IFAC-PapersOnLine, **52**(13), 2177-2182 (2019)

9. Griffiths, V., Scanlan, J. P., Eres, M. H., Martinez-Sykora, A., Chinchapatnam, P.: Cost-driven build orientation and bin packing of parts in Selective Laser Melting (SLM). European Journal of Operational Research, **273**(1), 334-352 (2019)

10. Zhang, J., Yao, X., Li, Y. : Improved evolutionary algorithm for parallel batch processing machine scheduling in additive manufacturing. International Journal of Production Research, 58(8), 2263-2282 (2020)

11. Kucukkoc, I.: MILP models to minimise makespan in additive manufacturing ma-chine scheduling problems. Computers & Operations Research, **105**, 58-67 (2019)

12. Rohaninejad, M., Sahraeian, R., Nouri, B. V.: Multi-objective optimization of in-tegrated lot-sizing and scheduling problem in flexible job shops. RAIRO-Operations Research, **50**(3), 587-609 (2016)

13. Rohaninejad, M., Kheirkhah, A., Fattahi, P., & Vahedi-Nouri, B.: A hybrid multi-objective genetic algorithm based on the ELECTRE method for a capacitated flexible job shop scheduling problem. The International Journal of Advanced Manufacturing Technology, **77**(1-4), 51-66 (2015)

14. Balasubramanian, H., Mönch, L., Fowler, J., Pfund, M.: Genetic algorithm based scheduling of parallel batch machines with incompatible job families to minimize total weighted tardiness. International Journal of Production Research, **42**(8), 1621-1638 (2004)