SCHEDULING PRODUCTS WITH BILLS OF MATERIALS USING AN IMPROVED LAGRANGIAN-RELAXATION TECHNIQUE

A bill of materials specifies the sequence in which parts are to be processed and assembled in order to manufacture a deliverable product. In practice, a bill of materials may be quite complex, involving hundreds of parts to be processed on a number of limited resources, making scheduling difficult. This has forced many practitioners to turn to Material Requirements Planning and heuristic rules to perform scheduling. These methods are seldom integrated, however, resulting in unreliable completion times for products and, hence, low customer satisfaction. This paper addresses the issue of integrally scheduling parts that are related through a bill of materials for the purpose of improving the on-time performance of products as well as reducing work-in-process (WIP) inventory. The technique presented here is based on an existing Lagrangian relaxation (LR) approach for the scheduling of independent parts in a job shop. The current problem, however, is more complicated than the job shop problem because of the constraints between parts, imposed by the bill of materials. In order to make Lagrangian relaxation a viable approach to this problem, an auxiliary problem formulation with a modified subgradient method are adopted to improve the computation time of the existing LR approach. This improved LR approach allows the bill of material constraints to be considered directly in the problem formulation. Results to date show that the above integration improves product tardiness and WIP levels, compared to techniques that do not integrate the bill of material constraints into the product scheduling problem. The improved ability of a manufacturer to meet promised delivery dates for products by the above integration will ultimately enhance its credibility and competitiveness in the marketplace.