A dynamic order acceptance and scheduling approach for additive manufacturing on-demand production

Additive manufacturing (AM), also known as 3D printing, has been called a disruptive technology as it enables the direct production of physical objects from digital designs and, thus, allows industrial as well as private users to design and produce their own products enhancing the idea of the rise of the “prosumer” [1, 2]. AM technology usually builds a structure into its designed shape using a “layer-by-layer” approach, which makes it versatile, flexible, highly customizable and suitable for most sectors of industrial production [3]. This characteristic of AM provides new opportunities for freedom of design and enables on-demand production of customized products without additional manufacturing costs due to the geometric complexity. The importance of AM technology has been recognized in various businesses [1, 2, 4, 5] and has been considered as one of the key supporting technologies for smart design and manufacturing in Industry 4.0 [6]. The advantages of AM technology over traditional manufacturing have been identified and discussed by Attaran [7]. It also has been predicted that, by 2030, a significant number of small and medium enterprises will share industry-specific AM production resources to achieve higher machine utilization and, across all industries, local production near customers enabled by AM will increase significantly [1]. By then, the problems regarding production planning and scheduling in on-demand production with industry-specific AM resources will be on the table. Typically, the decision-making on the order acceptance and scheduling (OAS) will play a crucial role when service providers dealing with on-demand production orders from small and medium enterprise are distributed around the world.

Two of the most representative AM processes, Selective Laser Melting (SLM) and Electron Beam Melting (EBM), classified as the Powder Bed Fusion (PBF) process, have received significant attention in the research and have been widely adopted in various industries due to their advantages in producing fine-resolution and high-quality near-full-density parts [3, 5]. PBF is an AM process, in which thermal energy source, either a laser or electron beam, is used to melt and fuse selective regions of a powder bed (ASTM:F2790-12a). A PBF system is a kind of batch processing machine (BPM) in which a batch of identical or non-identical parts can be processed simultaneously according to its capacity. A batch of parts can be grouped to form an AM job when they are able to fit the AM machine’s production capacity, which is generally limited by the cuboid space of the machine’s building chamber. The production of a batch of parts is usually called an AM job. The parts assigned to an AM job are processed simultaneously, and, once the job is started, no part can be added into or taken out of the machine until the whole AM job is completed.

The operations of an AM job usually comprise the following three steps: preparation, production, and collection. The general process of production with a PBF system is illustrated in Fig. 1, though the energy source and materials used in a particular PBF process might be different. First, a series of operations are needed to set up an AM job, including the processing of digital model data, preparation of powder materials, filling up the protective atmosphere, and warming up the machine if necessary. For metal PBF systems like SLM and EBM, the parts usually need to be built onto the metallic building platform to avoid thermal-induced deformation and should be properly oriented to reduce support structures [8, 9]. The metal parts are usually nested in two dimensions, although it is possible in three dimensions, using their 2D boundary box within the area of the building platform without overlap for the purpose of safety. Afterwards, the AM job can be started. A thin layer of powder materials with a typical thickness of 20 to 60 μm will be generated upon a base platform or the already-produced fraction of objects. Then, the cross-sections of sliced CAD files will be subsequently scanned using a high-power laser or electron beam to densify the powder materials, and the platform goes down a pitch equal to the layer thickness afterwards. These two procedures, namely powder layering and powder melting, will alternate until all parts in the job are produced [10]. Finally, the parts, together with the building platform, can be taken out of the machine when all the parts have been produced, and the machine can be cleaned for the preparation of the next AM job. Before the parts are delivered, they usually need to be heat-treated together with the building platform to release the thermal stress, and, then, the parts can be cut off from the platform for post-processing, such as support structures’ removal and surface polishing if necessary.

The characteristics of production with PBF systems, in particular, the uncertainty of the production time of an AM job, make it challenging when dealing with the OAS problem. According to the classification of batch processing problems (BPP) by Matin et al. [11], the production with PBF systems is similar to a serial batch scheduling problem where the processing time of each batch is a function of jobs’ attributes. Just to be clear, the terms “AM job” and “part” in this paper correspond to the terms “batch” and “job” used in BPP, respectively. The processing time of an AM job can be seen as the composition of two sections—the time spent on job preparation and part collection, which is relatively fixed, and the time spent on the production of parts assigned to the job, which is a function of the parts’ attributes as well as the machine’s specifications. To produce the parts assigned to an AM job, the processes of powder layering and powder melting are repeated alternately until all the layers have been processed. The time to melt powder materials to form a part depends on the building speed of the machine which is usually measured by the volume rate. However, the time required for powder layering depends on the number of layers and the settings of the machine. It must be pointed out that the accumulated time spent on generating powder layers will be significant when the thickness of each layer is quite small, even longer than the time spent on densifying the powder materials in some cases. For example, given that the layer thickness of 20 μm and 15 s for generating each powder layer, the machine will spend more than 62 h on generating powder layers to produce a part 300 mm high. This case could be worse for a particular PBF process, like EBM, where each layer might need additional time for powder materials’ pre-heating. Therefore, the production time of an AM job could be extended significantly by adding a new part, not only because it increases the time for powder melting but also because it might increase the time required for powder layering. The nature of production with PBF systems makes the production time of an AM job inconclusive before all the parts assigned to this job have been confirmed. Also, as the time for powder layering depends on the number of layers presented by the highest part included in an AM job and is shared by all the parts, the production time of an individual part is inconclusive before the confirmation of the job. Meanwhile, the production cost of an individual part is variational when it is assigned to different AM jobs due to the variety of production time. The difference of production cost per volume of material could be more than 40% when the part order was scheduled into different jobs [10].

This paper considers a dynamic OAS problem in an on-demand production environment where the service provider with multiple AM machines is making decisions on the acceptance of orders placed by customers and scheduling the accepted orders simultaneously, to maximize the average profit-per-unit-time obtained during the whole makespan. AM technologies, as a rapidly developing DDM technology, have become an important service form which can be provided across the world through an online platform, while the parts are produced locally near the customers [1, 3, 12, 13]. Generally, within an online service platform, the service providers with one or more PBF systems usually provide a unit service price based on the volume of materials and a due date which is generally a fixed time after the acceptance of the order. Customers around the world usually upload their digital models and make enquiries about the availability of the services if they are satisfied with the price and due date. The orders will be accepted automatically if the order can be delivered before the due date promised by the service providers. Otherwise, the customers may either further negotiate with the service providers for a new offer or turn to another service provider. In this paper, we consider the decision-making problem faced by an individual service provider on how to select the orders and schedule them within promised due date to maximize the average profit-per-unit-time during the whole makespan. For generalization, the orders are placed by customer randomly in a chronological order and to wait for the acceptance from the service provider. An order, termed part order in this paper, only contains one digital model data which has been properly oriented and cannot be separated. The service provider tries to group arrived part orders instantly into a batch to form an AM job on a specific AM machine by considering the constraints of the machine’s capacity as well as the promised latest due date of each part order. A part order will be accepted only if it can be processed within one of the machines’ jobs and the complete time of the job is not later than the promised latest due date. Otherwise, the part order will be rejected and handed over to another department for further negotiation with customers. All the accepted part orders will be produced according to the scheduled start time of the AM job they were assigned to. The completion time as well as the start time of a production job can only be determined when all part orders included in this job are confirmed. Therefore, any part order added into an unconfirmed AM job will occupy the capacity of the machine and affect the completion time of the job, which may render the machine unable to fit further part orders due to either the constraints of their due dates or the machine’s capacity.

The dynamic OAS problem in on-demand production with PBF systems is a joint decision on order acceptance and scheduling of batch processing machines. It is vitally important to appropriately determine which part orders should be accepted and how they should be scheduled simultaneously so as to maximize the average profit-per-unit-time corresponding to the whole makespan. Although the topics of OAS and BPP have been widely studied [11, 14, 15], to the best of our knowledge, no research has been conducted to address the dynamic OAS problem in production with PBF systems. In this paper, the dynamic OAS problem is defined and mathematically modelled with constraints of orders’ arrival time and due date for the first time. Since both OAS and BPP are strong NP hard problems, in regard to the characteristics of production with PBF systems, a strategy-based heuristic decision-making approach is proposed for the generation of feasible schedule solutions. The proposed approach can be used for the investigation of decision-making strategies to obtain promising profitability with a given price and due date. Alternatively, given an expected profitability and decision-making strategy, the approach can be used to generate competitive offers through reducing service price and/or narrowing due date.

The paper is organized as follows. The related works are reviewed in Section 2, and the problem of dynamic OAS in on-demand production with PBF systems is defined and modelled mathematically in Section 3. In Section 4, the heuristic procedures are proposed for the generation of feasible AM jobs on a single machine as well as multiple machines to form a feasible schedule result. Further, different decision strategies are proposed based on the analysis of the selective behaviours, which may affect the schedule results, during the generation of a feasible schedule. A comprehensive experimental study is designed and conducted in Section 5, followed by conclusions and future research directions in Section 6.

As an emerging disruptive manufacturing technology, the application of AM technologies has increased substantially in different industries during the past years, and considerable research, from scientific and technological challenges [3, 5, 7] to business model innovation and industry application issues [2, 4, 16‐18], has been carried out. A prediction of the future of AM, based on an extensive Delphi survey by Jiang et al. [1], indicated that, by 2030, a significant number of small and medium enterprises will share industry-specific additive manufacturing production resources to achieve higher machine utilization, learning effects, and quality assessments. Also, it was predicted that, by 2030, the distribution of final products will move significantly (> 25%) to selling digital files for direct manufacturing instead of selling the physical product due to the increase of local production near customers enabled by additive manufacturing. The research and development of the key technology of 3D printing cloud manufacturing platforms was summarized by Guo and Qiu [16], and the development of the combination of 3D printing and cloud manufacturing was proposed. In recent years, even more research is focusing on the practical problems related to production with AM technologies [10, 19‐23].

The problem of OAS in on-demand production with PBF systems involves the decision-making on order acceptance and scheduling of batch processing machines, both of which have been widely studied in different production environments [14, 24‐26]. The OAS problems usually occur, particularly in highly loaded make-to-order production systems, when the production capacity of a company is overloaded [14, 27]. A detailed taxonomy of OAS problems and a complete review of literature before 2011 were presented by Slotnick [14]. Recently, a genetic algorithm based on real-time OAS approach for permutation flow shop problems to maximize the revenue of a flow shop production business was proposed by Rahman et al. [28]. The demand uncertainty in production planning problems integrated with order acceptance was introduced by Aouam et al. [29], and a relax and fix (RF) heuristic for the construction of feasible solutions which can then be improved by a fix and optimist (FO) heuristic was proposed. Over the past decades, the BPPs which can be observed in many industries and service sectors have been widely studied in literature. Based on the batch processing time and the batch capacity restriction, the classification of BPP problems was proposed by Matin et al. [11], and a mixed-integer linear programming model as well as metaheuristic algorithms based on particle swarm optimization were proposed for the flow shop BPP problem with different batch compositions to minimize makespan. The scheduling problems for single/multiple parallel and serial batch processing machines have also been studied, and various approaches have been developed [24, 26, 30‐33]. Based on their previous studies of dynamic scheduling problem [34, 35], a case study focusing on online and dynamic scheduling of parallel heat treatment furnaces at a real manufacturing company was recently presented by Baykasoğlu and Ozsoydan [36] where a multi-start and constructive search algorithm was proposed to minimize the maximum completion time of the schedule. Concerning the latest industrial revolution (Industry 4.0), a novel general framework of assembly system was introduced by Bortolini et al. [37] and an innovative multi-objective optimization model as well as the key enabling technologies were introduced for the assembly line balancing problem [38, 39]. Although various approaches have been developed for various OAS problems and BPP problems, it is hard to adopt these approaches directly in on-demand production with PBF systems due to the unique nature of AM production.

The topic of AM has attracted considerable attention over the past decades [3, 5]. However, research on production planning and scheduling in AM, particularly, the OAS problems, is just catching up. Order acceptance and scheduling in production with PBF systems is an extremely complicated problem where multiple topics, including bin packing, batch processing, production cost/profit, makespan, and decision-making on order acceptance/rejection, need to be taken into account simultaneously. However, most of the research emerging in this field only addressed parts of the problem as shown in Table 1. The production planning problem of multiple metal AM machines was introduced and modelled mathematically for the first time by Li et al. [10]. The problem was solved with CPLEX as well as metaheuristic procedures to minimize the average production cost per unit volume of material; however, the due dates and the shape of part orders have not been considered. In our recent research [22], the production scheduling problem in a multiple AM machine environment by considering the release and due dates of part orders was studied and a genetic algorithm approach was developed to minimize the maximum lateness. Inspired by our research, several studies have been reported recently. The production planning and scheduling of identical parallel AM machines to fulfil the different orders by due dates and to minimize the total tardiness was studied by Akram et al. [40], where the mathematical formulation of the problem and a heuristic procedure were proposed. The problem was formulated as two subproblems—part/job assignment through part clustering based on due dates and job scheduling based on tardiness of the jobs. Dvorak et al. [41] investigated the problem of scheduling parts on multiple AM machines while minimizing time spent and satisfying deadlines, bringing together bin packing, nesting, job shop scheduling and constraint satisfaction. The problem was encapsulated within constraints and graph theory to represent relationships between individual parts, and search algorithms were introduced to find solution with minimum makespan. A modified genetic algorithm for time and cost optimization of an AM single-machine scheduling problem was proposed by Fera et al. [42] to balance the optimization of earliness/tardiness and production costs. Oh et al. [43] studied the production planning and scheduling problem in production with multiple AM machines where a heuristic algorithm was proposed for decision-making on build orientation, 2D packing and scheduling on multiple AM machines based on the longest cycle time. A decision aiding model, based on a multi-objective optimization for a batch of parts and multiple fused deposition modelling (FDM) printers, was proposed by Ransikarbum et al. [19] considering the operating cost, load balance among printers, total tardiness and total number of unprinted parts as objectives. The requirement of print time for FDM is based on the sum of all part time which is different with that of the PBF process. A cloud-based platform for automated order processing in Additive Manufacturing where the order acceptance is determined according to the checking of manufacturing restriction and design guidelines was proposed by Rudolph and Emmelmann [21], while the scheduling problem was not considered. The problem of multi-task scheduling of distributed 3D printing services in cloud manufacturing was discussed by Zhou et al. [13], and a 3D printing service scheduling (3DPSS) method to reduce the delivery time of tasks from candidate services obtained through service matching was proposed. The authors treated the 3D printer as a service which can only process one job at a time, and, thus, the batching problem was not considered. The OAS problem faced by AM service providers in a competitive environment was introduced and a strategy-based decision-making model was proposed in our previous work [44], while the decision-making strategies as well as their performance need to be further investigated.

The computational study was conducted to investigate the performance of the various decision strategies proposed in Section 4.3. A series of problems with different number of part orders and AM machines were generated randomly and solved with the heuristic algorithms proposed in Section 4.2. To evaluate the performance of different decision strategies, the difference between potential bad and good schedule results was investigated first with the proposed RDM decision strategy. Then, the performance of decision strategy sets listed in the previous subsection was evaluated by comparing their results with the best schedule results obtained with RDM decision strategy. The heuristic algorithms proposed in Section 4.2 were implemented in Python language. For reproducibility of the results, specific random seeds are used in the developed Python programme for the generation of the data of part orders and AM machines to keep consistency across different test problems. All experiments were performed on a computer equipped with Intel® Core™ i7-7700 CPU @3.60 GHz processors and 32 GB RAM. The CPU time consumed on different problem sizes was compared as well to evaluate the efficiency of the proposed heuristic algorithms.

The mathematical formulae and the heuristic procedures proposed in this paper provide a fundamental approach for the investigation of dynamic OAS problems in on-demand production with PBF systems. Firstly, the problem is formulated mathematically based on the analysis of production with PBF systems where the dynamic release time and due date of orders have been taken into account to reflect the realistic production scenarios. The calculations of production time, cost, and profit of an AM job in the model are parameterized with the realistic attributes of parts and AM machines. Therefore, the proposed approach could be adopted in real industrial production with limited modification. Secondly, the proposed heuristic procedures for the generation and confirmation of feasible AM jobs provide a practical approach to solve the dynamic OAS problem in on-demand production with PBF systems. The final decision on the acceptance and scheduling of a part order is instantly made by the machines and the service provider cooperatively under constraints of machines’ capacities as well as orders’ release time and due date. The experimental results indicated that the proposed heuristic procedures work properly and different selective behaviours lead to significant differences both in APT and total profit. Regarding the 100 schedule results generated through random selection for each problem, the best schedule results are approximately 59 and 50.5% higher in APT and total profit, respectively, compared to the worst results. Thirdly, the experimental results indicated that it is practicable to obtain promising APT as well as total profit through dynamic decision-making on the acceptance and scheduling of on-demand production orders applied with proper decision-making strategy sets. Regarding the performance indicator defined in Section 5.3, the best performance for each problem might be presented by a different decision-making strategy set. However, on average, the GPMS-LPPT decision strategy set presented the best performance for all 20 problems both in APT (129.1%) and total profit (136.7%). Last but not least, the experimental results indicated that the change in the market demand and the promised due date will affect the performance of a decision-making strategy set. The decision-making strategy sets of GPPT-LFIFO or GPMS-LFIFO will present the best schedule results in problems with less demand, while one of the other decision-making strategy sets will present the best results when there is sufficient demand. For a particular decision-making strategy set (e.g., GPMS-LPMS), the value of APT for all the 20 problems increases significantly when the promised due dates are increased from 1 day to 7 days. This is because the longer due date allows wider available time slot for an AM job to consider more part orders. However, if the promised due date is too long, the value of APT might decrease because more idle time might be caused when the machine prefers waiting for more part orders to maximize the utilization of its capacity.

As an attempt to address the dynamic OAS problem in on-demand production with PBF systems, the proposed approach and findings will open up research opportunities regarding production problems in industrial AM production field. First, the mathematical expressions proposed in this paper can be further extended by considering true shape 2D/3D nesting algorithms to cover more industrial AM processes such as Selective Laser Sintering (SLS) and binder jetting (ASTM:F2790-12a). Also, the cost structure of production with AM machine can be further refined by considering the idle time costs and materials changing costs of each AM machine for practical applications. Second, although the difference in schedule results has been demonstrated through random selection with proposed heuristic procedures, optimization algorithms are expected to solve the model optimally to find out the exact best and worst results for the evaluation of proposed decision-making strategies. Third, further investigation on the selective behaviours in decision-making on the acceptance and scheduling of on-demand production orders should be carried out to discover appropriate decision-making strategies according to the market situations. It has been proved in this paper that it is practicable to solve the dynamic OAS problem in on-demand production with PBF systems through the dynamic selection of part orders and confirmation of AM jobs based on a proper decision-making strategy set. However, advanced methodologies based on machine learning and/or bio-inspired algorithms are expected for the development of optimal decision-making strategy sets. Furthermore, within an on-demand production environment where multiple service providers exist, the competition among service providers may be taken into account in future research. The problem will be more complex and challenging where the service providers should make attractive offers to compete for as many profitable orders as possible to maximize the average profit-per-unit-time while the decision on acceptance of offers would be made by customers. Therefore, the decision-making strategies for both service providers and customers should be investigated and a novel simulation-based heuristic approach needs to be developed to solve the problem efficiently.