Scheduling of product families on multiple, identical parallel production lines to minimize setup costs

Monkman, Susan Kathleen
Journal Title
Journal ISSN
Volume Title

This dissertation addresses and solves a real-world production scheduling problem that was discovered early in 2003 at Dell, Inc.’s Morton L. Topfer Manufacturing Center (TMC). With continually increasing product variety and production volumes, TMC had reached the designed limits of the factory. When looking forward to 2004, TMC expected a volume increase of 20 percent and a doubling of product variety. Initially, no product family scheduling method was in place. This problem is a product family scheduling problem on multiple, identical parallel assembly lines with sequence-dependant setup costs and the goal of minimizing total setup costs. This dissertation solves the scheduling problem using three different approaches. The first approach was used to resolve the company’s immediate scheduling difficulties and assumes that setup costs are similar enough to be treated as sequence independent. As a result of the implementation of this approach, Dell accommodated an effective production volume increase of 35 percent and a doubling in product variety. Furthermore, Dell realized a conservative cost avoidance of over one million dollars annually, primarily from avoided overtime. The second approach explicitly considers the unusual sequence-dependant setup costs. We developed a three-step heuristic that involves assignment, sequencing, and time scheduling steps, each with an optimization component. For the most complex step we developed a greedy randomized adaptive search procedure (GRASP). We compared the setup costs resulting from using this approach against the costs using the first approach. Empirical results show the new approach achieved a reduction in factory-wide setups costs of 14 to 21 percent with single line setup cost reductions of 0 to 49 percent. The final approach tackles the difficult problem of combining the assignment and sequencing steps. The combined model theoretically dominates the second approach but it is both NP-hard and very large so cannot be solved to optimality. Instead, we develop a new GRASP for this combined model. We compare the setup costs using this final approach with the setup costs achieved by the second approach. Results show an average increase in setup costs of 46 percent, with a range of 27 to 60 percent increase.