Minimizing total weighted completion time at a pre-assembly stage composed of two feeding machines

This paper analyses a deterministic scheduling problem concerned with manufacturing two types of components at a pre-assembly stage which consists of two independent feeding machines each producing its own type of component. Each type represents a unique component which may have variations in its size or quality. Therefore, the completion time of each component depends on both its type and quality (size) variations. Such manufactured components are subsequently assembled into various component-dependent products. The problem has the objective measure of minimizing the total weighted completion time of a finite number of jobs (products) where the completion time of each job is measured by the latest completion time of its two components at the pre-assembly stage. The problem is shown to be NP-complete in the strong sense. A WSPT rule coupled with a machine-aggregation idea is developed for good heuristics which show the error bound of 2. Some empirical evaluations for the average-case performance of the heuristics are also performed.