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

这项学术与行业联络资助机会（GOALI）奖项支持为两个不同的问题领域开发一个框架，该框架由模型和有效的解决方案算法组成。一种是多阶段、序列相关的组调度问题，具有结转设置，另一种是无结转设置。前者适用于印刷电路板（PCB）组装，而后者适用于硬件（离散部件）制造，例如由细胞制造支持的制造。重点是开发真正反映实际操作约束的调度模型。在两阶段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.