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

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

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.