Analysis of irregular three-dimensional packing problems in additive manufacturing: a new taxonomy and dataset

With most Additive Manufacturing (AM) technology variants, build processes take place inside an internal enclosed build container, referred to as a ‘build volume’. It has been demonstrated that the effectiveness with which this volume is filled with product geometries forms an important determinant of overall process efficiency in AM. For effective operations management, it is important to understand not only the problem faced, but also which methods have proved effective (or ineffective) for problems with these characteristics in the past. This research aims to facilitate this increased understanding. The build volume packing task can be formulated as a three-dimensional irregular packing (3DIP) problem, which is a combinatorial optimisation problem requiring the configuration of a set of arbitrary volumetric items. This paper reviews existing general cutting and packing taxonomies and provides a new specification which is more appropriate for classifying the problems encountered in AM. This comprises a clear-cut problem definition, a set of precise categorisation criteria for objectives and problem instances, and a simple notation. Furthermore, the paper establishes an improved terminology with terms that are familiar to, but not limited to, researchers and practitioners in the field of AM. Finally, this paper describes a new dataset to be used in the evaluation of existing and proposed computational solution methods for 3DIP problems encountered in AM and discusses the importance of this research for further underpinning work.     

Optimal layout design of a satellite module

Layout design of a satellite module directly concerns its structure, performance, service life, and cost of assembly and maintenance. It is an important and NP-complete problem. The main difficulties consist of combinatorial optimizations in mathematics and system complexity in engineering practice, and relevant researches are far from enough. This paper proposes a basic solution strategy for the optimal layout design of a satellite module, which consists of two stages, global (or loose) layout design and detailed layout design. Corresponding algorithms are then developed while taking the layout design of an international commercial communication satellite as an example. They are the centripetal balancing method for global layout design and a quasi Traveling Salesman Problem (TSP) model-based Ant Colony Optimization (ACO) algorithm for layout optimization. The proposed method demonstrates its feasibility and validity on an application instance. Existing problems and further research directions are finally discussed.     

基于分组策略的多目标三维装箱算法

目的 针对现有三维装箱算法优化目标单一、优化效率低的问题,提出适用于求解大规模货物装载问题的多目标装箱算法,以提高装箱规划效率,确保货物运输安全。方法 考虑5种现实约束条件,以体积利用率和装载垛型重心偏移量为优化目标,建立多目标货物装载优化模型。采用拟人式装箱对货物进行预分组,减小决策空间,然后结合分组信息与装箱算法生成初始解;引入数据驱动的装箱交叉算子提高算法收敛性;设计多策略变异算子提高算法结果的多样性。结果 以公共数据集和真实航空货物数据作为实验数据进行实验。实验结果表明,在满足多种约束条件下,集装箱装载强异构货物平均体积利用率达到92.0%,重心位置空间偏移从20 cm减少到7.5 cm,并且算法运行时间减少了73.5%。结论 本文所提算法应用于求解大规模多目标三维装箱问题,提高了装箱质量和效率,可为三维装箱算法的工程应用提供参考。     

考虑装载顺序约束的航空货物装箱问题研究

目的 以航空货运背景下流水线上货物的装箱问题为研究对象,旨在最大化地利用集装箱装载空间.方法 在考虑货物装载顺序、质量、体积、不重叠、稳定性等一系列现实约束的条件下,建立集装箱堆码模型,设计一种拟人启发式与遗传相结合的组合启发式算法.首先通过设定规则并赋予权重,得到有序可放置点集合,采用拟人启发式算法构建货物装载策略,得到初始装箱方案;然后通过遗传算法中的交叉、变异操作对方案进行寻优,在可行方案中选出集装箱空间利用率最大的装箱方案;最后采用某机场物流公司的实际货物数据进行实验,并实现装载方案的可视化.结果 相较于混合模拟退火算法,组合启发式算法收敛性好,搜索速度快,能够在较短的时间内得到空间利用率较高的装载方案,货物垛形规划更为紧凑,稳定性更高.结论 所提算法对于不同种类的货物有着更好的适应性,能够实现强异构货物的合理布局,保证了货物装载过程中垛形的稳定性,可为航空货物装箱问题的工程应用提供参考.     

求解集装箱装载问题的混合蚁群模拟退火算法

目的 针对物流行业中存在的大规模、复杂、多规格货物的集装箱装载问题,提出一种基于塔装载启发式算法、二维装载点启发式算法、蚁群模拟退火算法的混合算法。方法 首先,采用塔装载启发式算法将三维待装箱装载成塔集,即将三维装箱问题降为二维装箱问题,有效降低集装箱的装载规模;其次,蚁群算法通过融入信息素选择更新策略,并利用自适应信息素挥发系数来提升算法整体的收敛速度,同时结合模拟退火算法对每代优秀路径集进行局部搜索,避免算法因收敛过快而陷入局部最优;最后,将蚁群模拟退火算法与二维装载点启发式算法相结合,优化每座塔的装载顺序和放置姿态,寻找最优的装载方案。结果 实验证明,在250组算例中,采用混合算法后,集装箱的平均空间利用率为90.92%,优于其他3种对比算法。结论 设计的混合蚁群模拟退火算法适用于解决大规模集装箱装载问题。     

连接不相交线段成简单多边形(链)的算法

提出一个实际问题，即如何连接平面上h条线段成一简单多边形或者简单多边形链，并证明了连接平面上线段集S成一简单多边形链的一个充分条件，S中有一条线段连接凸壳CH（S）中不相邻顶点，另外还提出了连接平面上线段集S成一简单多边形或者简单多边形链的算法，其基本思想是首先逐层计算线段集S的凸壳，并将这些凸壳改变多边形；然后计算各多边形之间的交点，进而删去这些交点。最后合并若干个简单多边形为一个简单多边形，当S中线段数目n较大时，用分治思想可以设计分治算法，较好地求解了这个问题，利用计算机求解这个问题上有实际应用价值。     

Hybrid Approach to Optimal Packing Using Genetic Algorithm and Coulomb Potential Algorithm

It is difficult and computationally time-consuming to find the best possible solutions for blank packing problems, because they include a lot of underlying combinational conditions. This paper presents two approaches for packing two-dimensional irregular-shaped polygonal elements—a real-encoded genetic algorithm and a hybrid algorithm using a real-encoded genetic algorithm and a local optimization algorithm. The local optimization algorithm presented is a novel one utilizing the Coulomb potential technique.

In the hybrid approach, the real-encoded genetic algorithm generates the order of the polygons while the coulomb potential algorithm determines the embodiment layout under the fixed combinations so as to minimize the scrap. The hybrid genetic algorithm is found to give better results for problems of larger size although it takes more computational time.     

基于视觉认知特性的作战显控界面信息结构布局研究

目的 智能化作战趋势相应地会对在作战显控系统界面的信息量和信息呈现内容提出要求。针对未来态势环境下显控界面信息结构更为复杂,且融入更多信息的显控系统界面需要不断迭代的问题,从显控界面的信息结构分类展开实验研究,设计不同的信息结构布局类型,从而进行认知绩效的视觉搜索测评实验。方法 通过文献分析,从认知特性与界面信息架构布局、飞行员的认知行为等方面出发,对相关成果进行综述梳理。运用眼动追踪实验,设计针对不同任务的视觉搜索实验,从而对不同信息布局形式的认知绩效进行评估测量。结果 实验结果表明,在“作战”与“导航”任务场景中“纵向任务栏型”布局形式整体更优于“横向主图型”任务布局。在“作战”任务中,纵向三分类型布局形式的绩效水平更优;在“导航”任务中,纵向二分类型布局形式的绩效水平更优。结论 针对复杂显控作战界面的信息呈现,可以通过设定与作战任务相匹配的不同结构布局来优化信息模块的合理分配方式,对后续在作战显控界面的信息模块布局设计优化起到一定参考作用。     

基于蚁群算法的军用车辆器材装箱配载问题

目的对军用车辆器材装箱配载问题进行合理优化,以提高集装箱的空间利用率。方法阐述了军用车辆器材装箱配载问题的重要性,并对装箱配载问题进行理论分析,应用蚁群算法建立数学模型和实现流程,通过实例分析验证该算法的合理性。结果利用蚁群算法模拟与优化装箱配载问题使集装箱利用率达到了88.96%,并确定出了最优的装箱配载方案。结论蚁群算法能够对军用车辆器材装箱配载问题进行合理优化。     

Scaled boundary polygons with application to fracture analysis of functionally graded materials

This study presents a framework for the development of polygon elements based on the scaled boundary FEM. Underpinning this study is the development of generalized scaled boundary shape functions valid for any n‐sided polygon. These shape functions are continuous inside each polygon and across adjacent polygons. For uncracked polygons, the shape functions are linearly complete. For cracked polygons, the shape functions reproduce the square‐root singularity and the higher‐order terms in the Williams eigenfunction expansion. This allows the singular stress field in the vicinity of the crack tip to be represented accurately. Using these shape functions, a novel‐scaled boundary polygon formulation that captures the heterogeneous material response observed in functionally graded materials is developed. The stiffness matrix in each polygon is derived from the principle of virtual work using the scaled boundary shape functions. The material heterogeneity is approximated in each polygon by a polynomial surface in scaled boundary coordinates. The intrinsic properties of the scaled boundary shape functions enable accurate computation of stress intensity factors in cracked functionally graded materials directly from their definitions. The new formulation is validated, and its salient features are demonstrated, using five numerical benchmarks. Copyright © 2014 John Wiley & Sons, Ltd.     

基于分层加权的多边形图形匹配

提出了一种适用凸凹多边形匹配的分层加权测度方法，在此方法中，对凹多边形、首先进行基于提取凸多边形的模式分解，对凹多边形添加辅助线，形成新的外接凸多边形、通过依次抽取外接凸多边形，将凹多边形表达为仅由凸多边形组成的多层拓扑结构，然后，利用预先定义的互为模板的相似度量准则和分层加权测度模型，计算得到多边形的相似度系数，从而实现凹多边形的匹配和检索。     

弹药外包装箱标志的探讨

目的探讨我国弹药外包装箱标志的设计方案,使弹药外包装箱标志满足国际民用航空运输要求。方法在保留现有弹药包装文字标志、军用物资图示标志、储运图示标志、危险物资图示标志以及弹药特殊标志的基础上,按照国际民航组织制定的《危险品航空安全运输技术细则》,融入关于爆炸品的基本标记、附加标记、UN规格包装标记和危险性标签、操作标签的设计要求。结果将弹药外包装箱正面布局为军用标志区,背面布局为民航运输标记与标签区,左、右端面为军用与民航共用标志区的设计,实现了在一个包装箱上集成军用与民航所要求的所有信息。结论经过重新布局的弹药包装箱标志与标签,既符合了国家军用标准的要求,也满足了国际民航安全运输的要求。     

Book reviews

In many current semiconductor manufacturing operations, headcount is manually allocated periodically based on man-machine ratio. Attributed to non-optimised allocation of direct labour to operations/machines, considerable productivity loss occurs. The problem is further complicated by some dynamic and uncertain factors such as constantly changing production targets and work in progress, overlapped labour skills, and variability in manufacturing operations and labour absenteeism rates. Motivated by the needs in real practice, this study aims to develop a model for allocating a direct workforce among semiconductor manufacturing operations to meet production targets and maximise labour productivity. This paper presents a two-stage goal programming model for the headcount allocation problem. To enhance the model's pragmatic use, a queueing module is introduced to account for the interferences among the multi-machine operations. Computational experiments are carried out to evaluate the performances of the proposed algorithms and pilot runs are implemented in a factory. Finally, a prototype system is developed and has been proved to be useful in practice.     

Combination of Lean value-oriented conception and facility layout design for even more significant efficiency improvement and cost reduction

Global market competition and fluctuating customers’ demands require manufacturing enterprises to focus on cost reduction and efficiency improvement to increase competitiveness and sustainability. The purpose of the research was the elaboration of the methodology and procedure of a new combined efficiency improvement method which basically applies Lean methods and also uses the facility layout design (FLD) method simultaneously, integrating the different advantages of these methods, which is even more efficient that applying each of the methods individually. The main significant added-value of the study is the elaboration of a new combined method, which results in even more significant improvement of efficiency and several KPIs, furthermore, cost reduction, which is confirmed by a real case study for the improvement of a manufacturing plant. In the case study, the application of 13 Lean methods and the FLD method (which aims at the minimisation of material workflow, travel distance of materials, material handling cost and space used for assembly) led to the improvement of 10 quantitative and 5 qualitative indicators: productivity; cycle-time; number of workstations and operators; WIP (work-in-process) inventories; space used for assembly; material workflow; travel distance of materials; material handling cost; labour cost; component supply; products’ quality; transparency; standardisation; workplace ergonomics.     

离散度参数对规则多边图形认知工效的影响

本研究用实验方法研究离散度参数对规则多边图形认知工效的影响。实验的自变量是图形的离散度参数，因变量是各离散度图形信号的反应时。实验的刺激材料是２５个离散度为０．３～０．７的规则多边图形。刺激材料的呈现与被试的反应记录都由计算机控制。结果表明：离散度适中（０．５左右）及偏小的图形信号认知工效较高，离散度从０．５增大到０．６，认知工效迅速下降，离散度继续增大，认知工效仍有下降，但趋势平缓。     

Solving an apparel trim placement problem using a maximum cover problem approach

A trim placement problem from the apparel industry is presented and solved. The problem is related to cutting and packing problems, which have received attention in the literature for close to 40 years. The problem is motivated by a pants layout problem involving irregularly-shaped pieces. A two-stage strategy is commonly employed, with large pieces, or panels, arranged first, followed by smaller pieces, or trim. This paper assumes the panels have been arranged, and presents an approach for placing the trim pieces into unused “containers” of the stock material. Groups of trim pieces are first generated using existing polygon containment algorithms. Then, groups are assigned to containers to maximize a weighted function of the trim pieces. The mathematical programming formulation is developed, which is a generalization of the Maximum Cover Problem, a well-known problem in the location literature. Due to wide variability in branch and bound solution times, a Lagrangian Heuristic incorporating an improvement heuristic is developed. Computational experience demonstrates the effectiveness of the Lagrangian Heuristic on real pants markers. The optimal solution is found for all, and solution times are less than branch and bound in 10 out of 12 problem instances (considerably less in three), and only slightly more in the other two. Times are also less variable than branch and bound, an important characteristic with an interactive layout system.     

Solving the container pre-marshalling problem using variable length genetic algorithms

In container terminals, the yard area consists of a set of blocks, which consists of a set of bays. Each bay consists of a set of stacks, which consists of a set of tiers. In the container pre-marshalling problem, an initial layout of a bay is converted to a final desired layout. The final layout follows the given loading schedule of this bay. This has a direct impact on the most important container terminal performance measure: the vessel loading time. The deviation between the current layout and the desired layout is expressed by the value of the mis-overlays. The objective of the pre-marshalling problem is to eliminate the mis-overlays with the minimum number of container movements. In this article, a variable chromosome length genetic algorithm was applied to solve the problem. The results of the new solution approach were compared against benchmark instances and the results were remarkably better.     

基于形心与顶点连线表示的多边形变形

研究了平面多边形变形问题。从几何角度出发,采用形心和形心与各顶点的连线来描述多边形。根据两多边形的形心—顶点连线长度及相邻连线之间的夹角给出匹配度函数,并以此来建立两多边形顶点之间的对应。线性插值对应连线的长度和相邻两连线之间的夹角,得到中间融合多边形相应的几何信息,然后按照给定方法顺时针依次生成中间多边形各顶点。实现了一般平面多边形的自然变形。     

Heuristic Programming in Spatial System Design

A link is needed to transform and to demonstrate the methodology of heuristic programming to the environment of spatial systems design. A class of problems is proposed which appears to be particularly suitable for this purpose. These problems relate to complex decisions in which the allocation and use of space is a critical dimension. This paper describes a game which may be viewed as an abstraction of real systems involving the packing of smaller items into a larger space; i.e., problems somewhat similar to the knapsack problem. The game has been invented as a means of focusing the attention of student designers on “real” games as opposed to parlor games. A computer implementation of a space game is described which provides for the addition and testing of subroutines incorporating heuristics for making decisions in design problems related to space.     

一刀切约束下的二维装箱问题高效求解算法

目的 为实现大规模物料的快速剪裁切割,对考虑一刀切约束的二维装箱问题进行研究,并构建相应的改进优先度算法IPH(Improved Priority Algorithm,IPH).方法 IPH能够在不需要任何迭代搜索下,直接进行剩余空间分割与填充.为此,发展PH算法中的优先度放置规则,并以最大化生成大空间面积和最小化生成小空间面积为基础,设计改进砌砖式空间分割策略.结果 针对标准数据集的对比实验表明,IPH能够在较短时间内完成大规模算例的高效求解,并首次获得了多个算例的最优填装效果.结论 基于概率较优的启发式求解方法,能够实现无迭代优选下的一刀切二维装箱问题直接求解,且运算效果令人满意.