布局问题概述：优化网页排版的重要性

布局问题的研究与Cutting & Packing问题的研究密不可分，此类问题开始于1964年的Dyckhoff对Cutting和Packing问题研究，Dyckhoff分析了Cutting和Packing问题的基本逻辑结构，认为空间布局问题也属于Cutting和Packing问题，并在广义上同背包问题、调度问题、分配问题等具有相同的逻辑结构和理论本质，同属于一类NP-hard或NPC问题。而本书研究航天器舱根据空间布局问题定义描述，亦可归属于空间布局问题。

布局问题广泛地存在于人类生产和生活中，近年来，不同领域、专业的空间布局问题研究越来越深入，主要集中在3个方面的研究：一是布局求解算法或方法；二是布局问题求解策略或框架；三是专业布局系统；目前对布局问题常用求解方法的研究主要包括这几方面：一是采用传统的数学规划法；二是利用启发式规则；三是借助于人工智能和演化计算技术，其中演化计算在解决此类问题时效果较好，但随着问题求解规模和求解复杂性的增加，算法的求解能力还是有限的。因此有必要从求解策略上进行深入研究，如近几年在其他领域发展起来的人机结合思想、多学科优化设计和协同进化等思想在布局设计领域开始为人们所关注，并取得了初步研究成果。尽管Dyckhoff试图找出一种用于求解布局问题的通用算法，但是特定的目标或约束等因素使得不同现实问题之间相差很远，所以找出通用算法是很困难的。Cagan等认为应针对不同的专业应用领域，研究相应的专用算法。基于此原因，同时针对本书研究的布局问题的三重求解难度，因此有必要研究新的求解框架与高效求解方法，将它们结合以求解本文的复杂布局问题。

而对于布局问题实用化技术的研究，目前国内外研究者主要开发专业的布局设计系统，主要集中在集成电路布局、版面布局、建筑平面设计、车间设备布局等领域，如VLSI布局设计系统GORDIAN、Ritual/Tiger；版面设计系统ADDI、UIDE；建筑布局系统EDGE、WRITE、ABD、ARCHIPLAN；车间布局系统FactoryOpt、VIP-PlanOpt等。而与本章工作密切相关的几类代表性的空间布局问题主要有2002年美国Carnegie Mellon大学著名学者Cagan和2004年美国Clemson大学著名学者Fadel分别研究的一类带性能约束的发动机舱、热力泵和小卫星舱内组件的复杂布局设计问题（如图1.4所示），其代表了带性能约束复杂布局问题研究的当前国际水平。但因问题求解的复杂性，他们研究问题规模较小，一般为10余个待布物。

(www.xing528.com)

图1.4　一类带性能约束的复杂布局设计问题

（a）汽车发动机舱布局设计；（b）热力泵布局/布线设计；（c）小卫星舱内组件布局设计
1—横向阀；2—压缩机；3—输入/输出阀；4—储蓄器

综上所述，不同领域、不同专业的布局设计问题的研究取得了一定的成果，除在建筑平面布局、车间设备布局、集成电路布局等几类布局空间和待布物形式比较规则、布局设计条件描述明确、定量化程度较高的布局问题的理论研究和工程应用比较深入和成功外，其他领域布局问题研究尚有待深入，尤其是诸如机械装备、航空航天器这类复杂工程系统的布局设计问题。

鉴于布局问题研究的现状，本书侧重于航天器舱布局设计问题求解方法和实用化布局设计系统的研究，本书认为基于人机结合的思想，研究新的求解框架与高效求解方法，将它们结合有助于复杂问题的求解，同时为使所研究的布局设计方法达到一定的工程实用化，有必要结合现有的三维仿真软件，将布局设计方法与三维仿真软件相结合，开发具有一定工程实用化的布局优化系统。