DECOMPOSITION HEURISTICS FOR ROBUST JOB-SHOP SCHEDULING

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.