Keywords

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 tardiness 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 Sect. 3, an illustrative problem in a multi-material AM is solved by applying the developed model. Finally, Sect. 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 \( \left( {i \in I} \right) \) 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 dynamically 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 associated 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^{\prime} \in K \)). After finishing a job, the machines should be cleaned and setup operations are performed. The setup time for jobs is sequence-dependent. 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 grouping. 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 restrictions. 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 1. Notations of the developed model
Full size table
$$ {\text{Min Z}}_{1} = C_{Max} $$
(1)
$$ {\text{Min Z}}_{2} = \mathop \sum \limits_{i \in I} p_{i} \times Tard_{i} $$
(2)

s.t.

$$ \mathop \sum \limits_{m \in M} \mathop \sum \limits_{j \in J} x_{mji } = 1; \forall i \in I $$
(3)
$$ \mathop \sum \limits_{i \in I} a_{i} .x_{mji} \le MA_{m} ; \forall m \in M,\forall j \in J $$
(4)
$$ h_{i} .x_{mji} \le MH_{m} ; \forall m \in M,\forall j \in J,\forall i \in I $$
(5)
$$ \mathop \sum \limits_{i \in I} x_{{m\left( {j + 1} \right)i }} \le \psi_{1} .\mathop \sum \limits_{i \in I} x_{mji } ; \forall m \in M,\forall j \in J $$
(6)
$$ \mathop \sum \limits_{k \in K} k.w_{mj}^{k} \le x_{mji} .type_{i} + \psi_{5} \left( {1 - x_{mji} } \right); \forall m \in M,\forall j \in J,\forall i \in I $$
(7)
$$ \mathop \sum \limits_{k \in K} k.w_{mj}^{k} \ge x_{mji} .type_{i} - \psi_{5} \left( {1 - x_{mji} } \right); \forall m \in M,\forall j \in J;\forall i \in I $$
(8)
$$ \mathop \sum \limits_{k \in K} w_{mj}^{k} \le 1; \forall m \in ,;\forall j \in J $$
(9)
$$ w_{mj}^{k} \le \mathop \sum \limits_{i} x_{mji } ; \forall m \in M,\forall k \in K,\forall j \in J $$
(10)
$$ y_{mj}^{{k^{\prime}k}} + 1 \ge w_{mj}^{k} + w_{mj - 1}^{{k^{\prime}}} ; \forall m \in M,\forall k \in K,\forall j \in J\, and\, j \ne 1 $$
(11)
$$ 2y_{mj}^{{k^{\prime}k}} \le w_{mj}^{k} + w_{mj - 1}^{{k^{\prime}}} ; \forall m \in M,\forall k \in K, \forall j \in J\, and\, j \ne 1 $$
(12)
$$ \begin{aligned} & PT_{mj}^{k} \ge VT_{m}^{k} \mathop \sum \limits_{i \in I} v_{i} .x_{mji} + HT_{m}^{k} \mathop {.\hbox{max} }\limits_{i \in I} \left\{ {h_{i} .x_{mji} } \right\} - \psi_{2} \left( {1 - w_{mj}^{k} } \right); \\ & \forall m \in M, \forall k \in K,\forall j \in J \\ \end{aligned} $$
(13)
$$ PT_{mj} \ge PT_{mj}^{k} ; \forall m \in M, \forall k \in K,\forall j \in J $$
(14)
$$ C_{mj} \ge C_{mj - 1} + PT_{mj} + y_{mj}^{{k^{\prime}k}} .ST_{m}^{{k^{\prime}k}} ; \forall m \in M,\forall k \in K,\forall j \in J \,and\, j \ne 1 $$
(15)
$$ C_{m1} \ge PT_{m1} + STF_{m}^{k} - \psi_{4} (1 - w_{m1}^{k} ); \forall m \in M,\forall k \in K,j = 1 $$
(16)
$$ C_{Max} \ge C_{mj} ; \forall m \in M,\forall j \in J $$
(17)
$$ C_{i} \ge C_{mj} - \psi_{3} \left( {1 - x_{mji} } \right); \forall m \in M,\forall j \in J,\forall i \in I $$
(18)
$$ C_{i} \le C_{mj} + \psi_{3} \left( {1 - x_{mji} } \right); \forall m \in M,\forall j \in J,\forall i \in I $$
(19)
$$ Tard_{i} \ge C_{i} - d_{i} ; \,\forall i \in I $$
(20)
$$ x_{mji} ,w_{mj}^{k} ,\, y_{mj}^{{k^{\prime}k}}\, \epsilon\, \left\{ {0,1} \right\}; PT_{mj} \ge 0; PT_{mj}^{k} \ge 0 $$
(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^{\prime}k}} \) takes 1 only if job \( j \) includes parts with material type \( k \) and job \( j - 1 \) includes parts with material type \( k^{\prime} \). 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.4 GHz 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 2. Parameters related to parts
Full size table
Table 3. Parameters related to machines
Full size table
Fig. 1.
figure 1

Gantt chart for minimizing the makespan.

Full size image
Fig. 2.
figure 2

Gantt chart for minimizing the total cost of tardiness

Full size image
Fig. 3.
figure 3

Pareto front of the problem

Full size image

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 \( \upvarepsilon \)-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.