Fixed pre-assembly scheduling on multiple fabrication machines

This paper considers a scheduling problem to minimize total weighted completion time at a fixed pre-assembly stage composed of multiple fabrication machines. In the fixed pre-assembly stage, each component part is machined on a fabrication machine specified in advance. The completion time of a product is measured by the latest completion time of its all components at the pre-assembly stage. Minimizing the total weighted completion time of a finite number of products is considered as the scheduling measure. Two lower bounds are derived and tested in a branch-and-bound algorithm. Also, an efficient greedy-type heuristic algorithm is developed to generate near-optimal schedules. Numerical experiments are performed to evaluate the performance of the proposed branch-and-bound and heuristic algorithms.