In this paper, we present an approach to weighted tardiness job-shop s
cheduling problems (JSP) using a graph decomposition technique, Our me
thod decomposes a JSP into a series of sub-problems by solving a varia
nt of the generalized assignment problem which we term ''VAP.'' Given
a specified assignment cost, VAP assigns operations to mutually exclus
ive and exhaustive subsets, identifying a partially specified schedule
, Compared to a conventional, completely specified schedule, this part
ial schedule is more robust to shop disturbances, and therefore more u
seful for planning and control, We have developed assignment heuristic
s which iteratively update the problem parameters using lower and uppe
r bounds computed from the corresponding schedule, The heuristics are
tested on standard test problems. We show that the proposed approach p
rovides a means for extending traditional scheduling capabilities to a
much wider spectrum of shop conditions and production scenarios.