| In this dissertation, a typical situation in the assembly of printed circuit boards is investigated. The planning problem faced is how to assemble boards of different types using a single line of placement machines within a stochastic environment. Specifically, we are interested in determining the component partitioning (or line configuration) and board type sequencing under the demand and/or capacity uncertainty such that the expected makespan is minimized. We propose two different strategies, namely the "fixed-line" and "partial setup" strategies, along with their respective stochastic models for this problem. Under the "fixed-line" strategy, the line is configured only once at the beginning of a production run so as to eliminate setups between board types. Under our assumptions and choice of performance measure, the board sequencing becomes irrelevant. The problem then becomes to partition component types to different machines in order to process all boards quickly with a good workload balance. The "partial setup" strategy includes "fixed-line" strategy as well as other common strategies found in literature and in practice as special cases. Under this strategy, the board sequencing and component partitioning are solve simultaneously while taking into account all possible scenario realizations. Unfortunately, the computational experimentation indicates that it is impractical to solve these models optimally when the problem instances are large. Therefore, we develop two tabu search algorithms, one for each model, in hope to obtain good feasible solution in a computationally inexpensive way. Computational results indicate that the running time of the proposed algorithms is extremely fast and the quality of the solution obtained is excellent. Furthermore, there is only a modest growth in computational effort as the problem size grows. Hence much larger problems may be successfully solved with a reasonable assurance of obtaining good solutions. |
