Group-scheduling problems in electronics manufacturing |
| |
Authors: | Cumhur A Gelogullari Rasaratnam Logendran |
| |
Affiliation: | (1) Department of Industrial Engineering, Korea Advanced Institute of Science and Technology, 373 1 Kusong Dong, Yusong Gu, Taejon, 305 701, Korea;(2) ETRI, 161 Kajong Dong, Yusong Gu, Taejon, 305 350, Korea;(3) Telecommunication Network Lab, Korea Telecom, Junmin Dong, Yusong Gu, Taejon, 305 390, Korea;(4) Telecommunication Network Lab, Korea Telecom, Junmin Dong, Yusong Gu, Taejon, 305 390, Korea |
| |
Abstract: | This paper addresses the flowshop group-scheduling problems typically encountered in the assembly of printed circuit boards
in electronics manufacturing. A mathematical programming model is formulated to capture the characteristics inherent to group-scheduling
problems experienced in electronics manufacturing as well as those common to a wide range of group-scheduling problems encountered
in other production environments. Several heuristics, each incorporating different components that underlie the tabu search
concept, are developed to solve this strongly NP-hard problem effectively in a timely manner. In order to investigate the
quality of the heuristic solutions with respect to tight lower bounds, an effective and efficient decomposition approach is
developed. The problem is decomposed into a master problem and single-machine subproblems, and a column generation algorithm
is developed to solve the linear programming relaxation of the master problem. Branching schemes, compatible with the column
generation subproblems, are employed to partition the solution space when the solution to the linear programming relaxation
is not integral. Furthermore, tabu search based fast heuristics are implemented to solve the subproblems, and an effective
stabilization method is developed to accelerate the column generation approach. An experimental design with both fixed and
random factors accompanied by rigorous statistical analyses of computational tests conducted on randomly generated test problems
as well as on a large size real industry problem confirm the high performance of the proposed approach in identifying quality
lower bounds and strongly suggest its flexibility and applicability to a wide range of real problems. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|