Reducing Product Tardiness in Optimization-Based Scheduling

A bill of materials details the structure of parts and raw materials required to manufacture a deliverable product. Scheduling products with bills of materials is an extremely difficult task because of the problem complexity. Many approaches attempt to decompose the task into manageable subproblems by assigning due dates to parts, for example, and then solve the subproblems independent of each other. This often yields schedules in which products are tardy as a result of the tardiness of one or two component parts. In this paper, a simplified situation is considered where products comprised of single operation, parallel parts with final assembly are to be scheduled on identical, parallel machinies. Two approaches are presented which integrate subproblems through the bill of materials in order to reduce product tardiness. In one approach, a heuristic reduces product tardiness by modifying part due dates (or priorities) based upon part tardiness obtainied from an initial schedule. The initial schedule is generated by an existing technique based on Lagrangian relaxation. Results indicate that product tardiness can be improved significantly using this heuristic approach. In the second approach, the problem of schedulinig products is formulated as a constrained minimization problem, where the bill of materials is modeled as another set of constraints. The problem is solved by relaxing the bill of material constraints, and the method is currently being tested.