Mixed-Integer Linear Programming Model and Heuristic for Short-Term Scheduling of Pressing Process in Multi-Layer Printed Circuit Board Manufacturing

Abstract

The main stages of printed circuit board (PCB) manufacturing are the design, fabrication, assembly, and testing. This paper focuses on the scheduling of the pressing process, which is a part of the fabrication process of a multi-layer PCB and is a new application since it has never been investigated in the literature. A novel mixed-integer linear programming (MILP) formulation for short-term scheduling of the pressing process is presented. The objective function is to minimize the makespan of the overall process. Moreover, a three-phase-PCB-pressing heuristic (3P-PCB-PH) for short-term scheduling of the pressing process is also presented. To illustrate the proposed MILP model and 3P-PCB-PH, the test problems generated from the real data acquired from a PCB company are solved. The results show that the proposed MILP model can find an optimal schedule for all small- and medium-sized problems but can do so only for some large-sized problems using the CPLEX solver within a time limit of 2 h. However, the proposed 3P-PCB-PH could find an optimal schedule for all problems that the MILP could find using much less computational time. Furthermore, it can also quickly find a near-optimal schedule for other large-sized problems that the MILP could not solved optimally.

Keywords

• pressing process
• printed circuit board
• scheduling
• mixed-integer linear programming
• heuristic