论文部分内容阅读
二十一世纪,技术的进步、经济全球化以及市场环境的迅速变化使得制造型企业的经营环境变得日益复杂,传统的大批量生产逐渐转变为多品种、小批量以及客户定制的生产制造方式。为了快速响应客户的个性化需求,生产部门的生产排程计划制定变得越发困难和复杂,因此生产排程问题成为制造型企业急需解决的核心问题之一。论文以半导体某一段封装测试工艺过程为应用场景,研究如何调配有限的测试资源,搭建每一工艺步骤的资源配置要求,从而最大化完成所有测试工艺步骤的芯片数量。出于以下四个方面的因素,该问题非常复杂:(1)每一工序的资源配置要求不同;(2)各个工艺步骤共享所有的测试资源,而且这些测试资源都有数量限制;(3)改变工序的某种资源以满足该工序对应的特定的资源配置要求需要耗用一定的时间;(4)工序不同资源的重新配置时间不同,取决于需要改变的测试资源的类型。本文为该问题建立了非线性规划模型。文章将每一机台每一时刻所处的工序状态定义为决策变量,根据每工序所要求的资源配置要求,我们可以透过工序的变化来分析机台的资源配置的动态变化。因为机台两个连续时刻的状态相互影响,所以解的结构比较复杂,求解该非线性规划模型相对困难。本文在深度优先搜索规则的基础上,拟采用约束传播与值域搜索相结合的求解方法,即在约束传播的过程中嵌入值域搜索。这种基于约束规划的方法主要分为两个步骤:首先,通过问题自有的约束条件进行一致性检查,得到了问题的可行解空间,达到了对问题解空间的初步界定。接着,在可行解空间的基础上结合一定的理论证明与仿真实验的结果分析,添加了增强型的一致性检查条件,从而删除没有前途的分枝。数值结果表明:(1)对于小、中规模算例,本文提出的基于约束规划的分割算法可以在合理时间内得出最优解,但是对于大规模的算例其计算时间较长;(2)对于大规模的算例,本文提出的基于判断系统是否达到平衡态的方法能够得到近似最优解。