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

Oregon State University, Corvallis OR

Investigators

Abstract

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.