Scheduling additive manufacturing systems: Complexity and algorithms to minimize the number of late parts
研究了增材制造中嵌套与调度问题，证明最小化延迟零件数量是强NP难问题，并开发了两种高效算法，平均性能在最优下界的7%以内。
Additive manufacturing (AM) is a process by which three-dimensional products are made via the addition of material in a layer-by-layer fashion. This manufacturing technique is growing in commercial usage, given its advantages in creating very dense or complex geometries as well as highly customizable components. In healthcare, for example, AM can be used to improve patient outcomes by providing timely medical devices (or parts) required for treatments. Minimizing the number of late parts in this context will directly improve the patients’ welfare. This paper studies the nesting and scheduling problem within the AM context and shows that the problem of minimizing the number of late parts is strongly NP-hard even if the nesting of parts into jobs is given. We also develop efficient algorithms to minimize the number of late parts, both when nesting is fixed beforehand and when nesting is part of the algorithm. The theoretical results, including algorithm performance bounds, developed in this paper are new contributions to the literature. An extensive computational study evaluates the performance of both algorithms. The nesting and scheduling algorithm performs within 7% of the lower bound on average and shows an effective way to nest and schedule systems containing challenging problem instances. Providing efficient, high-performing algorithms such as these will allow AM managers to quickly schedule parts for AM production with a minimum number of late parts and consequently improve both customer satisfaction and the profitability of the firm.