# A Bi-objective Scheduling Model for Additive Manufacturing with Multiple Materials and Sequence-Dependent Setup Time

Reza Tavakkoli-Moghaddam, Shadi Shirazian, Behdin Vahedi-Nouri

► To cite this version:

Reza Tavakkoli-Moghaddam, Shadi Shirazian, Behdin Vahedi-Nouri. A Bi-objective Scheduling Model for Additive Manufacturing with Multiple Materials and Sequence-Dependent Setup Time. IFIP International Conference on Advances in Production Management Systems (APMS), Aug 2020, Novi Sad, Serbia. pp.451-459, 10.1007/978-3-030-57997-5_52. hal-03635659

HAL Id: hal-03635659

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

Submitted on 20 Jun 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
# A Bi-objective Scheduling Model for Additive Manufacturing with Multiple Materials and Sequence-dependent Setup Time

Reza Tavakkoli-Moghaddam (✉), Shadi Shirazian, and Behdin Vahedi-Nouri

School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran
tavakoli@ut.ac.ir

**Abstract.** Considering the striking achievement of additive manufacturing (AM) as a revolutionary technology, it has increasingly attracted the attention of academia and industrial communities in recent years. Scheduling and production planning in AM play an essential role in the efficient and economical manufacturing of customized products through the saving of time and cost. In this paper, an AM scheduling problem is taken into account with different order specifications, especially the material type and due date on non-identical parallel machines. To formulate the problem, a bi-objective mixed-integer linear programming (MILP) model is proposed to minimize the makespan and the total tardiness penalty. Assuming parts with different material types necessitates the consideration of sequence-dependent setup time that depends on the material type of the current and previous jobs on an AM machine. Finally, an augmented $\varepsilon$-constraint method is applied for the problem to achieve a Pareto-optimal front in an illustrative instance.

**Keywords:** Scheduling, Industry 4.0, Additive manufacturing, Mathematical modeling, Sequence-dependent setup time.

## 1 Introduction and Literature Review

Additive manufacturing (AM) or 3D printing as an emerging technology has been developed over the last two decades. Compared to traditional manufacturing, in AM, the process of manufacturing parts is through joining materials layer by layer based on a three-dimensional computer-aided design (CAD) file [1]. AM enjoys significant benefits, such as design freedom, requires fewer materials and resources, and production flexibility [1, 2] that attracts industries (e.g., automotive, aerospace, medical, and defense). Applying AM can lead to the production of small and customized batches economically [3]. AM processes can be classified into three main clusters: powder-based system, liquid-based system, solid or wire extrusion [4]. In this research, a variation of powder-based AM process, namely selective laser melting (SLM), is considered. This variation is capable of the simultaneous production of several parts in one batch for the capacity constraint.
To start processing a new batch called a job, a series of works are required to set up the associated machine, such as preparing data, filling powder material, adjusting the machine, and filling the protective atmosphere [2]. Then, the layer generation is repeated until all parts inside the building platform of the machine are completed. It means that no part can be removed until the job is finished. Afterward, the machine should be cleaned, and some post-processing (typically manual) might be performed. Accordingly, the production cost and time are dynamically influenced by some factors, such as different combinations of parts in jobs, the maximum height of the parts allocated to a job, the thickness of layers, and build orientation. Also, since the processing and purchasing cost of AM machines is high, optimal assignment of ordered parts into jobs and the scheduling of these jobs on AM machines are of significant importance [1].

Regarding AM, different problems have been explored like sustainability in the AM supply chain [5], part orientation in 3D printers [6] and part placing problem [7]. However, to the best of our knowledge, only a few studies emphasize the production planning and scheduling problems in AM. The AM scheduling problem can be considered as an extension of the batch scheduling problem, in which different part assignments lead to different processing times regarding the volume and height of the parts allocated to a job (batch) [2]. Li et al. [1] presented a mixed-integer linear programming (MILP) model to minimize the average production cost per volume of material on non-identical AM machines. They considered only one type of material and part nesting in the absence of due dates for parts. Also, they proposed two heuristic procedures named ‘best-fit’ and ‘adapted best-fit’ to solve this problem. Chergui et al. [8] investigated the problem of scheduling and nesting of parts on parallel identical AM machines to minimize the maximum lateness. They divided the problem into two sub-problems: clustering of parts into a set of batches, and scheduling of batches on parallel machines. Dvorak et al. [9] considered two-dimensional bin packing, nesting, and scheduling of parts on a job shop to minimize the makespan respecting the deadlines of orders. Fera et al. [10] formulated a multi-objective model for a single AM machine scheduling problem that minimizes the time and cost and developed a modified genetic algorithm to solve the problem. Li et al. [11] studied the joint dynamic order acceptance and scheduling problem in AM to maximize the average profit-per-unit-time while minimizing the makespan. Kucukkoc [2] proposed several MILP models to address AM scheduling problems in single, identical parallel and non-identical parallel machine settings that minimize the makespan.

Regarding the literature, researchers have considered only one type of materials in the AM scheduling. However, in the real world, the material type of the received orders might be different, and 3D printers, which are compatible with different metal powders are available on the market. Accordingly, for the first time, this study aims to scrutinize the scheduling problem in AM scheduling, in which the material type of parts are different. In other words, a part is made up of only one material; however, the material type of two parts might be different. In this multi-material AM, setup time between each job on each machine is sequence-dependent, which depends on the material types of parts processed in the associated sequential jobs. The proposed AM problem is assumed in a non-identical parallel machine environment. A bi-objective MILP model is
devised to formulate the problem, which minimizes the makespan and the total tardi-
ness cost.

The rest of this paper is organized as follows. Section 2 is devoted to describing the problem, its assumptions, notations, and the proposed bi-objective mathematical model. In Section 3, an illustrative problem in a multi-material AM is solved by applying the developed model. Finally, Section 4 concludes this study and provides some recommendations for future studies.

## 2 Problem Description

As described above, the presented research concentrate on the scheduling problem in AM. A set of parts ($i \in I$) with different specification, such as height ($h_i$), area ($a_i$), volume ($v_i$), due date ($d_i$), tardiness penalty ($p_i$), and material type ($type_i \in K$) should be assigned into a set of jobs ($j \in J$), and scheduled on a set of AM machines ($m \in M$) that are arranged as non-identical parallel machines. The bi-objective model aims to find Pareto-optimal solutions by minimizing the makespan and the total tardiness cost.

The maximum completion time and accordingly tardiness cost for a part are dynam-
ically impacted by a combination of the parts in its associated job. In other words, the
processing time of a job depends on its assigned parts. Since the material type associ-
ated with each part could be different and a machine can be filled with only one material
at a time, the parts that are grouped in a job must be the same type. As a result, each
job is identified with a type ($k, k' \in K$). After finishing a job, the machines should be
cleaned and setup operations are performed. The setup time for jobs is sequence-de-
pendent. For instance, if the material type of the first job differs from the second one,
the setup time is longer than a case, in which the material type of sequential jobs is the
same. Besides, capacity constraints (i.e., height and area) play a key role in part group-
ing. Other assumptions of the problem are as follows. The rectangular shape is only
considered as the projection of part shapes, and a safety tolerance in the value of ($a_i$) is
regarded between the parts to avoid part damage and simplify the process of removing
parts. Build orientation is assumed to be fixed since it has an impact on quality [12].
All parts have the same layer thickness. All parts are ready at time zero. Each AM
machine can have specific features (e.g., build speed and laser power). All machines
can be reused after finishing a job, and setup times that are sequence-dependent must
be performed. Some parts cannot be assigned to some machines due to capacity re-
strictions. The number of parts is greater or equal to jobs. The other notations of the
problem are expressed in Table 1 followed by the proposed bi-objective mathematical
model.
<table><caption>**Table 1.** Notations of the developed model</caption><thead><tr><th>Parameters</th><th>Variables</th></tr></thead><tbody><tr><td>VT<sup>k</sup><sub>m</sub></td><td>x<sub>mji</sub> 1 if part i is assigned to job j on machine m; 0, otherwise</td></tr><tr><td>HT<sup>k</sup><sub>m</sub></td><td>w<sup>k</sup><sub>mj</sub> 1 if material type k is utilized for job j on machine m; 0, otherwise</td></tr><tr><td>STF<sup>k</sup><sub>m</sub></td><td>y<sup>k'k</sup><sub>mj</sub> 1 if job j with material type k succeeds job j - 1 with material type k'; 0, otherwise</td></tr><tr><td>ST<sup>k'k</sup><sub>m</sub></td><td>Tard<sub>i</sub> Tardiness of part i</td></tr><tr><td>MH<sub>m</sub></td><td>C<sub>mj</sub> Completion time of job j on machine m</td></tr><tr><td>ψ<sub>1</sub> - ψ<sub>5</sub></td><td>PT<sup>k</sup><sub>mj</sub> Processing time of job j on machine m if its material type is k</td></tr><tr><td>MA<sub>m</sub></td><td>PT<sub>mj</sub> Processing time of job j on machine m</td></tr><tr><td></td><td>C<sub>i</sub> Completion time of part i</td></tr></tbody></table>

$$ \text{Min } Z_1 = C_{Max} \qquad (1) $$

$$ \text{Min } Z_2 = \sum_{i \in I} p_i \times Tard_i \qquad (2) $$

s.t.

$$ \sum_{m \in M} \sum_{j \in J} x_{mji} = 1; \quad \forall i \in I \qquad (3) $$

$$ \sum_{i \in I} a_i \cdot x_{mji} \leq MA_m; \quad \forall m \in M, \forall j \in J \qquad (4) $$

$$ h_i \cdot x_{mji} \leq MH_m; \quad \forall m \in M, \forall j \in J, \forall i \in I \qquad (5) $$

$$ \sum_{i \in I} x_{m(j+1)i} \leq \psi_1 \cdot \sum_{i \in I} x_{mji}; \quad \forall m \in M, \forall j \in J \qquad (6) $$

$$ \sum_{k \in K} k \cdot w_{mj}^k \leq x_{mji} \cdot \text{type}_i + \psi_5(1 - x_{mji}); \quad \forall m \in M, \forall j \in J, \forall i \in I \qquad (7) $$

$$ \sum_{k \in K} k \cdot w_{mj}^k \geq x_{mji} \cdot \text{type}_i - \psi_5(1 - x_{mji}); \quad \forall m \in M, \forall j \in J; \forall i \in I \qquad (8) $$

$$ \sum_{k \in K} w_{mj}^k \leq 1; \quad \forall m \in M; \forall j \in J \qquad (9) $$

$$ w_{mj}^k \leq \sum_{i \in I} x_{mji}; \quad \forall m \in M, \forall k \in K, \forall j \in J \qquad (10) $$

$$ y_{mj}^{k'k} + 1 \geq w_{mj}^k + w_{mj-1}^{k'}; \quad \forall m \in M, \forall k \in K, \forall j \in J \text{ and } j \neq 1 \qquad (11) $$

$$ 2y_{mj}^{k'k} \leq w_{mj}^k + w_{mj-1}^{k'}; \quad \forall m \in M, \forall k \in K, \forall j \in J \text{ and } j \neq 1 \qquad (12) $$

$$ PT_{mj}^k \geq VT_m^k \sum_{i \in I} v_i \cdot x_{mji} + HT_m^k \max_{i \in I} \{h_i \cdot x_{mji}\} - \psi_2(1 - w_{mj}^k); \quad \forall m \in M, \forall k \in K, \forall j \in J \qquad (13) $$

$$ PT_{mj} \geq PT_{mj}^k; \quad \forall m \in M, \forall k \in K, \forall j \in J \qquad (14) $$
$$C_{mj} \geq C_{m_{j-1}} + PT_{mj} + y_{mj}^{k'k} \cdot ST_{m}^{k'k}; \quad \forall m \in M, \forall k \in K, \forall j \in J \text{ and } j \neq 1 \quad (15)$$

$$C_{m1} \geq PT_{m1} + STF_{m}^{k} - \psi_{4}(1 - w_{m1}^{k}); \quad \forall m \in M, \forall k \in K, j = 1 \quad (16)$$

$$C_{Max} \geq C_{mj}; \quad \forall m \in M, \forall j \in J \quad (17)$$

$$C_i \geq C_{mj} - \psi_3(1 - x_{mji}); \quad \forall m \in M, \forall j \in J, \forall i \in I \quad (18)$$

$$C_i \leq C_{mj} + \psi_3(1 - x_{mji}); \quad \forall m \in M, \forall j \in J, \forall i \in I \quad (19)$$

$$Tard_i \geq C_i - d_i; \quad \forall i \in I \quad (20)$$

$$x_{mji}, w_{mj}^{k}, y_{mj}^{k'k} \in \{0,1\}; PT_{mj} \geq 0; PT_{mj}^{k} \geq 0 \quad (21)$$

Equations (1) and (2) represent the two objective functions of the problem, including minimizing the makespan and the total tardiness cost, respectively. Constraint (3) guarantees that each part is allocated to only one job among all machines. Capacity constraints are respected by Constraints (4) and (5). Constraint (6) states that a job on a machine cannot be formed before the formation of its previous job on the machine. Constraints (7) to (10) identify the material type of each job concerning the type of its assigned parts. Constraint (9) guarantees that the material type of a job would not change. Constraint (10) states that if no part is assigned into a job, $w_{mj}^k$ would not take 1. Constraints (11) and (12) state that $y_{mj}^{k'k}$ takes 1 only if job j includes parts with material type k and job j-1 includes parts with material type k'. Constraints (13) and (14) calculate the processing time for each job of each machine as the function of total volume and maximum height of the parts assigned to. The completion times of jobs are determined by Constraints (15) and (16) according to their setup times and processing times. The makespan, completion times, and tardiness of parts are calculated by Constraints (17) to (20), respectively. Constraint (21) defines the variables of the respected model.

## 3 Computational Experiment

In this section, a simple numerical example with 10 parts, 2 machines, and 2 types of materials is presented to validate the mathematical model. Tables 2 and 3 display the parameters of the problem. Since the proposed model is a bi-objective one, the augmented $\varepsilon$-constraint method is applied to achieve a Pareto-optimal front. This method is a well-known and efficient multi-objective method presented by Mavrotas and Florios [13] and employed in a vast variety of research (i.e., [14, 15]). The original $\varepsilon$-constraint method is based on optimizing one objective and putting others as constraints. To reduce the drawbacks of this method, the augmented $\varepsilon$-constraint method introduced in 2009, in which slack variables are considered to make the equality constraint and the objective function is augmented with the weighted sum of slack variables. Then, the AUGMECON2 was developed as an improvement of the previous method in 2013, which is appropriate for multi-objective integer programming problems [13]. The proposed model was coded in GAMS software using CPLEX solver and executed on an AMD Quad Core A12-9700P CPU 3.4GHz system with 8 GB RAM.
The Gantt charts of single-objective optimal solutions based on the makespan and the total tardiness cost are depicted in Figs. 1 and 2, respectively. For example, in Fig. 1, the parts are assigned into 6 jobs; 2 jobs on machine 1, and 4 jobs on machine 2. The two colors are applied for the jobs to illustrate their material types. For instance, as seen in Fig. 1, the first job of machine 2 includes parts 1 and 8, which both are performed by material type 1. To minimize the makespan, the value of the makespan and the total cost of tardiness are obtained 282.06 and 1023.52, respectively. Then, to optimize the second objective the optimum total cost of tardiness is 51.19 and the makespan is determined 317.06. Also, the Pareto-optimal front of solving this example is shown in Fig. 3. It should be noted that in the AUGMECON2, the makespan is optimized and the second objective is applied as the constraint. Seven non-dominated solutions are generated by adjusting 9 grid points by which the decision-maker can select the most favorable solution among them based on his/her preference.

<table><caption>**Table 2.** Parameters related to parts</caption><thead><tr><th>i</th><th>h<sub>i</sub>-cm</th><th>a<sub>i</sub>-cm<sup>2</sup></th><th>v<sub>i</sub>-cm<sup>3</sup></th><th>Type<sub>i</sub></th><th>d<sub>i</sub>-hr</th><th>p<sub>i</sub>-$</th></tr></thead><tbody><tr><td>1</td><td>7.12</td><td>233.83</td><td>1718.83</td><td>1</td><td>285</td><td>3</td></tr><tr><td>2</td><td>26.37</td><td>184.80</td><td>2394.82</td><td>1</td><td>142</td><td>3</td></tr><tr><td>3</td><td>8.21</td><td>275.27</td><td>717.19</td><td>2</td><td>185</td><td>6</td></tr><tr><td>4</td><td>11.63</td><td>639.58</td><td>1933.09</td><td>2</td><td>285</td><td>8</td></tr><tr><td>5</td><td>27.47</td><td>71.90</td><td>2240.96</td><td>2</td><td>300</td><td>3</td></tr><tr><td>6</td><td>18.64</td><td>383.45</td><td>920.84</td><td>1</td><td>270</td><td>2</td></tr><tr><td>7</td><td>15.78</td><td>741.61</td><td>380.81</td><td>1</td><td>110</td><td>7</td></tr><tr><td>8</td><td>15.47</td><td>439.93</td><td>1476.41</td><td>1</td><td>155</td><td>7</td></tr><tr><td>9</td><td>7.15</td><td>736.59</td><td>519.70</td><td>1</td><td>50</td><td>5</td></tr><tr><td>10</td><td>7.12</td><td>233.83</td><td>1718.83</td><td>1</td><td>285</td><td>3</td></tr></tbody></table>

<table><caption>**Table 3.** Parameters related to machines</caption><thead><tr><th></th><th>ST<sup>1,1</sup><sub>m</sub></th><th>ST<sup>1,2</sup><sub>m</sub></th><th>ST<sup>2,1</sup><sub>m</sub></th><th>ST<sup>2,2</sup><sub>m</sub></th><th>STF<sup>1</sup><sub>m</sub></th><th>STF<sup>2</sup><sub>m</sub></th><th>VT<sup>1</sup><sub>m</sub></th><th>VT<sup>2</sup><sub>m</sub></th><th>HT<sup>1</sup><sub>m</sub></th><th>HT<sup>2</sup><sub>m</sub></th><th>MA<sub>m</sub></th><th>MH<sub>m</sub></th></tr></thead><tbody><tr><th>m1</th><td>1.27</td><td>1.15</td><td>1.52</td><td>1.4</td><td>1.31</td><td>1.14</td><td>0.035</td><td>0.034</td><td>0.7</td><td>0.7</td><td>1000</td><td>33.4</td></tr><tr><th>m2</th><td>1.62</td><td>1.24</td><td>1.53</td><td>1.61</td><td>1.04</td><td>1.05</td><td>0.035</td><td>0.04</td><td>0.7</td><td>0.7</td><td>900</td><td>38.7</td></tr></tbody></table>

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Gantt chart for minimizing the makespan.</figcaption></figure>
<figure><img src="image_3.png" /><figcaption>Fig. 2. Gantt chart for minimizing the total cost of tardiness</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 3. Pareto front of the problem</figcaption></figure>

**4 Conclusions**

This study explored a new scheduling problem in additive manufacturing (AM) with the presence of sequence-dependent setup times. The problem supposed parts with different material types on non-identical AM machines considering a trade-off between two objectives, including minimizing the makespan and the total tardiness cost. A bi-objective MILP model was proposed to formulate the problem, and an illustrative problem was solved by applying the augmented ε-constraint method for validating the developed model. Since the problem is intractable, developing efficient meta-heuristic algorithms can be a promising research area. Moreover, incorporating bin packing and uncertain consideration into the proposed model are suggested for future research.
References

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

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

3. Holmström, J., Partanen, J., Tuomi, J., & Walter, M. (2010). Rapid manufacturing in the spare parts supply chain. *Journal of Manufacturing Technology Management, 21*(6), 687-697.

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

5. Niaki, M. K., Torabi, S. A., & Nonino, F. (2019). Why manufacturers adopt additive manufacturing technologies: The role of sustainability. *Journal of Cleaner Production, 222*, 381-392.

6. Zhang, Y., Bernard, A., Harik, R., & Karunakaran, K. (2017). Build orientation optimization for multi-part production in additive manufacturing. *Journal of Intelligent Manufacturing, 28*(6), 1393-1407.

7. Canellidis, V., Giannatsis, J., & Dedoussis, V. (2013). Efficient parts nesting schemes for improving stereolithography utilization. *Computer-Aided Design, 45*(5), 875-886.

8. Chergui, A., Hadj-Hamou, K., & Vignat, F. (2018). Production scheduling and nesting in additive manufacturing. *Computers & Industrial Engineering, 126*, 292-301.

9. Dvorak, F., Micali, M., & Mathieug, M. (2018). Planning and scheduling in additive manufacturing. *Inteligencia Artificial, 21*(62), 40-52.

10. Fera, M., Fruggiero, F., Lambiase, A., Macchiaroli, R., & Todisco, V. (2018). A modified genetic algorithm for time and cost optimization of an additive manufacturing single-machine scheduling. *International Journal of Industrial Engineering Computations, 9*(4), 423-438.

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

12. Byun, H.-S., & Lee, K. H. (2006). Determination of the optimal build direction for different rapid prototyping processes using multi-criterion decision making. *Robotics and Computer-Integrated Manufacturing, 22*(1), 69-80.

13. Mavrotas, G., & Florios, K. (2013). An improved version of the augmented ε-constraint method (AUGMECON2) for finding the exact pareto set in multi-objective integer programming problems. *Applied Mathematics and Computation, 219*(18), 9652-9669.

14. Hamid, M., Tavakkoli-Moghaddam, R., Golpaygani, F., & Vahedi-Nouri, B. (2020). A multi-objective model for a nurse scheduling problem by emphasizing human factors. *Proceedings of the Institution of Mechanical Engineers, Part H: Journal of Engineering in Medicine, 234*(2), 179-199.

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