MINIMIZING TOTAL WEIGHTED COMPLETION-TIME AT A PRE-ASSEMBLY STAGE COMPOSED OF 2 FEEDING MACHINES

This paper analyses a deterministic scheduling problem concerned with manufacturing two types of components at a pre-assembly stage which co nsists 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 e ach component depends on both its type and quality (size) variations. Such manufactured components are subsequently assembled into various c omponent-dependent products. The problem has the objective measure of minimizing the total weighted completion time of a finite number of jo bs (products) where the completion time of each job is measured by the latest completion time of its two components at the preassembly stage . The problem is shown to be NP-complete in the strong sense. A WSPT r ule coupled with a machine-aggregation idea is developed for good heur istics which show the error bound of 2. Some empirical evaluations for the average-case performance of the heuristics are also performed. (C ) 1998 Elsevier Science B.V. All rights reserved.