Minimizing Total Weighted Completion Time at a Pre-assembly Stage Composed of Tow Feeding Machines

Abstract

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 preassembly 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. (C) 1998 Elsevier Science B.V. All rights reserved.