|Abstract or Summary
- This research considers a combinatorial optimization scheduling problem in the assembly of printed circuit boards (PCBs) in electronic manufacturing. For the first time in this research, the preparation process, which is typically called kitting operation, is paid attention to and is performed along with the assembly operation, described in this research as "integrating internal (assembly) and external (kitting) operations". In doing so and as a proposition, the role of kitting staff is completely eliminated and kitting is assigned to be performed by the machine operator when he is idle. In other words, the kitting operation required by the next group is performed by the machine operator during the assembly time of the current group. Unlike all of the traditional research, which assume boards to have static arrival times, a dynamic PCB assembly system is investigated in this research which shares some of the characteristics of just-in-time manufacturing systems. The scheduling objectives comply with the producer and customers' expectations simultaneously by minimizing the weighted flow times and weighted tardiness of boards. Both objectives are highly affected by the arrangements of boards within the groups and the groups themselves. To assemble a group on a machine, a setup operation is required, implying its existence between any two consecutive groups. In contrast to the previous research on PCB manufacturing, the setup dependency is not only on the immediately preceding scheduled group, but also is carried over all throughout the previously scheduled groups, starting with the first group in the sequence. In this setup, namely the carryover sequence-dependent setup, the type and different arrangements of the previously scheduled groups determine different setup times for transferring to the next group.
Given the possibility of considering either a single machine or a multi-machine problem, two different research problems are investigated, respectively, in Phases 1 and 2 of this research. For the problem in Phase 1, a Branch-and-Bound (B&B) algorithm along with a lower bound and an approach to identify repeated solutions are developed. In Phase 2, three mixed-integer linear mathematical programming models, referred to as MILP1, MILP2 and MILP3, that can optimally solve the problem are developed. The research problem being NP-hard in the strong sense, the mathematical models are incapable of optimally solving even medium-size problems. Thus, two very fast and effective heuristics, named CFIM1 and CFIM2 (Cycle Forward Improving Moves), are developed and compared against a version of Tabu Search (TS) algorithm, also developed in this research. Algorithmically evaluating the objective function in the heuristics is an essential part of this research. For this purpose, a very effective decision tree-based algorithm, called OFDT (Objective Function Decision-Tree) that can be integrated with the heuristics is developed.
As evaluating the effectiveness of the heuristics by finding optimal solutions is nearly impossible, a lower bounding mechanism based on the concepts of Column Generation and Branch-and-Price (B&P) is developed. The sub problems of the column generation problem are still complex that cannot be optimally solved in large-size problems. Thus, several optimal properties are developed to simplify solving the sub problems. For the algorithms and approaches developed in each phase, a comprehensive statistical analysis is carried out by solving several problem instances and the results are reported.