GOALI/Collaborative Research: Scheduling Methodologies for Electronics and Hardware Manufacturing

GOALI/协作研究：电子和硬件制造的调度方法

• 批准号: 0010118
• 负责人: Rasaratnam Logendran
• 金额: $ 20.54万
• 依托单位: Oregon State University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-07-01 至 2005-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0010118&HistoricalAwards=false
• 关键词: GOALI; Collaborative; Research; Scheduling; Methodologies

This Grant Opportunities for Academic Liaison with Industry (GOALI) award supports the development of a framework, comprised of models and efficient solution algorithms, for two different problem domains. One that is characterized as multi-stage, sequence-dependent group scheduling problem with carry-over setups, and the other with no carry-over setups. Applications of the former exist in printed circuit board (PCB) assembly, while the latter is applicable in hardware (discrete parts) manufacturing such as those supported by cellular manufacturing. The emphasis is on the development of scheduling models that truly reflect real operational constraints. In a two-stage PCB assembly process, these include performing the setup required on either stage based on a surrogate board group representing all board types, and performing the setup on the second stage in anticipation of the arriving board group. The impact of carry-over sequence dependency is assessed by recognizing that the setup time required of a surrogate board group on either stage is dependent upon the entire set of preceding surrogate board groups that have so far been processed. A variety of performance measures including the minimization of total completion time, mean flow time, and weighted tardiness will be considered in order for the producer to be highly responsive to a variety of customer needs. Recognizing that both problems belong to a class of notoriously difficult 'NP-hard' combinatorial optimization problems, the structure of the problems will be exploited to develop efficient lower bounds. For the minimization of mean flow time, special cases will be investigated to identify those that can be optimally solved in polynomial time. For completely solving problem instances that have industrial merit, computationally efficient solution techniques that combine the underlying concepts of branch-and-bound aided by filtered-beam search, and tabu search will be developed and tested. The lower-bounding mechanisms will be embedded in these techniques to not only seek solutions with guaranteed quality, but also use them advantageously to terminate the search to enhance computational efficiency. For the total completion time minimization problem with no carry-over setups, an approach based on an equivalent formulation of the asymmetric generalized traveling salesman problem will be investigated. Finally, the solution techniques developed will be tested with data obtained from industrial collaborators to validate their computational efficiency and ability to obtain solutions with guaranteed quality. The successful completion of this project will provide both electronics and hardware manufacturing companies with methodological frameworks for rapidly generating schedules with guaranteed quantifiable performance. The insightful research findings so obtained will also enhance the existing graduate courses in scheduling at Oregon State University and University of Texas at Dallas.

这个赠款机会学术联络与产业（GOALI）奖支持一个框架的发展，包括模型和有效的解决方案算法，两个不同的问题域。一个是多阶段的，顺序相关的带结转设置的成组调度问题，另一个是没有结转设置。前者的应用存在于印刷电路板（PCB）组装中，而后者适用于硬件（分立部件）制造，例如由单元制造支持的那些。重点是发展调度模型，真正反映真实的业务约束。在两阶段PCB组装过程中，这些包括基于代表所有板类型的替代板组在任一阶段上执行所需的设置，以及在第二阶段上执行预期到达的板组的设置。通过认识到任一阶段上的替代板组所需的设置时间取决于到目前为止已处理的先前替代板组的整个集合，来评估结转序列依赖性的影响。各种性能的措施，包括最小化的总完成时间，平均流动时间，加权拖期将被考虑，以使生产商是高度响应各种客户的需求。认识到这两个问题属于一类众所周知的困难的“NP难”组合优化问题，将利用问题的结构来开发有效的下界。对于平均流时间的最小化，将研究特殊情况，以确定那些可以在多项式时间内最佳解决。为了完全解决具有工业价值的问题实例，将开发和测试联合收割机结合过滤束搜索辅助的分支定界和禁忌搜索的基本概念的计算效率解决方案技术。下界机制将被嵌入这些技术中，不仅寻求具有保证质量的解决方案，而且还使用它们有利地终止搜索，以提高计算效率。对于总完工时间最小化问题，没有结转设置，一种方法的基础上等价制定的非对称广义旅行商问题进行了研究。最后，开发的解决方案技术将使用从工业合作者获得的数据进行测试，以验证其计算效率和获得质量保证的解决方案的能力。 该项目的成功完成将为电子和硬件制造公司提供快速生成具有保证的量化性能的时间表的方法框架。这些富有洞察力的研究成果也将加强俄勒冈州州立大学和德克萨斯大学达拉斯分校现有的研究生课程。